Separable approximations and decomposition methods for the augmented Lagrangian

References

• A.J. Berger, J.M. Mulvey, and A. Ruszczyński, An extension of the DQA algorithm to convex stochastic programs, SIAM J. Optim. 4(4) (1994), pp. 735–753. doi: 10.1137/0804043
   Google Scholar
• D.P. Bertsekas, Extended monotropic programming and duality, Extended Monotropic Program Duality 139(2) (2008), pp. 209–225.
   Google Scholar
• D. Bertsekas, Constrained Optimization and Lagrange Multiplier Methods, Athena Scientific, Belmont, MA, 1996.
   Google Scholar
• E.G. Birgin and J.M. Martínez, Improving ultimate convergence of an augmented Lagrangian method, Optim. Methods Softw. 23(2) (2011), pp. 177–195. doi: 10.1080/10556780701577730
   Web of Science ®Google Scholar
• M. Blondel, K. Seki, and K. Uehara, Block coordinate descent algorithms for large-scale sparse multiclass classification, Mach. Learn. 93(1) (2013), pp. 31–52. doi: 10.1007/s10994-013-5367-2
   Web of Science ®Google Scholar
• J.K. Bradley, A. Kyrola, D. Bickson, and C. Guestrin, Parallel coordinate descent for L1-regularized loss minimization, in 28th International Conference on Machine Learning (ICML-11), L. Getoor and T. Scheffer, eds., ACM, June 2011, pp. 321–328.
   Google Scholar
• J. Eckstein, Augmented Lagrangian and alternating direction methods for convex optimization: A tutorial and some illustrative computational results. Technical report, December 2012. RUTCOR Research Report RRR 32–2012.
   Google Scholar
• J. Eckstein and D.P. Bertsekas, On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators, Math. Program. 55 (1992), pp. 293–318. doi: 10.1007/BF01581204
   Web of Science ®Google Scholar
• O. Fercoq, Parallel coordinate descent for the Adaboost problem, Technical report, University of Edinburgh, July 2013. arXiv:1310.1840v1 [cs.LG].
   Google Scholar
• O. Fercoq and P. Richtárik, Smoothed parallel coordinate descent method, Technical report, University of Edinburgh, 2013.
   Google Scholar
• A. Hamdi and A. Griewank, Properties of an augmented Lagrangian for design optimization, Optim. Methods Softw. 25(4) (2009), pp. 645–664. doi: 10.1080/10556780903270910
   Web of Science ®Google Scholar
• B.S. He, M. Tao, and X.M. Yuan, Alternating direction method with Gaussian back substitution for separable convex programming, SIAM J. Optim. 22(2) (2012), pp. 313–340. doi: 10.1137/110822347
   Web of Science ®Google Scholar
• M.R. Hestenes, Multiplier and gradient methods, J. Optim. Theory Appl. 4 (1969), pp. 303–320. doi: 10.1007/BF00927673
   Google Scholar
• M. Hong and Z.Q. Luo, On the linear convergence of the alternating direction method of multipliers. Technical report, August 2012. arXiv:1208.3922.
   Google Scholar
• C.-J. Hsieh, K.-W. Chang, C.-J. Lin, S. Sathiya Keerthi, and S. Sundararajan, A dual coordinate descent method for large-scale linear SVM. In ICML 2008, ACM, New York, 2008, pp. 408–415.
   Google Scholar
• Y.T. Lee and A. Sidford, Efficient accelerated coordinate descent methods and faster algorithms for solving linear systems. Technical report, 2013. arXiv:1305:1922v1.
   Google Scholar
• Y. Li and S. Osher, Coordinate descent optimization for l1 minimization with application to compressed sensing; a greedy algorithm, Inverse Probl. Imag. 3 (2009), pp. 487–503. doi: 10.3934/ipi.2009.3.487
   Web of Science ®Google Scholar
• Z. Lu and L. Xiao, On the complexity analysis of randomized block-coordinate descent methods. Technical report, May 2013. arXiv:1305.4723.
   Google Scholar
• Z. Lu and L. Xiao, Randomized block coordinate non-monotone gradient method for a class of nonlinear programming. Technical report, June 2013. arXiv:1306.5918.
   Google Scholar
• J.M. Mulvey and A. Ruszczyński, A diagonal quadratic approximation method for large scale linear programs, Oper. Res. Lett. 12 (1992), pp. 205–215. doi: 10.1016/0167-6377(92)90046-6
   Web of Science ®Google Scholar
• J.M. Mulvey and A. Ruszczyński, A new scenario decomposition method for large scale stochastic optimization, Oper. Res. 43(3) (1995), pp. 477–490. doi: 10.1287/opre.43.3.477
   Web of Science ®Google Scholar
• I. Necoara, Y. Nesterov, and F. Glineur, Efficiency of randomized coordinate descent methods on optimization problems with linearly coupled constraints. Technical report, June 2012.
   Google Scholar
• I. Necoară and A. Patrascu, A random coordinate descent algorithm for optimization problems with composite objective function and linear coupled constraints, Comput. Optim. Appl. 57(2) (2014), pp. 307–337. doi: 10.1007/s10589-013-9598-8
   Web of Science ®Google Scholar
