Search NASA⌕ Search

SEARCH · Search NASA

Results for “optimization problems”

Search indexed NASA NTRS and DOE OSTI research on propulsion, heat transfer, battery materials and energy systems. Follow report and document links to the original sources.

Quote a phrase for an exact phrase match. Source license links do not imply unrestricted reuse.

At least 37 records · Page 2

An Empirical Quantile Estimation Approach for Chance-Constrained Nonlinear Optimization Problems

We investigate an empirical quantile estimation approach to solve chance-constrained nonlinear optimization problems. Our approach is based on the reformulation of the chance constraint as an equivalent quantile constraint to provide stronger signals on the gradient. In this approach, the value of the quantile function is estimated empirically from samples drawn from the random parameters, and the gradient of the quantile function is estimated via a finite-difference approximation on top of the quantile-function-value estimation. We establish a convergence theory of this approach within the framework of an augmented Lagrangian method for solving general nonlinear constrained optimization problems. The foundation of the convergence analysis is a concentration property of the empirical quantile process, and the analysis is divided based on whether or not the quantile function is differentiable. In contrast to the sampling-and-smoothing approach used in the literature, the method developed in this paper does not involve any smoothing function and hence the quantile-function gradient approximation is easier to implement and there are less accuracy-control parameters to tune. Furthermore, we demonstrate the effectiveness of this approach and compare it with a smoothing method for the quantile-gradient estimation. Numerical investigation shows that the two approaches are competitive for certain problem instances.

Applied Probability↗

High-order entropy-based closures for linear transport in slab geometry II: A computational study of the optimization problem

We present a numerical algorithm to implement entropy-based (M{sub N}) moment models in the context of a simple, linear kinetic equation for particles moving through a material slab. The closure for these models - as is the case for all entropy-based models - is derived through the solution of constrained, convex optimization problem. The algorithm has two components. The first component is a discretization of the moment equations which preserves the set of realizable moments, thereby ensuring that the optimization problem has a solution (in exact arithmetic). The discretization is a second-order kinetic scheme which uses MUSCL-type limiting in space and a strong-stability-preserving, Runge-Kutta time integrator. The second component of the algorithm is a Newton-based solver for the dual optimization problem, which uses an adaptive quadrature to evaluate integrals in the dual objective and its derivatives. The accuracy of the numerical solution to the dual problem plays a key role in the time step restriction for the kinetic scheme. We study in detail the difficulties in the dual problem that arise near the boundary of realizable moments, where quadrature formulas are less reliable and the Hessian of the dual objection function is highly ill-conditioned. Extensive numerical experiments are performed to illustrate these difficulties. In cases where the dual problem becomes 'too difficult' to solve numerically, we propose a regularization technique to artificially move moments away from the realizable boundary in a way that still preserves local particle concentrations. We present results of numerical simulations for two challenging test problems in order to quantify the characteristics of the optimization solver and to investigate when and how frequently the regularization is needed.

99 GENERAL AND MISCELLANEOUS↗

Algorithm 1028: VTMOP: Solver for Blackbox Multiobjective Optimization Problems

VTMOP is a Fortran 2008 software package containing two Fortran modules for solving computationally expensive bound-constrained blackbox multiobjective optimization problems. VTMOP implements the algorithm of [32], which handles two or more objectives, does not require any derivatives, and produces well-distributed points over the Pareto front. The first module contains a general framework for solving multiobjective optimization problems by combining response surface methodology, trust region methodology, and an adaptive weighting scheme. The second module features a driver subroutine that implements this framework when the objective functions can be wrapped as a Fortran subroutine. Lastly, support is provided for both serial and parallel execution paradigms, and VTMOP is demonstrated on several test problems as well as one real-world problem in the area of particle accelerator optimization.

97 MATHEMATICS AND COMPUTING↗

OpenGraphGym: A Parallel Reinforcement Learning Framework for Graph Optimization Problems

This paper presents an open-source, parallel AI environment (named OpenGraphGym) to facilitate the application of reinforcement learning (RL) algorithms to address combinatorial graph optimization problems. This environment incorporates a basic deep reinforcement learning method, and several graph embeddings to capture graph features, it also allows users to rapidly plug in and test new RL algorithms and graph embeddings for graph optimization problems. This new open-source RL framework is targeted at achieving both high performance and high quality of the computed graph solutions. This RL framework forms the foundation of several ongoing research directions, including 1) benchmark works on different RL algorithms and embedding methods for classic graph problems; 2) advanced parallel strategies for extreme-scale graph computations, as well as 3) performance evaluation on real-world graph solutions.

Zheng, Weijian↗

Multigrid preconditioning of linear systems for semi-smooth Newton methods applied to optimization problems constrained by smoothing operators

This article is concerned here with the question of constructing efficient multigrid preconditioners for the linear systems arising when applying semi-smooth Newton methods to large-scale linear-quadratic optimization problems constrained by smoothing operators with box-constraints on the controls. It is shown that, for certain discretizations of the optimization problem, the linear systems to be solved at each semi-smooth Newton iteration reduce to inverting principal minors of the Hessian of the associated unconstrained problem. As in the case when box-constraints on the controls are absent, the multigrid preconditioner introduced here is shown to increase in quality as the mesh-size decreases, resulting in a number of iterations that decreases with mesh-size. However, unlike the unconstrained case, the spectral distance between the preconditioners and the Hessian is shown to be of suboptimal order in general.

