Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Inexact accelerated augmented Lagrangian methods

  • Published:
Computational Optimization and Applications Aims and scope Submit manuscript

Abstract

The augmented Lagrangian method (ALM) is a popular method for solving linearly constrained convex minimization problems, and it has been used in many applications such as compressive sensing or image processing. Recently, accelerated versions of the augmented Lagrangian method (AALM) have been developed, and they assume that the subproblem can be exactly solved. However, the subproblem of the augmented Lagrangian method in general does not have a closed-form solution. In this paper, we introduce an inexact version of an accelerated augmented Lagrangian method (I-AALM), with an implementable inexact stopping condition for the subproblem. It is also proved that the convergence rate of our method remains the same as the accelerated ALM, which is \({{\mathcal {O}}}(\frac{1}{k^2})\) with an iteration number \(k\). In a similar manner, we propose an inexact accelerated alternating direction method of multiplier (I-AADMM), which is an inexact version of an accelerated ADMM. Numerical applications to compressive sensing or image inpainting are also presented to validate the effectiveness of the proposed iterative algorithms.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Alber, Y.I., Burachik, R.S., Iusem, A.N.: A proximal point method for nonsmooth convex optimization problems in Banach spaces. Abstr. Appl. Anal. 2, 97–120 (1997)

    Article  MATH  MathSciNet  Google Scholar 

  2. Beck, A., Teboulle, M.: A fast iterative shrinkage-threshoilding algorithm for linear inverse problems. SIAM J. Imag. Sci. 2(1), 183–202 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  3. Benfenati, A., Ruggiero, V.: Inexact Bregman iteration with an application to poisson data reconstruction. Inverse Probl. 29(6), 065,016 (2013)

    Article  MathSciNet  Google Scholar 

  4. Bertsekas, D.P.: Constrained Optimization and Lagrange Multiplier Methods. Athena Scientific, New York (1996)

    Google Scholar 

  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), 1–122 (2010)

    Article  MATH  Google Scholar 

  6. Cai, J., Osher, S., Shen, Z.: Linearized Bregman iterations for compressed sensing. Math. Comput. 78, 1515–1536 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  7. Candés, E., Romberg, J., Tao, T.: Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information. IEEE Trans. Inf. Thoery 52(2), 489–509 (2006)

    Article  MATH  Google Scholar 

  8. Daubechies, I., Defrise, M., Mol, C.D.: An iterative thresholding algorithm for linear inverse problems with a sparsity constraint. Commun. Pure Appl. Math. 57, 1413–1457 (2004)

    Article  MATH  Google Scholar 

  9. Donga, F., Zhangb, H., Kongc, D.X.: Nonlocal total variation models for multiplicative noise removal using split Bregman iteration. Math. Comput. Model. 55, 939–954 (2012)

    Article  Google Scholar 

  10. Douglas, J., Rachford, H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Am. Math. Soc. 82(3), 421–439 (1956)

    Article  MATH  MathSciNet  Google Scholar 

  11. Elad, M., Matalon, B., Zibulevsky, M.: Subspace optimization methods for linear least squares with non-quadratic regularization. Appl. Comput. Harmon. Anal. 23, 346–367 (2007)

    Article  MATH  MathSciNet  Google Scholar 

  12. Esser, E.: Applications of Lagrangian-based alternating direction methods and connections to split-Bregman. UCLA CAM Report 09–31 (2009)

  13. Freiedlander, J., Tseng, P.: Exact regularization of convex programs. SIAM J. Opt. 18(4), 1326–1350 (2007)

    Article  Google Scholar 

  14. Goldstein, T., O’Donoghue, B., Setzer, S.: Fast alternating direction optimization methods. UCLA CAM Report, pp. 12–35 (2012)

  15. Goldstein, T., Osher, S.: The split Bregman method for l1-regularized problems. SIAM J. Imag. Sci. 2(2), 323–343 (2009)

    Article  MATH  MathSciNet  Google Scholar 

  16. Hale, E., Yin, W., Zhang, Y.: Fixed-point continuation applied to compressed sensing: implementation and numerical experiments. J. Comput. Math. 28, 170–194 (2010)

    MATH  MathSciNet  Google Scholar 

  17. He, B., Yang, H.: Some convergence properties of a method of multipliers for linearly constrained monotone variational inequalities. Oper. Res. Lett. 23, 151–161 (1998)

    Article  MATH  MathSciNet  Google Scholar 

  18. He, B., Yuan, X.: The acceleration of augmented Lagrangian method for linearly constrained optimization. Optimization online  www.optimization-online.org/DBFILE/2010/10/2760.pdf (2010)

  19. He, B., Yuan, X.: An accelerated inexact proximal point algorithm for convex minimization. J. Optim. Thoery Appl. 154(2), 536–548 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  20. Hestenes, M.R.: Multiplier and gradient methods. J. Optim. Thoery Appl. 4, 303–320 (1969)

    Article  MATH  MathSciNet  Google Scholar 

  21. Hiriart-Urruty, J.B., Lemarechal, C.: Convex Analysis and Minimization Algorithms: Part 1: Fundamentals. Springer-Verlag, New York (1996)

    Google Scholar 

  22. Huang, B., Ma, S., Goldfarb, D.: Accelerated linearized Bregman method. J. Sci. Comput. 54, 428–453 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  23. Jiang, K., Sun, D., Toh, K.C.: An inexact accelerated proximal gradient method for large scale linearly constrained convex SDP. SIAM J. Optim. 22(3), 1042–1064 (2012)

    Article  MATH  MathSciNet  Google Scholar 

  24. Kang, M., Yun, S., Woo, H., Kang, M.: Accelerated bregman method for linearly constrained \(\ell _1\) -\(\ell _2\) minimization. J. Sci. Comput. 56(3), 515–534 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  25. Nedelcu, V., Necoara, I.: Iteration complexity of an inexact augmented Lagrangian method for constrained mpc. Paper presented at the IEEE 51st annual conference on decision and control, pp. 650–655 (2012)

  26. Nesterov, Y.: Gradient methods for minimizing composite objective function. CORE (2007)

  27. Ng, M.K., Wang, F., Yuan, X.: Inexact alternating direction methods for image recovery. SIAM J. Sci. Comput. 33(4), 1643–1668 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  28. Ochs, P., Brox, T., Pock, T.: ipiasco : Inertial proximal algorithm for strongly convex optimization. Manuscript (2014)

  29. Powell, M.J.D.: A Method for Nonlinear Constraints in Minimization Problems. Academic Press, New York (1972)

    Google Scholar 

  30. Rockafellar, R.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2), 97–116 (1976)

    Article  MATH  MathSciNet  Google Scholar 

  31. Rockafellar, R.T., Wets, R.B.: Variational Analysis. Springer, New York (1998)

    Book  MATH  Google Scholar 

  32. Setzer, S.: Operator splittings, Bregman methods and frame shrinkage in image processing. Int. J. Comput. Vis. 92, 265–280 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  33. Villa, S., Salzo, S., Baldassarre, L., Verri, A.: Accelerated and inexact forward–backward algorithms. SIAM J. Optim. 23(3), 1607–1633 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  34. Wang, Y., Yang, J., Yin, W., Zhang, Y.: A new alternating minimization algorithm for total variation image reconstruction. SIAM J. Imag. Sci. 1(3), 248–272 (2008)

    Article  MATH  MathSciNet  Google Scholar 

  35. Wright, S.J., Nowak, R.D., Figueiredo, M.A.T.: Sparse reconstruction by separable approximation. IEEE Trans. Signal Proc. 57, 2479–2493 (2009)

    Article  MathSciNet  Google Scholar 

  36. Yang, J., Zhang, Y.: Alternating direction algorithms for \(\ell _1\)-problems in compressive sensing. SIAM J. Sci. Comput. 33(1), 250–278 (2011)

    Article  MATH  MathSciNet  Google Scholar 

  37. Yang, J., Zhang, Y., Yin, W.: A fast alternating direction method for TV L1–L2 signal reconstruction from partial fourier data. IEEE J. Sel. Top. Signal Process. 4(2), 288–297 (2010)

    Article  Google Scholar 

  38. Yang, Y., Möller, M., Osher, S.: A dual split Bregman method for fast \(\ell _1\) minimization. Math. Comput. 82(284), 2061–2085 (2013)

    Article  MATH  Google Scholar 

  39. Yin, W.: Analysis and generalizations of the linearized Bregman method. SIAM J. Imag. Sci. 3(4), 856–877 (2010)

    Article  MATH  Google Scholar 

  40. Yin, W., Osher, S.: Error forgetting of Bregman iteration. J. Sci. Comput. 54, 684–695 (2013)

    Article  MATH  MathSciNet  Google Scholar 

  41. Yin, W., Osher, S., Goldfarb, D., Darbon, J.: Bregman iterative algorithms for \(\ell _1\)-minimization with applications to compressive sensing. SIAM J. Imag. Sci. 1(1), 143–168 (2008)

    Article  MATH  MathSciNet  Google Scholar 

