Abstract
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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bertsekas D.P., Tsitsiklis J.N.: Parallel and distributed computation: numerical methods. Prentice-Hall, Upper Saddle River (1989)
Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Tech. rep, Department of Management Sciences, University of Iowa (2008)
Burer S., Monteiro R.D.C.: A nonlinear programming algorithm for solving semidefinite programs via low-rank factorization. Math. Program. 95, 329–357 (2003)
Burer S., Monteiro R.D.C.: Local minima and convergence in low-rank semidefinite programming. Math. Program. 103, 427–444 (2005)
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)
Burer S., Vandenbussche D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726–750 (2006)
Chen G., Teboulle M.: A proximal-based decomposition method for convex minimization problems. Math. Program 64, 81–101 (1994)
Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002)
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)
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)
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.]
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)
Goldfarb, D., Ma, S.: Fast alternating linearization methods for minimizing the sum of two convex functions. Tech. rep. IEOR, Columbia University (2009)
Goldfarb, D., Ma, S.: Fast multiple splitting algorithms for convex optimization. Tech. rep. IEOR, Columbia University (2009)
Hale E.T., Yin W., Zhang Y.: Fixed-point continuation for l 1-minimization: methodology and convergence. SIAM J. Optim. 19, 1107–1130 (2008)
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)
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)
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)
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]
Kiwiel K.C., Rosa C.H., Ruszczyński A.: Proximal decomposition via alternating linearization. SIAM J. Optim. 9, 668–689 (1999)
Kontogiorgis S., Meyer R.R.: A variable-penalty alternating directions method for convex optimization. Math. Program. 83, 29–53 (1998)
Malick J., Povh J., Rendl F., Wiegele A.: Regularization methods for semidefinite programming. SIAM J Optim. 20, 336–356 (2009)
Pataki, G., Schmieta, S.: The dimacs library of semidefinite-quadratic-linear programs. Tech. rep., Center, Columbia University (1999)
Povh J., Rendl F., Wiegele A.: A boundary point method to solve semidefinite programs. Computing 78, 277–286 (2006)
Sloane, N.J.A.: Challenge problems: independent sets in graphs. http://research.att.com/njas/doc/graphs.html
Todd M.J.: Semidefinite optimization. Acta Numer. 10, 515–560 (2001)
Toh K.-C.: Solving large scale semidefinite programs via an iterative solver on the augmented systems. SIAM J. Optim. 14, 670–698 (2003)
Tseng P.: Alternating projection-proximal methods for convex programming and variational inequalities. SIAM J. Optim. 7, 951–965 (1997)
Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996)
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)
Wen, Z., Goldfarb, D., Ma, S., Scheinberg, K.: Row by row methods for semidefinite program ming. Technical report, Department of IEOR, Columbia University (2009)
Wiegele, A.: Biq mac library—a collection of max-cut and quadratic 0-1 programming instances of medium size. Technical report (2007)
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)
Yang, J., Yuan, X.: An inexact alternating direction method for trace norm regularized least squares problem. Technical report, Department of Mathematics, Nanjing University (2010)
Yang, J., Zhang, Y.: Alternating direction algorithms for l1-problems in compressive sensing. Technical report, Rice University (2009)
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)
Ye C., Yuan X.: A descent method for structured monotone variational inequalities. Optimi Methods Softw 22, 329–338 (2007)
Yu Z.: Solving semidefinite programming problems via alternating direction methods. J. Comput. Appl. Math. 193, 437–445 (2006)
Yuan, X.: Alternating direction methods for sparse covariance selection. Technical report, Department of Mathematics, Hong Kong Baptist University (2009)
Zhang, Y.: User’s guide for yall1: Your algorithms for l1 optimization. Technical report, Rice Univer sity (2009)
Zhao X., Sun D., Toh K.: A newton-cg augmented lagrangian method for semidefinite programming. SIAM J. Optim. 20, 1737–1765 (2010)
Author information
Authors and Affiliations
Corresponding author
Additional information
The work of Z. Wen and D. Goldfarb was supported in part by NSF Grant DMS 06-06712, ONR Grant N00014-08-1-1118 and DOE Grant DE-FG02-08ER58562. The work of W. Yin was supported in part by NSF CAREER Award DMS-07-48839, ONR Grant N00014-08-1-1101, the US Army Research Laboratory and the US Army Research Office grant W911NF-09-1-0383, and an Alfred P. Sloan Research Fellowship.
Rights and permissions
About this article
Cite this article
Wen, Z., Goldfarb, D. & Yin, W. Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Prog. Comp. 2, 203–230 (2010). https://doi.org/10.1007/s12532-010-0017-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s12532-010-0017-1