A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions

详细信息    查看全文

• 作者：Xudong Li ; Defeng Sun ; Kim-Chuan Toh
• 关键词：Convex quadratic conic programming ; Multiple ; block ADMM ; Semi ; proximal ADMM ; Convergence ; QSDP ; 90C06 ; 90C20 ; 90C22 ; 90C25 ; 65F10
• 刊名：Mathematical Programming
• 出版年：2016
• 出版时间：January 2016
• 年：2016
• 卷：155
• 期：1-2
• 页码：333-373
• 全文大小：762 KB
• 参考文献：1.Qi, H.: Local duality of nonlinear semidefinite programming. Math. Oper. Res. 34(1), 124–141 (2009)MATH MathSciNet CrossRef
  2.Sun, J., Zhang, S.: A modified alternating direction method for convex quadratically constrained quadratic semidefinite programs. Eur. J. Oper. Res. 207, 1210–1220 (2010)MATH CrossRef
  3.Toh, K.C.: An inexact primal-dual path following algorithm for convex quadratic sdp. Math. Program. 112(1), 221–254 (2008)MATH MathSciNet CrossRef
  4.Sun, D.F.: The strong second-order sufficient condition and constraint nondegeneracy in nonlinear semidefinite programming and their implications. Math. Oper. Res. 31(4), 761–776 (2006)MATH MathSciNet CrossRef
  5.Bi, S., Pan, S., Chen, J.S.: Nonsingularity conditions for the Fischer–Burmeister system of nonlinear sdps. SIAM J. Optim. 21(4), 1392–1417 (2011)MATH MathSciNet CrossRef
  6.Zhao, X.Y.: A semismooth newton-cg augmented lagrangian method for large scale linear and convex quadratic sdps. Ph.D. thesis, Department of Mathematics, National University of Singapore (2009)
  7.Miao, W., Pan, S., Sun, D.F.: A rank-corrected procedure for matrix completion with fixed basis coefficients. Technical Report, National University of Singapore (2014)
  8.Miao, W.: Matrix completion models with fixed basis coefficients and rank regularized prbolems with hard constraints. Ph.D. thesis, Department of Mathematics, Nationla University of Singapore (2013)
  9.Wu, B.: High-dimensional analysis on matrix decomposition with application to correlation matrix estimation in factor models. Ph.D. thesis, Department of Mathematics, Nationla University of Singapore (2014)
  10.Negahban, S., Wainwright, M.J.: Restricted strong convexity and weighted matrix completion: optimal bounds with noise. J. Mach. Learn. Res. 13(1), 1665–1697 (2012)MATH MathSciNet
  11.Klopp, O.: Noisy low-rank matrix completion with general sampling distribution. Bernoulli 20(1), 282–303 (2014)MATH MathSciNet CrossRef
  12.Wright, J., Ganesh, A., Rao, S., Peng, Y., Ma, Y.: Robust principal component analysis: exact recovery of corrupted low-rank matrices by convex optimization. In: Proceedings of Neural Information Processing Systems, vol. 3 (2009)
  13.Tao, M., Yuan, X.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21(1), 57–81 (2011)MATH MathSciNet CrossRef
  14.Glowinski, R., Marrocco, A.: Sur l’approximation, par éléments finis d’ordre un, et la résolution, par pénalisation-dualité, d’une classe de problèmes de dirichlet non linéares. Revue Francaise d’Automatique, Informatique et Recherche Opérationelle 9, 41–76 (1975)MATH MathSciNet
  15.Gabay, D., Mercier, B.: A dual algorithm for the solution of nonlinear variational problems via finite element approximation. Comput. Math. Appl. 2(1), 17–40 (1976)MATH CrossRef
  16.Glowinski, R.: Lectures on numerical methods for nonlinear variational problems. In: Tata Institute of Fundamental Research Lectures on Mathematics and Physics, vol. 65. Tata Institute of Fundamental Research, Bombay. Notes by M. G. Vijayasundaram and M. Adimurthi (1980)
  17.Fortin, M., Glowinski, R.: Augmented Lagrangian Methods, Studies in Mathematics and its Applications, vol. 15. North-Holland Publishing Co., Amsterdam. Applications to the numerical solution of boundary value problems. Translated from the French by B. Hunt and D. C. Spicer (1983)
  18.Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Fortin, M., Glowinski, R. (eds.) Augmented Lagrangian Methods: Applications to the Numerical Solution of Boundary-Value Problems, Studies in Mathematics and Its Applications, vol. 15, pp. 299–331. Elsevier (1983). doi:10.​1016/​S0168-2024(08)70034-1 . http://​www.​sciencedirect.​com/​science/​article/​pii/​S016820240870034​1
  19.Eckstein, J., Bertsekas, D.P.: On the Douglas–Rachford splitting method and the proximal point algorithm for maximal monotone operators. Math. Program. 55(1–3), 293–318 (1992)MATH MathSciNet CrossRef
  20.Chen, C., He, B., Ye, Y., Yuan, X.: The direct extension of admm for multi-block convex minimization problems is not necessarily convergent. Math. Program. 1–23 (2014). doi:10.​1007/​s10107-014-0826-5
  21.Sun, D.F., Toh, K.C., Yang, L.: A convergent 3-block semi-proximal alternating direction method of multipliers for conic programming with 4-type of constraints (2014). arXiv:​1404.​5378
  22.Fazel, M., Pong, T.K., Sun, D.F., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34(3), 946–977 (2013)MATH MathSciNet CrossRef
  23.Zhao, X.Y., Sun, D.F., Toh, K.C.: A Newton-cg augmented lagrangian method for semidefinite programming. SIAM J. Optim. 20(4), 1737–1765 (2010)MATH MathSciNet CrossRef
  24.Yang, L., Sun, D.F., Toh, K.C.: Sdpnal \(+\) : a majorized semismooth Newton-cg augmented lagrangian method for semidefinite programming with nonnegative constraints (2014). arXiv:​1406.​0942
  25.He, B., Tao, M., Yuan, X.: Alternating direction method with gaussian back substitution for separable convex programming. SIAM J. Optim. 22(2), 313–340 (2012)MATH MathSciNet CrossRef
  26.Li, L., Toh, K.C.: An inexact interior point method for l1-regularized sparse covariance selection. Math. Program. Comput. 2(3–4), 291–315 (2010)MATH MathSciNet CrossRef
  27.Jiang, K., Sun, D.F., Toh, K.C.: An inexact accelerated proximal gradient method for large scale linearly constrained convex sdp. SIAM J. Optim. 22(3), 1042–1064 (2012)MATH MathSciNet CrossRef
  28.He, B., Yuan, X.: Linearized alternating direction method of multipliers with Gaussian back substitution for separable convex programming. Numer. Algebra Control Optim. 3(2), 247–260 (2013)MATH MathSciNet CrossRef
  
