Kybernetika 52 no. 2, 169-208, 2016

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

Matus Benko and Helmut GfrererDOI: 10.14736/kyb-2016-2-0169

Abstract:

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.

Keywords:

SQP method, active set method, mathematical program with complementarity constraints, strong M-stationarity

Classification:

49M37, 90C26, 90C33, 90C55

paper.pdf

References:

  1. M. Anitescu: 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
  2. M. Anitescu: 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
  3. L. T. Biegler and A. U. Raghunathan: An interior point method for mathematical programs with complementarity constraints (MPCCs). SIAM J. Optim. 15 (2005), 720-750.   DOI:10.1137/s1052623403429081
  4. V. DeMiguel, M. P. Friedlander, F. J. Nogales and S. Scholtes: A two-sided relaxation scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 16 (2005), 587-609.   DOI:10.1137/04060754x
  5. F. Facchinei, H. Jiang and L. Qi: A smoothing method for mathematical programs with equilibrium constraints. Math. Programming 85 (1999), 107-134.   DOI:10.1007/s101070050048
  6. R. Fletcher: Practical Methods of Optimization 2: Constrained Optimization. John Wiley and Sons, Chichester 1981.   CrossRef
  7. R. Fletcher and S. Leyffer: Solving mathematical programs with complementary constraints as nonlinear programs.    CrossRef
  8. R. Fletcher, S. Leyffer, D. Ralph and S. Scholtes: Local convergence of SQP methods for mathematical programs with equilibrium constraints. SIAM J. Optim. 17 (2006), 259-286.   DOI:10.1137/s1052623402407382
  9. M. Fukushima and P. Tseng: 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
  10. H. Gfrerer: 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
  11. G. Giallombardo and D. Ralph: 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
  12. X. M. Hu and D. Ralph: 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
  13. A. F. Izmailov, A. L. Pogosyan and M. V. Solodov: 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
  14. H. Jiang and D. Ralph: QPECgen, a MATLAB generator for mathematical programs with quadratic objectives and affine variational inequality constraints. Comput. Optim. Appl. 13 (1999), 25-59.   CrossRef
  15. H. Jiang and D. Ralph: Extension of quasi-newton methods to mathematical programs with complementarity constraints. Comput. Optim. Appl. 25 (2002), 123-150.   CrossRef
  16. A. Kadrani, J. P. Dussault and A. Benchakroun: A new regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 20 (2009), 78-103.   DOI:10.1137/070705490
  17. C. Kanzow and A. Schwartz: A new regularization method for mathematical programs with complementarity constraints with strong convergence properties. SIAM J. Optim. 23 (2013), 770-798.   CrossRef
  18. C. Kanzow and A. Schwartz: 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
  19. S. Leyffer: MacMPEC: AMPL collection of MPECs, 2000.    https://wiki.mcs.anl.gov/leyffer/index.php/MacMPEC
  20. S. Leyffer, G. López-Calva and J. Nocedal: Interior methods for mathematical programs with complementarity constraints. SIAM J. Optim. 17 (2006), 52-77.   DOI:10.1137/040621065
  21. G. H. Lin and M. Fukushima: A modified relaxation scheme for mathematical programs with complementarity constraints. Ann. Oper. Res. 133 (2005), 63-84.   DOI:10.1007/s10479-004-5024-z
  22. Z. Q. Luo, J. S. Pang and D. Ralph: Mathematical Programs with Equilibrium Constraints. Cambridge University Press, Cambridge, New York, Melbourne 1996.   DOI:10.1017/cbo9780511983658
  23. Z. Q. Luo, J. S. Pang and D. Ralph: 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
  24. Z. Q. Luo, J. S. Pang, D. Ralph and S. Q. Wu: Exact penalization and stationarity conditions of mathematical programs with equilibrium constraints. Math. Programming 75 (1996), 19-76.   DOI:10.1007/bf02592205
  25. J. V. Outrata, M. Kočvara and J. Zowe: 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}
  26. M. J. D. Powell: 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
  27. D. Ralph and S. J. Wright: Some properties of regularization and penalization schemes for MPECs. Optim. Methods Software 19 (2004), 527-556.   DOI:10.1080/10556780410001709439
  28. H. Scheel and S. Scholtes: Mathematical programs with complementarity constraints: Stationarity, optimality, and sensitivity. Math. Oper. Res. 25 (2000), 1-22.   DOI:10.1287/moor.25.1.1.15213
  29. S. Scholtes: Convergence properties of a regularization scheme for mathematical programs with complementarity constraints. SIAM J. Optim. 11 (2001), 918-936.   DOI:10.1137/s1052623499361233
  30. S. Scholtes and M. Stöhr: Exact penalization of mathematical programs with equilibrium constraints. SIAM J. Control Optim. 37 (1999), 617-652.   DOI:10.1137/s0363012996306121
  31. S. Steffensen and M. Ulbrich: A new regularization scheme for mathematical programs with equilibrium constraints. SIAM J. Optim. 20 (2010), 2504-2539.   DOI:10.1137/090748883
  32. O. Stein: Lifting mathematical programs with complementarity constraints. Math. Programming 131 (2012), 71-94.   DOI:10.1007/s10107-010-0345-y
  33. M. Stöhr: Nonsmooth Trust Region Methods and their Applications to Mathematical Programs with Equilibrium Constraints. Shaker-Verlag, Aachen 1999.   CrossRef
  34. J. Zhang and G. Liu: 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.   CrossRef