Search NASA⌕ Search

SEARCH · Search NASA

Results for “Interior point methods”

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

Final Scientific/Technical Report

In this work, we have built upon our results from previous DOE funding (DEFG 0204ER25655), where we developed new and more efficient methods for solving certain optimization problems with many inequality constraints. This past work resulted in efficient algorithms (and analysis of their convergence) for linear programming, convex quadratic programming, and the training of support vector machines. The algorithms are based on using constraint reduction in interior point methods: at each iteration we consider only a smaller subset of the inequality constraints, focusing on the constraints that are close enough to be relevant. Surprisingly, we have been able to show theoretically that such algorithms are globally convergent and to demonstrate experimentally that they are much more efficient than standard interior point methods.

97 MATHEMATICS AND COMPUTING↗

Exploiting Power Flow Manifold to Solve AC Optimal Power Flow

AC optimal power flow has proven difficult to solve with interior point methods on GPUs. This is largely due to challenging linear algebra problems that current state of the art massively parallel linear solvers struggle with. However, the advent of Riemannian optimization techniques and the fact that the power flow equations form a smooth manifold present an alternative approach. In this talk, we present the basics of Riemannian optimization techniques in which optimization is done directly on a manifold. Then we present computational results showing that Riemannian techniques are capable of producing solutions of comparable quality as interior point methods.

AC optimal power flow↗

A preconditioning technique for Schur complement systems arising in stochastic optimization

Deterministic sample average approximations of stochastic programming problems with recourse are suitable for a scenario-based parallelization. In this paper the parallelization is obtained by using an interior-point method and a Schur complement mechanism for the interior-point linear systems. However, the direct linear solves involving the dense Schur complement matrix are expensive, and adversely affect the scalability of this approach. We address this issue by proposing a stochastic preconditioner for the Schur complement matrix and by using Krylov iterative methods for the solution of the dense linear systems. The stochastic preconditioner is built based on a subset of existing scenarios and can be assembled and factorized on a separate process before the computation of the Schur complement matrix finishes on the remaining processes. The expensive factorization of the Schur complement is removed from the parallel execution flow and the scaling of the optimization solver is considerably improved with this approach. The spectral analysis indicates an exponentially fast convergence in probability to 1 of the eigenvalues of the preconditioned matrix with the number of scenarios incorporated in the preconditioner. Numerical experiments performed on the relaxation of a unit commitment problem show good performance, in terms of both the accuracy of the solution and the execution time.

99 GENERAL AND MISCELLANEOUS↗

TAS: 89 0227: TAS Recovery Act - Optimization and Control of Electric Power Systems: ARRA

The name SuperOPF is used to refer several projects, problem formulations and soft-ware tools intended to extend, improve and re-define some of the standard methods of optimizing electric power systems. Our work included applying primal-dual interior point methods to standard AC optimal power flow problems of large size, as well as extensions of this problem to include co-optimization of multiple scenarios. The original SuperOPF problem formulation was based on co-optimizing a base scenario along with multiple post-contingency scenarios, where all AC power flow models and constraints are enforced for each, to find optimal energy contracts, endogenously determined locational reserves and appropriate nodal energy prices for a single period optimal power flow problem with uncertainty. This led to example non-linear programming problems on the order of 1 million constraints and half a million variables. The second generation SuperOPF formulation extends this by adding multiple periods and multiple base scenarios per period. It also incorporates additional variables and constraints to model load following reserves, ramping costs, and storage resources. A third generation of the multi-period SuperOPF, adds both integer variables and a receding horizon framework in which the problem type is more challenging (mixed integer), the size is even larger, and it must be solved more frequently, pushing the limits of currently available algorithms and solvers. The consideration of transient stability constraints in optimal power flow (OPF) problems has become increasingly important in modern power systems. Transient stability constrained OPF (TSCOPF) is a nonlinear optimization problem subject to a set of algebraic and differential equations. Solving a TSCOPF problem can be challenging due to (i) the differential-equation constraints in an optimization problem, (ii) the lack of a true analytical expression for transient stability in OPF. To handle the dynamics in TSCOPF, the set of differential equations can be approximated or converted into equivalent algebraic equations before they are included in an OPF formulation. In Chapter 4, a rigorous evaluation of using a predefined and fixed threshold for rotor angles as a mean to determine transient stability of the system is developed. TSCOPF can be modeled as a large-scale nonlinear programming problem including the constraints of differential-algebraic equations (DAE). Solving a TSCOPF problem can be challenging due to (i) the differential-equation constraints in an optimization problem, (ii) the lack of a true analytical expression for transient stability constraint in OPF. Unfortunately, even the current best TSCOPF solvers still suffer from the curse of dimensionality and unacceptable computational time, especially for large-scale power systems with multiple contingencies. In chapter 5, thse issues will be addressed and a new method to incorporate the transient stability constraints will be presented.

