Interior-Point Algorithms, Penalty Methods and Equilibrium Problems

Hande Y Benson (bensondrexel.edu)
Arun Sen (asenprinceton.edu)
David F. Shanno (shannorutcor.rutgers.edu)
Robert J. Vanderbei (rvdbprinceton.edu)

Abstract: In this paper we consider the question of solving equilibrium problems---formulated as complementarity problems and, more generally, mathematical programs with equilibrium constraints (MPEC's)---as nonlinear programs, using an interior-point approach. These problems pose theoretical difficulties for nonlinear solvers, including interior-point methods. We examine the use of penalty methods to get around these difficulties, present an example from game theory where this makes a difference in practice, and provide substantial numerical results. We go on to show that penalty methods can resolve some problems that interior-point algorithms encounter in general.

Keywords: interior-point methods, nonlinear programming, penalty methods, equilibrium problems, complementarity

Category 1: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 2: Complementarity and Variational Inequalities

Category 3: Other Topics (Game Theory )

Citation: Technical Report ORFE-03-02, Department of Operations Research and Financial Engineering, Princeton University, Princeton NJ, 08544, October 2003.

Download: [PDF]

Entry Submitted: 10/01/2003
Entry Accepted: 10/01/2003
Entry Last Modified: 10/01/2003

Modify/Update this entry