Download references

Acknowledgments

Myeongmin Kang was supported by BK21 PLUS SNU Mathematical Sciences Division. Myungjoo Kang was supported by Basic Sciences Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Science, ICT and future Planning (2014R1A2A1A10050531) and MOTIE (10048720). Miyoun Jung was supported by Hankuk University of Foreign Studies Research Fund.

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, Seoul National University, Seoul, Korea

    Myeongmin Kang & Myungjoo Kang

  2. Department of Mathematics, Hankuk University of Foreign Studies, Yongin, Korea

    Miyoun Jung

Authors
  1. Myeongmin Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Myungjoo Kang
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Miyoun Jung
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Miyoun Jung.

Appendix

Appendix

1.1 Proof of Theorem 2

Proof

Let \(h_k = t_k^2(D(\lambda ^*) - D(\lambda _k)) \ge 0\) and \(p_k = \frac{1}{2\tau }\Vert s_k\Vert ^2_2.\) By Remark 1 with setting \(\gamma = \lambda ^*\), we have

$$\begin{aligned} -h_1\ge & {} \frac{1}{\tau }(\lambda ^* - \hat{\lambda }_{1})^T(\hat{\lambda }_{1} - \lambda _{1}) + \frac{1}{2\tau }\Vert \hat{\lambda }_{1} - \lambda _{1}\Vert ^2_2 - \frac{1}{t_2^2}\epsilon _{0}^2 + (\lambda ^* - \lambda _{1})^T(\eta ^1_{1} + \eta ^2_{1}) \nonumber \\= & {} \frac{1}{2\tau }\Vert \lambda _1 - \lambda ^*\Vert ^2_2 - \frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2 - \frac{1}{t_2^2}\epsilon _{0}^2 + (\lambda ^* - \lambda _{1})^T(\eta ^1_{1} + \eta ^2_{1})\nonumber \\= & {} p_1 - \frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2 - \frac{1}{t_2^2}\epsilon _{0}^2 + (s_1)^T(\eta ^1_{1} + \eta ^2_{1}). \end{aligned}$$
(47)

