Optimization Online


Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs

Giovanni Giallombardo (giallo***at***deis.unical.it)
Daniel Ralph (d.ralph***at***jbs.cam.ac.uk)

Abstract: We study piecewise decomposition methods for mathematical programs with equilibrium constraints (MPECs) for which all constraint functions are linear. At each iteration of a decomposition method, one step of a nonlinear programming scheme is applied to one piece of the MPEC to obtain the next iterate. Our goal is to understand global convergence to B-stationary points of these methods when the embedded nonlinear programming solver is a trust-region scheme, and the selection of pieces is determined using multipliers generated by solving the trust-region subproblem. To this end we study global convergence of a linear trust-region scheme for linearly-constrained NLPs that we call a trust-search method. The trust-search has two features that are critical to global convergence of decomposition methods for MPECs: a robustness property with respect to switching pieces, and a multiplier convergence result that appears to be quite new for trust-region methods. These combine to clarify and strengthen global convergence of decomposition methods without resorting either to additional conditions such as eventual inactivity of the trust-region constraint, or more complex methods that require a separate subproblem for multiplier estimation.

Keywords: mathematical program with equilibrium constraints, MPEC, complementarity constraints, MPCC, B-stationary, M-stationary, linear constraints, nonlinear program

Category 1: Nonlinear Optimization

Category 2: Nonlinear Optimization (Constrained Nonlinear Optimization )

Category 3: Complementarity and Variational Inequalities


Download: [PDF]

Entry Submitted: 08/15/2006
Entry Accepted: 08/15/2006
Entry Last Modified: 08/15/2006

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