Complementarity and Variational Inequalities

Extension of Quasi-Newton Methods to Mathematical Programs with Complementarity Constraints

  • Houyuan Jiang
  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , , , ,

    Quasi-Newton methods in conjunction with the piecewise sequential quadratic programming are investigated for solving mathematical programming with equilibrium constraints, in particular for problems with complementarity constraints. Local convergence as well as superlinear convergence of these quasi-Newton methods can be established under suitable assumptions. In particular, several well-known quasi-Newton methods such as BFGS and DFP are … Read more

    Convergence of a Penalty Method for Mathematical Programmingwith ComplementarityConstraints

  • Xinmin Hu
  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , , ,

    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

    A stable homotopy approach to horizontal linear complementarity problems

  • Daniel Ralph
    • Categories Complementarity and Variational Inequalities Tags , , , , , , , , , , , ,

    We are interested in the solution of Horizontal Linear Complementarity Problems, HLCPs, that is complementarity problems with more variables than equations. Globally metrically regular HLCPs have nonempty solution sets that are stable with respect to “right-hand-side perturbations” of the data, hence are numerically attractive. The main purpose of the paper is to show how the … Read more

    A new path-following algorithm for nonlinear P_* complementarity problems

  • Duan Li
  • Yun-Bin Zhao
    • Categories Complementarity and Variational Inequalities

    Inspired by the recent theoretical results of Zhao and Li [{\em Math. Oper. Res.,} 26 (2001), pp. 119-146], we present in this paper a new path-following method for nonlinear P$_*$ complementarity problems. Different from most existing interior-point algorithms that are based on the central path, this algorithm is to track the newly defined “regularized central … Read more

    Numerical experience with solving MPECs as NLPs

  • Roger Fletcher
  • Sven Leyffer
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization, Optimization Software Benchmark Tags , , , ,

    This paper describes numerical experience with solving MPECs as NLPs on a large collection of test problems. The key idea is to use off-the-shelf NLP solvers to tackle large instances of MPECs. It is shown that SQP methods are very well suited to solving MPECs and at present outperform Interior Point solvers both in terms … Read more

    Interior-Point Methods for Nonconvex Nonlinear Programming: Complementarity Constraints

  • Hande Benson
  • David F. Shanno
  • Robert J. Vanderbei
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , ,

    In this paper, we present the formulation and solution of optimization problems with complementarity constraints using an interior-point method for nonconvex nonlinear programming. We identify possible difficulties that could arise, such as unbounded faces of dual variables, linear dependence of constraint gradients and initialization issues. We suggest remedies. We include encouraging numerical results on the … Read more

    Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

  • Lídia Montero
  • Dulce Rosas
  • Jordi Castro
    • Categories Complementarity and Variational Inequalities, Transportation Tags , , ,

    The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient … Read more

    Local convergence of SQP methods for Mathematical Programs with Equilibrium Constraints

  • Roger Fletcher
  • Sven Leyffer
  • Daniel Ralph
  • Stefan Scholtes
    • Categories Complementarity and Variational Inequalities, Constrained Nonlinear Optimization Tags , , , ,

    Recently, it has been shown that Nonlinear Programming solvers can successfully solve a range of Mathematical Programs with Equilibrium Constraints (MPECs). In particular, Sequential Quadratic Programming (SQP) methods have been very successful. This paper examines the local convergence properties of SQP methods applied to MPECs. It is shown that SQP converges superlinearly under reasonable assumptions … Read more

    The Penalty Interior Point Method fails to converge for Mathematical Programs with Equilibrium Constraints

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

    This paper presents a small example for which the Penalty Interior Point Method converges to a non-stationary point. The reasons for this adverse behaviour are discussed. Citation Numerical Analysis Report NA/208, Department of Mathematics, University of Dundee, February 2002. Article Download View The Penalty Interior Point Method fails to converge for Mathematical Programs with Equilibrium … Read more

    A new class of merit functions for the semidefinite complementarity problem

  • Rosely M. B. Goes
  • Paulo Roberto Oliveira
    • Categories Complementarity and Variational Inequalities, Semi-definite Programming Tags , ,

    Recently,Tseng extended a class of merit functions for the nonlinear complementarity problem to semidefinite complementarity problem (SDCP), showing some properties under suitable assumptions. Yamashita and Fukushima also presented other properties. In this paper, we propose a new class of merit functions for the SDCP, and prove some of those properties, under weaker hypothesis. Particularly, we … Read more