Search NASA⌕ Search

SEARCH · Search NASA

Results for “Convex Optimization”

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 433 records · Page 24

Solution of monotone complementarity and general convex programming problems using a modified potential reduction interior point method

We present a homogeneous algorithm equipped with a modified potential function for the monotone complementarity problem. We show that this potential function is reduced by at least a constant amount if a scaled Lipschitz condition (SLC) is satisfied. A practical algorithm based on this potential function is implemented in a software package named iOptimize. The implementation in iOptimize maintains global linear and polynomial time convergence properties, while achieving practical performance. It either successfully solves the problem, or concludes that the SLC is not satisfied. When compared with the mature software package MOSEK (barrier solver version 6.0.0.106), iOptimize solves convex quadratic programming problems, convex quadratically constrained quadratic programming problems, and general convex programming problems in fewer iterations. Moreover, several problems for which MOSEK fails are solved to optimality. In addition, we also find that iOptimize detects infeasibility more reliably than the general nonlinear solvers Ipopt (version 3.9.2) and Knitro (version 8.0).

97 MATHEMATICS AND COMPUTING↗

Dynamically Learning Incentives for Load Control

As electrical generation becomes more distributed and volatile, and loads become more uncertain, controllability of distributed energy resources (DERs), regardless of their ownership status, will be necessary for grid reliability. Grid operators lack direct control over end-users' grid interactions, such as energy usage, but incentives can influence behavior -- for example, an end-user that receives a grid-driven incentive may adjust their consumption or expose relevant control variables in response. A key challenge in studying such incentives is the lack of data about human behavior, which usually motivates strong assumptions, such as distributional assumptions on compliance or rational utility-maximization. In this paper, we propose a general incentive mechanism in the form of a constrained optimization problem -- our approach is distinguished from prior work by modeling human behavior (e.g., reactions to an incentive) as an arbitrary unknown function. We propose feedback-based optimization algorithms to solve this problem that each leverage different amounts of information and/or measurements. We show that each converges to an asymptotically stable incentive with (near)-optimality guarantees given mild assumptions on the problem. Finally, we evaluate our proposed techniques in voltage regulation simulations on standard test beds. We test a variety of settings, including those that break assumptions required for theoretical convergence (e.g., convexity, smoothness) to capture realistic settings. In this evaluation, our proposed algorithms are able to find near-optimal incentives even when the reaction to an incentive is modeled by a theoretically difficult (yet realistic) function.

demand response↗

Optimal Wentzell Boundary Control of Parabolic Equations

This paper deals with a class of optimal control problems governed by an initial-boundary value problem of a parabolic equation. The case of semi-linear boundary control is studied where the control is applied to the system via the Wentzell boundary condition. The differentiability of the state variable with respect to the control is established and hence a necessary condition is derived for the optimal solution in the case of both unconstrained and constrained problems. The condition is also sufficient for the unconstrained convex problems. A second order condition is also derived.

97 MATHEMATICS AND COMPUTING↗

A Multi-Parametric optimization approach for bilevel mixed-integer linear and quadratic programming problems

Optimization problems involving two decision makers at two different decision levels are referred to as bi-level programming problems. Herein, we present novel algorithms for the exact and global solution of two classes of bi-level programming problems, namely (i) bi-level mixed-integer linear programming problems (B-MILP) and (ii) bi-level mixed-integer convex quadratic programming problems (B-MIQP) containing both integer and bounded continuous variables at both optimization levels. Based on multi-parametric programming theory, the main idea is to recast the lower level problem as a multi-parametric programming problem, in which the optimization variables of the upper level problem are considered as bounded parameters for the lower level. The resulting exact multi-parametric mixed-integer linear or quadratic solutions are then substituted into the upper level problem, which can be solved as a set of single-level, independent, deterministic mixed-integer optimization problems. Extensions to problems including right-hand-side uncertainty on both lower and upper levels are also discussed. Finally, computational implementation and studies are presented through test problems.

42 ENGINEERING↗

Robust Trajectory Optimization for NRHO Rendezvous Using SPICE Kernel Relative Motion