• 作者单位：Xudong Li (1)
  Defeng Sun (2)
  Kim-Chuan Toh (1)
  
  1. Department of Mathematics, National University of Singapore, 10 Lower Kent Ridge Road, Singapore, 119076, Singapore
  2. Department of Mathematics and Risk Management Institute, National University of Singapore, 10 Lower Kent Ridge Road, Singapore, 119076, Singapore
  
• 刊物类别：Mathematics and Statistics
• 刊物主题：Mathematics
  Calculus of Variations and Optimal Control
  Mathematics of Computing
  Numerical Analysis
  Combinatorics
  Mathematical and Computational Physics
  Mathematical Methods in Physics
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1436-4646

文摘

This paper is devoted to the design of an efficient and convergent semi-proximal alternating direction method of multipliers (ADMM) for finding a solution of low to medium accuracy to convex quadratic conic programming and related problems. For this class of problems, the convergent two block semi-proximal ADMM can be employed to solve their primal form in a straightforward way. However, it is known that it is more efficient to apply the directly extended multi-block semi-proximal ADMM, though its convergence is not guaranteed, to the dual form of these problems. Naturally, one may ask the following question: can one construct a convergent multi-block semi-proximal ADMM that is more efficient than the directly extended semi-proximal ADMM? Indeed, for linear conic programming with 4-block constraints this has been shown to be achievable in a recent paper by Sun et al. (2014, arXiv:​1404.​5378). Inspired by the aforementioned work and with the convex quadratic conic programming in mind, we propose a Schur complement based convergent semi-proximal ADMM for solving convex programming problems, with a coupling linear equality constraint, whose objective function is the sum of two proper closed convex functions plus an arbitrary number of convex quadratic or linear functions. Our convergent semi-proximal ADMM is particularly suitable for solving convex quadratic semidefinite programming (QSDP) with constraints consisting of linear equalities, a positive semidefinite cone and a simple convex polyhedral set. The efficiency of our proposed algorithm is demonstrated by numerical experiments on various examples including QSDP. Keywords Convex quadratic conic programming Multiple-block ADMM Semi-proximal ADMM Convergence QSDP