24 POWER TRANSMISSION AND DISTRIBUTION↗

Parallel interior-point solver for block-structured nonlinear programs on SIMD/GPU architectures

Here, we investigate how to port the standard interior-point method to new exascale architectures for block-structured nonlinear programs with state equations. Computationally, we decompose the interior-point algorithm into two successive operations: the evaluation of the derivatives and the solution of the associated Karush-Kuhn-Tucker (KKT) linear system. Our method accelerates both operations using two levels of parallelism. First, we distribute the computations on multiple processes using coarse parallelism. Second, each process uses SIMD/GPU accelerators locally to accelerate the operations using fine-grained parallelism. The KKT system is reduced by eliminating the inequalities and the state variables from the corresponding equations. We demonstrate our method's capability on the supercomputer Polaris, a testbed for the future exascale Aurora system. Each node is equipped with four GPUs, a setup amenable to our two-level approach. Our experiments on the stochastic optimal power flow problem show that the reduction method is 50x faster than the sparse linear solver HSL MA57 running in serial on the CPU, and 6x faster than Pardiso running in parallel on CPU on the same number of processes.

97 MATHEMATICS AND COMPUTING↗

Loss Minimization With Optimal Power Dispatch in Multi-Frequency HVac Power Systems

Low-frequency high-voltage ac transmission scheme has recently been proposed as an alternative approach for bulk power transmission. This paper proposes a multi-period optimal power flow (OPF) for a multi-frequency HVac transmission system that interconnects both conventional 50/60-Hz and low-frequency grids using back-to-back converters with a centralized control scheme. The OPF objective is to minimize system losses by determining the optimal dispatch for generators, shunt capacitors, and converters. The OPF constraints include the operational constraints of all HVac grid and converter stations. The resulting mixed-integer nonlinear programing problem is solved using a proposed framework based on the predictor-corrector primal-dual interior-point method. The proposed OPF formulation and solution approach are verified using a multi-frequency HVac transmission system that is modified from the IEEE 57-bus system. Here, the results with the optimal dispatch from the proposed method during a simulated day show a significant loss reduction and an improved voltage regulation compared to those when an arbitrary dispatch is chosen.

32 ENERGY CONSERVATION, CONSUMPTION, AND UTILIZATI↗

A homogeneous model for monotone mixed horizontal linear complementarity problems

In this paper, we propose a homogeneous model for the class of mixed horizontal linear complementarity problems. The proposed homogeneous model is always solvable and provides the solution of the original problem if it exists, or a certificate of infeasibility otherwise. Our formulation preserves the sparsity of the original formulation and does not reduce to the homogeneous model of the equivalent standard linear complementarity problem. We study the properties of the model and show that interior-point methods can be used efficiently for the numerical solutions of the homogeneous problem. Finally, numerical experiments show convincingly that it is more efficient to use the proposed homogeneous model for the mixed horizontal linear complementarity problem than to use known homogeneous models for the equivalent standard linear complementarity problem.

97 MATHEMATICS AND COMPUTING↗

A Scalable Interior‐Point Gauss–Newton Method for PDE‐Constrained Optimization With Bound Constraints

Here, we present a scalable approach to solve a class of partial differential equation (PDE)‐constrained optimization problems with bound constraints. This approach utilizes a robust full‐space interior‐point (IP)‐Gauss–Newton optimization method. To cope with the poorly‐conditioned IP‐Gauss–Newton saddle‐point linear systems that need to be solved approximately, once per optimization step, we propose two spectrally related preconditioners. These preconditioners leverage the limited informativeness of data in regularized PDE‐constrained optimization problems. A block Gauss–Seidel preconditioner is proposed for the GMRES‐based solution of the IP‐Gauss–Newton linear systems. It is shown, for a large‐class of PDE‐ and bound‐constrained optimization problems, that the spectrum of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix is asymptotically independent of discretization and is not impacted by the ill‐conditioning that notoriously plagues interior‐point methods. We exploit symmetry of the IP‐Gauss–Newton linear systems and propose a regularization and log‐barrier Hessian preconditioner for the preconditioned conjugate gradient (PCG)‐based solution of the equivalent IP‐Gauss–Newton–Schur complement linear systems. The eigenvalues of the block Gauss–Seidel preconditioned IP‐Gauss–Newton matrix, that are not equal to one, are identical to the eigenvalues of the regularization and log‐barrier Hessian preconditioned Schur complement matrix. The scalability of the approach is demonstrated on two example problems. The numerical solution of these optimization problems is shown to require a discretization independent number of IP‐Gauss–Newton linear solves. Furthermore, the linear systems are solved in a discretization and IP ill‐conditioning independent number of preconditioned Krylov subspace iterations. The parallel scalability of the preconditioner, achieved via algebraic multigrid component solvers when applicable, and the aforementioned algorithmic scalability permits a parallel scalable means to compute solutions of a large class of PDE‐ and bound‐constrained problems.

