×

zbMATH — the first resource for mathematics

Study of a primal-dual algorithm for equality constrained minimization. (English) Zbl 1304.49050
Summary: The paper proposes a primal-dual algorithm for solving an equality constrained minimization problem. The algorithm is a Newton-like method applied to a sequence of perturbed optimality systems that follow naturally from the quadratic penalty approach. This work is first motivated by the fact that a primal-dual formulation of the quadratic penalty provides a better framework than the standard primal form. This is highlighted by strong convergence properties proved under standard assumptions. In particular, it is shown that the usual requirement of solving the penalty problem with a precision of the same size as the perturbation parameter, can be replaced by a much less stringent criterion, while guaranteeing the superlinear convergence property. A second motivation is that the method provides an appropriate regularization for degenerate problems with a rank deficient Jacobian of constraints. Numerical experiments clearly bear this out. Another important feature of our algorithm is that the penalty parameter is allowed to vary during the inner iterations, while it is usually kept constant. This alleviates the numerical problem due to ill-conditioning of the quadratic penalty, leading to an improvement of the numerical performance.

MSC:
49M15 Newton-type methods
49M37 Numerical methods based on nonlinear programming
65K05 Numerical mathematical programming methods
90C06 Large-scale problems in mathematical programming
90C30 Nonlinear programming
90C51 Interior-point methods
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Armand, P, A quasi-Newton penalty barrier method for convex minimization problems, Comput. Optim. Appl., 26, 5-34, (2003) · Zbl 1053.90106
[2] Armand, P; Benoist, J; Orban, D, Dynamic updates of the barrier parameter in primal-dual methods for nonlinear programming, Comput. Optim. Appl., 41, 1-25, (2008) · Zbl 1180.90305
[3] Armand, P; Benoist, J; Orban, D, From global to local convergence of interior methods for nonlinear optimization, Optim. Methods Softw., 28, 1051-1080, (2013) · Zbl 1278.90254
[4] Benchakroun, A; Dussault, JP; Mansouri, A, A two parameter mixed interior-exterior penalty algorithm, ZOR—Math. Methods Oper. Res., 41, 25-55, (1995) · Zbl 0834.90114
[5] Benson, HY; Shanno, DF, Interior-point methods for nonconvex nonlinear programming: regularization and warmstarts, Comput. Optim. Appl., 40, 143-189, (2008) · Zbl 1181.90243
[6] Benson, HY; Vanderbei, RJ; Shanno, DF, Interior-point methods for nonconvex nonlinear programming: filter methods and merit functions, Comput. Optim. Appl., 23, 257-272, (2002) · Zbl 1022.90017
[7] Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Computer Science and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York (1982) · Zbl 0572.90067
[8] Biegler, L.T.: Nonlinear Programming: Concepts, Algorithms, and Applications to Chemical Processes, MOS-SIAM Series on Optimization, vol. 10. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA (2010) · Zbl 1207.90004
[9] Bousquet, E.: Optimisation non linéaire et application au réglage d’un réseau de télescopes. Ph.D. thesis, Université de Limoges, École Doctorale S2i (2009)
[10] Broyden, C.G., Attia, N.F.: A smooth sequential penalty function method for solving nonlinear programming problems. In: System Modelling and Optimization (Copenhagen, 1983). Lecture Notes in Control and Information Sciences, vol. 59, pp. 237-245. Springer, Berlin (1984) · Zbl 0549.90079
[11] Broyden, CG; Attia, NF, Penalty functions, newton’s method and quadratic programming, J. Optim. Theory Appl., 58, 377-385, (1988) · Zbl 0628.90056
[12] Byrd, RH; Gilbert, JC; Nocedal, J, A trust region method based on interior point techniques for nonlinear programming, Math. Program., 89, 149-185, (2000) · Zbl 1033.90152
[13] Byrd, RH; Marazzi, M; Nocedal, J, On the convergence of Newton iterations to non-stationary points, Math. Program., 99, 127-148, (2004) · Zbl 1072.90038
[14] Byrd, RH; Nocedal, J; Waltz, RA, Feasible interior methods using slacks for nonlinear optimization, Comput. Optim. Appl., 26, 35-61, (2003) · Zbl 1053.90119
[15] Byrd, R.H., Nocedal, J., Waltz, R.A.: KNITRO: An integrated package for nonlinear optimization. In: Large-Scale Nonlinear Optimization. Nonconvex Optimization and Its Applications, vol. 83, pp. 35-59. Springer, New York (2006) · Zbl 1108.90004
[16] Chen, L; Goldfarb, D, Interior-point \(l_2\)-penalty methods for nonlinear programming with strong global convergence properties, Math. Program., 108, 1-36, (2006) · Zbl 1142.90498
[17] Conn, A.R., Gould, N.I.M., Toint, P.L.: Trust-Region Methods. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (2000) · Zbl 0958.65071
[18] Courant, R, Variational methods for the solution of problems of equilibrium and vibrations, Bull. Am. Math. Soc., 49, 1-23, (1943) · Zbl 0063.00985
[19] Curtis, FE; Nocedal, J; Wächter, A, A matrix-free algorithm for equality constrained optimization problems with rank-deficient Jacobians, SIAM J. Optim., 20, 1224-1249, (2009) · Zbl 1195.49035
[20] Debreu, G, Definite and semidefinite quadratic forms, Econometrica, 20, 295-300, (1952) · Zbl 0046.24401
[21] Dennis Jr, J.E., Schnabel, R.B.: Numerical methods for unconstrained optimization and nonlinear equations. Prentice Hall Series in Computational Mathematics. Prentice Hall Inc., Englewood Cliffs (1983) · Zbl 0579.65058
[22] Dolan, E., Moré, J., Munson, T.: Benchmarking optimization software with COPS 3.0. Tech. rep., Argonne National Laboratory (2004) · Zbl 1075.90078
[23] Dolan, ED; Moré, JJ, Benchmarking optimization software with performance profiles, Math. Program., 91, 201-213, (2002) · Zbl 1049.90004
[24] Duff, IS, Ma57—a code for the solution of sparse symmetric definite and indefinite systems, ACM Trans. Math. Softw., 30, 118-144, (2004) · Zbl 1070.65525
[25] Fiacco, A.V., McCormick, G.P.: Nonlinear Programming: Sequential Unconstrained Minimization Techniques. Wiley, New York (1968) · Zbl 0193.18805
[26] Fletcher, R.: Practical Methods of Optimization, 2nd edn. Wiley, Chichester (1987) · Zbl 0905.65002
[27] Forsgren, A; Gill, PE, Primal-dual interior methods for nonconvex nonlinear programming, SIAM J. Optim., 8, 1132-1152, (1998) · Zbl 0915.90236
[28] Forsgren, A; Gill, PE; Wright, MH, Interior methods for nonlinear optimization, SIAM Rev., 44, 525-597, (2002) · Zbl 1028.90060
[29] Fourer, R., Gay, D.M., Kernighan, B.W.: AMPL: A Modeling Language for Mathematical Programming, 2nd edn. Brooks/Cole (2002) · Zbl 0701.90062
[30] Gertz, EM; Gill, PE, A primal-dual trust region algorithm for nonlinear optimization, Math. Program., 100, 49-94, (2004) · Zbl 1146.90514
[31] Gill, PE; Robinson, DP, A primal-dual augmented Lagrangian, Comput. Optim. Appl., 51, 1-25, (2012) · Zbl 1244.90219
[32] Goldfarb, D; Polyak, R; Scheinberg, K; Yuzefovich, I, A modified barrier-augmented Lagrangian method for constrained minimization, Comput. Optim. Appl., 14, 55-74, (1999) · Zbl 0951.90042
[33] Gould, N; Orban, D; Toint, P, Cuter and sifdec: a constrained and unconstrained testing environment, revisited, ACM Trans. Math. Softw., 29, 373-394, (2003) · Zbl 1068.90526
[34] Gould, N., Orban, D., Toint, P.: An interior-point \(ℓ _1\)-penalty method for nonlinear optimization. Tech. Rep. RAL-TR-2003-022, Rutherford Appleton Laboratory, Chilton, Oxfordshire, England (2003) · Zbl 1070.65525
[35] Gould, N; Orban, D; Toint, P, Numerical methods for large-scale nonlinear optimization, Acta Numer., 14, 299-361, (2005) · Zbl 1119.65337
[36] Gould, NIM, On the accurate determination of search directions for simple differentiable penalty functions, IMA J. Numer. Anal., 6, 357-372, (1986) · Zbl 0691.65054
[37] Gould, NIM, On the convergence of a sequential penalty function method for constrained minimization, SIAM J. Numer. Anal., 26, 107-128, (1989) · Zbl 0667.65050
[38] Griva, I; Shanno, DF; Vanderbei, RJ; Benson, HY, Global convergence of a primal-dual interior-point method for nonlinear programming, Algorithmic Oper. Res., 3, 12-29, (2008) · Zbl 1277.90148
[39] Murray, W, Analytical expressions for the eigenvalues and eigenvectors of the Hessian matrices of barrier and penalty functions, J. Optim. Theory Appl., 7, 189-196, (1971) · Zbl 0198.52504
[40] Nemirovski, AS; Todd, MJ, Interior-point methods for optimization, Acta Numer., 17, 191-234, (2008) · Zbl 1160.65027
[41] Nocedal, J., Wright, S.J.: Numerical optimization. Springer Series in Operations Research and Financial Engineering, 2nd edn. Springer, New York (2006)
[42] Shanno, D.F., Vanderbei, R.J.: Interior-point methods for nonconvex nonlinear programming: orderings and higher-order methods. Math. Program. 87(2, Ser. B), 303-316 (2000). Studies in algorithmic optimization · Zbl 1054.90091
[43] Tits, AL; Wächter, A; Bakhtiari, S; Urban, TJ; Lawrence, CT, A primal-dual interior-point method for nonlinear programming with strong global and local convergence properties, SIAM J. Optim., 14, 173-199, (2003) · Zbl 1075.90078
[44] Vanderbei, R.J., Shanno, D.F.: An interior-point algorithm for nonconvex nonlinear programming. Comput. Optim. Appl. 13(1-3), 231-252 (1999). Computational optimization-a tribute to Olvi Mangasarian, Part II · Zbl 1040.90564
[45] Wächter, A; Biegler, LT, Failure of global convergence for a class of interior point methods for nonlinear programming, Math. Program., 88, 565-574, (2000) · Zbl 0963.65063
[46] Wächter, A; Biegler, LT, Line search filter methods for nonlinear programming: local convergence, SIAM J. Optim., 16, 32-48, (2005) · Zbl 1115.90056
[47] Wächter, A; Biegler, LT, Line search filter methods for nonlinear programming: motivation and global convergence, SIAM J. Optim., 16, 1-31, (2005) · Zbl 1114.90128
[48] Wächter, A; Biegler, LT, On the implementation of an interior-point filter line-search algorithm for large-scale nonlinear programming, Math. Program., 106, 25-57, (2006) · Zbl 1134.90542
[49] Waltz, RA; Morales, JL; Nocedal, J; Orban, D, An interior algorithm for nonlinear optimization that combines line search and trust region steps, Math. Program., 107, 391-408, (2006) · Zbl 1134.90053
[50] Wright, MH, The interior-point revolution in optimization: history, recent developments, and lasting consequences, Bull. Am. Math. Soc. (N.S.), 42, 39-56, (2005) · Zbl 1114.90153
[51] Yamashita, H; Yabe, H, An interior point method with a primal-dual quadratic barrier penalty function for nonlinear optimization, SIAM J. Optim., 14, 479-499, (2003) · Zbl 1072.90050
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.