Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Journal of Scientific Computing
Published in: Journal of Scientific Computing 2/2016

18-12-2015

Alternating Proximal Gradient Method for Convex Minimization

Author: Shiqian Ma

Published in: Journal of Scientific Computing | Issue 2/2016

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In this paper, we apply the idea of alternating proximal gradient to solve separable convex minimization problems with three or more blocks of variables linked by some linear constraints. The method proposed in this paper is to firstly group the variables into two blocks, and then apply a proximal gradient based inexact alternating direction method of multipliers to solve the new formulation. The main computational effort in each iteration of the proposed method is to compute the proximal mappings of the involved convex functions. The global convergence result of the proposed method is established. We show that many interesting problems arising from machine learning, statistics, medical imaging and computer vision can be solved by the proposed method. Numerical results on problems such as latent variable graphical model selection, stable principal component pursuit and compressive principal component pursuit are presented.
previous article A Cell-Centered Nonlinear Finite Volume Scheme Preserving Fully Positivity for Diffusion Equation
next article Computation Algorithm for Convex Semi-infinite Program with Second-Order Cones: Special Analyses for Affine and Quadratic Case

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now
Literature
1.
Aybat, N.S., Iyengar, G.: An alternating direction method with increasing penalty for stable principal component pursuit. Comput. Optim. Appl. 61, 635–668 (2015)MathSciNetCrossRefMATH
2.
Banerjee, O., El Ghaoui, L., d’Aspremont, A.: Model selection through sparse maximum likelihood estimation for multivariate Gaussian for binary data. J. Mach. Learn. Res. 9, 485–516 (2008)MathSciNetMATH
3.
Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and distributed computation: numerical methods. Prentice-Hall Inc, Upper Saddle River (1989)MATH
4.
Boley, D.: Local linear convergence of the alternating direction method of multipliers on quadratic or linear programs. SIAM J. Optim. 23, 2183–2207 (2013)MathSciNetCrossRefMATH
5.
Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3, 1–122 (2011)CrossRefMATH
6.
Cai, J., Candès, E.J., Shen, Z.: A singular value thresholding algorithm for matrix completion. SIAM J. Optim. 20, 1956–1982 (2010)MathSciNetCrossRefMATH
7.
8.
9.
Candès, E.J., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Theory 52, 489–509 (2006)MathSciNetCrossRefMATH
10.
Candès, E.J., Tao, T.: The power of convex relaxation: near-optimal matrix completion. IEEE Trans. Inform. Theory 56, 2053–2080 (2009)MathSciNetCrossRef
11.
Chandrasekaran, V., Parrilo, P.A., Willsky, A.S.: Latent variable graphical model selection via convex optimization. Ann. Stat. 40, 1935–1967 (2012)MathSciNetCrossRefMATH
12.
Chandrasekaran, V., Sanghavi, S., Parrilo, P., Willsky, A.: Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21, 572–596 (2011)MathSciNetCrossRefMATH
13.
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. (2014). doi:10.​1007/​s10107-014-0826-5
14.
15.
Combettes, P.L., Pesquet, J.-C.: A Douglas–Rachford splitting approach to nonsmooth convex variational signal recovery. IEEE J. Sel. Topics Signal Proc. 1, 564–574 (2007)CrossRef
16.
Combettes, P.L., Wajs, V.R.: Signal recovery by proximal forward-backward splitting. SIAM J. Multiscale Model. Simul. 4, 1168–1200 (2005)MathSciNetCrossRefMATH
17.
d’Aspremont, A., El Ghaoui, L., Jordan, M.I., Lanckriet, G.R.G.: A direct formulation for sparse PCA using semidefinite programming. SIAM Rev. 49, 434–448 (2007)MathSciNetCrossRefMATH
18.
Deng, W., Lai, M., Peng, Z., Yin, W.: Parallel multi-block ADMM with \(o(1/k)\) convergence. tech. report, UCLA CAM, 13–64 (2013)
19.
Deng, W., Yin, W.: On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. (2015)
20.
21.
Douglas, J., Rachford, H.H.: On the numerical solution of the heat conduction problem in 2 and 3 space variables. Trans. Am. Math. Soc. 82, 421–439 (1956)MathSciNetCrossRefMATH
22.
Eckstein, J.: Splitting methods for monotone operators with applications to parallel optimization. PhD thesis, Massachusetts Institute of Technology (1989)
23.
Eckstein, J.: Some saddle-function splitting methods for convex programming. Optim. Methods Softw. 4, 75–83 (1994)MathSciNetCrossRef
24.
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)MathSciNetCrossRefMATH
25.
Fazel, M., Pong, T., Sun, D., Tseng, P.: Hankel matrix rank minimization with applications to system identification and realization. SIAM J. Matrix Anal. Appl. 34, 946–977 (2013)MathSciNetCrossRefMATH
26.
Friedman, J., Hastie, T., Tibshirani, R.: Sparse inverse covariance estimation with the graphical lasso. Biostatistics 9, 432–441 (2008)CrossRefMATH
27.
Gabay, D.: Applications of the method of multipliers to variational inequalities. In: Augmented Lagrangian Methods: Applications to the Solution of Boundary Value Problems, M. Fortin and R. Glowinski (eds.), North-Hollan, Amsterdam (1983)
28.
Glowinski, R.: Numerical methods for nonlinear variational problems. Springer, Berlin (1984)CrossRefMATH
29.
Glowinski, R., Le Tallec, P.: Augmented lagrangian and operator-splitting methods in nonlinear mechanics. SIAM, Philadelphia (1989)CrossRefMATH
30.
31.
Goldfarb, D., Ma, S., Scheinberg, K.: Fast alternating linearization methods for minimizing the sum of two convex functions. tech. report, Department of IEOR, Columbia University. Preprint available at arXiv:​0912.​4571, (2010)
32.
Goldfarb, D., Ma, S., Scheinberg, K.: Fast alternating linearization methods for minimizing the sum of two convex functions. Math. Program. 141, 349–382 (2013)MathSciNetCrossRefMATH
33.
Goldstein, T., O’Donoghue, B., Setzer, S., Baraniuk, R.: Fast alternating direction optimization methods. SIAM J. Imaging Sci. 7, 1588–1623 (2014)MathSciNetCrossRefMATH
34.
35.
Han, D., Yuan, X.: Local linear convergence of the alternating direction method of multipliers for quadratic programs. SIAM J. Numer. Anal. 51, 3446–3457 (2013)MathSciNetCrossRefMATH
36.
He, B., Hou, L., Yuan, X.: On full Jacobian decomposition of the augmented Lagrangian method for separable convex programming. SIAM J. Optim. 25, 2274–2312 (2015)MathSciNetCrossRefMATH
37.
He, B., Tao, M., Yuan, X.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22, 313–340 (2012)MathSciNetCrossRefMATH
38.
He, B., Yuan, X.: On the \({O}(1/n)\) convergence rate of Douglas-Rachford alternating direction method. SIAM J. Numer. Anal. 50, 700–709 (2012)MathSciNetCrossRefMATH
39.
He, B., Yuan, X.: On nonergodic convergence rate of Douglas-Rachford alternating direction method of multipliers. Numer. Math. 130, 567–577 (2015)MathSciNetCrossRefMATH
40.
He, B.S., Liao, L., Han, D., Yang, H.: A new inexact alternating direction method for monotone variational inequalities. Math. Program. 92, 103–118 (2002)MathSciNetCrossRefMATH
41.
42.
Hong, M., Chang, T.-H., Wang, X., Razaviyayn, M., Ma, S., Luo, Z.-Q.: A block successive upper bound minimization method of multipliers for linearly constrained convex optimization (2014). arXiv:​1401.​7079
43.
44.
45.
Lauritzen, S.: Graphical models. Oxford University Press, Oxford (1996)MATH
46.
Li, L., Toh, K.-C.: An inexact interior point method for \(l_1\)-regularized sparse covariance selection. Math. Program. Comput. 2, 291–315 (2010)MathSciNetCrossRefMATH
47.
Lin, T., Ma, S., Zhang, S.: An extragradient-based alternating direction method for convex minimization. to appear in Foundations of Computational Mathematics (2015)
48.
Lin, T., Ma, S., Zhang, S.: On the global linear convergence of the ADMM with multi-block variables. SIAM J. Optim. 25, 1478–1497 (2015)MathSciNetCrossRefMATH
49.
50.
Lin, Z., Liu, R., Su, Z.: Linearized alternating direction method with adaptive penalty for low rank representation. in NIPS (2011)
51.
52.
Liu, R., Lin, Z.: Linearized alternating direction method with parallel splitting and adaptive penalty for separable convex programs in machine learning. in ACML (2013)
53.
Lustig, M., Donoho, D., Pauly, J.: Sparse MRI: the application of compressed sensing for rapid MR imaging. Magn. Reson. Med. 58, 1182–1195 (2007)CrossRef
54.
Ma, S.: Alternating direction method of multipliers for sparse principal component analysis. J. Oper. Res. Soc. China 1, 253–274 (2013)CrossRefMATH
55.
Ma, S., Goldfarb, D., Chen, L.: Fixed point and Bregman iterative methods for matrix rank minimization. Math. Program. Series A 128, 321–353 (2011)MathSciNetCrossRefMATH
56.
Ma, S., Xue, L., Zou, H.: Alternating direction methods for latent variable gaussian graphical model selection. Neural Comput. 25, 2172–2198 (2013)MathSciNetCrossRef
57.
Ma, S., Yin, W., Zhang, Y., Chakraborty, A.: An efficient algorithm for compressed MR imaging using total variation and wavelets. in CVPR, pp. 1–8 (2008)
58.
Malick, J., Povh, J., Rendl, F., Wiegele, A.: Regularization methods for semidefinite programming. SIAM J. Optim. 20, 336–356 (2009)MathSciNetCrossRefMATH
59.
Monteiro, R.D.C., Svaiter, B.F.: Iteration-complexity of block-decomposition algorithms and the alternating direction method of multipliers. SIAM J. Optim. 23, 475–507 (2013)MathSciNetCrossRefMATH
60.
Parikh, N., Boyd, S.: Block splitting for large-scale distributed learning. in NIPS (2011)
61.
Peng, Y., Ganesh, A., Wright, J., Xu, W., Ma, Y.: RASL: robust alignment by sparse and low-rank decomposition for linearly correlated images. IEEE Trans. Pattern Anal. Mach. Intell. 34, 2233–2246 (2012)CrossRef
62.
Qin, Z., Goldfarb, D., Ma, S.: An alternating direction method for total variation denoising. Optim. Methods Softw. 30, 594–615 (2015)MathSciNetCrossRefMATH
63.
Recht, B., Fazel, M., Parrilo, P.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471–501 (2010)MathSciNetCrossRefMATH
64.
Scheinberg, K., Ma, S., Goldfarb, D.: Sparse inverse covariance selection via alternating linearization methods. in NIPS (2010)
65.
Scheinberg, K., Rish, I.: Learning sparse Gaussian Markov networks using a greedy coordinate ascent approach. In: Proceedings of the 2010 European conference on machine learning and knowledge discovery in databases: Part III, ECML PKDD’10, Berlin, Heidelberg, Springer-Verlag, pp. 196–212 (2010)
66.
Tao, M., Yuan, X.: Recovering low-rank and sparse components of matrices from incomplete and noisy observations. SIAM J. Optim. 21, 57–81 (2011)MathSciNetCrossRefMATH
67.
Tibshirani, R.: Regression shrinkage and selection via the lasso. J. Royal. Statist. Soc. B. 58, 267–288 (1996)MathSciNetMATH
68.
Wang, C., Sun, D., Toh, K.-C.: Solving log-determinant optimization problems by a Newton-CG primal proximal point algorithm. SIAM J. Optim. 20, 2994–3013 (2010)MathSciNetCrossRefMATH
69.
Wang, X., Hong, M., Ma, S., Luo, Z.-Q.: Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers. Pacific J. Optim. 11, 645–667 (2015)MathSciNetMATH
70.
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)MathSciNetCrossRefMATH
71.
Wen, Z., Goldfarb, D., Yin, W.: Alternating direction augmented Lagrangian methods for semidefinite programming. Math. Program. Comput. 2, 203–230 (2010)MathSciNetCrossRefMATH
72.
73.
Xue, L., Ma, S., Zou, H.: Positive definite \(\ell _1\) penalized estimation of large covariance matrices. J. Am. Stat. Assoc. 107, 1480–1491 (2012)MathSciNetCrossRefMATH
74.
Yang, J., Yuan, X.: Linearized augmented lagrangian and alternating direction methods for nuclear norm minimization. Math. Comput. 82, 301–329 (2013)MathSciNetCrossRefMATH
75.
Yang, J., Zhang, Y.: Alternating direction algorithms for \(\ell _1\) problems in compressive sensing. SIAM J. Sci. Comput. 33, 250–278 (2011)MathSciNetCrossRef
76.
Yang, J., Zhang, Y., Yin, W.: A fast TVL1-L2 algorithm for image reconstruction from partial fourier data. IEEE J. Sel. Top. Signal Proces. Spec. Issue Compress. Sens. 4, 288–297 (2010)CrossRef
77.
78.
79.
Zhang, X., Burger, M., Bresson, X., Osher, S.: Bregmanized nonlocal regularization for deconvolution and sparse reconstruction. SIAM J. Imaging Sci. 3, 253–276 (2010)MathSciNetCrossRefMATH
80.
Zhou, Z., Li, X., Wright, J., Candès, E.J., Ma, Y.: Stable principal component pursuit. Proceedings of International Symposium on Information Theory (2010)
81.
Zou, H., Hastie, T., Tibshirani, R.: Sparse principal component analysis. J. Comput. Graph. Stat. 15, 265–286 (2006)MathSciNetCrossRef
Metadata
Title
Alternating Proximal Gradient Method for Convex Minimization
Author
Shiqian Ma
Publication date
18-12-2015
Publisher
Springer US
Published in
Journal of Scientific Computing / Issue 2/2016
Print ISSN: 0885-7474
Electronic ISSN: 1573-7691
DOI
https://doi.org/10.1007/s10915-015-0150-0

Other articles of this Issue 2/2016

Journal of Scientific Computing 2/2016 Go to the issue

OriginalPaper

Positivity-Preserving High Order Finite Volume HWENO Schemes for Compressible Euler Equations

OriginalPaper

A Spectral Element Method with Transparent Boundary Condition for Periodic Layered Media Scattering

OriginalPaper

Solving Multi-linear Systems with $$\mathcal {M}$$ M -Tensors

OriginalPaper

Efficient Spectral-Galerkin Method and Analysis for Elliptic PDEs with Non-local Boundary Conditions

OriginalPaper

A Novel Scheme for Liouville’s Equation with a Discontinuous Hamiltonian and Applications to Geometrical Optics

OriginalPaper

An Efficient Implicit Compact Streamfunction Velocity Formulation of Two Dimensional Flows

Premium Partner

    Image Credits