From the inexact conditions (32) and (33) of subproblems in the I-AADMM, we note that

$$\begin{aligned} (s_k)^T(\eta ^1_{k} + \eta ^2_{k})\le & {} \Vert s_k\Vert _2(\Vert \eta ^1_k\Vert _2 + \Vert \eta ^2_k\Vert _2)\nonumber \\\le & {} \Vert s_k\Vert _2\left( \frac{\sqrt{\rho (B^TB)}}{\sigma _H}\Vert \delta _k\Vert _2 + \frac{\sqrt{\rho (C^TC)}}{\sigma _G}\Vert \xi _k\Vert _2\right) \nonumber \\\le & {} \Vert s_k\Vert _2\frac{\epsilon _k}{t_{k}} \le \sqrt{2\tau p_k} \frac{\epsilon _k}{t_{k}}. \end{aligned}$$
(48)

Then, from the inequalities (47)–(48) and by setting \(\epsilon _{-1} = \epsilon _0,\) we obtain

$$\begin{aligned} h_1 + p_1 \le \frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2 + \epsilon _0^2 + \epsilon _1\sqrt{2\tau p_1} = \frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2 + \epsilon _{-1}^2 + \epsilon _1\sqrt{2\tau p_1}.\nonumber \\ \end{aligned}$$
(49)

