×

Multiplier convergence in trust-region methods with application to convergence of decomposition methods for MPECs. (English) Zbl 1145.90073

Summary: 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.

MSC:

90C30 Nonlinear programming
90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming)

Software:

MacMPEC; OPECgen
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Anitescu M. (2005) On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15, 1203–1236 · Zbl 1097.90050 · doi:10.1137/S1052623402401221
[2] Anitescu, M., Tseng, P., Wright, S.J.: Elastic-mode algorithms for mathematical programs with equilibrium constraints: global convergence and stationarity properties. Technical ANL/MCS P1242-0405, Mathematics and Computer Science Division, Argonne National Laboratory, Argonne, IL, USA, May 2005 · Zbl 1119.90050
[3] Benson, H.Y., Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: complementarity constraints. Technical Report ORFE 02-02, Department of Operations Research and Financial Engineering, Princeton University, July 2002. Math. Program. Ser. A (to appear) · Zbl 1022.90017
[4] Bertsekas D.P. (1995) Nonlinear Programming. Athena Scientific Belmont, Massachussets · Zbl 0935.90037
[5] Bonnans J.F., Shapiro A. (2000) Perturbation Analysis of Optimization Problems. Springer, Berlin Heidelberg New York · Zbl 0966.49001
[6] Byrd R.H., Gould N.I.M., Nocedal J., Waltz R.H. (2004) An algorithm for nonlinear optimization using linear programming and equality constrained subproblems. Math. Program. 100, 27–48 · Zbl 1146.90513
[7] Byrd R.H., Gould N.I.M., Nocedal J., Waltz R.H. (2005) On the convergence of successive linear-quadratic programming algorithms. SIAM J. Optim. 16, 471–489 · Zbl 1092.90061 · doi:10.1137/S1052623403426532
[8] Calamai P.H., Moré J.J. (1987) Projected gradient methods for linearly constrained problems. Math. Program. 39, 93–116 · Zbl 0634.90064 · doi:10.1007/BF02592073
[9] Chin, C.M., Fletcher, R.: Numerical performance of an SLP-filter algorithm that takes EQP steps. Technical Report NA/202, Department of Mathematics, University of Dundee, Dundee, UK (2001) · Zbl 1023.90060
[10] Chin C.M., Fletcher R. (2003) On the global convergence of an SLP-filter algorithm that takes EQP steps. Math. Program. 96, 161–177 · Zbl 1023.90060 · doi:10.1007/s10107-003-0378-6
[11] Conn A.R., Gould N.I.M., Toint Ph.L. Trust-region methods. MPS-SIAM (2000)
[12] de Miguel A.V., Friedlander M., Nogales F., Scholtes S. (2005) An interior-point method for MPECS based on strictly feasible relaxations. SIAM J. Optim. 16, 587–609 · Zbl 1122.90060 · doi:10.1137/04060754x
[13] Facchinei F., Jiang H., Qi L. (1999) A smoothing method for mathematical programs with equilibrium constraints. Math. Program. 85, 81–106 · Zbl 0959.65079 · doi:10.1007/s101070050048
[14] Facchinei F., Pang J.S. (2003) Finite-dimensional variational inequalities and complementarity problems, Vol I Springer series in operations research. Springer, Berlin Heidelberg New York · Zbl 1062.90001
[15] Ferris, M.C., Ralph, D.: Projected gradient methods for nonlinear complementarity problems via normal maps. In: Du, D.Z., Qi, L., Womersley, R.S. (eds.) Recent Advances in Nonsmooth Optimization. World Scientific Publishing (1995) · Zbl 0946.90090
[16] Fiacco A.V. Introduction to sensitivity and stability analysis in nonlinear programming. Math. Sci. Eng. 165, Academic, London (1983) · Zbl 0543.90075
[17] Fischer A. (1999) Modified Wilson method for nonlinear programs with nonunique multipliers. Math. Oper. Res. 24, 699–727 · Zbl 0944.90085 · doi:10.1287/moor.24.3.699
[18] Fletcher R. (1987) Practical Methods of Optimization. Wiley, New York · Zbl 0905.65002
[19] Fletcher R., Leyffer S. (2004) Solving mathematical programs with complementarity constraints as nonlinear programs. Optim. Methods Softw. 19, 15–40 · Zbl 1074.90044 · doi:10.1080/10556780410001654241
[20] Fletcher R., Leyffer S., Ralph D., Scholtes S. (2006) Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17, 259–286 · Zbl 1112.90098 · doi:10.1137/S1052623402407382
[21] Fletcher R., Sainz de la Maza E. (1989) Nonlinear programming and nonsmooth optimization by successive linear programming. Math. Program. 43, 235–256 · Zbl 0724.90062 · doi:10.1007/BF01582292
[22] Fukushima, M., Pang, J.S.: Convergence of a smoothing continuation method for mathematical programs with complementarity constraints. In: Théra, M., Tichatschke, R. (eds.) Ill-posed Variational Problems and Regularization Techniques, vol. 447 of Lecture Notes in Economics and Mathematical Systems, Berlin/Heidelberg, pp. 99–110 (1999) · Zbl 0944.65070
[23] Fukushima M., Tseng P. (2002) An implementable active-set algorithm for computing a B-stationary point of a mathematical program with linear complementarity constraints. SIAM J. Optim. 12, 724–739 · Zbl 1005.65064 · doi:10.1137/S1052623499363232
[24] Gabriel S.A., Pang J.S. (1994) A trust region method for constrained nonsmooth equations. In: Hager W.W., Hearn D.W., Pardalos P.M. (eds) Large Scale Optimization: State of the Art. Kluwer, Dordrecht · Zbl 0813.65091
[25] Hu X., Ralph D. (2004) Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123, 365–390 · doi:10.1007/s10957-004-5154-0
[26] Huang X.X., Yang X.Q., Zhu D.L. (2006) A sequential smooth penalization approach to mathematical programs with complementarity constraints. Num. Funct. Anal. Optim. 27, 71–98 · Zbl 1119.90051 · doi:10.1080/01630560500538797
[27] Jiang H., Fukushima M., Qi L., Sun D. (1998) A trust region method for solving generalized complementarity problems. SIAM J. Optim. 8, 140–157 · Zbl 0911.90324 · doi:10.1137/S1052623495296541
[28] Jiang H., Ralph D. (1999) QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints. Comput. Optim. Appl. 13, 25–59 · Zbl 1040.90500 · doi:10.1023/A:1008696504163
[29] Jiang H., Ralph D. (2000) Smooth SQP methods for mathematical programs with nonlinear complementarity constraints. SIAM J. Optim. 10, 779–808 · Zbl 0955.90134 · doi:10.1137/S1052623497332329
[30] Lin G.H., Fukushima M. (2006) Hybrid algorithms with active set identification for mathematical programs with complementarity constraints. J. Optim. Theory Appl. 128, 1–28 · Zbl 1130.90047 · doi:10.1007/s10957-005-7549-y
[31] Liu X., Perakis G., Sun J. (2006) A robust SQP methods for mathematical programs with complementarity constraints. Comput. Optim. Appl. 34, 5–33 · Zbl 1111.90110 · doi:10.1007/s10589-005-3075-y
[32] Luo Z.Q., Pang J.S., Ralph D. (1996) Mathematical Programs With Equilibrium Constraints. Cambridge University Press, Cambridge · Zbl 0870.90092
[33] Luo Z.Q., Pang J.S., Ralph D. (1998) Piecewise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints. In: Migdalas A., Pardalos P.M., Värbrand P. (eds) Multilevel Optimization: Algorithms, Complexity and Applications. Kluwer, Norwell, pp. 209–229 · Zbl 0897.90184
[34] Maier G., Giannessi F., Nappi A. (1982) Indirect identification of yield limits by mathematical programming. Eng. Struct. 4, 86–98 · doi:10.1016/0141-0296(82)90042-6
[35] Outrata J.V., Kocvara M., Zowe J. (1998) Nonsmooth Approach to Optimization Problems with Equilibrium Constraints. Kluwer, Dordrecht
[36] Polak E. (1971) Computational Methods in Optimization: A Unified Approach. Academic, New York · Zbl 0257.90055
[37] Raghunathan A.U., Biegler L.T. (2005) Interior point methods for mathematical programs with complementarity constraints. SIAM J. Optim. 15, 720–750 · Zbl 1077.90079 · doi:10.1137/S1052623403429081
[38] Ralph D., Wright S.J. (2004) Some properties of regularization and penalization schemes for MPECs. Optim. Methods Softw. 19, 527–556 · Zbl 1097.90054 · doi:10.1080/10556780410001709439
[39] Rockafellar R.T. (1970) Convex Analysis. Princeton University Press, Princeton · Zbl 0193.18401
[40] Scheel H., Scholtes S. (2000) Mathematical programs with complementarity constraints: stationarity, optimality, and sensitivity. Math. Oper. Res. 25, 1–22 · Zbl 1073.90557
[41] Scholtes S. (2001) Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11, 918–936 · Zbl 1010.90086 · doi:10.1137/S1052623499361233
[42] Scholtes S. (2004) Nonconvex structures in nonlinear programming. Oper. Res. 52, 368–383 · Zbl 1165.90597 · doi:10.1287/opre.1030.0102
[43] Scholtes S., Stöhr M. (1999) Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37, 617–652 · Zbl 0922.90128 · doi:10.1137/S0363012996306121
[44] Stöhr M. (1999) Nonsmooth Trust Region Methods and Their Applications to Mathematical Programs With Equilibrium Constraints. Shaker-Verlag, Aachen Germany
[45] Zhang J., Liu G. (2001) A new extreme point algorithm and its application in PSQP algorithms for solving mathematical programs with linear complementarity constraints. J. Global Optim. 19, 335–361 · Zbl 1049.90125 · doi:10.1023/A:1011226232107
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.