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

Giovanni Giallombardo (giallodeis.unical.it)
Daniel Ralph (d.ralphjbs.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

Citation:

Download: [PDF]

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

Modify/Update this entry