Artículos de revistas
On The Behaviour Of Constrained Optimization Methods When Lagrange Multipliers Do Not Exist
Registro en:
Optimization Methods And Software. , v. 29, n. 3, p. 646 - 657, 2014.
10556788
10.1080/10556788.2013.841692
2-s2.0-84890439972
Autor
Andreani R.
Martinez J.M.
Santos L.T.
Svaiter B.F.
Institución
Resumen
Sequential optimality conditions are related to stopping criteria for nonlinear programming algorithms. Local minimizers of continuous optimization problems satisfy these conditions without constraint qualifications. It is interesting to discover whether well-known optimization algorithms generate primal-dual sequences that allow one to detect that a sequential optimality condition holds. When this is the case, the algorithm stops with a correct diagnostic of success (convergence). Otherwise, closeness to a minimizer is not detected and the algorithm ignores that a satisfactory solution has been found. In this paper it will be shown that a straightforward version of the Newton-Lagrange (sequential quadratic programming) method fails to generate iterates for which a sequential optimality condition is satisfied. On the other hand, a Newtonian penalty-barrier Lagrangian method guarantees that the appropriate stopping criterion eventually holds. © 2013 © 2013 Taylor & Francis. 29 3 646 657 Andreani, R., Martínez, J.M., Schuverdt, M.L., On the relation between the constant positive linear dependence condition and quasinormality constraint qualification (2005) J. Optim. Theory Appl, 125, pp. 473-485. , doi: 10.1007/s10957-004-1861-9 Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L., On augmented Lagrangian methods with general lower-level constraints (2007) SIAM J. Optim, 18, pp. 1286-1309. , doi: 10.1137/060654797 Andreani, R., Martínez, J.M., Svaiter, B.F., A new sequential optimality condition for constrained optimization and algorithmic consequences (2010) SIAM J. Optim, 20, pp. 3533-3554. , doi: 10.1137/090777189 Andreani, R., Haeser, G., Martínez, J.M., On sequential optimality conditions for smooth constrained optimization (2011) Optimization, 60, pp. 627-641. , doi: 10.1080/02331930903578700 Andreani, R., Haeser, G., Schuverdt, M.L., Silva, P.J.S., Two new weak constraint qualifications and applications (2012) SIAM J. Optim, 22, pp. 1109-1135. , doi: 10.1137/110843939 Andreani, R., Haeser, G., Schuverdt, M.L., Silva, P.J.S., A relaxed constant positive linear dependence constraint qualification and applications (2012) Math. Program, 135, pp. 255-273. , doi: 10.1007/s10107-011-0456-0 Arutyunov, A.V., (2000) Optimality Conditions - Abnormal and Degenerate Problems, , Kluwer, Dordrecht Bartholomew-Biggs, M.C., Recursive quadratic programming methods based on the augmented Lagrangian (1987) Math. Program. Study, 31, pp. 21-41. , doi: 10.1007/BFb0121177 Benson, H.Y., Shanno, D.F., Vanderbei, R.J., Interior-point methods for nonconvex nonlinear programming - Filter methods and merit functions (2002) Comput. Optim. Appl, 23, pp. 257-272. , doi: 10.1023/A:1020533003783 Bertsekas, D.P., (1999) Nonlinear Programming, , Athena Scientific, Belmont, MA Bielschowsky, R.H., Gomes, F.A.M., Dynamic control of infeasibility in equality constrained optimization (2008) SIAM J. Optim, 19, pp. 1299-1325. , doi: 10.1137/070679557 Byrd, R.H., Gilbert, J.Ch., Nocedal, J., A trust region method based on interior point techniques for nonlinear programming (2000) Math. Program, 89, pp. 149-185. , doi: 10.1007/PL00011391 Byrd, R.H., Nocedal, J., Waltz, R.A., KNITRO - An integrated package for nonlinear optimization (2006) Large-Scale Nonlinear Optimization, pp. 35-59. , in, G. Di Pillo and M. Roma, eds. Springer, New York Conn, A.R., Gould, N.I.M., Toint, Ph.L., (2000) Trust Region Methods, , MPS/SIAM Series on Optimization, SIAM, Philadelphia, PA Contesse-Becker, L., Extended convergence results for the method of multipliers for non-strictly binding inequality constraints (1993) J. Optim. Theory Appl, 79, pp. 273-310. , doi: 10.1007/BF00940582 Di Pillo, G., Lucidi, S., An augmented Lagrangian function with improved exactness properties (2001) SIAM J. Optim, 12, pp. 376-406. , doi: 10.1137/S1052623497321894 Di Pillo, G., Liuzzi, G., Lucidi, S., Palagi, L., An exact augmented Lagrangian function for nonlinear programming with two-sided constraints (2003) Comput. Optim. Appl, 25, pp. 57-83. , doi: 10.1023/A:1022948903451 Di Pillo, G., Liuzzi, G., Lucidi, S., Palagi, L., A truncated Newton method in an augmented Lagrangian framework for nonlinear programming (2010) Comput. Optim. Appl, 45, pp. 311-352. , doi: 10.1007/s10589-008-9216-3 Di Pillo, G., Liuzzi, G., Lucidi, S., An exact penalty-Lagrangian approach for large-scale nonlinear programming (2011) Optimization, 60, pp. 223-252. , doi: 10.1080/02331934.2010.505964 Fan, J.Y., Yuan, Y.X., On the quadratic convergence of the Levenberg-Marquardt method without nonsingularity assumption (2005) Computing, 34, pp. 23-39. , doi: 10.1007/s00607-004-0083-1 Fernández, D., A quasi-Newton strategy for the sSQP method for variational inequality and optimization problems (2011) Math. Program, pp. 199-223. , doi: 10.1007/s10107-011-0493-8 Fernández, D., Solodov, M., Stabilized sequential quadratic programming for optimization and a stabilized Newton-Type method for variational problems (2010) Math. Program, 125, pp. 47-73. , doi: 10.1007/s10107-008-0255-4 Fletcher, R., (1987) Practical Methods of Optimization, , Academic Press, London Fletcher, R., Leyffer, S., Toint, Ph.L., On the global convergence of a filter-SQP algorithm (2002) SIAM J. Optim, 13, pp. 44-59. , doi: 10.1137/S105262340038081X Fletcher, R., Gould, N.I.M., Leyffer, S., Toint, Ph.L., Wächter, A., Global convergence of trust-region SQP-filter algorithms for general nonlinear programming (2002) SIAM J. Optim, 13, pp. 635-659. , doi: 10.1137/S1052623499357258 Giannessi, F., (2005) Separation of Sets and Optimality Conditions, , Springer, New York Gould, N.I.M., Toint, Ph.L., Nonlinear programming without a penalty function or a filter (2010) Math. Program, 122, pp. 155-196. , doi: 10.1007/s10107-008-0244-7 Gratton, S., Mouffe, M., Toint, Ph.L., Stopping rules and backward error analysis for bound-constrained optimization (2011) Numer. Math, 119, pp. 163-187. , doi: 10.1007/s00211-011-0376-1 Izmailov, A., Solodov, M., Stabilized SQP revisited (2010) Math. Program, pp. 93-120. , doi: 10.1007/s10107-010-0413-3 Liu, X.W., Yuan, Y.X., A null-space primal-dual interior-point algorithm for nonlinear optimization with nice convergence properties (2010) Math. Program, 125, pp. 163-193. , doi: 10.1007/s10107-009-0272-y Liu, X.W., Yuan, Y.X., A sequential quadratic programming method without a penalty function or a filter for nonlinear equality constrained optimization (2011) SIAM J. Optim, 21, pp. 545-571. , doi: 10.1137/080739884 Luksan, L., Matonoha, C., Vlcek, J., Interior point methods for large-scale nonlinear programming (2003) Optim. Methods Softw, 20, pp. 569-582. , doi: 10.1080/10556780500140508 Luksan, L., Matonoha, C., Vlcek, J., Algorithm 896: LSA: Algorithms for large-scale optimization (2009) ACM Trans. Math. Softw, 36, pp. 161-1629. , doi: 10.1145/1527286.1527290 Martínez, J.M., Santos, L.T., Some new theoretical results on recursive quadratic programming algorithms (1998) J. Optim. Theory Appl, 97, pp. 435-454. , doi: 10.1023/A:1022686919295 Martínez, J.M., Svaiter, B.F., A practical optimality condition without constraint qualifications for nonlinear programming (2003) J. Optim. Theory Appl, 118, pp. 117-133. , doi: 10.1023/A:1024791525441 Nocedal, J., Wright, S.J., (1999) Numerical Optimization, , Springer, New York Qi, L., Wei, Z., On the constant positive linear dependence condition and its application to SQP methods (2000) SIAM J. Optim, 10, pp. 963-981. , doi: 10.1137/S1052623497326629 Schiela, A., Guenther, A., An interior point algorithm with inexact step computation in function space for state constrained optimal control (2011) Numer. Math, 119, pp. 373-407. , doi: 10.1007/s00211-011-0381-4 Shen, C., Xue, W., Pu, D., A filter SQP algorithm without a feasibility restoration phase (2009) Comput. Appl. Math, 28, pp. 167-194. , doi: 10.1590/S1807-03022009000200003 Shen, C., Leyffer, S., Fletcher, R., Nonmonotone filter method for nonlinear optimization (2012) Comput. Optim. Appl, 52, pp. 583-607. , doi: 10.1007/s10589-011-9430-2 Wächter, A., Biegler, L.T., On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming (2006) Math. Program, 106, pp. 25-57. , doi: 10.1007/s10107-004-0559-y Wright, S.J., Superlinear convergence of a stabilized SQP method to a degenerate solution (1998) Comput. Optim. Appl, 11, pp. 253-275. , doi: 10.1023/A:1018665102534 Wright, S.J., Modifying SQP for degenerate problems (2002) SIAM J. Optim, 13, pp. 470-497. , doi: 10.1137/S1052623498333731