Previous |  Up |  Next

Article

Keywords:
SQP method; active set method; mathematical program with complementarity constraints; strong M-stationarity
Summary:
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.
References:
[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 10.1137/040606855 | MR 2177772 | Zbl 1099.65050
[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 10.1137/s1052623402401221 | MR 2178496 | Zbl 1097.90050
[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 10.1137/s1052623403429081 | MR 2142858 | Zbl 1077.90079
[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 10.1137/04060754x | MR 2197997 | Zbl 1122.90060
[5] Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints. Math. Programming 85 (1999), 107-134. DOI 10.1007/s101070050048 | MR 1689366 | Zbl 0959.65079
[6] Fletcher, R.: Practical Methods of Optimization 2: Constrained Optimization. John Wiley and Sons, Chichester 1981. MR 0633058
[7] Fletcher, R., Leyffer, S.: Solving mathematical programs with complementary constraints as nonlinear programs. Zbl 1074.90044
[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 10.1137/s1052623402407382 | MR 2219153 | Zbl 1112.90098
[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 10.1137/s1052623499363232 | MR 1884914 | Zbl 1127.65034
[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 10.1137/130914449 | MR 3217222 | Zbl 1298.49021
[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 10.1007/s10107-006-0020-5 | MR 2361928 | Zbl 1145.90073
[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 10.1007/s10957-004-5154-0 | MR 2101411
[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 10.1007/s10589-010-9341-7 | MR 2872496 | Zbl 1245.90124
[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 10.1023/A:1008696504163 | MR 1704113
[15] Jiang, H., Ralph, D.: Extension of quasi-newton methods to mathematical programs with complementarity constraints. Comput. Optim. Appl. 25 (2002), 123-150. DOI 10.1023/A:1022945316191 | MR 1996665 | Zbl 1038.90100
[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 10.1137/070705490 | MR 2496894 | Zbl 1187.65064
[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 10.1137/100802487 | MR 3045664 | Zbl 1282.65069
[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 10.1287/moor.2014.0667 | MR 3320430
[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 10.1137/040621065 | MR 2219144 | Zbl 1112.90095
[21] Lin, G. H., Fukushima, M.: A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133 (2005), 63-84. DOI 10.1007/s10479-004-5024-z | MR 2119313 | Zbl 1119.90058
[22] Luo, Z. Q., Pang, J. S., Ralph, D.: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge, New York, Melbourne 1996. DOI 10.1017/cbo9780511983658 | MR 1419501 | Zbl 1139.90003
[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 10.1007/978-1-4613-0307-7_9 | MR 1605239 | Zbl 0897.90184
[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 10.1007/bf02592205 | MR 1415093 | Zbl 0870.90092
[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 10.1007/978-1-4757-2825-5 | MR 1641213
[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 10.1007/bfb0067703 | MR 0483447 | Zbl 0374.65032
[27] Ralph, D., Wright, S. J.: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Software 19 (2004), 527-556. DOI 10.1080/10556780410001709439 | MR 2095351 | Zbl 1097.90054
[28] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25 (2000), 1-22. DOI 10.1287/moor.25.1.1.15213 | MR 1854317 | Zbl 1073.90557
[29] Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11 (2001), 918-936. DOI 10.1137/s1052623499361233 | MR 1855214 | Zbl 1010.90086
[30] Scholtes, S., Stöhr, M.: Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37 (1999), 617-652. DOI 10.1137/s0363012996306121 | MR 1670641 | Zbl 0922.90128
[31] Steffensen, S., Ulbrich, M.: A new regularization scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 20 (2010), 2504-2539. DOI 10.1137/090748883 | MR 2678403
[32] Stein, O.: Lifting mathematical programs with complementarity constraints. Math. Programming 131 (2012), 71-94. DOI 10.1007/s10107-010-0345-y | MR 2886141 | Zbl 1250.90094
[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 10.1023/A:1011226232107 | MR 1824769 | Zbl 1049.90125
Partner of
EuDML logo