Optimization Online


A stable homotopy approach to horizontal linear complementarity problems

Daniel Ralph (danny.ralph***at***jims.cam.ac.uk)

Abstract: 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 stability or conditioning properties of globally metrically regular HLCPs are preserved by a homotopy framework for solving the HLCP that finds a ``stable'' direction at each iteration as a local minimizer of a strongly convex quadratic program with linear complementarity constraints, QPCC. Apart from intrinsic interest in numerical solution of HLCPs, this investigation has application in solving horizontal nonlinear complementarity problems and more broadly in the area of mathematical programs with complementarity constraints, MPCCs.

Keywords: horizontal linear complementarity problem, mathematical program with complementarity constraints, piecewise affine system, global metric regularity, pseudo-Lipschitz continuity, stable solution, homotopy method, path following, active set method, MPCC, MPEC, QPCC, MPCC-LICQ

Category 1: Complementarity and Variational Inequalities

Citation: The Judge Institute of Management, University of Cambridge, Trumpington St, CB2 1AG, UK

Download: [Postscript][Compressed Postscript]

Entry Submitted: 09/02/2002
Entry Accepted: 09/03/2002
Entry Last Modified: 09/02/2002

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society