complementarity constraints

Mathematical Programs with Cardinality Constraints: Reformulation by Complementarity-type Constraints and a Regularization Method

  • Oleg Burdakov
  • Christian Kanzow
  • Alexandra Schwartz
    • Categories Complementarity and Variational Inequalities, Global Optimization, Nonlinear Optimization Tags , , , , , , ,

    Optimization problems with cardinality constraints are very dicult mathematical programs which are typically solved by global techniques from discrete optimization. Here we introduce a mixed-integer formulation whose standard relaxation still has the same solutions (in the sense of global minima) as the underlying cardinality-constrained problem; the relation between the local minima is also discussed in … Read more

    Complementarity Formulations of l0-norm Optimization Problems

  • Mingbin Feng
  • John E. Mitchell
  • Jong-Shi Pang
  • Xin Shen
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , ,

    In a number of application areas, it is desirable to obtain sparse solutions. Minimizing the number of nonzeroes of the solution (its l0-norm) is a difficult nonconvex optimization problem, and is often approximated by the convex problem of minimizing the l1-norm. In contrast, we consider exact formulations as mathematical programs with complementarity constraints and their … Read more

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

  • Zoumana Coulibaly
  • Dominique Orban
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , , ,

    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

    A Pivoting Algorithm for Linear Programming with Linear Complementarity Constraints

  • Haw-ren Fang
  • Sven Leyffer
  • Todd S. Munson
    • Categories Complementarity and Variational Inequalities Tags , ,

    We present a pivoting algorithm for solving linear programs with linear complementarity constraints. Our method generalizes the simplex method for linear programming to deal with complementarity conditions. We develop an anticycling scheme that can verify Bouligand stationarity. We also give an optimization-based technique to find an initial feasible vertex. Starting with a feasible vertex, our … Read more

    Interior-point method for nonlinear programming with complementarity constraints

  • Ladislav Lukšan
  • Ctirad Matonoha
  • Jan Vlček
    • Categories Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , , ,

    In this report, we propose an algorithm for solving nonlinear programming problems with com-plementarity constraints, which is based on the interior-point approach. Main theoretical results concern direction determination and step-length selection. We use an exact penalty function to remove complementarity constraints. Thus a new indefinite linear system is defined with a tridiagonal low-right submatrix. Inexact … Read more

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

  • Giovanni Giallombardo
  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Nonlinear Optimization Tags , , , , , , ,

    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

    A Note on Multiobjective Optimization and Complementarity Constraints

  • Sven Leyffer
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Multi-Criteria Optimization Tags , , ,

    We propose a new approach to convex nonlinear multiobjective optimization that captures the geometry of the Pareto set by generating a discrete set of Pareto points optimally. We show that the problem of finding an optimal representation of the Pareto surface can be formulated as a mathematical program with complementarity constraints. The complementarity constraints arise … Read more

    Elastic-Mode Algorithms for Mathematical Programs with Equilibrium Constraints: Global Convergence and Stationarity Properties

  • Mihai Anitescu
  • Paul Tseng
  • Stephen Wright
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , ,

    The elastic-mode formulation of the problem of minimizing a nonlinear function subject to equilibrium constraints has appealing local properties in that, for a finite value of the penalty parameter, local solutions satisfying first- and second-order necessary optimality conditions for the original problem are also first- and second-order points of the elastic-mode formulation. Here we study … Read more

    Interior Methods for Mathematical Programs with Complementarity Constraints

  • Sven Leyffer
  • Gabriel Lopez-Calva
  • Jorge Nocedal
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , ,

    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

    GLOBAL CONVERGENCE OF AN ELASTIC MODE APPROACH FOR A CLASS OF MATHEMATICAL PROGRAMS WITH COMPLEMENTARITY CONSTRAINTS

  • Mihai Anitescu
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Mechanical Engineering Tags , , ,

    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