• Y. Nesterov, Efficiency of coordinate descent methods on huge-scale optimization problems, SIAM J. Optim. 22(2) (2012), pp. 341–362. doi: 10.1137/100802001
   Web of Science ®Google Scholar
• A. Patrascu and I. Necoara, Efficient random coordinate descent algorithms for large-scale structured nonconvex optimization. Technical report, University Politehnica Bucharest, May 2013.
   Google Scholar
• M.J.D. Powell, A method for nonlinear constraints in minimization problems, in Optimization, R. Fletcher, ed., Academic Press, New York, 1972, pp. 283–298.
   Google Scholar
• Z.T. Qin, K. Scheinberg and D. Goldfarb, Efficient block-coordinate descent algorithms for the group lasso, Math. Program. Comput. 5(2) (2013), pp. 143–169. doi: 10.1007/s12532-013-0051-x
   Google Scholar
• P. Richtárik and M. Takáč, Efficient serial and parallel coordinate descent methods for huge-scale truss topology design, in Operations Research Proceedings 2011, D. Klatte, H.-J. Lüthi, and K. Schmedders, (eds.), Springer, Berlin, 2012, pp. 27–32.
   Google Scholar
• P. Richtárik and M. Takáč, Iteration complexity of randomized block-coordinate descent methods for minimizing a composite function, Math. Program. Ser. A, 144 (2012), pp. 1–38. doi: 10.1007/s10107-012-0614-z
   Web of Science ®Google Scholar
• P. Richtárik and M. Takáč, Parallel coordinate descent methods for big data optimization. Technical report, November 2012. arXiv:1212.0873.
   Google Scholar
• P. Richtárik and M. Takáč, Efficiency of randomized coordinate descent methods on minimization problems with a composite objective function. 4th Workshop on Signal Processing with Adaptive Sparse Structured Representations, June 2011.
   Google Scholar
• R. Tyrell Rockafellar, The multiplier method of Hestenes and Powell applied to convex programming, J. Optim. Theory Appl. 12 (1973), pp. 555–562. doi: 10.1007/BF00934777
   Web of Science ®Google Scholar
• R. Tyrell Rockafellar, Augmented Lagrangians and applications of the proximal point algorithm in convex programming, Math. Oper Res. 1 (1976), pp. 97–116. doi: 10.1287/moor.1.2.97
   Google Scholar
• R. Tyrell Rockafellar and R.J.-B. Wets, Scenarios and policy aggregation in optimization under uncertainty, Math. Oper. Res. 16 (1991), pp. 1–23. doi: 10.1287/moor.16.1.1
   Web of Science ®Google Scholar
• A. Ruszczyński, An augmented Lagrangian method for block diagonal linear programming problems, Oper. Res. Lett. 8 (1989), pp. 287–294. doi: 10.1016/0167-6377(89)90055-2
   Web of Science ®Google Scholar
• A. Ruszczyński, On convergence of an augmented Lagrangian decomposition method for sparse convex optimization, Math. Oper. Res. 20(3) (1995), pp. 634–656. doi: 10.1287/moor.20.3.634
   Web of Science ®Google Scholar
• H. Schwarz, Über einen Grenzübergang durch alternierendes Verfahren, Vierteljahrsschrift der Naturforschenden Gesellschaft in Zürich 15 (1870), pp. 272–286.
   Google Scholar
• S. Shalev-Shwartz and A. Tewari, Stochastic methods for ℓ1 regularized loss minimization, in Proceedings of the 26th International Conference on Machine Learning, L. Bottou and M. Littman, eds., Omnipress, Montreal, June 2009, pp. 929–936.
   Google Scholar
• S. Shalev-Shwartz and T. Zhang, Stochastic dual coordinate ascent methods for regularized loss minimization, J. Mach. Learn. Res. 14 (2013), pp. 567–599.
   Web of Science ®Google Scholar
• G. Stephanopoulos and A.W. Westerberg, The use of Hestenes’ method of multipliers to resolve dual gaps in engineering system optimization, J. Optim. Theory Appl. 15 (1975), pp. 285–309. doi: 10.1007/BF00933339
   Web of Science ®Google Scholar
• M. Takáč, A. Bijral, P. Richtárik, and N. Srebro, Mini-batch primal and dual methods for SVMs, in 30th International Conference on Machine Learning, Volume 28 of JMLR: Workshop and Conference Proceedings, S. Dasgupta and D. McAllester, eds., Microtome Publishing, Atlanta, GA, 2013, pp. 1022–1030.
   Google Scholar
• R. Tappenden, P. Richtárik, and J. Gondzio, Inexact coordinate descent: Complexity and preconditioning. Technical report, University of Edinburgh, April 2013. arXiv:1304.5530.
   Google Scholar
• P. Tseng, Convergence of a block coordinate descent method for nondifferentiable minimization, J. Optim. Theory Appl. 109 (2001), pp. 475–494. doi: 10.1023/A:1017501703105
   Web of Science ®Google Scholar
• X. Wang, M. Hong, S. Ma, and Z.Q. Luo, Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers. Technical report, August 2013. arXiv:1308.5294.
   Google Scholar
• N. Watanabe, Y. Nishimura, and M. Matsubara, Decomposition in large system optimization using the method of multipliers, J. Optim. Theory Appl. 25 (1978), pp. 181–193. doi: 10.1007/BF00933211
   Web of Science ®Google Scholar