Kirches, Christian; Larson, Jeffrey; Leyffer, Sven; Manns, Paul Sequential linearization method for bound-constrained mathematical programs with complementarity constraints. (English) Zbl 1484.90126 SIAM J. Optim. 32, No. 1, 75-99 (2022). Summary: We propose an algorithm for solving bound-constrained mathematical programs with complementarity constraints on the variables. Each iteration of the algorithm involves solving a linear program with complementarity constraints in order to obtain an estimate of the active set. The algorithm enforces descent on the objective function to promote global convergence to B-stationary points. We provide a convergence analysis and preliminary numerical results on a range of test problems. We also study the effect of fixing the active constraints in a bound-constrained quadratic program that can be solved on each iteration in order to obtain fast convergence. Cited in 1 Document MSC: 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions) (aspects of mathematical programming) 90C55 Methods of successive quadratic programming type Keywords:mathematical programs with complementarity constraints; B-stationarity; sequential linear programming Software:pySLEQP; LANCELOT; SNOPT; MacMPEC; ALGENCAN; MINOS; TANGO; Ipopt; PATH Solver PDFBibTeX XMLCite \textit{C. Kirches} et al., SIAM J. Optim. 32, No. 1, 75--99 (2022; Zbl 1484.90126) Full Text: DOI arXiv References: [1] E. G. Birgin, TANGO: Trustable Algorithms for Nonlinear General Optimization, Institute of Mathematics, Statistics and Scientific Computation, University of Campinas, Campinas, Brazil, https://www.ime.usp.br/ egbirgin/tango, 2005. [2] E. G. Birgin and J. M. Martínez, Practical Augmented Lagrangian Methods for Constrained Optimization, SIAM, Philadelphia, 2014, https://doi.org/10.1137/1.9781611973365. · Zbl 1339.90312 [3] E. G. Birgin and J. M. Martínez, Improving ultimate convergence of an augmented Lagrangian method, Optim. Methods Softw., 23 (2008), pp. 177-195, https://doi.org/10.1080/10556780701577730. · Zbl 1211.90222 [4] R. H. Byrd, N. I. M. Gould, J. Nocedal, and R. A. Waltz, An algorithm for nonlinear optimization using linear programming and equality constrained subproblems, Math. Program. Ser. B, 100 (2004), pp. 27-48, https://doi.org/10.1007/s10107-003-0485-4. · Zbl 1146.90513 [5] L. Chen and D. Goldfarb, An Active-Set Method for Mathematical Programs with Linear Complementarity Constraints, Technical report, Columbia University, 2007. [6] C. Chin and R. Fletcher, On the global convergence of an SLP-filter algorithm that takes EQP steps, Math. Program., 96 (2003), pp. 161-177, https://doi.org/10.1007/s10107-003-0378-6. · Zbl 1023.90060 [7] A. R. Conn, N. I. M. Gould, and P. L. Toint, LANCELOT: A Fortran package for large-scale nonlinear optimization (Release A), Springer-Verlag, Berlin, 1992, https://doi.org/10.1007/978-3-662-12211-2. · Zbl 0761.90087 [8] A. R. Conn, N. I. M. Gould, and P. L. Toint, Numerical experiments with the LANCELOT package (Release A) for large-scale nonlinear optimization, Math. Program., 73 (1996), pp. 73-110, https://doi.org/10.1007/bf02592099. · Zbl 0848.90109 [9] R. W. Cottle and G. B. Dantzig, Complementary pivot theory of mathematical programming, Linear Algebra Appl., 1 (1968), pp. 103-125, https://doi.org/10.1016/0024-3795(68)90052-9. · Zbl 0155.28403 [10] F. E. Curtis, H. Jiang, and D. P. Robinson, An adaptive augmented Lagrangian method for large-scale constrained optimization, Math. Program., 152 (2015), pp. 201-245, https://doi.org/10.1007/s10107-014-0784-y. · Zbl 1323.49015 [11] H. Fang, S. Leyffer, and T. S. Munson, A pivoting algorithm for linear programming with linear complementarity constraints, Optim. Methods Softw., 27 (2012), pp. 89-114, https://doi.org/10.1080/10556788.2010.512956. · Zbl 1311.90152 [12] M. C. Ferris, R. Fourer, and D. M. Gay, Expressing complementarity problems in an algebraic modeling language and communicating them to solvers, SIAM J. Optim., 9 (1999), pp. 991-1009, https://doi.org/10.1137/s105262349833338x. · Zbl 0997.90087 [13] M. C. Ferris and T. S. Munson, Interfaces to PATH 3.0: Design, implementation and usage, Comput. Optim. Appl., 12 (1999), pp. 207-227, https://doi.org/10.1023/A:1008636318275. · Zbl 1040.90549 [14] M. L. Flegel and C. Kanzow, Abadie-type constraint qualification for mathematical programs with equilibrium constraints, J. Optim. Theory Appl., 124 (2005), pp. 595-614, https://doi.org/10.1007/s10957-004-1176-x. · Zbl 1090.90200 [15] R. Fletcher and E. S. de la Maza, Nonlinear programming and nonsmooth optimization by successive linear programming, Math. Program., 43 (1989), pp. 235-256, https://doi.org/10.1007/bf01582292. · Zbl 0724.90062 [16] R. Fletcher and S. Leyffer, Nonlinear programming without a penalty function, Math. Program., 91 (2002), pp. 239-269, https://doi.org/10.1007/s101070100244. · Zbl 1049.90088 [17] R. Fletcher and S. Leyffer, Solving mathematical program with complementarity constraints as nonlinear programs, Optim. Methods Softw., 19 (2004), pp. 15-40, https://doi.org/10.1080/10556780410001654241. · Zbl 1074.90044 [18] 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), pp. 259-286, https://doi.org/10.1137/s1052623402407382. · Zbl 1112.90098 [19] R. Fletcher, S. Leyffer, and P. L. Toint, On the global convergence of a filter-SQP algorithm, SIAM J. Optim., 13 (2002), pp. 44-59, https://doi.org/10.1137/s105262340038081x. · Zbl 1029.65063 [20] M. P. Friedlander and M. A. Saunders, A globally convergent linearly constrained Lagrangian method for nonlinear optimization, SIAM J. Optim., 15 (2005), pp. 863-897, https://doi.org/10.1137/s1052623402419789. · Zbl 1077.90065 [21] M. Fukushima and P. Tseng, An implementable active-set algorithm for computing a B-stationary point of the mathematical program with linear complementarity constraints, SIAM J. Optim., 12 (2002), pp. 724-739, https://doi.org/10.1137/050642460. · Zbl 1005.65064 [22] P. Gill, W. Murray, and M. A. Saunders, SNOPT: An SQP algorithm for large-scale constrained optimization, SIAM Rev., 47 (2005), pp. 99-131, https://doi.org/10.1137/s0036144504446096. · Zbl 1210.90176 [23] J. Hu, J. E. Mitchell, J.-S. Pang, K. P. Bennett, and G. Kunapuli, On the global solution of linear programs with linear complementarity constraints, SIAM J. Optim., 19 (2008), pp. 445-471, https://doi.org/10.1137/07068463x. · Zbl 1163.90031 [24] J. J. Júdice, H. D. Sherali, I. M. Ribeiro, and A. M. Faustino, Complementarity active-set algorithm for mathematical programming problems with equilibrium constraints, J. Optim. Theory Appl., 134 (2007), pp. 467-481, https://doi.org/10.1007/s10957-007-9231-z. · Zbl 1145.90075 [25] C. Kirches, J. Larson, S. Leyffer, and P. Manns, Sequential Linearization Method for Bound-Constrained Mathematical Programs with Complementarity Constraints, Technical report version including appendices, https://arxiv.org/pdf/2009.14047v4.pdf, 2021. [26] F. Lenders, C. Kirches, and H. G. Bock, pySLEQP: A sequential linear quadratic programming method implemented in Python, in Modeling, Simulation and Optimization of Complex Processes HPSC 2015, Springer-Verlag, Berlin, 2017, pp. 103-113, https://doi.org/10.1007/978-3-319-67168-0_9. [27] S. Leyffer, MacMPEC: AMPL Collection of MPECs, Argonne National Laboratory, Lemont, IL, https://www.mcs.anl.gov/ leyffer/MacMPEC/, 2020. [28] S. Leyffer, G. Lopez-Calva, and J. Nocedal, Interior methods for mathematical programs with complementarity constraints, SIAM J. Optim., 17 (2006), pp. 52-77, https://doi.org/10.1137/040621065. · Zbl 1112.90095 [29] Z.-Q. Luo, J.-S. Pang, and D. Ralph, Mathematical Programs with Equilibrium Constraints, Cambridge University Press, Cambridge, 1996, https://doi.org/10.1017/cbo9780511983658. [30] B. A. Murtagh and M. A. Saunders, Large-scale linearly constrained optimization, Math. Program., 14 (1978), pp. 41-72, https://doi.org/10.1007/bf01588950. · Zbl 0383.90074 [31] B. A. Murtagh and M. A. Saunders, MINOS 5.51 User’s Guide, Report SOL 83-20R, Stanford University, 2003, https://web.stanford.edu/group/SOL/guides/minos551.pdf. [32] J. Nocedal and S. J. Wright, Numerical Optimization, 2nd ed., Springer-Verlag, Berlin, 2006, https://doi.org/10.1007/978-0-387-40065-5. · Zbl 1104.65059 [33] J. V. Outrata, Optimality conditions for a class of mathematical programs with equilibrium constraints, Math. Oper. Res., 24 (1999), pp. 627-644, https://doi.org/10.1287/moor.24.3.627. · Zbl 1039.90088 [34] A. Raghunathan and L. T. Biegler, An interior point method for mathematical programs with complementarity constraints (MPCCs), SIAM J. Optim., 15 (2005), pp. 720-750, https://doi.org/10.1137/S1052623403429081. · Zbl 1077.90079 [35] S. Scholtes and M. Stöhr, Exact penalization of mathematical programs with equilibrium constraints, SIAM J. Control Optim., 37 (1999), pp. 617-652, https://doi.org/10.1137/S0363012996306121. · Zbl 0922.90128 [36] A. Wächter and L. T. Biegler, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106 (2005), pp. 25-57, https://doi.org/10.1007/s10107-004-0559-y. · Zbl 1134.90542 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.