×

zbMATH — the first resource for mathematics

The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. (English) Zbl 1190.90117
Summary: We analyze the rate of local convergence of the augmented Lagrangian method in nonlinear semidefinite optimization. The presence of the positive semidefinite cone constraint requires extensive tools such as the singular value decomposition of matrices, an implicit function theorem for semismooth functions, and variational analysis on the projection operator in the symmetric matrix space. Without requiring strict complementarity, we prove that, under the constraint nondegeneracy condition and the strong second order sufficient condition, the rate of convergence is linear and the ratio constant is proportional to \(1/ c\), where \(c\) is the penalty parameter that exceeds a threshold \(\overline{c} > 0\).

MSC:
90C22 Semidefinite programming
65K05 Numerical mathematical programming methods
49J52 Nonsmooth analysis
Software:
COMPleib
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Arnold V.I. (1971). On matrices depending on parameters. Russ. Math. Surv. 26: 29–43 · Zbl 0259.15011
[2] Arrow K.J. and Solow R.M. (1958). Gradient methods for constrained maxima with weakened assumptions. In: Arrow, K.J., Hurwicz, L. and Uzawa, H. (eds) Studies in Linear and Nonlinear Programming., pp 165–176. Stanford University Press, Stanford
[3] Bertsekas D.P. (1976). On penalty and multiplier methods for constrained minimization. SIAM J. Cont. Optim. 14: 216–235 · Zbl 0324.49029
[4] Bertsekas D.P. (1982). Constrained Optimization and Lagrange Multiplier Methods. Academic, New York · Zbl 0572.90067
[5] Bonnans J.F., Cominetti R. and Shapiro A. (1998). Sensitivity analysis of optimization problems under second order regularity constraints. Math. Oper. Res. 23: 803–832 · Zbl 0977.90053
[6] Bonnans J.F., Cominetti R. and Shapiro A. (1999). Second order optimality conditions based on parabolic second order tangent sets. SIAM J. Optim. 9: 466–493 · Zbl 0990.90127
[7] Bonnans J.F., Ramírez C. and H (2005). Perturbation analysis of second order cone programming problems. Math. Programm. Ser. B 104: 205–227 · Zbl 1124.90039
[8] Bonnans J.F. and Shapiro A. (2000). Perturbation Analysis of Optimization Problems. Springer, New York · Zbl 0966.49001
[9] Chen X., Qi H.-D. and Tseng P. (2003). Analysis of nonsmooth symmetric-matrix functions with applications to semidefinite complementarity problems. SIAM J. Optim. 13: 960–985 · Zbl 1076.90042
[10] Clarke F.H. (1983). Optimization and Nonsmooth Analysis. Wiley, New York · Zbl 0582.49001
[11] Conn A.R., Gould N.I.M. and Toint Ph. L. (1991). A globally convergent augmented Lagrangian algorithm for optimization with general constraints and simple bounds. SIAM J. Numer. Anal. 28: 545–572 · Zbl 0724.65067
[12] Contesse-Becker L. (1993). Extended convergence results for the method of multipliers for non-strictly binding inequality constraints. J. Optim. Theory Appl. 79: 273–310 · Zbl 0797.90087
[13] Debreu G. (1952). Definite and semidefinite quadratic forms. Econometrica 20: 295–300 · Zbl 0046.24401
[14] Diehl M., Jarre F. and Vogelbusch C. (2006). Loss of superlinear convergence for an SQP-type method with conic constraints. SIAM J. Optim. 16: 1201–1210 · Zbl 1131.90058
[15] Eaves B.C. (1971). On the basic theorem of complementarity. Math. Programm. 1: 68–75 · Zbl 0227.90044
[16] Faraut J. and Korányi A. (1994). Analysis on Symmetric Cones. Clarendon Press, London · Zbl 0841.43002
[17] Golshtein E.G. and Tretyakov N.V. (1989). Modified Lagrangians and Monotone Maps in Optimization. Wiley, New York · Zbl 0848.49001
[18] Golub G. and Van Loan C.F. (1996). Matrix Computations. The Johns Hopkins University Press, Baltimore · Zbl 0865.65009
[19] Hestenes M.R. (1969). Multiplier and gradient methods. J. Optim. Theory Appl. 4: 303–320 · Zbl 0174.20705
[20] Higham N.J. (1998). Computing a nearest symmetric positive semidefinite matrix. Linear Algebra Appl. 103: 103–118 · Zbl 0649.65026
[21] Ito K. and Kunisch K. (1990). The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces. Math. Program. 46: 341–360 · Zbl 0706.90096
[22] Kummer B. (1988). Newton’s method for non-differentiable functions. In: Guddat, J. (eds) Advances in Mathematical Optimization, pp 114–125. Akademie-Verlag, Berlin
[23] Kummer B. (1991). Lipschitzian inverse functions, directional derivatives and applications in C 1,1-optimization. J. Optim. Theory Appl. 70: 559–580 · Zbl 0795.49012
[24] Leibfritz, F.: COMPl e ib 1.1: COnstraint Matrix-optimization Problem Library–a collection of test examples for nonlinear semidefinite programs, control system design and related problems. Technical Report, Department of Mathematics, University of Trier, Germany (2005)
[25] Löwner K. (1934). Über monotone matrixfunktionen. Mathematische Zeitschrift 38: 177–216 · Zbl 0008.11301
[26] Kocvara M. and Stingl M. (2004). Solving nonconvex SDP problems of structural optimization with stability control. Optim. Methods Softw. 19: 595–609 · Zbl 1135.49304
[27] Meng F., Sun D. and Zhao G. (2005). Semismoothness of solutions to generalized equations and the Moreau–Yosida regularization. Math. Program. Ser. B 104: 561–581 · Zbl 1093.90059
[28] Mifflin R. (1977). Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15: 957–972 · Zbl 0376.90081
[29] Pang J.-S., Sun D. and Sun J. (2003). Semismooth homeomorphisms and strong stability of semidefinite and Lorentz complementarity problems. Math. Oper. Res. 28: 39–63 · Zbl 1082.90115
[30] Pennanen T. (2002). Local convergence of the proximal point algorithm and multiplier methods without monotonicity. Math. Oper. Res. 27: 170–191 · Zbl 1082.90582
[31] Powell M.J.D. (1972). A method for nonlinear constraints in minimization problems. In: Fletcher, R. (eds) Optimization, pp 283–298. Academic, New York
[32] Qi L. and Sun J. (1993). A nonsmooth version of Newton’s method. Math. Program. 58: 353–367 · Zbl 0780.90090
[33] Robinson S.M. (1984). Local structure of feasible sets in nonlinear programming, part II: nondegeneracy. Math. Program. Study 22: 217–230 · Zbl 0573.90075
[34] Rockafellar R.T. (1973). A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5: 354–373 · Zbl 0279.90035
[35] Rockafellar R.T. (1973). The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12: 555–562 · Zbl 0254.90045
[36] Rockafellar R.T. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14: 877–898 · Zbl 0358.90053
[37] Rockafellar R.T. (1976). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1: 97–116 · Zbl 0402.90076
[38] Rockafellar R.T. (1993). Lagrange multipliers and optimality. SIAM Rev. 35: 183–238 · Zbl 0779.49024
[39] Rockafellar R.T. and Wets R.J.-B (1998). Variational Analysis. Springer, New York · Zbl 0888.49001
[40] Shapiro A. (1990). On concepts of directional differentiability. J. Optim. Theory Appl. 66: 477–487 · Zbl 0682.49015
[41] Shapiro A. (2003). Sensitivity analysis of generalized equations. J. Math. Sci. 115: 2554–2565 · Zbl 1136.90482
[42] Shapiro A. and Sun J. (2001). Some properties of the augmented Lagrangian in cone constrained optimization. Math. Oper. Res. 29: 479–491 · Zbl 1082.90109
[43] Sun D. (2001). A further result on an implicit function theorem for locally Lipschitz functions. Oper. Res. Lett. 28: 193–198 · Zbl 1006.49009
[44] Sun D. (2006). The strong second order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31: 761–776 · Zbl 1278.90304
[45] Sun D. and Sun J. (2002). Semismooth matrix valued functions. Math. Oper. Res. 27: 150–169 · Zbl 1082.49501
[46] Sun, D., Sun, J.: Löwner’s operator and spectral functions in Euclidean Jordan algebras. Department of Mathematics, National University of Singapore (2004) · Zbl 1218.90197
[47] Tretyakov N.V. (1973). A method of penalty estimates for convex programming problems.. Èkonomika i Matematicheskie Metody 9: 525–540
[48] Tseng P. (1998). Merit functions for semi-definite complementarity problems. Math. Program. 83: 159–185 · Zbl 0920.90135
[49] Tsing N.-K., Fan M.K.H. and Verriest E.I. (1994). On analyticity of functions involving eigenvalues. Linear Algebra Appl. 207: 159–180 · Zbl 0805.15022
[50] Zarantonello E.H. (1971). Projections on convex sets in Hilbert space and spectral theory I and II. In: Zarantonello, E.H. (eds) Contributions to Nonlinear Functional Analysis, pp 237–424. Academic, New York
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.