Solving Highly Detailed Gas Transport MINLPs: Block Separability and Penalty Alternating Direction Methods

Detailed modeling of gas transport problems leads to nonlinear and nonconvex mixed-integer optimization or feasibility models (MINLPs) because both the incorporation of discrete controls of the network as well as accurate physical and technical modeling is required in order to achieve practical solutions. Hence, ignoring certain parts of the physics model is not valid for … Read more

Penalty Alternating Direction Methods for Mixed-Integer Optimization: A New View on Feasibility Pumps

Feasibility pumps are highly effective primal heuristics for mixed-integer linear and nonlinear optimization. However, despite their success in practice there are only few works considering their theoretical properties. We show that feasibility pumps can be seen as alternating direction methods applied to special reformulations of the original problem, inheriting the convergence theory of these methods. … Read more

A Penalty-Interior-Point Algorithm for Nonlinear Constrained Optimization

Penalty and interior-point methods for nonlinear optimization problems have enjoyed great successes for decades. Penalty methods have proved to be effective for a variety of problem classes due to their regularization effects on the constraints. They have also been shown to allow for rapid infeasibility detection. Interior-point methods have become the workhorse in large-scale optimization … Read more

Convergence Analysis of an Interior-Point Method for Nonconvex Nonlinear Programming

In this paper, we present global and local convergence results for an interior-point method for nonlinear programming. The algorithm uses an $\ell_1$ penalty approach to relax all constraints, to provide regularization, and to bound the Lagrange multipliers. The penalty problems are solved using a simplified version of Chen and Goldfarb’s strictly feasible interior-point method [6]. … Read more

Interior-Point Methods for Nonconvex Nonlinear Programming: Regularization and Warmstarts

In this paper, we investigate the use of an exact primal-dual penalty approach within the framework of an interior-point method for nonconvex nonlinear programming. This approach provides regularization and relaxation, which can aid in solving ill-behaved problems and in warmstarting the algorithm. We present details of our implementation within the LOQO algorithm and provide extensive … Read more

An Exact Primal-Dual Penalty Method Approach to Warmstarting Interior-Point Methods for Linear Programming

One perceived deficiency of interior-point methods in comparison to active set methods is their inability to efficiently re-optimize by solving closely related problems after a warmstart. In this paper, we investigate the use of a primal-dual penalty approach to overcome this problem. We prove exactness and convergence and show encouraging numerical results on a set … Read more

Steering Exact Penalty Methods for Optimization

This paper reviews, extends and analyzes a new class of penalty methods for nonlinear optimization. These methods adjust the penalty parameter dynamically; by controlling the degree of linear feasibility achieved at every iteration, they promote balanced progress toward optimality and feasibility. In contrast with classical approaches, the choice of the penalty parameter ceases to be … Read more

On the Convergence of Successive Linear-Quadratic Programming Algorithms

The global convergence properties of a class of penalty methods for nonlinear programming are analyzed. These methods include successive linear programming approaches, and more specifically, the successive linear-quadratic programming approach presented by Byrd, Gould, Nocedal and Waltz (Math. Programming 100(1):27–48, 2004). Every iteration requires the solution of two trust-region subproblems involving piecewise linear and quadratic … Read more

Interior-Point Algorithms, Penalty Methods and Equilibrium Problems

In this paper we consider the question of solving equilibrium problems—formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC’s)—as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example … Read more

Convergence of a Penalty Method for Mathematical Programmingwith ComplementarityConstraints

We adapt the convergence analysis of smoothing (Fukushima and Pang) and regularization (Scholtes) methods to a penalty framework for mathematical programs with complementarity constraints (MPCCs), and show that the penalty framework shares similar convergence properties to these methods. Moreover, we give sufficient conditions for a sequence generated by the penalty framework to be attracted to … Read more