97 MATHEMATICS AND COMPUTING↗

A new modified BFGS method for unconstrained optimization problems

Using chain rule, we propose a modified secant equation to get a more accurate approximation of the second curvature of the objective function. Then, based on this modified secant equation we present a new BFGS method for solving unconstrained optimization problems. The proposed method makes use of both gradient and function values, and utilizes information from two most recent steps, while the usual secant relation uses only the latest step information. Under appropriate conditions, we show that the proposed method is globally convergent without convexity assumption on the objective function. Comparative numerical results show computational efficiency of the proposed method in the sense of the Dolan–Moré performance profiles.

97 MATHEMATICS AND COMPUTING↗

Globally Optimizing QAOA Circuit Depth for Constrained Optimization Problems

We develop a global variable substitution method that reduces n-variable monomials in combinatorial optimization problems to equivalent instances with monomials in fewer variables. We apply this technique to 3-SAT and analyze the optimal quantum unitary circuit depth needed to solve the reduced problem using the quantum approximate optimization algorithm. For benchmark 3-SAT problems, we find that the upper bound of the unitary circuit depth is smaller when the problem is formulated as a product and uses the substitution method to decompose gates than when the problem is written in the linear formulation, which requires no decomposition.

3-SAT↗

To the optimization problem in minority game model

The article presents the research results of the optimization problem in minority game model to a gaussian approximation using replica symmetry breaking by one step (1RSB). A comparison to replica symmetry approximation (RS) and the results from literary sources received using other methods has been held.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

spopt: a python package for solving spatial optimization problems in PySAL

Spatial optimization is a major spatial analytical tool in management and planning, the significance of which cannot be overstated. Spatial optimization models play an important role in designing and managing effective and efficient service systems such as transportation, education, public health, environmental protection, and commercial investment among others. To this end, spopt (spatial optimization) is under active development for the inclusion of newly proposed models and methods for regionalization, facility location, and transportation-oriented solutions (Feng et al., 2021). Spopt is a submodule in the open-source spatial analysis library PySAL (Python Spatial Analysis Library) founded by Dr. Sergio J. Rey and Dr. Luc Anselin in 2005 (Rey et al., 2015, 2021; Rey & Anselin, 2007). The goal of developing spopt is to provide management and decision-making support to all relevant practitioners and to further promote the appropriate and meaningful application of spatial optimization models in practice.

97 MATHEMATICS AND COMPUTING↗

Decentralized Schemes with Overlap for Solving Graph-Structured Optimization Problems

We present a new algorithmic paradigm for the decentralized solution of graph-structured optimization problems that arise in the estimation and control of network systems. A key and novel design concept of the proposed approach is that it uses overlapping subdomains to promote and accelerate convergence. We show that the algorithm converges if the size of the overlap is sufficiently large and that the convergence rate improves exponentially with the size of the overlap. The proposed approach provides a bridge between fully decentralized and centralized architectures and is flexible in that it enables the implementation of asynchronous schemes, handling of constraints, and balancing of computing, communication, and data privacy needs. The proposed scheme is tested in an estimation problem for a 9241-node power network and we show that it outperforms the alternating direction method of multipliers.

asynchronous↗

A comparison of eight optimization methods applied to a wind farm layout optimization problem

Abstract. Selecting a wind farm layout optimization method is difficult. Comparisons between optimization methods in different papers can be uncertain due to the difficulty of exactly reproducing the objective function. Comparisons by just a few authors in one paper can be uncertain if the authors do not have experience using each algorithm. In this work we provide an algorithm comparison for a wind farm layout optimization case study between eight optimization methods applied, or directed, by researchers who developed those algorithms or who had other experience using them. We provided the objective function to each researcher to avoid ambiguity about relative performance due to a difference in objective function. While these comparisons are not perfect, we try to treat each algorithm more fairly by having researchers with experience using each algorithm apply each algorithm and by having a common objective function provided for analysis. The case study is from the International Energy Association (IEA) Wind Task 37, based on the Borssele III and IV wind farms with 81 turbines. Of particular interest in this case study is the presence of disconnected boundary regions and concave boundary features. The optimization methods studied represent a wide range of approaches, including gradient-free, gradient-based, and hybrid methods; discrete and continuous problem formulations; single-run and multi-start approaches; and mathematical and heuristic algorithms. We provide descriptions and references (where applicable) for each optimization method, as well as lists of pros and cons, to help readers determine an appropriate method for their use case. All the optimization methods perform similarly, with optimized wake loss values between 15.48 % and 15.70 % as compared to 17.28 % for the unoptimized provided layout. Each of the layouts found were different, but all layouts exhibited similar characteristics. Strong similarities across all the layouts include tightly packing wind turbines along the outer borders, loosely spacing turbines in the internal regions, and allocating similar numbers of turbines to each discrete boundary region. The best layout by annual energy production (AEP) was found using a new sequential allocation method, discrete exploration-based optimization (DEBO). Based on the results in this study, it appears that using an optimization algorithm can significantly improve wind farm performance, but there are many optimization methods that can perform well on the wind farm layout optimization problem, given that they are applied correctly.

