Alternating direction augmented Lagrangian methods for semidefinite programming. (English) Zbl 1206.90088

Summary: We present an alternating direction dual augmented Lagrangian method for solving semidefinite programming (SDP) problems in standard form. At each iteration, our basic algorithm minimizes the augmented Lagrangian function for the dual SDP problem sequentially, first with respect to the dual variables corresponding to the linear constraints, and then with respect to the dual slack variables, while in each minimization keeping the other variables fixed, and then finally it updates the Lagrange multipliers (i.e., primal variables). Convergence is proved by using a fixed-point argument. For SDPs with inequality constraints and positivity constraints, our algorithm is extended to separately minimize the dual augmented Lagrangian function over four sets of variables. Numerical results for frequency assignment, maximum stable set and binary integer quadratic programming problems demonstrate that our algorithms are robust and very efficient due to their ability or exploit special structures, such as sparsity and constraint orthogonality in these problems.


90C06 Large-scale problems in mathematical programming
90C22 Semidefinite programming
90C30 Nonlinear programming
90C35 Programming involving graphs or networks
Full Text: DOI Link


[1] Bertsekas D.P., Tsitsiklis J.N.: Parallel and distributed computation: numerical methods. Prentice-Hall, Upper Saddle River (1989) · Zbl 0743.65107
[2] Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Tech. rep, Department of Management Sciences, University of Iowa (2008) · Zbl 1190.90135
[3] Burer S., Monteiro R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329–357 (2003) · Zbl 1030.90077
[4] Burer S., Monteiro R.D.C.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 427–444 (2005) · Zbl 1099.90040
[5] Burer S., Monteiro R.D.C., Zhang Y.: A computational study of a gradient-based log-barrier algorithm for a class of large-scale SDPs. Math. Program. 95, 359–379 (2003) · Zbl 1030.90076
[6] Burer S., Vandenbussche D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726–750 (2006) · Zbl 1113.90100
[7] Chen G., Teboulle M.: A proximal-based decomposition method for convex minimization problems. Math. Program 64, 81–101 (1994) · Zbl 0823.90097
[8] Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004
[9] Eckstein, J., Bertsekas, D.P.: An alternating direction method for linear programming. LIDS-P, Cambridge, MA, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology (1967)
[10] Eckstein J., Bertsekas D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55, 293–318 (1992) · Zbl 0765.90073
[11] Fortin, M., Glowinski, R.: Augmented Lagrangian methods. In: Studies in Mathematics and its Applications, vol.15. North-Holland Publishing Co., Amsterdam (1983) [Applications to the numerical solution of boundary value problems, Translated from the French by Hunt, B.D., Spicer, C.] · Zbl 0525.65045
[12] Glowinski, R., Le Tallec, P.: Augmented Lagrangian and operator-splitting methods in nonlinear mechanics. In: SIAM Studies in Applied Mathematics, vol. 9. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1989) · Zbl 0698.73001
[13] Goldfarb, D., Ma, S.: Fast alternating linearization methods for minimizing the sum of two convex functions. Tech. rep. IEOR, Columbia University (2009) · Zbl 1280.65051
[14] Goldfarb, D., Ma, S.: Fast multiple splitting algorithms for convex optimization. Tech. rep. IEOR, Columbia University (2009) · Zbl 1254.65075
[15] Hale E.T., Yin W., Zhang Y.: Fixed-point continuation for l 1-minimization: methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008) · Zbl 1180.65076
[16] He B., Liao L.-Z., Han D., Yang H.: A new inexact alternating directions method for monotone variational inequalities. Math. Program. 92, 103–118 (2002) · Zbl 1009.90108
[17] He B.S., Yang H., Wang S.L.: Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities. J. Optim. Theory Appl. 106, 337–356 (2000) · Zbl 0997.49008
[18] Hiriart-Urruty, J.-B., Lemaréchal, C.: Convex analysis and minimization algorithms. I. Fundamentals. In: Grundlehren der Mathematischen Wissenschaften. Fundamental Principles of Mathematical Sciences, vol. 305. Springer, Berlin (1993)
[19] Johnson, D.S., Trick, M.A. (eds.): Cliques, coloring, and satisfiability. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 26. American Mathematical Society, Providence (1996) [Papers from the workshop held as part of the 2nd DIMACS Implementation Challenge in New Brunswick, NJ, October 11–13, 1993]
[20] Kiwiel K.C., Rosa C.H., Ruszczyński A.: Proximal decomposition via alternating linearization. SIAM J. Optim. 9, 668–689 (1999) · Zbl 0958.65068
[21] Kontogiorgis S., Meyer R.R.: A variable-penalty alternating directions method for convex optimization. Math. Program. 83, 29–53 (1998) · Zbl 0920.90118
[22] Malick J., Povh J., Rendl F., Wiegele A.: Regularization methods for semidefinite programming. SIAM J Optim. 20, 336–356 (2009) · Zbl 1187.90219
[23] Pataki, G., Schmieta, S.: The dimacs library of semidefinite-quadratic-linear programs. Tech. rep., Center, Columbia University (1999)
[24] Povh J., Rendl F., Wiegele A.: A boundary point method to solve semidefinite programs. Computing 78, 277–286 (2006) · Zbl 1275.90055
[25] Sloane, N.J.A.: Challenge problems: independent sets in graphs. http://research.att.com/njas/doc/graphs.html
[26] Todd M.J.: Semidefinite optimization. Acta Numer. 10, 515–560 (2001) · Zbl 1105.65334
[27] Toh K.-C.: Solving large scale semidefinite programs via an iterative solver on the augmented systems. SIAM J. Optim. 14, 670–698 (2003) · Zbl 1071.90026
[28] Tseng P.: Alternating projection-proximal methods for convex programming and variational inequalities. SIAM J. Optim. 7, 951–965 (1997) · Zbl 0914.90218
[29] Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996) · Zbl 0845.65023
[30] Wang Y., Yang J., Yin W., Zhang Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imaging Sci. 1, 248–272 (2008) · Zbl 1187.68665
[31] Wen, Z., Goldfarb, D., Ma, S., Scheinberg, K.: Row by row methods for semidefinite program ming. Technical report, Department of IEOR, Columbia University (2009)
[32] Wiegele, A.: Biq mac library–a collection of max-cut and quadratic 0-1 programming instances of medium size. Technical report (2007)
[33] Wolkowicz, H., Saigal, R., Vandenberghe, L. (eds.): Handbook of semidefinite programming: theory, algorithms, and applications. In: International Series in Operations Research & Management Science, vol. 27. Kluwer, Boston (2000) · Zbl 0962.90001
[34] Yang, J., Yuan, X.: An inexact alternating direction method for trace norm regularized least squares problem. Technical report, Department of Mathematics, Nanjing University (2010)
[35] Yang, J., Zhang, Y.: Alternating direction algorithms for l1-problems in compressive sensing. Technical report, Rice University (2009)
[36] Yang J., Zhang Y., Yin W.: An efficient tvl1 algorithm for deblurring multichannel images corrupted by impulsive noise. SIAM J. Sci. Comput. 31, 2842–2865 (2008) · Zbl 1195.68110
[37] Ye C., Yuan X.: A descent method for structured monotone variational inequalities. Optimi Methods Softw 22, 329–338 (2007) · Zbl 1196.90118
[38] Yu Z.: Solving semidefinite programming problems via alternating direction methods. J. Comput. Appl. Math. 193, 437–445 (2006) · Zbl 1098.65069
[39] Yuan, X.: Alternating direction methods for sparse covariance selection. Technical report, Department of Mathematics, Hong Kong Baptist University (2009)
[40] Zhang, Y.: User’s guide for yall1: Your algorithms for l1 optimization. Technical report, Rice Univer sity (2009)
[41] Zhao X., Sun D., Toh K.: A newton-cg augmented lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010) · Zbl 1213.90175
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.