Complementarity and Variational Inequalities

Quadratic Convergence of a Squared Smoothing Newton Method for Nonsmooth Matrix Equations and Its Applications in Semidefinite Optimization Problems

  • Liqun Qi
  • Jie Sun
  • Defeng Sun
    • Categories Complementarity and Variational Inequalities, Nonsmooth Optimization, Semi-definite Programming Tags ,

    We study a smoothing Newton method for solving a nonsmooth matrix equation that includes semidefinite programming and the semidefinte complementarity problem as special cases. This method, if specialized for solving semidefinite programs, needs to solve only one linear system per iteration and achieves quadratic convergence under strict complementarity. We also establish quadratic convergence of this … Read more

    A semidefinite programming heuristic for quadratic programming problems with complementarity constraints

  • Stephen E. Braun
  • John E. Mitchell
    • Categories Complementarity and Variational Inequalities, Finance and Economics, Semi-definite Programming Tags , ,

    The presence of complementarity constraints brings a combinatorial flavour to an optimization problem. A quadratic programming problem with complementarity constraints can be relaxed to give a semidefinite programming problem. The solution to this relaxation can be used to generate feasible solutions to the complementarity constraints. A quadratic programming problem is solved for each of these … 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

    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 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

    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. CitationNumerical Analysis Report NA/208, Department of Mathematics, University of Dundee, February 2002.ArticleDownload View PDF