On the behavior of Lagrange multipliers in convex and nonconvex infeasible interior point methods. (English) Zbl 1459.90152
Summary: We analyze sequences generated by interior point methods (IPMs) in convex and nonconvex settings. We prove that moving the primal feasibility at the same rate as the barrier parameter \(\mu\) ensures the Lagrange multiplier sequence remains bounded, provided the limit point of the primal sequence has a Lagrange multiplier. This result does not require constraint qualifications. We also guarantee the IPM finds a solution satisfying strict complementarity if one exists. On the other hand, if the primal feasibility is reduced too slowly, then the algorithm converges to a point of minimal complementarity; if the primal feasibility is reduced too quickly and the set of Lagrange multipliers is unbounded, then the norm of the Lagrange multiplier tends to infinity. Our theory has important implications for the design of IPMs. Specifically, we show that IPOPT, an algorithm that does not carefully control primal feasibility has practical issues with the dual multipliers values growing to unnecessarily large values. Conversely, the one-phase IPM of O. Hinder and Y. Ye [“A one-phase interior point method for nonconvex optimization”, Preprint, arXiv:1801.03072], an algorithm that controls primal feasibility as our theory suggests, has no such issue.
MSC:
| 90C25 | Convex programming |
| 90C30 | Nonlinear programming |
| 90C46 | Optimality conditions and duality in mathematical programming |
| 90C51 | Interior-point methods |
Keywords:
interior point methods; Lagrange multipliers; complementarity; nonlinear optimization; convex optimizationReferences:
| [1] | Altman, A.; Gondzio, J., Regularized symmetric indefinite systems in interior point methods for linear and quadratic optimization, Optim. Methods Softw., 11, 1-4, 275-302 (1999) · Zbl 0957.90101 · doi:10.1080/10556789908805754 |
| [2] | Andersen, ED; Andersen, KD, The mosek interior point optimizer for linear programming: an implementation of the homogeneous algorithm, High Perform. Optim., 33, 197-232 (2000) · Zbl 1028.90022 · doi:10.1007/978-1-4757-3216-0_8 |
| [3] | Andersen, ED; Ye, Y., A computational study of the homogeneous algorithm for large-scale convex optimization, Comput. Optim. Appl., 10, 3, 243-269 (1998) · Zbl 0914.90212 · doi:10.1023/A:1018369223322 |
| [4] | Andersen, ED; Ye, Y., On a homogeneous algorithm for the monotone complementarity problem, Math. Program., 84, 2, 375-399 (1999) · Zbl 0972.90078 · doi:10.1007/s101070050027 |
| [5] | Andreani, R.; Haeser, G.; Schuverdt, ML; Silva, PJS, Two new weak constraint qualifications and applications, SIAM J. Optim., 22, 1109-1135 (2012) · Zbl 1302.90244 · doi:10.1137/110843939 |
| [6] | Andreani, R.; Haeser, G.; Schuverdt, ML; Silva, PJS, A relaxed constant positive linear dependence constraint qualification and applications, Math. Program., 135, 255-273 (2012) · Zbl 1262.90162 · doi:10.1007/s10107-011-0456-0 |
| [7] | Andreani, R.; Martínez, JM; Ramos, A.; Silva, PJS, A cone-continuity constraint qualification and algorithmic consequences, SIAM J. Optim., 26, 1, 96-110 (2016) · Zbl 1329.90162 · doi:10.1137/15M1008488 |
| [8] | Andreani, R.; Martínez, JM; Ramos, A.; Silva, PJS, Strict constraint qualifications and sequential optimality conditions for constrained optimization, Math. Oper. Res. (2018) · Zbl 1516.90091 · doi:10.1287/moor.2017.0879 |
| [9] | Andreani, R.; Martínez, JM; Svaiter, BF, A new sequential optimality condition for constrained optimization and algorithmic consequences, SIAM J. Optim., 20, 6, 3533-3554 (2010) · Zbl 1217.90148 · doi:10.1137/090777189 |
| [10] | Andreani, R.; Haeser, G.; Martínez, JM, On sequential optimality conditions for smooth constrained optimization, Optimization, 60, 5, 627-641 (2011) · Zbl 1225.90123 · doi:10.1080/02331930903578700 |
| [11] | Bazaraa, MS; Sherali, HD; Shetty, CM, Practical methods of optimization: theory and algorithms (2006), Hoboken, New Jersey: Wiley, Hoboken, New Jersey · Zbl 1140.90040 |
| [12] | Benson, H.Y., Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: Complementarity constraints. Operations Res. Financ. Eng. pp. 1-20 (2002) · Zbl 1022.90017 |
| [13] | Burgschweiger, J.; Gnädig, B.; Steinbach, MC, Optimization models for operative planning in drinking water networks, Optim. Eng., 10, 1, 43-73 (2009) · Zbl 1273.76072 · doi:10.1007/s11081-008-9040-8 |
| [14] | Byrd, RH; Gilbert, JC; Nocedal, J., A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 1, 149-185 (2000) · Zbl 1033.90152 · doi:10.1007/PL00011391 |
| [15] | Chen, L.; Goldfarb, D., Interior-point \(\ell_2\)-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108, 1, 1-36 (2006) · Zbl 1142.90498 · doi:10.1007/s10107-005-0701-5 |
| [16] | Debreu, G., Definite and semidefinite quadratic forms, Econometrica (pre-1986), 20, 2, 295 (1952) · Zbl 0046.24401 · doi:10.2307/1907852 |
| [17] | Dunning, I.; Huchette, J.; Lubin, M., Jump: a modeling language for mathematical optimization, SIAM Rev., 59, 2, 295-320 (2017) · Zbl 1368.90002 · doi:10.1137/15M1020575 |
| [18] | El-Bakry, AS; Tapia, RA; Tsuchiya, T.; Zhang, Y., On the formulation and theory of the newton interior-point method for nonlinear programming, J. Optim. Theory Appl., 89, 3, 507-541 (1996) · Zbl 0851.90115 · doi:10.1007/BF02275347 |
| [19] | Gauvin, J., A necessary and sufficient regularity condition to have bounded multipliers in nonconvex programming, Math. Program., 12, 136-138 (1977) · Zbl 0354.90075 · doi:10.1007/BF01593777 |
| [20] | Giorgi, G.; Jiménez, B.; Novo, V., Approximate Karush-Kuhn-Tucker condition in multiobjective optimization, J. Optim. Theory Appl., 171, 1, 70-89 (2016) · Zbl 1351.90144 · doi:10.1007/s10957-016-0986-y |
| [21] | Gondzio, J., Matrix-free interior point method, Comput. Optim. Appl., 51, 2, 457-480 (2012) · Zbl 1241.90179 · doi:10.1007/s10589-010-9361-3 |
| [22] | Güler, O.; Ye, Y., Convergence behavior of interior-point algorithms, Math. Program., 60, 1, 215-228 (1993) · Zbl 0803.90087 · doi:10.1007/BF01580610 |
| [23] | Haeser, G., A second-order optimality condition with first- and second-order complementarity associated with global convergence of algorithms, Comput. Optim. Appl., 70, 2, 615-639 (2018) · Zbl 1391.90636 · doi:10.1007/s10589-018-0005-3 |
| [24] | Haeser, G.; Schuverdt, ML, On approximate KKT condition and its extension to continuous variational inequalities, J. Optim. Theory Appl., 149, 3, 528-539 (2011) · Zbl 1220.90130 · doi:10.1007/s10957-011-9802-x |
| [25] | Hager, WW; Mico-Umutesi, D., Error estimation in nonlinear optimization, J. Global Optim., 59, 327-341 (2014) · Zbl 1325.90088 · doi:10.1007/s10898-014-0186-y |
| [26] | Hinder, O., Ye, Y.: A one-phase interior point method for nonconvex optimization (2018) . arXiv preprint arXiv:1801.03072 |
| [27] | Jeyakumar, V.; Lee, GM; Dinh, N., New sequential lagrange multiplier conditions characterizing optimality without constraint qualification for convex programs, SIAM J. Optim., 14, 2, 534-547 (2003) · Zbl 1046.90059 · doi:10.1137/S1052623402417699 |
| [28] | Leyffer, S.; López-Calva, G.; Nocedal, J., Interior methods for mathematical programs with complementarity constraints, SIAM J. Optim., 17, 1, 52-77 (2006) · Zbl 1112.90095 · doi:10.1137/040621065 |
| [29] | Lustig, IJ, Feasibility issues in a primal-dual interior-point method for linear programming, Math. Program., 49, 1-3, 145-162 (1990) · Zbl 0726.90050 · doi:10.1007/BF01588785 |
| [30] | Lustig, IJ; Marsten, RE; Shanno, DF, Interior point methods for linear programming: computational state of the art, ORSA J. Comput., 6, 1, 1-14 (1994) · Zbl 0798.90100 · doi:10.1287/ijoc.6.1.1 |
| [31] | McLinden, L., An analogue of Moreau’s proximation theorem, with application to the nonlinear complementarity problem, Pac. J. Math., 88, 1, 101-161 (1980) · Zbl 0403.90081 · doi:10.2140/pjm.1980.88.101 |
| [32] | Megiddo, N.: Pathways to the optimal set in linear programming. In: Progress in Mathematical Programming. Springer, pp. 131-158 (1989) · Zbl 0687.90056 |
| [33] | Mehrotra, S., On the implementation of a primal-dual interior point method, SIAM J. Optim., 2, 4, 575-601 (1992) · Zbl 0773.90047 · doi:10.1137/0802028 |
| [34] | Mizuno, S.; Todd, MJ; Ye, Y., A surface of analytic centers and primal-dual infeasible-interior-point algorithms for linear programming, Math. Oper. Res., 20, 1, 135-162 (1995) · Zbl 0834.90088 · doi:10.1287/moor.20.1.135 |
| [35] | Nesterov, Y.; Polyak, BT, Cubic regularization of newton method and its global performance, Math. Program., 108, 1, 177-205 (2006) · Zbl 1142.90500 · doi:10.1007/s10107-006-0706-8 |
| [36] | Nocedal, J.; Wright, S., Numer. Optim. (2006), Berlin: Springer, Berlin |
| [37] | Qi, L.; Wei, Z., On the constant positive linear dependence conditions and its application to SQP methods, SIAM J. Optim., 10, 963-981 (2000) · Zbl 0999.90037 · doi:10.1137/S1052623497326629 |
| [38] | Rockafellar, RT; Wets R, J-B, Variational Analysis (1998), Berlin: Springer, Berlin · Zbl 0888.49001 · doi:10.1007/978-3-642-02431-3 |
| [39] | Sonnevend, G.: An “analytical centre” for polyhedrons and new classes of global algorithms for linear (smooth, convex) programming. In: System Modelling And Optimization. Springer, pp. 866-875 (1986) · Zbl 0602.90106 |
| [40] | Vicente, LN; Wright, SJ, Local convergence of a primal-dual method for degenerate nonlinear programming, Comput. Optim. Appl., 22, 3, 311-328 (2002) · Zbl 1039.90093 · doi:10.1023/A:1019798502851 |
| [41] | Wächter, A.; Biegler, LT, Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 16, 1, 1-31 (2005) · Zbl 1114.90128 · doi:10.1137/S1052623403426556 |
| [42] | Wächter, A.; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 1, 25-57 (2006) · Zbl 1134.90542 · doi:10.1007/s10107-004-0559-y |
| [43] | Ye, Y.; Anstreicher, K., On quadratic and \({O}(\sqrt{n}{L})\) convergence of a predictor-corrector algorithm for LCP, Math. Program., 62, 1-3, 537-551 (1993) · Zbl 0799.90111 · doi:10.1007/BF01585182 |
| [44] | Ye, Y.; Todd, MJ; Mizuno, S., An \({O}(\sqrt{n}{L})\)-iteration homogeneous and self-dual linear programming algorithm, Math. Oper. Res., 19, 1, 53-67 (1994) · Zbl 0799.90087 · doi:10.1287/moor.19.1.53 |
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.