In this paper, robust optimization is performed on trajectory correction maneuvers during the lunar lander return phase of an Artemis mission, treating the trajectory from one hour after low lunar orbit departure to arrival in the vicinity of the lunar Gateway as a relative motion problem. To enable rapid stochastic optimization techniques requiring many candidate trajectories, SPICE kernel relative motion as implemented by the Quadratic Interpolated State Transition (QIST) system is used as the underlying dynamics propagation. The optimization is performed with a genetic optimizer using linear covariance (LinCov) software in a simplified operational context, taking into account the availability of navigation sensors with varying measurement models, ranges, and accuracies. No numerical integration is used, since the relative motion around Gateway is fully characterized with the a priori computation of the QIST coefficients. Maneuver placements are computed to optimize the minimum 3σ delta-v of the trajectory, the position dispersion at a target point, and a convex combination of these two metrics. An order of magnitude runtime improvement is provided over legacy methods with less than 10% error introduced. All QIST results are shown to be in-family with legacy methods. The tradespace for optimal delta-v design is found to range from 77.0 to 93.9 m/s, while the range of optimal dispersion is between 1.4 and 11.7 km.

Relative Motion↗

SU-E-T-06: 4D Particle Swarm Optimization to Enable Lung SBRT in Patients with Central And/or Large Tumors

