| Title:
|
An SQP method for mathematical programs with complementarity constraints with strong convergence properties (English) |
| Author:
|
Benko, Matus |
| Author:
|
Gfrerer, Helmut |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
52 |
| Issue:
|
2 |
| Year:
|
2016 |
| Pages:
|
169-208 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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. (English) |
| Keyword:
|
SQP method |
| Keyword:
|
active set method |
| Keyword:
|
mathematical program with complementarity constraints |
| Keyword:
|
strong M-stationarity |
| MSC:
|
49M37 |
| MSC:
|
90C26 |
| MSC:
|
90C33 |
| MSC:
|
90C55 |
| idZBL:
|
Zbl 1357.49124 |
| idMR:
|
MR3501157 |
| DOI:
|
10.14736/kyb-2016-2-0169 |
| . |
| Date available:
|
2016-07-17T11:59:41Z |
| Last updated:
|
2018-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/145769 |
| . |
| Reference:
|
[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. Zbl 1099.65050, MR 2177772, 10.1137/040606855 |
| Reference:
|
[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. Zbl 1097.90050, MR 2178496, 10.1137/s1052623402401221 |
| Reference:
|
[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. Zbl 1077.90079, MR 2142858, 10.1137/s1052623403429081 |
| Reference:
|
[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. Zbl 1122.90060, MR 2197997, 10.1137/04060754x |
| Reference:
|
[5] Facchinei, F., Jiang, H., Qi, L.: A smoothing method for mathematical programs with equilibrium constraints..Math. Programming 85 (1999), 107-134. Zbl 0959.65079, MR 1689366, 10.1007/s101070050048 |
| Reference:
|
[6] Fletcher, R.: Practical Methods of Optimization 2: Constrained Optimization..John Wiley and Sons, Chichester 1981. MR 0633058 |
| Reference:
|
[7] Fletcher, R., Leyffer, S.: Solving mathematical programs with complementary constraints as nonlinear programs.. Zbl 1074.90044 |
| Reference:
|
[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. Zbl 1112.90098, MR 2219153, 10.1137/s1052623402407382 |
| Reference:
|
[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. Zbl 1127.65034, MR 1884914, 10.1137/s1052623499363232 |
| Reference:
|
[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. Zbl 1298.49021, MR 3217222, 10.1137/130914449 |
| Reference:
|
[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. Zbl 1145.90073, MR 2361928, 10.1007/s10107-006-0020-5 |
| Reference:
|
[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. MR 2101411, 10.1007/s10957-004-5154-0 |
| Reference:
|
[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. Zbl 1245.90124, MR 2872496, 10.1007/s10589-010-9341-7 |
| Reference:
|
[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. MR 1704113, 10.1023/A:1008696504163 |
| Reference:
|
[15] Jiang, H., Ralph, D.: Extension of quasi-newton methods to mathematical programs with complementarity constraints..Comput. Optim. Appl. 25 (2002), 123-150. Zbl 1038.90100, MR 1996665, 10.1023/A:1022945316191 |
| Reference:
|
[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. Zbl 1187.65064, MR 2496894, 10.1137/070705490 |
| Reference:
|
[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. Zbl 1282.65069, MR 3045664, 10.1137/100802487 |
| Reference:
|
[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. MR 3320430, 10.1287/moor.2014.0667 |
| Reference:
|
[19] Leyffer, S.: MacMPEC: AMPL collection of MPECs, 2000.. |
| Reference:
|
[20] Leyffer, S., López-Calva, G., Nocedal, J.: Interior methods for mathematical programs with complementarity constraints..SIAM J. Optim. 17 (2006), 52-77. Zbl 1112.90095, MR 2219144, 10.1137/040621065 |
| Reference:
|
[21] Lin, G. H., Fukushima, M.: A modified relaxation scheme for mathematical programs with complementarity constraints..Ann. Oper. Res. 133 (2005), 63-84. Zbl 1119.90058, MR 2119313, 10.1007/s10479-004-5024-z |
| Reference:
|
[22] Luo, Z. Q., Pang, J. S., Ralph, D.: Mathematical Programs with Equilibrium Constraints..Cambridge University Press, Cambridge, New York, Melbourne 1996. Zbl 1139.90003, MR 1419501, 10.1017/cbo9780511983658 |
| Reference:
|
[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. Zbl 0897.90184, MR 1605239, 10.1007/978-1-4613-0307-7_9 |
| Reference:
|
[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. Zbl 0870.90092, MR 1415093, 10.1007/bf02592205 |
| Reference:
|
[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. MR 1641213, 10.1007/978-1-4757-2825-5 |
| Reference:
|
[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. Zbl 0374.65032, MR 0483447, 10.1007/bfb0067703 |
| Reference:
|
[27] Ralph, D., Wright, S. J.: Some properties of regularization and penalization schemes for MPECs..Optim. Methods Software 19 (2004), 527-556. Zbl 1097.90054, MR 2095351, 10.1080/10556780410001709439 |
| Reference:
|
[28] Scheel, H., Scholtes, S.: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity..Math. Oper. Res. 25 (2000), 1-22. Zbl 1073.90557, MR 1854317, 10.1287/moor.25.1.1.15213 |
| Reference:
|
[29] Scholtes, S.: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints..SIAM J. Optim. 11 (2001), 918-936. Zbl 1010.90086, MR 1855214, 10.1137/s1052623499361233 |
| Reference:
|
[30] Scholtes, S., Stöhr, M.: Exact penalization of mathematical programs with equilibrium constraints..SIAM J. Control Optim. 37 (1999), 617-652. Zbl 0922.90128, MR 1670641, 10.1137/s0363012996306121 |
| Reference:
|
[31] Steffensen, S., Ulbrich, M.: A new regularization scheme for mathematical programs with equilibrium constraints..SIAM J. Optim. 20 (2010), 2504-2539. MR 2678403, 10.1137/090748883 |
| Reference:
|
[32] Stein, O.: Lifting mathematical programs with complementarity constraints..Math. Programming 131 (2012), 71-94. Zbl 1250.90094, MR 2886141, 10.1007/s10107-010-0345-y |
| Reference:
|
[33] Stöhr, M.: Nonsmooth Trust Region Methods and their Applications to Mathematical Programs with Equilibrium Constraints..Shaker-Verlag, Aachen 1999. |
| Reference:
|
[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. Zbl 1049.90125, MR 1824769, 10.1023/A:1011226232107 |
| . |
