zbMATH — the first resource for mathematics

Examples
Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

Operators
a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
Fields
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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.
MSC:
90C06Large-scale problems (mathematical programming)
90C22Semidefinite programming
90C30Nonlinear programming
90C35Programming involving graphs or networks
Software:
SDPLR; DIMACS
References:
[1]Bertsekas D.P., Tsitsiklis J.N.: Parallel and distributed computation: numerical methods. Prentice-Hall, Upper Saddle River (1989)
[2]Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Tech. rep, Department of Management Sciences, University of Iowa (2008)
[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 · doi:10.1007/s10107-002-0352-8
[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 · doi:10.1007/s10107-004-0564-1
[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 · doi:10.1007/s10107-002-0353-7
[6]Burer S., Vandenbussche D.: Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726–750 (2006) · Zbl 1113.90100 · doi:10.1137/040609574
[7]Chen G., Teboulle M.: A proximal-based decomposition method for convex minimization problems. Math. Program 64, 81–101 (1994) · Zbl 0823.90097 · doi:10.1007/BF01582566
[8]Dolan E.D., Moré J.J.: Benchmarking optimization software with performance profiles. Math. Program. 91, 201–213 (2002) · Zbl 1049.90004 · doi:10.1007/s101070100263
[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 · doi:10.1007/BF01581204
[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.]
[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)
[13]Goldfarb, D., Ma, S.: Fast alternating linearization methods for minimizing the sum of two convex functions. Tech. rep. IEOR, Columbia University (2009)
[14]Goldfarb, D., Ma, S.: Fast multiple splitting algorithms for convex optimization. Tech. rep. IEOR, Columbia University (2009)
[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 · doi:10.1137/070698920
[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 · doi:10.1007/s101070100280
[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 · doi:10.1023/A:1004603514434
[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 · doi:10.1137/S1052623495288064
[21]Kontogiorgis S., Meyer R.R.: A variable-penalty alternating directions method for convex optimization. Math. Program. 83, 29–53 (1998)
[22]Malick J., Povh J., Rendl F., Wiegele A.: Regularization methods for semidefinite programming. SIAM J Optim. 20, 336–356 (2009) · Zbl 1187.90219 · doi:10.1137/070704575
[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 05082638 · doi:10.1007/s00607-006-0182-2
[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 · doi:10.1017/S0962492901000071
[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 · doi:10.1137/S1052623402419819
[28]Tseng P.: Alternating projection-proximal methods for convex programming and variational inequalities. SIAM J. Optim. 7, 951–965 (1997) · Zbl 0914.90218 · doi:10.1137/S1052623495279797
[29]Vandenberghe L., Boyd S.: Semidefinite programming. SIAM Rev. 38, 49–95 (1996) · Zbl 0845.65023 · doi:10.1137/1038003
[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 · doi:10.1137/080724265
[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)
[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 · doi:10.1137/080732894
[37]Ye C., Yuan X.: A descent method for structured monotone variational inequalities. Optimi Methods Softw 22, 329–338 (2007) · Zbl 1196.90118 · doi:10.1080/10556780600552693
[38]Yu Z.: Solving semidefinite programming problems via alternating direction methods. J. Comput. Appl. Math. 193, 437–445 (2006) · Zbl 1098.65069 · doi:10.1016/j.cam.2005.07.002
[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 · doi:10.1137/080718206