PDE-constrained optimization↗

Implementing a unified solver for nonlinearly constrained optimization

SQP and interior-point methods (also referred to as Lagrange-Newton methods) typically share key algorithmic components, such as strategies for computing descent directions and mechanisms that promote global convergence. Building on this insight, we introduce a unifying framework with eight building blocks that abstracts the workflows of Lagrange-Newton methods. We then present Uno, a modular C++ solver that implements our unifying framework and allows the automatic combination of a wide range of strategies with no programming effort from the user. Uno is meant to (1) organize mathematical optimization strategies into a coherent hierarchy; (2) offer a wide range of efficient and robust methods that can be compared for a given instance; (3) enable researchers to experiment with novel optimization strategies; and (4) reduce the cost of development and maintenance of multiple optimization solvers. Uno’s software design allows user to compose new customized solvers for emerging optimization areas such as robust optimization or optimization problems with complementarity constraints, while building on reliable nonlinear optimization techniques. We demonstrate that Uno is highly competitive against state-of-the-art solvers filterSQP, IPOPT, SNOPT, MINOS, LANCELOT, LOQO, and CONOPT on a subset of 429 small problems from the CUTE collection. Uno is available as open-source software under the MIT license at https://github.com/cvanaret/Uno and via its C, Julia, Python, Fortran, and AMPL interfaces.

97 MATHEMATICS AND COMPUTING↗

Symmetric Random Butterfly Transform (SRBT) Based Preconditioner

Summary of work using Symmetric Random Butterfly Transformation (SRBT) in conjunction with Incomplete LDL T factorization as a preconditioner for FGMRES solver as a way of solving linear systems arising from interior point methods applied to power system problems. These linear systems have proven difficult to parallelize and this represents a possible route forward.

interior point optimization↗

Toward a scalable robust security-constrained optimal power flow using a proximal projection bundle method

Robust security-constrained optimal power flow (rSCOPF) aims to find the worst-case contingencies of alternating current optimal power flow (ACOPF) in power systems. With the rise of GPU architectures on the upcoming supercomputer architectures, optimization algorithms that rely on sparse linear algebra and indefinite linear systems are becoming increasingly hard to solve efficiently (e.g. interior-point method). To address this we revisit a maximin optimization formulation of the rSCOPF and the single-level mixed-integer semidefinite programming (MISDP) reformulation, which is obtained by taking the Lagrangian relaxation of the inner minimization ACOPF problem. In this paper, we focus on the development of a proximal projection bundle method (PPBM) for solving continuous relaxation node subproblems of the MISDP problem, based primarily on the well-known alternating direction method of multipliers. Cutting planes reminiscent of bundle method ideas are also applied in coordination with updates of the proximal parameter. The cutting-plane method can generate a large number of linear inequalities, leading to a large scale but decomposable quadratic programming (QP) subproblem that is amenable to GPUs. We present the numerical results on the IEEE 30, 57, 118, and 300-bus systems by using our PBMM method. We discuss the main computational bottleneck of our method, which is the time taken to solve each iteration of a QP subproblem instance of the PPBM, and how GPU architectures can accelerate this solution process.

bundle method↗

Final Technical Report: Sparse Grid Scenario Generation and Interior Algorithms for Stochastic Optimization in a Parallel Computing Environment

The support from this grant resulted in seven published papers and a technical report. Two papers are published in SIAM J. on Optimization [87, 88]; two papers are published in IEEE Transactions on Power Systems [77, 78]; one paper is published in Smart Grid [79]; one paper is published in Computational Optimization and Applications [44] and one in INFORMS J. on Computing [67]). The works in [44, 67, 87, 88] were funded primarily by this DOE grant. The applied papers in [77, 78, 79] were also supported through a subcontract from the Argonne National Lab. We start by presenting our main research results on the scenario generation problem in Sections 1–2. We present our algorithmic results on interior point methods for convex optimization problems in Section 3. We describe a new ‘central’ cutting surface algorithm developed for solving large scale convex programming problems (as is the case with our proposed research) with semi-infinite number of constraints in Section 4. In Sections 5–6 we present our work on two application problems of interest to DOE.

97 MATHEMATICS AND COMPUTING↗

