An SQP method for mathematical programs with complementarity constraints with strong convergence properties

Benko, Matus   ; Gfrerer, Helmut

Kybernetika, Tome 52 (2016) no. 2, pp. 169-208

Abstract (VO)

We propose an SQP algorithm for mathematical programs with complementarity constraints which solves at each iteration a quadratic program with linear complementarity constraints. We demonstrate how strongly M-stationary solutions of this quadratic program can be obtained by an active set method without using enumeration techniques. We show that all limit points of the sequence of iterates generated by our SQP method are at least M-stationary.

Détail

DOI : 10.14736/kyb-2016-2-0169

Classification : 49M37, 90C26, 90C33, 90C55
Keywords: SQP method; active set method; mathematical program with complementarity constraints; strong M-stationarity

Bibliographie

[1] Anitescu, M.: Global convergence of an elastic mode approach for a class of mathematical programs with complementarity constraints. SIAM J. Optim. 16 (2005), 120-145. | DOI | MR | Zbl

[2] Anitescu, M.: On using the elastic mode in nonlinear programming approaches to mathematical programs with complementarity constraints. SIAM J. Optim. 15 (2005), 1203-1236. | DOI | MR | Zbl

[3] Biegler, L. T., Raghunathan, A. U.: An interior point method for mathematical programs with complementarity constraints (MPCCs). SIAM J. Optim. 15 (2005), 720-750. | DOI | MR | Zbl

[4] DeMiguel, V., Friedlander, M. P., Nogales, F. J., Scholtes, S.: A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16 (2005), 587-609. | DOI | MR | Zbl

[5] Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Programming 85 (1999), 107-134. | DOI | MR | Zbl

[6] Fletcher, R.: Practical Methods of Optimization 2: Constrained Optimization. John Wiley and Sons, Chichester 1981. | MR

[7] Fletcher, R., Leyffer, S.: Solving mathematical programs with complementary constraints as nonlinear programs. | Zbl

[8] Fletcher, R., Leyffer, S., Ralph, D., Scholtes, S.: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17 (2006), 259-286. | DOI | MR | Zbl

[9] Fukushima, M., Tseng, P.: An implementable active-set algorithm for computing a b-stationary point of a mathematical program with linear complementarity constraints. SIAM J. Optim. 12 (2002), 724-739. | DOI | MR | Zbl

[10] Gfrerer, H.: Optimality conditions for disjunctive programs based on generalized differentiation with application to mathematical programs with equilibrium constraints. SIAM J. Optim. 24 (2014), 898-931. | DOI | MR | Zbl

[11] Giallombardo, G., Ralph, D.: Multiplier convergence in trust region methods with application to convergence of decomposition methods for MPECs. Math. Programming 112 (2008), 335-369. | DOI | MR | Zbl

[12] Hu, X. M., Ralph, D.: Convergence of a penalty method for mathematical programming with complementarity constraints. J. Optim. Theory Appl. 123 (2004), 365-390. | DOI | MR

[13] Izmailov, A. F., Pogosyan, A. L., Solodov, M. V.: Semismooth Newton method for the lifted reformulation of mathematical programs with complementarity constraints. Computational Optim. Appl. 51 (2012), 199-221. | DOI | MR | Zbl

[14] Jiang, H., Ralph, D.: QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints. Comput. Optim. Appl. 13 (1999), 25-59. | DOI | MR

[15] Jiang, H., Ralph, D.: Extension of quasi-newton methods to mathematical programs with complementarity constraints. Comput. Optim. Appl. 25 (2002), 123-150. | DOI | MR | Zbl

[16] Kadrani, A., Dussault, J. P., Benchakroun, A.: A new regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 20 (2009), 78-103. | DOI | MR | Zbl

[17] Kanzow, C., Schwartz, A.: A new regularization method for mathematical programs with complementarity constraints with strong convergence properties. SIAM J. Optim. 23 (2013), 770-798. | DOI | MR | Zbl

[18] Kanzow, C., Schwartz, A.: The price of inexactness: convergence properties of relaxation methods for mathematical programs with equilibrium constraints revisited. Math. Oper. Res. 40 (2015), 2, 253-275. | DOI | MR

[19] Leyffer, S.: MacMPEC: AMPL collection of MPECs, 2000. DOI 

[20] Leyffer, S., López-Calva, G., Nocedal, J.: Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17 (2006), 52-77. | DOI | MR | Zbl

[21] Lin, G. H., Fukushima, M.: A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133 (2005), 63-84. | DOI | MR | Zbl

[22] Luo, Z. Q., Pang, J. S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge, New York, Melbourne 1996. | DOI | MR | Zbl

[23] Luo, Z. Q., Pang, J. S., Ralph, D.: Piecewise sequential quadratic programming for mathematical programs with nonlinear complementarity constraints. In: Multilevel Optimization: Algorithms, Complexity, and Applications (A. Migdalas, P. Pardalos, and P. Värbrand, eds.), Kluwer Academic Publishers, Dordrecht 1998, pp. 209-229. | DOI | MR | Zbl

[24] Luo, Z. Q., Pang, J. S., Ralph, D., Wu, S. Q.: Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints. Math. Programming 75 (1996), 19-76. | DOI | MR | Zbl

[25] Outrata, J. V., Kočvara, M., Zowe, J.: Nonsmooth Approach to Optimization Problems with Equilibrium Constraints, Nonconvex Optimization and its Applications. Kluwer Academic Publishers, Dordrecht 1998. | DOI | MR

[26] Powell, M. J. D.: A fast algorithm for nonlinearly constrained optimization calculations. In: Numerical Analysis Dundee 1977 (G. A. Watson, ed.), Lecture Notes in Mathematics 630, Springer, Berlin, 1978, pp. 144-157. | DOI | MR | Zbl

[27] Ralph, D., Wright, S. J.: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Software 19 (2004), 527-556. | DOI | MR | Zbl

[28] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25 (2000), 1-22. | DOI | MR | Zbl

[29] Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11 (2001), 918-936. | DOI | MR | Zbl

[30] Scholtes, S., Stöhr, M.: Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37 (1999), 617-652. | DOI | MR | Zbl

[31] Steffensen, S., Ulbrich, M.: A new regularization scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 20 (2010), 2504-2539. | DOI | MR

[32] Stein, O.: Lifting mathematical programs with complementarity constraints. Math. Programming 131 (2012), 71-94. | DOI | MR | Zbl

[33] Stöhr, M.: Nonsmooth Trust Region Methods and their Applications to Mathematical Programs with Equilibrium Constraints. Shaker-Verlag, Aachen 1999.

[34] Zhang, J., Liu, G.: A new extreme point algorithm and its application in psqp algorithms for solving mathematical programs with linear complementarity constraints. J. Glob. Optim. 19 (2001), 335-361. | DOI | MR | Zbl