Abstract
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\) .
Similar content being viewed by others
References
Arnold V.I. (1971). On matrices depending on parameters. Russ. Math. Surv. 26: 29–43
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
Bertsekas D.P. (1976). On penalty and multiplier methods for constrained minimization. SIAM J. Cont. Optim. 14: 216–235
Bertsekas D.P. (1982). Constrained Optimization and Lagrange Multiplier Methods. Academic, New York
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
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
Bonnans J.F., Ramírez C. and H (2005). Perturbation analysis of second order cone programming problems. Math. Programm. Ser. B 104: 205–227
Bonnans J.F. and Shapiro A. (2000). Perturbation Analysis of Optimization Problems. Springer, New York
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
Clarke F.H. (1983). Optimization and Nonsmooth Analysis. Wiley, New York
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
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
Debreu G. (1952). Definite and semidefinite quadratic forms. Econometrica 20: 295–300
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
Eaves B.C. (1971). On the basic theorem of complementarity. Math. Programm. 1: 68–75
Faraut J. and Korányi A. (1994). Analysis on Symmetric Cones. Clarendon Press, London
Golshtein E.G. and Tretyakov N.V. (1989). Modified Lagrangians and Monotone Maps in Optimization. Wiley, New York
Golub G. and Van Loan C.F. (1996). Matrix Computations. The Johns Hopkins University Press, Baltimore
Hestenes M.R. (1969). Multiplier and gradient methods. J. Optim. Theory Appl. 4: 303–320
Higham N.J. (1998). Computing a nearest symmetric positive semidefinite matrix. Linear Algebra Appl. 103: 103–118
Ito K. and Kunisch K. (1990). The augmented Lagrangian method for equality and inequality constraints in Hilbert spaces. Math. Program. 46: 341–360
Kummer B. (1988). Newton’s method for non-differentiable functions. In: Guddat, J. (eds) Advances in Mathematical Optimization, pp 114–125. Akademie-Verlag, Berlin
Kummer B. (1991). Lipschitzian inverse functions, directional derivatives and applications in C 1,1-optimization. J. Optim. Theory Appl. 70: 559–580
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)
Löwner K. (1934). Über monotone matrixfunktionen. Mathematische Zeitschrift 38: 177–216
Kocvara M. and Stingl M. (2004). Solving nonconvex SDP problems of structural optimization with stability control. Optim. Methods Softw. 19: 595–609
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
Mifflin R. (1977). Semismooth and semiconvex functions in constrained optimization. SIAM J. Control Optim. 15: 957–972
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
Pennanen T. (2002). Local convergence of the proximal point algorithm and multiplier methods without monotonicity. Math. Oper. Res. 27: 170–191
Powell M.J.D. (1972). A method for nonlinear constraints in minimization problems. In: Fletcher, R. (eds) Optimization, pp 283–298. Academic, New York
Qi L. and Sun J. (1993). A nonsmooth version of Newton’s method. Math. Program. 58: 353–367
Robinson S.M. (1984). Local structure of feasible sets in nonlinear programming, part II: nondegeneracy. Math. Program. Study 22: 217–230
Rockafellar R.T. (1973). A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Program. 5: 354–373
Rockafellar R.T. (1973). The multiplier method of Hestenes and Powell applied to convex programming. J. Optim. Theory Appl. 12: 555–562
Rockafellar R.T. (1976). Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14: 877–898
Rockafellar R.T. (1976). Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1: 97–116
Rockafellar R.T. (1993). Lagrange multipliers and optimality. SIAM Rev. 35: 183–238
Rockafellar R.T. and Wets R.J.-B (1998). Variational Analysis. Springer, New York
Shapiro A. (1990). On concepts of directional differentiability. J. Optim. Theory Appl. 66: 477–487
Shapiro A. (2003). Sensitivity analysis of generalized equations. J. Math. Sci. 115: 2554–2565
Shapiro A. and Sun J. (2001). Some properties of the augmented Lagrangian in cone constrained optimization. Math. Oper. Res. 29: 479–491
Sun D. (2001). A further result on an implicit function theorem for locally Lipschitz functions. Oper. Res. Lett. 28: 193–198
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
Sun D. and Sun J. (2002). Semismooth matrix valued functions. Math. Oper. Res. 27: 150–169
Sun, D., Sun, J.: Löwner’s operator and spectral functions in Euclidean Jordan algebras. Department of Mathematics, National University of Singapore (2004)
Tretyakov N.V. (1973). A method of penalty estimates for convex programming problems.. Èkonomika i Matematicheskie Metody 9: 525–540
Tseng P. (1998). Merit functions for semi-definite complementarity problems. Math. Program. 83: 159–185
Tsing N.-K., Fan M.K.H. and Verriest E.I. (1994). On analyticity of functions involving eigenvalues. Linear Algebra Appl. 207: 159–180
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
Author information
Authors and Affiliations
Corresponding author
Additional information
The research of Defeng Sun is partly supported by the Academic Research Fund from the National University of Singapore. The research of Jie Sun and Liwei Zhang is partly supported by Singapore–MIT Alliance and by Grants RP314000-042/057-112 of the National University of Singapore. The research of Liwei Zhang is also supported by the National Natural Science Foundation of China under project grant no. 10471015 and by the Scientific Research Foundation for the Returned Overseas Chinese Scholars, State Education Ministry, China.
Rights and permissions
About this article
Cite this article
Sun, D., Sun, J. & Zhang, L. The rate of convergence of the augmented Lagrangian method for nonlinear semidefinite programming. Math. Program. 114, 349–391 (2008). https://doi.org/10.1007/s10107-007-0105-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10107-007-0105-9
Keywords
- Nonlinear semidefinite programming
- Rate of convergence
- The augmented Lagrangian method
- Variational analysis