MPCC Strategies for Nonsmooth NLPs

This paper develops solution strategies for large-scale nonsmooth optimization problems. We transform nonsmooth programs into equivalent mathematical programs with complementarity constraints (MPCCs), and then employ NLP-based strategies for their so- lution. For this purpose, two NLP formulations based on complementarity relaxations are put forward, one of which applies a parameterized formulation and operates with a … Read more

Optimization with Least Constraint Violation

Study about theory and algorithms for constrained optimization usually assumes that the feasible region of the optimization problem is nonempty. However, there are many important practical optimization problems whose feasible regions are not known to be nonempty or not, and optimizers of the objective function with the least constraint violation prefer to be found. A … Read more

Complementarity-Based Nonlinear Programming Techniques for Optimal Mixing in Gas Networks

We consider nonlinear and nonsmooth mixing aspects in gas transport optimization problems. As mixed-integer reformulations of pooling-type mixing models already render small-size instances computationally intractable, we investigate the applicability of smooth nonlinear programming techniques for equivalent complementarity-based reformulations. Based on recent results for remodeling piecewise affine constraints using an inverse parametric quadratic programming approach, we … Read more

A Study of the Difference-of-Convex Approach for Solving Linear Programs with Complementarity Constraints

This paper studies the difference-of-convex (DC) penalty formulations and the associated difference-of-convex algorithm (DCA) for computing stationary solutions of linear programs with complementarity constraints (LPCCs). We focus on three such formulations and establish connections between their stationary solutions and those of the LPCC. Improvements of the DCA are proposed to remedy some drawbacks in a … Read more

An L1 Elastic Interior-Point Method for Mathematical Programs with Complementarity Constraints

We propose an interior-point algorithm based on an elastic formulation of the L1-penalty merit function for mathematical programs with complementarity constraints. The method generalizes that of Gould, Orban and Toint (2003) and naturally converges to a strongly stationary point or delivers a certificate of degeneracy without recourse to second-order intermediate solutions. Remarkably, the method allows … Read more

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary … Read more

Interior Methods for Mathematical Programs with Complementarity Constraints

This paper studies theoretical and practical properties of interior-penalty methods for mathematical programs with complementarity constraints. A framework for implementing these methods is presented, and the need for adaptive penalty update strategies is motivated with examples. The algorithm is shown to be globally convergent to strongly stationary points, under standard assumptions. These results are then … Read more


We prove that any accumulation point of an elastic mode approach, applied to the optimization of a mixed P variational inequality, that approximately solves the relaxed subproblems is a C-stationary point of the problem of optimizing a parametric mixed P variational inequality. If, in addition, the accumulation point satis es the MPCC-LICQ constraint quali cation and if … Read more


We investigate the possibility of solving mathematical programs with complementarity constraints (MPCCs) using algorithms and procedures of smooth nonlinear programming. Although MPCCs do not satisfy a constraint qualification, we establish sucient conditions for their Lagrange multiplier set to be nonempty. MPCCs that have nonempty Lagrange multiplier sets and that satisfy the quadratic growth condition can … Read more

An Interior Point Method for Mathematical Programs with Complementarity Constraints (MPCCs)

Interior point methods for nonlinear programs (NLPs) are adapted for solution of mathematical programs with complementarity constraints (MPCCs). The constraints of the MPCC are suitably relaxed so as to guarantee a strictly feasible interior for the inequality constraints. The standard primal-dual algorithm has been adapted with a modified step calculation. The algorithm is shown to … Read more