×

Numerical comparison of augmented Lagrangian algorithms for nonconvex problems. (English) Zbl 1101.90066

Summary: Augmented Lagrangian algorithms are very popular tools for solving nonlinear programming problems. At each outer iteration of these methods a simpler optimization problem is solved, for which efficient algorithms can be used, especially when the problems are large. The most famous Augmented Lagrangian algorithm for minimization with inequality constraints is known as Powell-Hestenes-Rockafellar (PHR) method. The main drawback of PHR is that the objective function of the subproblems is not twice continuously differentiable. This is the main motivation for the introduction of many alternative Augmented Lagrangian methods. Most of them have interesting interpretations as proximal point methods for solving the dual problem, when the original nonlinear programming problem is convex. In this paper a numerical comparison between many of these methods is performed using all the suitable problems of the CUTE collection.

MSC:

90C30 Nonlinear programming
90C26 Nonconvex programming, global optimization

Software:

SPG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] R.R. Allran and S.E.J. Johnsen, ”An algorithm for solving nonlinear programming problems subject to nonlinear inequality constraints,” The Computer Journal, vol. 13, pp. 171–177, 1970. · Zbl 0191.17104 · doi:10.1093/comjnl/13.2.171
[2] A. Auslender, M. Teboulle, and S. Ben-Tiba, ”Interior proximal and multiplier methods based on second order homogeneous kernels,” Mathematics of Operations Research, vol. 24, pp. 645–668, 1999. · Zbl 1039.90518 · doi:10.1287/moor.24.3.645
[3] A. Ben Tal, I. Yuzefovich, and M. Zibulevsky, ”Penalty/barrier multiplier methods for minimax and constrained smooth convex programs,” Research Report 9/92, Optimization Laboratory, Faculty of Industrial Engineering Management, Technion, Haifa, Israel, 1992.
[4] A. Ben-Tal and M. Zibulevsky, ”Penalty/barrier multiplier methods for convex programming problems,” SIAM Journal on Optimization, vol. 7, pp. 347–366, 1997. · Zbl 0872.90068 · doi:10.1137/S1052623493259215
[5] D.P. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Academic Press: New York, 1982. · Zbl 0572.90067
[6] D.P. Bertsekas, Nonlinear Programming, 2nd edition, Athena Scientific: Belmont, MA, 1999.
[7] E.G. Birgin and J.M. Martínez, ”Large-scale active-set box-constrained optimization method with spectral projected gradients,” Computational Optimization and Applications, vol. 23, pp. 101–125, 2002. · Zbl 1031.90012 · doi:10.1023/A:1019928808826
[8] E.G. Birgin, J.M. Martínez, and M. Raydan, ”Nonmonotone spectral projected gradient methods on convex sets,” SIAM Journal on Optimization, vol. 10, pp. 1196–1211, 2000. · Zbl 1047.90077 · doi:10.1137/S1052623497330963
[9] E.G. Birgin, J.M. Martínez, and M. Raydan, ”Algorithm 813: SPG–Software for convex-constrained optimization,” ACM Transactions on Mathematical Software, vol. 27, pp. 340–349, 2001. · Zbl 1070.65547 · doi:10.1145/502800.502803
[10] R.A. Castillo, ”Métodos de Lagrangiano Aumentado usando penalidades general-izadas para programação não linear,” Tese de Doutorado, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil, 1998.
[11] A.R. Conn, N.I.M. Gould, and Ph.L. Toint, ”A globally convergent Augmented Lagrangian algorithm for optimization with general constraints and simple bounds,” SIAM Journal on Numerical Analysis, vol. 28, pp. 545–572, 1991. · Zbl 0724.65067 · doi:10.1137/0728030
[12] E.D. Dolan and J.J. Moré, ”Benchmarking optimization software with performance profiles,” Mathematical Programming, vol. 91, pp. 201–213, 2002. · Zbl 1049.90004 · doi:10.1007/s101070100263
[13] Z. Dostál, A. Friedlander, and S.A. Santos, ”Augmented Lagrangians with adaptive precision control for quadratic programming with equality constraints,” Computational Optimization and Applications, vol. 14, pp. 37–53, 1999. · Zbl 0958.90064 · doi:10.1023/A:1008700911674
[14] Z. Dostál, A. Friedlander, and S.A. Santos, ”Augmented Lagrangians with adaptive precision control for quadratic programming with simple bounds and equality constraints,” SIAM Journal on Optimization, vol. 13, pp. 1120–1140, 2003. · Zbl 1043.65076 · doi:10.1137/S1052623499362573
[15] Z. Dostál, F.A.M. Gomes, and S.A. Santos, ”Solution of contact problems by FETI domain decomposition with natural coarse space projection,” Computational Method in Applied Mechanics and Engineering, vol. 190, pp. 1611–1627, 2002. · Zbl 1005.74064 · doi:10.1016/S0045-7825(00)00180-8
[16] R. Fletcher, Practical Methods for Optimization, John Wiley and Sons: Chichester, 1987. · Zbl 0905.65002
[17] C.C. Gonzaga and R.A. Castillo, ”A nonlinear programming algorithm based on non-coercive penalty functions,” Mathematical Programming, vol. 96, pp. 87–101, 2003. · Zbl 1023.90061 · doi:10.1007/s10107-002-0332-z
[18] W.W. Hager, ”Dual techniques for constrained optimization,” Journal of Optimization Theory and Applications, vol. 55, pp. 33–72, 1987. · Zbl 0622.90075 · doi:10.1007/BF00939044
[19] W.W. Hager, ”Analysis and implementation of a dual algorithm for constrained optimization,” Journal of Optimization Theory and Applications, vol. 79, pp. 427–462, 1993. · Zbl 0797.90092 · doi:10.1007/BF00940552
[20] M.R. Hestenes, ”Multiplier and gradient methods,” Journal of Optimization Theory and Applications, vol 4, pp. 303–320, 1969. · Zbl 0174.20705 · doi:10.1007/BF00927673
[21] C. Humes and P.S. Silva, ”Strict convex regularizations, proximal points and Augmented Lagrangians,” RAIRO Operations Research, vol. 34, pp. 283–303, 2000. · Zbl 1029.90069 · doi:10.1051/ro:2000102
[22] A.N. Iusem, ”Augmented Lagrangian methods and proximal point methods for convex optimization,” Investigacion Operativa, vol. 8, pp. 11–50, 1999.
[23] K.C. Kiwiel, ”Proximal minimization methods with generalized Bregman functions,” SIAM Journal on Control and Optimization, vol. 35, pp. 1142–1168, 1997. · Zbl 0890.65061 · doi:10.1137/S0363012995281742
[24] B.W. Kort and D.P. Bertsekas, ”Multiplier methods for convex programming,” in Proceeding of the IEEE Decision and Control Conference, San Diego, CA, 1973, pp. 260–264.
[25] B.W. Kort and D.P. Bertsekas, ”Combined primal-dual and penalty methods for convex programming,” SIAM Journal on Control and Optimization, vol. 14, pp. 268–294, 1976. · Zbl 0332.90035 · doi:10.1137/0314020
[26] O.L. Mangasarian and S. Fromovitz, ”The Fritz-John necessary optimality conditons in presence of equality and inequality constraints,” Journal of Mathematical Analysis and Applications, vol. 17, pp. 37–47, 1967. · Zbl 0149.16701 · doi:10.1016/0022-247X(67)90163-1
[27] L.C. Matioli, ”Uma nova metodologia para construção de funções de penalização para algoritoms de Lagrangiano Aumentado,” Tese de Doutorado, Universidade Federal de Santa Catarina, Florianópolis, Brasil, 2001.
[28] F.H. Murphy, ”A class of exponential penalty functions,” SIAM Journal on Control, vol. 12, pp. 679–687, 1974. · Zbl 0289.90038 · doi:10.1137/0312052
[29] H. Nakayama, H. Samaya, and Y. Sawaragi, ”A generalized Lagrangian function and multiplier method,” Journal of Optimization Theory and Applications, vol. 17, pp. 211–227, 1975. · Zbl 0298.49016 · doi:10.1007/BF00933876
[30] J. Nocedal and S.J. Wright, Numerical Optimization, Springer Verlag: New York, 1999. · Zbl 0930.65067
[31] R.A. Polyak, ”Log-sigmoid multiplier method in constrained optimization,” Annals of Operation Research, vol. 101, pp. 427–460, 2001. · Zbl 0996.90088 · doi:10.1023/A:1010938423538
[32] R. Polyak and M. Teboulle, ”Nonliner rescaling and proximal-like methods in convex optimization,” Mathematical Programming, vol. 76, pp. 265–284, 1997. · Zbl 0882.90106
[33] M.J.D. Powell, ”A method for nonlinear constraints in minimization problems,” in Optimization, R. Fletcher (Ed.), Academic Press, New York, NY, 1969, pp. 283–298. · Zbl 0194.47701
[34] R.T. Rockafellar, ”The multiplier method of Hestenes and Powell applied to convex programming,” Journal of Optimization Theory and Applications, vol. 12, pp. 555–562, 1973. · Zbl 0254.90045 · doi:10.1007/BF00934777
[35] P. Tseng and D. Bertseaks, ”On the convergence of the exponential multiplier method for convex programming,” Mathematical Programming, vol. 17, pp. 670–690, 1993.
[36] A.E. Xavier, ”Penalização hiperbolica,” Tese de Doutorado, COPPE, Universidade Federal do Rio de Janeiro, Rio de Janeiro, Brasil, 1992.
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.