Abstract
Practical Nonlinear Programming algorithms may converge to infeasible points. It is sensible to detect this situation as quickly as possible, in order to have time to change initial approximations and parameters, with the aim of obtaining convergence to acceptable solutions in further runs. In this paper, a recently introduced Augmented Lagrangian algorithm is modified in such a way that the probability of quick detection of asymptotic infeasibility is enhanced. The modified algorithm preserves the property of convergence to stationary points of the sum of squares of infeasibilities without harming the convergence to KKT points in feasible cases.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Andreani, R., Birgin, E.G., Martínez, J.M., Schuverdt, M.L.: On augmented lagrangian methods with general lower-level constraints. SIAM J. Optim. 18, 1286–1309 (2007)
Andreani, R., Haeser, G., Martínez, J.M.: On sequential optimality conditions for smooth constrained optimization. Optimization 60, 627–641 (2011)
Andreani, R., Haeser, G., Schuverdt, M. L., Silva, P. J. S.: A relaxed constant positive linear dependence constraint qualification and applications. Math. Program. (2011). doi:10.1007/s10107-011-0456-0
Andreani, R., Haeser, G., Schuverdt, M.L., Silva, P.J.S.: Two new constraint qualifications and applications. Technical report, available in Optimization online (2011)
Andreani, R., Martínez, J.M., Schuverdt, M.L.: On the relation between the constant positive linear dependence condition and quasinormality constraint qualification. J. Optim. Theory Appl. 125, 473–485 (2005)
Andreani, R., Martínez, J.M., Svaiter, B.F.: A new sequential optimality condition for constrained optimization and algorithmic consequences. SIAM J. Optim. 20, 3533–3554 (2010)
Benson, H.Y., Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: filter methods and merit functions. Comput. Optim. Appl. 23, 257–272 (2002)
Bertsekas, D.P.: Nonlinear Programming, 2nd edn. Athena Scientific, Belmont (1999)
Birgin, E.G., Martínez, J.M.: Improving ultimate convergence of an Augmented Lagrangian method. Optim Methods Softw 23, 177–195 (2008)
Birgin, E.G., Martínez J.M.: Large-scale active-set box-constrained optimization method with spectral projected gradients. Comput. Optim. Appl. 23, 101–125 (2002)
Byrd, R.H., Curtis, F.E. Nocedal, J.: Infeasibility detection and SQP methods for nonlinear optimization. SIAM J. Optim. 20, 2281–2299 (2010)
Byrd, R.H., Gilbert, J.Ch., Nocedal, J.: A trust region method based on interior point techniques for nonlinear programming. Math. Program. 89, 149185 (2000)
Byrd, R.H., Nocedal, J., Waltz, R.A.: KNITRO: an integrated package for nonlinear optimization. In: Di Pillo, G., Roma, M. (eds.) Large-Scale Nonlinear Optimization, pp. 3559. Springer, New York (2006)
Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust region methods. In: MPS/SIAM Series on Optimization. SIAM, Philadelphia (2000)
Dostál, Z.: Optimal Quadratic Programming Algorithms. Springer, New York (2009)
Dostál, Z., Friedlander, A., Santos, S.A.: Augmented Lagrangians with adaptive precision control for quadratic programming with simple bounds and equality constraints. SIAM J. Optim. 13, 1120–1140 (2003)
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. SIAM J. Optim. 13, 635–659 (2002)
Fletcher, R., Leyffer, S.: Nonlinear programming without a penalty function. Math. Program. 91, 239–269 (2002)
Fletcher, R., Leyffer, S., Toint, Ph.L.: On the global convergence of a filter-SQP algorithm. SIAM J. Optim. 13, 4459 (2002)
Hager, W.W.: Analysis and implementation of a dual algorithm for constrained optimization. J. Optim. Theory Appl. 79, 427–462 (1993)
Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969)
Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, New York (1969)
Prudente, L.F.: Augmented Lagrangian approaches in nonlinear programming. Doctoral dissertation, State University of Campinas (in preparation)
Qi, L., Wei, L. Qi, Wei, Z.: On the constant positive linear dependence condition and its application to SQP methods. SIAM J. Optim. 10, 963–981 (2000)
Rockafellar, R.T.: Augmented Lagrange multiplier functions and duality in nonconvex programming. SIAM J. Control Optim. 12, 268–285 (1974)
Shen, C., Xue, W., Pu, D.: A filter SQP algorithm without a feasibility restoration phase. Comput. Appl. Math. 28, 167–194 (2009)
Shen, C., Leyffer, S., Fletcher, R.: A nonmonotone filter method for nonlinear optimization. Comput. Optim. Appl. (2011). 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. Math. Program. 106, 25–57 (2006)
Author information
Authors and Affiliations
Corresponding author
Additional information
This author was supported by PRONEX-Optimization (PRONEX—CNPq/FAPERJ E-26/171.164/2003—APQ1), FAPESP (Grant 06/53768-0) and CNPq.
Rights and permissions
About this article
Cite this article
Martínez, J.M., Prudente, L.d.F. Handling infeasibility in a large-scale nonlinear optimization algorithm. Numer Algor 60, 263–277 (2012). https://doi.org/10.1007/s11075-012-9561-2
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11075-012-9561-2