Furthermore, by Lemma 8 and the inequality (48), we have

$$\begin{aligned} h_{k+1} + p_{k+1} \le h_k + p_k + \epsilon _{k-1}^2 + \sqrt{2\tau p_{k+1}}\epsilon _{k+1}. \end{aligned}$$
(50)

The inequalities (49) and (50) yield that

$$\begin{aligned} \frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2\ge & {} h_1 + p_1 - \epsilon _{-1}^2 - \epsilon _1\sqrt{2\tau p_1}\nonumber \\\ge & {} h_2 + p_2 - \epsilon _{-1}^2 - \epsilon _0^2 - \epsilon _1\sqrt{2\tau p_1} - \epsilon _2\sqrt{2\tau p_2}\nonumber \\\ge & {} \cdots \ge h_k + p_k - q_k, \end{aligned}$$
(51)

where \( q_k =\sqrt{2\tau p_1}\epsilon _1+ \cdots + \sqrt{2\tau p_k}\epsilon _k + \epsilon _{-1}^2 + \cdots + \epsilon _{k-2}^2.\) Since \(h_k\ge 0\) and due to the inequality (51), we have

$$\begin{aligned} q_k= & {} q_{k-1} + \epsilon _{k}\sqrt{2\tau p_k} + \epsilon _{k-2}^2 \le q_{k-1} + \epsilon _k\sqrt{2\tau \left( q_k+\frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2\right) } + \epsilon _{k-2}^2.\nonumber \\ \end{aligned}$$
(52)

Since \(\frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2 \ge p_1 -\epsilon _{-1}^2 -\epsilon _1\sqrt{2\tau p_1},\) we obtain the following, by the triangle inequality

$$\begin{aligned} \sqrt{p_1}\le & {} \frac{\epsilon _1\sqrt{2\tau } + \sqrt{2\tau \epsilon _1^2 + 4(\epsilon _{-1}^2 + \frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2)}}{2} \le \epsilon _1\sqrt{2\tau }\\&+\,\sqrt{\epsilon _{-1}^2+\frac{1}{2\tau }\Vert \lambda ^* - \hat{\lambda }_1\Vert ^2_2}. \end{aligned}$$

This inequality and the triangle inequality lead to

$$\begin{aligned} q_1 = \sqrt{2\tau p_1}\epsilon _1 + \epsilon _{-1}^2\le & {} \sqrt{2\tau }\epsilon _1\left[ \epsilon _1\sqrt{2\tau } + \sqrt{\epsilon _{-1}^2 + \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2}\right] + \epsilon _{-1}^2\nonumber \\\le & {} 2\tau \epsilon _1^2 +\epsilon _{-1}^2 + \epsilon _1(\sqrt{2\tau }\epsilon _{-1} + \Vert \lambda ^*-\hat{\lambda }_1\Vert _2). \end{aligned}$$
(53)

From (52), we have

$$\begin{aligned} \left( \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2+q_k\right) - \epsilon _{k}\sqrt{2\tau \left( q_k + \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2\right) } \\ - \left( \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2+ q_{k-1} +\epsilon _{k-2}^2\right) \le 0, \end{aligned}$$

i.e.,

$$\begin{aligned}&\sqrt{q_k + \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2} \nonumber \\&\quad \le \frac{1}{2}\left[ \sqrt{2\tau }\epsilon _k + \sqrt{2\tau \epsilon _k^2 + 4\left( \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2 + q_{k-1} + \epsilon _{k-2}^2\right) }\right] . \end{aligned}$$
(54)

Consequently, we obtain the following inequalities