Purpose: Patients presenting with large and/or centrally-located lung tumors are currently considered ineligible for highly potent regimens such as SBRT due to concerns of toxicity to normal tissues and organs-at-risk (OARs). We present a particle swarm optimization (PSO)-based 4D planning technique, designed for MLC tracking delivery, that exploits the temporal dimension as an additional degree of freedom to significantly improve OAR-sparing and reduce toxicity to levels clinically considered as acceptable for SBRT administration. Methods: Two early-stage SBRT-ineligible NSCLC patients were considered, presenting with tumors of maximum dimensions of 7.4cm (central-right lobe; 1.5cm motion) and 11.9cm (upper-right lobe; 1cm motion). In each case, the target and normal structures were manually contoured on each of the ten 4DCT phases. Corresponding ten initial 3D-conformal plans (Pt#1: 7-beams; Pt#2: 9-beams) were generated using the Eclipse planning system. Using 4D-PSO, fluence weights were optimized over all beams and all phases (70 and 90 apertures for Pt1&2, respectively). Doses to normal tissues and OARs were compared with clinicallyestablished lung SBRT guidelines based on RTOG-0236. Results: The PSO-based 4D SBRT plan yielded tumor coverage and dose—sparing for parallel and serial OARs within the SBRT guidelines for both patients. The dose-sparing compared to the clinically-delivered conventionallyfractionated plan for Patient 1 (Patient 2) was: heart Dmean = 11% (33%); lung V20 = 16% (21%); lung Dmean = 7% (20%); spinal cord Dmax = 5% (16%); spinal cord Dmean = 7% (33%); esophagus Dmax = 0% (18%). Conclusion: Truly 4D planning can significantly reduce dose to normal tissues and OARs. Such sparing opens up the possibility of using highly potent and effective regimens such as lung SBRT for patients who were conventionally considered SBRT non-eligible. Given the large, non-convex solution space, PSO represents an attractive, parallelizable tool to successfully achieve a globally optimal solution for this problem. This work was supported through funding from the National Institutes of Health and Varian Medical Systems.

60 APPLIED LIFE SCIENCES↗

Beyond Relaxation and Newton–Raphson: Solving AC OPF for Multi-Phase Systems With Renewables

This paper focuses on the AC Optimal Power Flow (OPF) problem for multi-phase systems. Particular emphasis is given to systems with high integration of renewables, where adjustments of the real and reactive output powers from renewable sources of energy are necessary in order to enforce voltage regulation. The AC OPF problem is known to be nonconvex (and, in fact, NP-hard). Convex relaxation techniques have been recently explored to solve the OPF task with reduced computational burden; however, sufficient conditions for tightness of these relaxations are only available for restricted classes of system topologies and problem setups. Identifying feasible power-flow solutions remains hard in more general problem formulations, especially in unbalanced multi-phase systems with renewables. To identify feasible and optimal AC OPF solutions in challenging scenarios where existing methods may fail, this paper leverages the Feasible Point Pursuit - Successive Convex Approximation algorithm - a powerful approach for general nonconvex quadratically constrained quadratic programs. The merits of the approach are illustrated using single- and multiphase distribution networks with renewables, as well as several transmission systems.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Optimizing Vehicle Fleet and Assignment for Concentrating Solar Power Plant Heliostat Washing

Concentrating solar power central-receiver plants use thousands of sun-tracking mirrors, i.e., heliostats, to reflect sunlight to a central receiver, which collects and uses the heat to generate electricity. Over time, soiling reduces the reflectivity of the heliostats and, therefore, the efficiency of the system. Current industry practice sends vehicles to wash heliostats in an ad hoc fashion. We present a mixed-integer nonlinear program that determines wash vehicle fleet size, mix, and assignment of wash crews to heliostats to minimize the sum of (i) the revenues lost due to heliostat soiling, (ii) the costs of hiring wash crews and operating the vehicles, and (iii) the costs of purchasing wash vehicles. We establish conditions for convexity of the objective function, and then propose a decomposition method that enables near-optimal solutions to the wash vehicle fleet sizing and assignment problem on the order of a couple of minutes. Furthermore, these solutions yield hundreds of thousands of dollars in savings per year over current industry practices.

14 SOLAR ENERGY↗

Iterative subspace algorithms for finite-temperature solution of Dyson equation

One-particle Green’s functions obtained from the self-consistent solution of the Dyson equation can be employed in the evaluation of spectroscopic and thermodynamic properties for both molecules and solids. However, typical acceleration techniques used in the traditional quantum chemistry self-consistent algorithms cannot be easily deployed for the Green’s function methods because of a non-convex grand potential functional and a non-idempotent density matrix. Moreover, the optimization problem can become more challenging due to the inclusion of correlation effects, changing chemical potential, and fluctuations of the number of particles. In this paper, we study acceleration techniques to target the self-consistent solution of the Dyson equation directly. We use the direct inversion in the iterative subspace (DIIS), the least-squared commutator in the iterative subspace (LCIIS), and the Krylov space accelerated inexact Newton method (KAIN). We observe that the definition of the residual has a significant impact on the convergence of the iterative procedure. Based on the Dyson equation, we generalize the concept of the commutator residual used in DIIS and LCIIS and compare it with the difference residual used in DIIS and KAIN. The commutator residuals outperform the difference residuals for all considered molecular and solid systems within both GW and GF2. For a number of bond-breaking problems, we found that an easily obtained high-temperature solution with effectively suppressed correlations is a very effective starting point for reaching convergence of the problematic low-temperature solutions through a sequential reduction of temperature during calculations.

37 INORGANIC, ORGANIC, PHYSICAL, AND ANALYTICAL CH↗

Hodograph analysis in aircraft trajectory optimization

An account is given of key geometrical concepts involved in the use of a hodograph as an optimal control theory resource which furnishes a framework for geometrical interpretation of the minimum principle. Attention is given to the effects of different convexity properties on the hodograph, which bear on the existence of solutions and such types of controls as chattering controls, 'bang-bang' control, and/or singular control. Illustrative aircraft trajectory optimization problems are examined in view of this use of the hodograph.

Cliff, Eugene M.↗

A Convex Guidance Algorithm for Formation Reconfiguration

In this paper, a reconfiguration guidance algorithm for formation flying spacecraft is presented. The formation reconfiguration guidance problem is first formulated as a continuous-time minimum-fuel or minimum-energy optimal control problem with collision avoidance and control constraints. The optimal control problem is then discretized to obtain a finite dimensional parameter optimization problem. In this formulation, the collision avoidance constraints are imposed via separating planes between each pair of spacecraft. A heuristic is introduced to choose these separating planes that leads to the convexification of the collision avoidance constraints. Additionally, convex constraints are imposed to guarantee that no collisions occur between discrete time samples. The resulting finite dimensional optimization problem is a second order cone program, for which standard algorithms can compute the global optimum with deterministic convergence and a prescribed level of accuracy. Consequently, the formation reconfiguration algorithm can be implemented onboard a spacecraft for real-time operations.

formation reconfiguration↗

Optimisation of dynamic reactive power sources using mesh adaptive direct search

Dynamic reactive power sources can be used to effectively mitigate the fault-induced delayed voltage recovery and transient voltage instability issues. When many var sources need to be installed at planned locations, optimisation of their sizes is a complicated non-linear optimisation problem due to its non-convexity and the dependence of the constraint on time-series trajectories of post-fault voltages. Solving this optimal sizing problem needs to utilise both a non-linear optimisation solver and a power system differential-algebraic equation solver. This study proposes a new approach for solving this problem under both a single contingency and multiple contingencies by using the mesh adaptive direct search algorithm interfaced with a power system simulator. The proposed approach is validated by case studies on a North American Eastern Interconnection model to optimise the sizes of planned STATCOMs against critical contingencies.

Huang, Weihong↗

New displacement-based methods for optimal truss topology design

Two alternate methods for maximum stiffness truss topology design are presented. The ground structure approach is used, and the problem is formulated in terms of displacements and bar areas. This large, nonconvex optimization problem can be solved by a simultaneous analysis and design approach. Alternatively, an equivalent, unconstrained, and convex problem in the displacements only can be formulated, and this problem can be solved by a nonsmooth, steepest descent algorithm. In both methods, the explicit solving of the equilibrium equations and the assembly of the global stiffness matrix are circumvented. A large number of examples have been studied, showing the attractive features of topology design as well as exposing interesting features of optimal topologies.

Bendsoe, Martin P.↗

Interior Point Algorithms for Optimization Problems (Final Technical Report)

Over the period of this award we developed an algorithmic framework for constraint reduction in linear programming (LP) and convex quadratic programming (QP), proved convergence of our algorithms, and applied them to a variety of applications, including entropy-based moment closure in gas dynamics.

97 MATHEMATICS AND COMPUTING↗

On convexity of H-infinity Riccati solutions and its applications

The celebrated two-Riccati-equation solution to a standard H-infinity control problem can be used to characterize all possible stabilizing optimal or suboptimal H-infinity controllers if the optimal H-infinity norm or gamma, an upper bound of a suboptimal H-infinity norm, is given. In this note, some properties of these H-infinity Riccati solutions are revealed. Among them, the most prominent one is that the spectral radius of the product of these two Riccati solutions is a continuous, nonincreasing, convex function of gamma on the domain of interest. Based on these properties, a quadratically convergent algorithm is developed to compute the optimal H-infinity norm.

Li, X. P.↗

An algorithm for linearizing convex extremal problems

This paper suggests a method of approximating the solution of minimization problems for convex functions of several variables under convex constraints is suggested. The main idea of this approach is the approximation of a convex function by a piecewise linear function, which results in replacing the problem of convex programming by a linear programming problem. To carry out such an approximation, the epigraph of a convex function is approximated by the projection of a polytope of greater dimension. In the first part of the paper, the problem is considered for functions of one variable. In this case, an algorithm for approximating the epigraph of a convex function by a polygon is presented, it is shown that this algorithm is optimal with respect to the number of vertices of the polygon, and exact bounds for this number are obtained. After this, using an induction procedure, the algorithm is generalized to certain classes of functions of several variables. Applying the suggested method, polynomial algorithms for an approximate calculation of the L{sub p}-norm of a matrix and of the minimum of the entropy function on a polytope are obtained. Bibliography: 19 titles.

97 MATHEMATICS AND COMPUTING↗

Noise thresholds for higher-dimensional systems using the discrete Wigner function

For a quantum computer acting on d-dimensional systems, we analyze the computational power of circuits wherein stabilizer operations are perfect, and we allow access to imperfect nonstabilizer states or operations. If the noise rate affecting the nonstabilizer resource is sufficiently high, then these states and operations can become simulable in the sense of the Gottesman-Knill theorem, reducing the overall power of the circuit to no better than classical. In this paper we find the depolarizing noise rate at which this happens and consequently the most robust nonstabilizer states and non-Clifford gates. In doing so, we make use of the discrete Wigner function and derive facets of the so-called qudit Clifford polytope, i.e., the inequalities defining the convex hull of all qudit Clifford gates. Our results for robust states are provably optimal. For robust gates we find a critical noise rate that, as dimension increases, rapidly approaches the the theoretical optimum of 100%. Some connections with the question of qudit magic state distillation are discussed.

71 CLASSICAL AND QUANTUM MECHANICS, GENERAL PHYSIC↗

A Risk-Averse Approach for Distribution Grid Expansion Planning

Recent episodes of natural disasters have challenged the resilience of power grids. Adequate distribution grid planning that properly captures the risk aversion of the utility system planner is a key factor to increase the flexibility of distribution networks to circumvent these events. In this paper, we propose a methodology to determine the optimal portfolio of investments in lines and storage devices in order to minimize a convex combination between expected value and CVaR of operational costs, including energy not served, while taking into account the multistage nature of the energy storage management within this context. While the expected value of energy not served has been traditionally employed to tackle routine failures, we also minimize the CVaR of energy not served to address high-impact, low-probability (HILP) events. We illustrate the performance of the proposed methodology with a 54-Bus system test case.

24 POWER TRANSMISSION AND DISTRIBUTION↗