pnnl/Pathway_Controlled_Optimization

A method for prediction of cell regulation to maximize cell growth rate while maintaining the solvent capacity of the cell. Prediction is formulated as an optimization problem using a thermodynamic framework that can leverage experimental data. We develop a formulation and variable initialization procedure that allows for computing solutions of the optimization with an interior point method

Central, PNNL Developer↗

An approach to learn regulation to maximize growth and entropy production rates in metabolism

Elucidating cell regulation remains a challenging task due to the complexity of metabolism and the difficulty of experimental measurements. Here we present a method for prediction of cell regulation to maximize cell growth rate while maintaining the solvent capacity of the cell. Prediction is formulated as an optimization problem using a thermodynamic framework that can leverage experimental data. We develop a formulation and variable initialization procedure that allows for computing solutions of the optimization with an interior point method. The approach is applied to photoheterotrophic growth of Rhodospirilium rubrum using ethanol as a carbon source, which has applications to biosynthesis of ethylene production. Growth is captured as the rate of synthesis of amino acids into proteins, and synthesis of nucleotide triphoshaptes into RNA and DNA. The method predicts regulation that produces a high rate of protein and RNA synthesis while DNA synthesis is reduced close to zero in agreement with production of DNA being turned off for much of the cell cycle.

59 BASIC BIOLOGICAL SCIENCES↗

Deep Sigma Point Processes-Assisted Chance-Constrained Power System Transient Stability Preventive Control

Here this paper proposes a deep sigma point processes (DSPP)-assisted chance-constrained power system transient stability preventive control method to deal with uncertain renewable energy and loads-induced stability risk. The traditional transient stability-constrained preventive control is reformulated as a chance-constrained optimization problem. To deal with the computational bottleneck of the time-domain simulation-based probabilistic transient stability assessment, the DSPP is developed. DSPP is a parametric Bayesian approach that allows us to predict system transient stability with high computational efficiency while accurately quantifying the confidence intervals of the predictions that can be used to inform system instability risk. To this end, with a given preset confidence probability, we embed DSPP into the primal dual interior point method to help solve the chance-constrained preventive control problem, where the corresponding Jacobian and Hessian matrices are derived. Comparison results with other existing methods show that the proposed method can significantly speed up preventive control while maintaining high accuracy and convergence

97 MATHEMATICS AND COMPUTING↗

TH-C-BRD-10: An Evaluation of Three Robust Optimization Approaches in IMPT Treatment Planning

Purpose: Various robust optimization approaches have been proposed to ensure the robustness of intensity modulated proton therapy (IMPT) in the face of uncertainty. In this study, we aim to investigate the performance of three classes of robust optimization approaches regarding plan optimality and robustness. Methods: Three robust optimization models were implemented in our in-house IMPT treatment planning system: 1) L2 optimization based on worst-case dose; 2) L2 optimization based on minmax objective; and 3) L1 optimization with constraints on all uncertain doses. The first model was solved by a L-BFGS algorithm; the second was solved by a gradient projection algorithm; and the third was solved by an interior point method. One nominal scenario and eight maximum uncertainty scenarios (proton range over and under 3.5%, and setup error of 5 mm for x, y, z directions) were considered in optimization. Dosimetric measurements of optimized plans from the three approaches were compared for four prostate cancer patients retrospectively selected at our institution. Results: For the nominal scenario, all three optimization approaches yielded the same coverage to the clinical treatment volume (CTV) and the L2 worst-case approach demonstrated better rectum and bladder sparing than others. For the uncertainty scenarios, the L1 approach resulted in the most robust CTV coverage against uncertainties, while the plans from L2 worst-case were less robust than others. In addition, we observed that the number of scanning spots with positive MUs from the L2 approaches was approximately twice as many as that from the L1 approach. This indicates that L1 optimization may lead to more efficient IMPT delivery. Conclusion: Our study indicated that the L1 approach best conserved the target coverage in the face of uncertainty but its resulting OAR sparing was slightly inferior to other two approaches.

60 APPLIED LIFE SCIENCES↗

A Full-Newton Step Infeasible Interior-Point Algorithm for Linear Programming Based on a Kernel Function

This paper proposes an infeasible interior-point algorithm with full-Newton step for linear programming, which is an extension of the work of Roos (SIAM J. Optim. 16(4):1110-1136, 2006). The main iteration of the algorithm consists of a feasibility step and several centrality steps. We introduce a kernel function in the algorithm to induce the feasibility step. For parameter p element of [0,1], the polynomial complexity can be proved and the result coincides with the best result for infeasible interior-point methods, that is, O(nlog n/{epsilon})

97 MATHEMATICS AND COMPUTING↗