17 WIND ENERGY↗

Embedding Equality Constraints of Optimization Problems into a Quantum Annealer

Quantum annealers such as D-Wave machines are designed to propose solutions for quadratic unconstrained binary optimization (QUBO) problems by mapping them onto the quantum processing unit, which tries to find a solution by measuring the parameters of a minimum-energy state of the quantum system. While many NP-hard problems can be easily formulated as binary quadratic optimization problems, such formulations almost always contain one or more constraints, which are not allowed in a QUBO. Embedding such constraints as quadratic penalties is the standard approach for addressing this issue, but it has drawbacks such as the introduction of large coefficients and using too many additional qubits. In this paper, we propose an alternative approach for implementing constraints based on a combinatorial design and solving mixed-integer linear programming (MILP) problems in order to find better embeddings of constraints of the type Σ x i = k for binary variables x i . Our approach is scalable to any number of variables and uses a linear number of ancillary variables for a fixed k.

97 MATHEMATICS AND COMPUTING↗

Linear solvers for power grid optimization problems: A review of GPU-accelerated linear solvers

The linear equations that arise in interior methods for constrained optimization are sparse symmetric indefinite, and they become extremely ill-conditioned as the interior method converges. These linear systems present a challenge for existing solver frameworks based on sparse LU or LDL T decompositions. Here, we benchmark five well known direct linear solver packages on CPU- and GPU-based hardware, using matrices extracted from power grid optimization problems. The achieved solution accuracy varies greatly among the packages. None of the tested packages delivers significant GPU acceleration for our test cases. For completeness of the comparison we include results for MA57, which is one of the most efficient and reliable CPU solvers for this class of problem.

97 MATHEMATICS AND COMPUTING↗

Efficient Solution Methods for Large-scale Optimization Problems Constrained by Time-dependent Partial Differential Equations (Final Report)

The objectives of this project are to devise and analyze efficient solvers for several classes of PDE- constrained optimization problems. The project was initially focused on, but not restricted to time- dependent PDE-constraints such as parabolic equations, time-dependent fluid flows (Navier-Stokes equations), hyperbolic equations (Burgers equation, shallow water equations). Other constraints considered are PDEs with stochastic coefficients. Additional elements of interest are the handling of problems with control and/or state inequality constraints or non-differentiable regularization terms, and boundary controls. A direction of work not initially listed among the goals, which was triggered by conversations with DOE scientists from the Sandia National Labs, is to develop efficient solvers for optimization- based domain-decomposition PDE-solvers. Also targeted in the project are a number of technical issues necessary for facilitating the integration of the methods resulted from this project with existing high-performance packages developed at DOE national labs; this integration is expected to further enable the scientific community to use the novel methods. An example of such a task is the need to develop algebraic multigrid (AMG) versions of the algorithms. A list of accomplishments in several areas is detailed as well as a list of publications.

97 MATHEMATICS AND COMPUTING↗

Solving iTOUGH2 simulation and optimization problems using the PEST protocol

The PEST protocol has been implemented into the iTOUGH2 code, allowing the user to link any simulation program (with ASCII-based inputs and outputs) to iTOUGH2's sensitivity analysis, inverse modeling, and uncertainty quantification capabilities. These application models can be pre- or post-processors of the TOUGH2 non-isothermal multiphase flow and transport simulator, or programs that are unrelated to the TOUGH suite of codes. PEST-style template and instruction files are used, respectively, to pass input parameters updated by the iTOUGH2 optimization routines to the model, and to retrieve the model-calculated values that correspond to observable variables. We summarize the iTOUGH2 capabilities and demonstrate the flexibility added by the PEST protocol for the solution of a variety of simulation-optimization problems. In particular, the combination of loosely coupled and tightly integrated simulation and optimization routines provides both the flexibility and control needed to solve challenging inversion problems for the analysis of multiphase subsurface flow and transport systems.

54 ENVIRONMENTAL SCIENCES↗

Solving complex maintenance planning optimization problems using stochastic simulation and multi-criteria fuzzy decision making

One of the most important factors in the operations of many cooperations today is to maximize profit and one important tool to that effect is the optimization of maintenance activities. Maintenance activities is at the largest level divided into two major areas, corrective maintenance (CM) and preventive maintenance (PM). When optimizing maintenance activities, by a maintenance plan or policy, we seek to find the best activities to perform at each point in time, be it PM or CM. We explore the use of stochastic simulation, genetic algorithms and other tools for solving complex maintenance planning optimization problems in terms of a suggested framework model based on discrete event simulation.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Hybrid Approach for Solving Optimization Problems on Small Quantum Computers

Solving larger-sized problems is an important area of research in quantum computing. Designing hybrid quantum-classical algorithms is a promising approach to solving this. We discuss decomposition-based hybrid approaches for solving optimization problems and demonstrate them for applications related to community detection.

97 MATHEMATICS AND COMPUTING↗