An interior-point method for MPECs based on strictly feasible relaxations

Angel-Victor DeMiguel (avmiguellondon.edu)
Michael Friedlander (michaelmcs.anl.gov)
Francisco Javier Nogales (FcoJavier.Nogalesuc3m.es)
Stefan Scholtes (s.scholtesjims.cam.ac.uk)

Abstract: An interior-point method for solving mathematical programs with equilibrium constraints (MPECs) is proposed. At each iteration of the algorithm, a single primal-dual step is computed from each subproblem of a sequence. Each subproblem is defined as a relaxation of the MPEC with a nonempty strictly feasible region. In contrast to previous approaches, the proposed relaxation scheme preserves the nonempty strict feasibility of each subproblem even in the limit. Local and superlinear convergence of the algorithm is proved even with a less restrictive strict complementarity condition than the standard one. Moreover, mechanisms for inducing global convergence in practice are proposed. Numerical results on the MacMPEC test problem set demonstrate the fast-local convergence properties of the algorithm.

Keywords: nonlinear programming, mathematical programs with equilibrium constraints, constrained minimization, interior-point methods, primal-dual methods, barrier methods

Category 1: Nonlinear Optimization

Citation: London Business School working paper, 2004.

Download: [PDF]

Entry Submitted: 04/29/2004
Entry Accepted: 04/29/2004
Entry Last Modified: 04/29/2004

Modify/Update this entry