An adaptive augmented Lagrangian method for large-scale constrained optimization

详细信息    查看全文

• 作者：Frank E. Curtis ; Hao Jiang ; Daniel P. Robinson
• 关键词：Nonlinear optimization ; Nonconvex optimization ; Large ; scale optimization ; Augmented Lagrangians ; Matrix ; free methods ; Steering methods ; 49M05 ; 49M15 ; 49M29 ; 49M37 ; 65K05 ; 65K10 ; 65K15 ; 90C06 ; 90C30 ; 93B40
• 刊名：Mathematical Programming
• 出版年：2015
• 出版时间：August 2015
• 年：2015
• 卷：152
• 期：1-2
• 页码：201-245
• 全文大小：1,170 KB
• 参考文献：1.Andreani, R., Birgin, E.G., Mart铆nez, J.M., Schuverdt, M.L.: Augmented Lagrangian methods under the constant positive linear dependence constraint qualification. Math. Program. 111, 5鈥?2 (2008)MathSciNet View Article MATH
  2.Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Computer Science and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York (1982)
  3.Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, Belmont, Massachusetts (1996)
  4.Birgin, E.G., Mart铆nez, J.M.: Augmented Lagrangian method with nonmonotone penalty parameters for constrained optimization. Comput. Optim. Appl. 51, 941鈥?65 (2012)MathSciNet View Article MATH
  5.Boggs, P.T., Tolle, J.W.: A family of descent functions for constrained optimization. SIAM J. Numer. Anal. 21, 1146鈥?161 (1984)MathSciNet View Article MATH
  6.Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn 3, 1鈥?22 (2011)View Article MATH
  7.Byrd, R.H., Lopez-Calva, G., Nocedal, J.: A line search exact penalty method using steering rules. Math Program 133, 39鈥?3 (2012)MathSciNet View Article MATH
  8.Byrd, R.H., Nocedal, J., Waltz, R.A.: Steering exact penalty methods for nonlinear programming. Optim. Methods Softw. 23, 197鈥?13 (2008)MathSciNet View Article MATH
  9.Conn, A.R., Gould, N.I.M., Toint, P.L.: A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28, 545鈥?72 (1991)MathSciNet View Article MATH
  10.Conn, A.R., Gould, N.I.M., Toint, P.L.: LANCELOT : A Fortran package for large-scale nonlinear optimization (Release A). Lecture Notes in Computation Mathematics, vol. 17. Springer, Berlin, Heidelberg, New York, London, Paris and Tokyo (1992)
  11.Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2000)View Article MATH
  12.Davidson, K.R., Donsig, A.P.: Real analysis and applications. Undergraduate Texts in Mathematics. Springer, New York (2010). Theory in practiceView Article MATH
  13.Dembo, R.S., Eisenstat, S.C., Steihaug, T.: Inexact Newton methods. SIAM J. Numer. Anal. 19, 400鈥?08 (1982)MathSciNet View Article MATH
  14.Dennis Jr, J., El-Alem, M., Maciel, M.C.: A global convergence theory for general trust-region-based algorithms for equality constrained optimization. SIAM J. Optim. 7, 177鈥?07 (1997)MathSciNet View Article MATH
  15.DiPillo, G., Grippo, L.: A new class of augmented Lagrangians in nonlinear programming. SIAM J. Control Optim. 17, 618鈥?28 (1979)MathSciNet View Article
  16.Dolan, E.D., Mor茅, J.J.: Benchmarking Optimization Software with COPS, Technical Memorandum ANL/MCS-TM-246. Argonne National Laboratory, Argonne, IL (2000)
  17.El-Alem, M.: A global convergence theory for dennis, el-alem, and maciel鈥檚 class of trust-region algorithms for constrained optimization without assuming regularity. SIAM J. Optim. 9, 965鈥?90 (1999)MathSciNet View Article MATH
  18.Fern谩ndez, D., Solodov, M.: Local convergence of exact and inexact augmented Lagrangian methods under the second-order sufficiency condition. IMPA, preprint A677 (2010)
  19.Fern谩ndez, D., Solodov, M.: Stabilized sequential quadratic programming for optimization and a stabilized Newton-type method for variational problems. Math. Program. 125, 47鈥?3 (2010)MathSciNet View Article MATH
  20.Fletcher, R.: A class of methods for nonlinear programming with termination and convergence properties. In: Abadie, J. (ed.) Integer and Nonlinear Programming, pp. 157鈥?75. North-Holland, The Netherlands (1970)
  21.Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximations. Comput. Math. Appl. 2, 17鈥?0 (1976)View Article MATH
  22.Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99鈥?31 (2005)MathSciNet View Article MATH
  23.Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Some Theoretical Properties of an Augmented Lagrangian Merit Function, Report SOL 86鈥?R. Stanford University, Stanford, CA (1986)
  24.Gill, P.E., Robinson, D.P.: A Globally Convergent Stabilized SQP Method, Numerical Analysis Report 12鈥?2. University of California, San Diego, La Jolla, CA (2012)
  25.Glowinski, R., Marroco, A.: Sur l鈥橝pproximation, par Elements Finis d鈥橭rdre Un, el la Resolution, par Penalisation-Dualit茅, d鈥檜ne Classe de Probl猫mes de Dirichlet Nonlineares. Revue Fran莽aise d鈥橝utomatique, Informatique et Recherche Op茅rationelle 9, 41鈥?6 (1975)MATH
  26.Gould, N.I.M., Orban, D., Toint, P.L.: CUTEr and SifDec: A constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29, 373鈥?94 (2003)MathSciNet View Article MATH
  27.Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303鈥?20 (1969)MathSciNet View Article MATH
  28.Hock, W., Schittkowski, K.: Test Examples for Nonlinear Programming Codes. Lecture Notes in Economics and Mathematical Systems, vol. 187. Springer, Berlin, Heidelberg and New York (1981)
  29.ILOG Inc, ILOG CPLEX: High-performance software for mathematical programming and optimization, 2006. See http://鈥媤ww.鈥媔log.鈥媍om/鈥媝roducts/鈥媍plex/鈥?/span>
  30.Izmailov, A.F., Solodov, M.V.: On attraction of linearly constrained Lagrangian methods and of stabilized and quasi-Newton SQP methods to critical multipliers. Math. Program. 126, 231鈥?57 (2011)MathSciNet View Article
  31.Izmailov, A.F., Solodov, M.V.: Stabilized SQP revisited. Math. Program. 133, 93鈥?20 (2012)MathSciNet View Article MATH
  32.Ko膷vara, M., Stingl, M., PENNON: A generalized augmented Lagrangian method for semidefinite programming, in High performance algorithms and software for nonlinear optimization (Erice: vol. 82 of Appl. Optim., Kluwer Acad. Publ. Norwell, MA 2003, pp. 303鈥?21 (2001)
  33.Li, D.-H., Qi, L.: A stabilized SQP method via linear equations, technical Report AMR00/5. University of New South Wales, Sydney, School of Mathematics (2000)
  34.Mongeau, M., Sartenaer, A.: Automatic decrease of the penalty parameter in exact penalty function methods. Eur. J. Oper. Res. 83(3), 686鈥?99 (1995)
  35.Mor茅, J.J.: Trust regions and projected gradients. In M. Iri and K. Yajima, (eds.) System Modelling and Optimization. vol. 113 of Lecture Notes in Control and Information Sciences, pp. 1鈥?3. Springer, Berlin Heidelberg (1988)
  36.Mostafa, E.-S., Vicente, L., Wright, S.: Numerical behavior of a stabilized SQP method for degenerate NLP problems. In C. Bliek, C. Jermann, and A. Neumaier (eds.) Global Optimization and Constraint Satisfaction, vol. 2861 of Lecture Notes in Computer Science, pp. 123鈥?41. Springer, Berlin/Heidelberg (2003)
  37.Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283鈥?98. Academic Press, London and New York (1969)
  38.Qin, Z., Goldfarb, D., Ma, S.: An alternating direction method for total variation denoising, arXiv, preprint arXiv:鈥?108.鈥?587 (2011)
  39.Toint, P.L.: Nonlinear stepsize control, trust regions and regularizations for unconstrained optimization. Optim. Methods Softw 28, 82鈥?5 (2013)MathSciNet View Article MATH
  40.Wright, S.J.: Superlinear convergence of a stabilized SQP method to a degenerate solution. Comput. Optim. Appl. 11, 253鈥?75 (1998)MathSciNet View Article MATH
  41.Yang, J., Zhang, Y., Yin, W.: A fast alternating direction method for tvl1-l2 signal reconstruction from partial fourier data. IEEE J. Sel. Top. Signal Proces. 4, 288鈥?97 (2010)View Article
  
• 作者单位：Frank E. Curtis (1)
  Hao Jiang (2)
  Daniel P. Robinson (2)
  
  1. Department of Industrial and Systems Engineering, Lehigh University, Bethlehem, PA, USA
  2. Department of Applied Mathematics and Statistics, Johns Hopkins University, Baltimore, MD, USA
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

We propose an augmented Lagrangian algorithm for solving large-scale constrained optimization problems. The novel feature of the algorithm is an adaptive update for the penalty parameter motivated by recently proposed techniques for exact penalty methods. This adaptive updating scheme greatly improves the overall performance of the algorithm without sacrificing the strengths of the core augmented Lagrangian framework, such as its ability to be implemented matrix-free. This is important as this feature of augmented Lagrangian methods is responsible for renewed interests in employing such methods for solving large-scale problems. We provide convergence results from remote starting points and illustrate by a set of numerical experiments that our method outperforms traditional augmented Lagrangian methods in terms of critical performance measures.