$$\begin{aligned} q_k\le & {} q_{k-1} + \epsilon _{k-1}^2 + \epsilon _k^2 \tau +\frac{1}{2}\epsilon _{k}\sqrt{2\tau }\sqrt{2\tau \epsilon _k^2 + 4\left( \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert ^2_2 + q_{k-1} + \epsilon _{k-2}^2\right) } \nonumber \\\le & {} q_{k-1} + \epsilon _{k-2}^2 +2 \epsilon _k^2 \tau + \epsilon _k\left( \Vert \lambda ^*-\hat{\lambda }_1\Vert _2 + \sqrt{2\tau q_{k-1}} + \sqrt{2\tau }\epsilon _{k-2}\right) , \end{aligned}$$
(55)

where the first inequality is from (52) and (54), and the last inequality is from the triangle inequality.

By summing the inequality (55) from \(2\) to \(k\), we have

$$\begin{aligned} q_k\le & {} q_1 + \sum _{j=2}^{k} \epsilon _{j-2}^2 + 2\tau \sum _{j=2}^{k}\epsilon _j^2 + \Vert \lambda ^*-\hat{\lambda }_1\Vert _2 \sum _{j=2}^{k} \epsilon _{j}+ \sqrt{2\tau }\sum _{j=2}^{k} \epsilon _{j}(\sqrt{ q_{j-1}} + \epsilon _{j-2})\\\le & {} \sum _{j=1}^{k} \epsilon _{j-2}^2+ 2\tau \sum _{j=1}^{k}\epsilon _j^2 + \Vert \lambda ^*-\hat{\lambda }_1\Vert _2 \sum _{j=1}^{k} \epsilon _{j} + \sum _{j=1}^k \epsilon _j \sqrt{2\tau q_j} + \sqrt{2\tau }\sum _{j=1}^k \epsilon _j\epsilon _{j-2}\\\le & {} \sum _{j=1}^{k} \epsilon _{j-2}^2+ 2\tau \sum _{j=1}^{k}\epsilon _j^2 + \Vert \lambda ^*-\hat{\lambda }_1\Vert _2 \sum _{j=1}^{k} \epsilon _{j} + \sqrt{2\tau q_k}\sum _{j=1}^k \epsilon _j + \sqrt{2\tau }\sum _{j=1}^k \epsilon _j\epsilon _{j-2}\\\le & {} \Vert \lambda ^*-\hat{\lambda }_1\Vert _2\bar{\epsilon }_k + \tilde{\epsilon }_k + \sqrt{2\tau q_k}\bar{\epsilon }_k \end{aligned}$$

where the second inequality is from (53) and \(\epsilon _j\le \epsilon _{j+1}\). This implies that

$$\begin{aligned} \sqrt{q_k} \le \frac{1}{2}\left( \sqrt{2\tau }\bar{\epsilon }_k + \sqrt{2\tau \bar{\epsilon }_k^2 + 4\Vert \lambda ^*-\hat{\lambda }_1\Vert _2\bar{\epsilon }_k + 4\tilde{\epsilon }_k}\right) . \end{aligned}$$

From here, we have \(q_k \le 2\tau \bar{\epsilon }_k^2 + 2 \Vert \lambda ^*-\hat{\lambda }_1\Vert _2\bar{\epsilon }_k + 2\tilde{\epsilon }_k\), by the arithmetic mean-geometric mean inequality.

Since \(h_k \le \frac{1}{2\tau }\Vert \lambda ^*-\hat{\lambda }_1\Vert _2^2 + q_k,\) we get to the final inequality

$$\begin{aligned} h_k \le \left( \sqrt{2\tau }\bar{\epsilon }_k + \frac{1}{\sqrt{2\tau }}\Vert \lambda ^* - \hat{\lambda }_1\Vert _2\right) ^2 + 2\tilde{\epsilon }_k. \end{aligned}$$

\(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Kang, M., Kang, M. & Jung, M. Inexact accelerated augmented Lagrangian methods. Comput Optim Appl 62, 373–404 (2015). https://doi.org/10.1007/s10589-015-9742-8

Download citation

  • Received:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10589-015-9742-8

Keywords

Search

Navigation