×

zbMATH — the first resource for mathematics

A primal-dual augmented Lagrangian. (English) Zbl 1244.90219
Summary: Nonlinearly constrained optimization problems can be solved by minimizing a sequence of simpler unconstrained or linearly constrained subproblems. In this paper, we consider the formulation of subproblems in which the objective function is a generalization of the Hestenes-Powell augmented Lagrangian function. The main feature of the generalized function is that it is minimized with respect to both the primal and the dual variables simultaneously. The benefits of this approach include: (i) the ability to control the quality of the dual variables during the solution of the subproblem; (ii) the availability of improved dual estimates on early termination of the subproblem; and (iii) the ability to regularize the subproblem by imposing explicit bounds on the dual variables. We propose two primal-dual variants of conventional primal methods: a primal-dual bound constrained Lagrangian (pdBCL) method and a primal-dual \(\ell _{1}\) linearly constrained Lagrangian (pd\(\ell _{1}\)LCL) method. Finally, a new sequential quadratic programming (pdSQP) method is proposed that uses the primal-dual augmented Lagrangian as a merit function.

MSC:
90C30 Nonlinear programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bertsekas, D.P.: Constrained optimization and Lagrange multiplier methods. In: Computer Science and Applied Mathematics. Academic Press, New York (1982) · Zbl 0572.90067
[2] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, Belmont (1996) · Zbl 0866.90059
[3] Biggs, M.C.: Constrained minimization using recursive equality quadratic programming. In: Lootsma, F.A. (ed.) Numerical Methods for Nonlinear Optimization, pp. 411–428. Academic Press, London (1972)
[4] Boggs, P.T., Kearsley, A.J., Tolle, J.W.: A global convergence analysis of an algorithm for large-scale nonlinear optimization problems. SIAM J. Optim. 9(4), 833–862 (1999) · Zbl 0986.90078
[5] Boggs, P.T., Tolle, J.W.: A family of descent functions for constrained optimization. SIAM J. Numer. Anal. 21, 1146–1161 (1984) · Zbl 0575.65066
[6] Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numer. 4, 1–51 (1995) · Zbl 0828.65060
[7] Bongartz, I., Conn, A.R., Gould, N.I.M., Toint, Ph.L.: CUTE: Constrained and unconstrained testing environment. ACM Trans. Math. Software 21(1), 123–160 (1995) · Zbl 0886.65058
[8] Byrd, R.H., Tapia, R.A., Zhang, Y.: An SQP augmented Lagrangian BFGS algorithm for constrained optimization. SIAM J. Optim. 20, 210–241 (1992) · Zbl 0773.90065
[9] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: A comprehensive description of LANCELOT. Technical Report 91/10, Département de Mathématique, Facultés Universitaires de Namur (1991)
[10] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28, 545–572 (1991) · Zbl 0724.65067
[11] Conn, A.R., Gould, N.I.M., Toint, Ph.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2000) · Zbl 0958.65071
[12] Curtis, F.E., Nocedal, J.: Flexible penalty functions for nonlinear constrained optimization. IMA J. Numer. Anal. 28, 749–769 (2008) · Zbl 1156.65058
[13] DiPillo, G., Grippo, L.: A new class of augmented Lagrangians in nonlinear programming. SIAM J. Control Optim. 17, 618–628 (1979) · Zbl 0418.90077
[14] Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, New York (1968) · Zbl 0193.18805
[15] Fiacco, A.V., McCormick, G.P.: Nonlinear programming. In: Classics in Applied Mathematics, 2nd edn. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1990). Reprint of the 1968 original · Zbl 0193.18805
[16] Fletcher, R.: A class of methods for nonlinear programming with termination and convergence properties. In: Abadie, J. (ed.) Integer and Nonlinear Programming, pp. 157–175. North-Holland, Amsterdam (1970) · Zbl 0332.90039
[17] Fletcher, R.: Practical Methods of Optimization. Vol. 2: Constrained Optimization. Wiley, Chichester (1981) · Zbl 0474.65043
[18] Fontecilla, R., Steihaug, T., Tapia, R.A.: A convergence theory for a class of quasi-Newton methods for constrained optimization. SIAM J. Numer. Anal. 24, 1133–1151 (1987) · Zbl 0634.65045
[19] Forsgren, A., Gill, P.E.: Primal-dual interior methods for nonconvex nonlinear programming. SIAM J. Optim. 8, 1132–1152 (1998) · Zbl 0915.90236
[20] Forsgren, A., Gill, P.E., Wright, M.H.: Interior methods for nonlinear optimization. SIAM Rev. 44, 525–597 (2002) · Zbl 1028.90060
[21] Forsgren, A., Murray, W.: Newton methods for large-scale linear equality-constrained minimization. SIAM J. Matrix Anal. Appl. 14, 560–587 (1993) · Zbl 0774.65034
[22] Friedlander, M.P., Saunders, M.A.: A globally convergent linearly constrained Lagrangian method for nonlinear optimization. SIAM J. Optim. 15(3), 863–897 (2005) · Zbl 1077.90065
[23] Gertz, E.M., Gill, P.E.: A primal-dual trust-region algorithm for nonlinear programming. Math. Program., Ser. B 100, 49–94 (2004) · Zbl 1146.90514
[24] Gill, P.E., Murray, W., Saunders, M.A.: SNOPT: An SQP algorithm for large-scale constrained optimization. SIAM Rev. 47, 99–131 (2005) · Zbl 1210.90176
[25] Gill, P.E., Murray, W., Saunders, M.A.: User’s guide for SNOPT version 7: Software for large-scale nonlinear programming. Numerical Analysis Report 06-2, Department of Mathematics, University of California, San Diego, La Jolla, CA (2006)
[26] Gill, P.E., Murray, W., Saunders, M.A., Wright, M.H.: Some theoretical properties of an augmented Lagrangian merit function. In: Pardalos, P.M. (ed.) Advances in Optimization and Parallel Computing, pp. 101–128. North Holland, Amsterdam (1992) · Zbl 0814.90094
[27] Gould, N.I.M.: On the accurate determination of search directions for simple differentiable penalty functions. IMA J. Numer. Anal. 6, 357–372 (1986) · Zbl 0691.65054
[28] Gould, N.I.M., Orban, D., Toint, Ph.L.: CUTEr and SifDec: A constrained and unconstrained testing environment, revisited. ACM Trans. Math. Softw. 29(4), 373–394 (2003) · Zbl 1068.90526
[29] Gould, N.I.M., Robinson, D.P.: A second derivative SQP method: Global convergence. SIAM J. Optim. 20(4), 2023–2048 (2010) · Zbl 1202.49039
[30] Gould, N.I.M., Robinson, D.P.: A second derivative SQP method: Local convergence and practical issues. SIAM J. Optim. 20(4), 2049–2079 (2010) · Zbl 1202.49040
[31] Greenstadt, J.: On the relative efficiencies of gradient methods. Math. Comp. 21, 360–367 (1967) · Zbl 0159.20305
[32] Hager, W.W.: Stabilized sequential quadratic programming. Comput. Optim. Appl. 12(1–3), 253–273 (1999). Computational optimization–a tribute to Olvi Mangasarian, Part I · Zbl 1040.90566
[33] Han, S.P.: A globally convergent method for nonlinear programming. J. Optim. Theory Appl. 22, 297–309 (1977) · Zbl 0336.90046
[34] Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4, 303–320 (1969) · Zbl 0174.20705
[35] Mangasarian, O.L., Fromovitz, S.: The Fritz John necessary optimality conditions in the presence of equality and inequality constraints. J. Math. Anal. Appl. 17, 37–47 (1967) · Zbl 0149.16701
[36] Maratos, N.: Exact penalty function algorithms for finite-dimensional and control optimization problems. PhD thesis, Department of Computing and Control, University of London (1978)
[37] Murray, W.: An algorithm for constrained minimization. In: Optimization, Sympos., Univ. Keele, Keele, 1968, pp. 247–258. Academic Press, London (1969)
[38] Murray, W.: Constrained optimization. PhD thesis, Department of Computer Science, University of London (1969) · Zbl 0194.47702
[39] Murtagh, B.A., Saunders, M.A.: A projected Lagrangian algorithm and its implementation for sparse nonlinear constraints. Math. Program. 16, 84–117 (1982) · Zbl 0477.90069
[40] Murtagh, B.A., Saunders, M.A.: MINOS 5.5 User’s Guide. Report SOL 83-20R, Department of Operations Research, Stanford University, Stanford, CA, (Revised 1998)
[41] Nocedal, J., Wright, S.J.: Numerical Optimization. Springer, New York (1999) · Zbl 0930.65067
[42] Powell, M.J.D.: A method for nonlinear constraints in minimization problems. In: Fletcher, R. (ed.) Optimization, pp. 283–298. Academic Press, London (1969) · Zbl 0194.47701
[43] Powell, M.J.D.: A fast algorithm for nonlinearly constrained optimization calculations. Technical Report 77/NA 2, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, England (1977) · Zbl 0374.65032
[44] Powell, M.J.D.: The convergence of variable metric methods for nonlinearly constrained optimization calculations. In: Nonlinear Programming, 3, Proc. Sympos., Special Interest Group Math. Programming, Univ. Wisconsin, Madison, Wis., 1977, pp. 27–63. Academic Press, New York (1978)
[45] Robinson, D.P.: Primal-Dual Methods for Nonlinear Optimization. PhD thesis, Department of Mathematics, University of California, San Diego (September 2007)
[46] Robinson, S.M.: A quadratically-convergent algorithm for general nonlinear programming problems. Math. Program. 3, 145–156 (1972) · Zbl 0264.90041
[47] Rockafellar, R.T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116 (1976) · Zbl 0402.90076
[48] Rockafellar, R.T.: Monotone operators and the proximal-point algorithm. SIAM J. Control Optim. 14, 877–898 (1976) · Zbl 0358.90053
[49] Schittkowski, K.: The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function. I. Convergence analysis. Numer. Math. 38(1), 83–114 (1981/82) · Zbl 0534.65030
[50] Schittkowski, K.: The nonlinear programming method of Wilson, Han, and Powell with an augmented Lagrangian type line search function. II. An efficient implementation with linear least squares subproblems. Numer. Math. 38(1), 115–127 (1981/82) · Zbl 0534.65031
[51] Schittkowski, K.: On the convergence of a sequential quadratic programming method with an augmented Lagrangian line search function. Math. Oper.forsch Stat. Ser. Optim. 14(2), 197–216 (1983) · Zbl 0523.90075
[52] Tapia, R.A.: Diagonalized multiplier methods and quasi-Newton methods for constrained optimization. J. Optim. Theory Appl. 22, 135–194 (1977) · Zbl 0336.65034
[53] Wächter, A., Biegler, L.T., Lang, Y.-D., Raghunathan, A.: IPOPT: An interior point algorithm for large-scale nonlinear optimization (2002). http://www.coin-or.org
[54] Wright, M.H.: Interior methods for constrained optimization. Acta Numer. 1992, 341–407 (1992) · Zbl 0766.65053
[55] Wright, S.J.: An algorithm for degenerate nonlinear programming with rapid local convergence. SIAM J. Optim. 15(3), 673–696 (2005) · Zbl 1077.90067
[56] Wright, S.J., Orban, D.: Properties of the log-barrier function on degenerate nonlinear programs. Math. Oper. Res. 27(3), 585–613 (2002) · Zbl 1082.90566
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.