First-Order Methods for Constrained Convex Programming Based on Linearized Augmented Lagrangian Function

References

• Ahmadi H, Aybat NS, Shanbhag UV (2016) On the analysis of inexact augmented lagrangian schemes for misspecified conic convex programs. Proc. Amer. Control Conf. (ACC) (IEEE, Piscataway, NJ), 4841–4846.Google Scholar
• Aravkin AY, Burke JV, Drusvyatskiy D, Friedlander MP, Roy S (2019) Level-set methods for convex optimization. Math. Programming 174(1-2):359–390.Google Scholar
• Aybat NS, Iyengar G (2013) An augmented lagrangian method for conic convex programming. Preprint, submitted February 26, https://arxiv.org/abs/1302.6322v1.Google Scholar
• Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1):183–202.Google Scholar
• Ben-Tal A, Zibulevsky M (1997) Penalty/barrier multiplier methods for convex programming problems. SIAM J. Optim 7(2):347–366.Google Scholar
• Chambolle A, Ehrhardt MJ, Richtarik P, Schonlieb C-B (2018) Stochastic primal-dual hybrid gradient algorithm with arbitrary sampling and imaging applications. SIAM J. Optim. 28(4):2783–2808.Google Scholar
• Combettes PL, Pesquet J-C (2015) Stochastic quasi-fejér block-coordinate fixed point iterations with random sweeping. SIAM J. Optim. 25(2):1221–1248.Google Scholar
• Cui Y, Li X, Sun D, Toh K-C (2016) On the convergence properties of a majorized alternating direction method of multipliers for linearly constrained convex optimization problems with coupled objective functions. J. Optim. Theory Appl. 169(3):1013–1041.Google Scholar
• Dang C, Lan G (2014) Randomized first-order methods for saddle point optimization. Preprint, submitted September 30, https://arxiv.org/abs/1409.8625v4.Google Scholar
• Deng W, Yin W (2016) On the global and linear convergence of the generalized alternating direction method of multipliers. J. Sci. Comput. 66(3):889–916.Google Scholar
• Gao X, Zhang S-Z (2017) First-order algorithms for convex optimization with nonseparable objective and coupled constraints. J. Oper. Res. Soc. China 5(2):131–159.Google Scholar
• Gao X, Xu Y-Y, Zhang S-Z (2019) Randomized primal–dual proximal block coordinate updates. J. Oper. Res. Soc. China 7(2):205–250.Google Scholar
• Grant M, Boyd S, Ye Y (2008) CVX: Matlab Software for Disciplined Convex Programming.Google Scholar
• Hamedani EY, Aybat NS (2018) A primal-dual algorithm for general convex-concave saddle point problems. Preprint, submitted March 4, https://arxiv.org/abs/1803.01401v4.Google Scholar
• Hamedani EY, Aybat NS (2019) A decentralized primal-dual method for constrained minimization of a strongly convex function. Preprint, submitted August 30, https://arxiv.org/abs/1908.11835v1.Google Scholar
• Hamedani EY, Jalilzadeh A, Aybat NS, Shanbhag UV (2018) Iteration complexity of randomized primal-dual methods for convex-concave saddle point problems. Preprint, submitted June 11, https://arxiv.org/abs/1806.04118v2.Google Scholar
• He B, Yuan X (2015) On non-ergodic convergence rate of douglas–rachford alternating direction method of multipliers. Numerical Math. 130(3):567–577.Google Scholar
• He N, Juditsky A, Nemirovski A (2015) Mirror prox algorithm for multi-term composite minimization and semi-separable problems. Comput. Optim. Appl. 61(2):275–319.Google Scholar
• Hien LTK, Zhao R, Haskell WB (2017) An inexact primal-dual smoothing framework for large-scale non-bilinear saddle point problems. Preprint, submitted November 10, https://arxiv.org/abs/1711.03669v3.Google Scholar
• Hong M, Luo Z-Q (2017) On the linear convergence of the alternating direction method of multipliers. Math. Programming 162(1-2):165–199.Google Scholar
• Hong M, Chang T-H, Wang X, Razaviyayn M, Ma S, Luo Z-Q (2020) A block successive upper bound minimization method of multipliers for linearly constrained convex optimization. Preprint, January 26, https://arxiv.org/abs/1401.7079v1.Google Scholar
• Kolossoski O, Monteiro RDC (2017) An accelerated non-Euclidean hybrid proximal extragradient-type algorithm for convex–concave saddle-point problems. Optim. Methods Software 32(6):1244–1272.Google Scholar
• Lan G, Monteiro RDC (2016) Iteration-complexity of first-order augmented lagrangian methods for convex programming. Math. Programming 155(1-2):511–547.Google Scholar
• Lin Q, Nadarajah S, Soheili N (2018) A level-set method for convex optimization with a feasible solution path. SIAM J. Optim. 28(4):3290–3311.Google Scholar
• Liu Y-F, Liu X, Ma S (2019) On the nonergodic convergence rate of an inexact augmented lagrangian framework for composite convex programming. Math. Oper. Res. 44(2):632–650.Link, Google Scholar
• Lu Z, Zhou Z (2018) Iteration-complexity of first-order augmented lagrangian methods for convex conic programming. Preprint, submitted March 27, https://arxiv.org/abs/1803.09941v2.Google Scholar
• Necoara I, Patrascu A, Glineur F (2017) Complexity of first-order inexact lagrangian and penalty methods for conic convex programming. Optim. Methods Softw. 34(2):1–31.Google Scholar
• Nedelcu V, Necoara I, Tran-Dinh Q (2014) Computational complexity of inexact gradient augmented lagrangian methods: Application to constrained mpc. SIAM J. Control Optim. 52(5):3109–3134.Google Scholar
• Nedić A, Ozdaglar A (2009) Subgradient methods for saddle-point problems. J. Optim. Theory Appl. 142(1):205–228.Google Scholar
• Nemirovski A (2004) Prox-method with rate of convergence o(1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Google Scholar
• Nesterov Yu (2012) Efficiency of coordinate descent methods on huge-scale optimization problems. SIAM J. Optim. 22(2):341–362.Google Scholar
• Nesterov Yu (2013) Gradient methods for minimizing composite functions. Math. Programming 140(1):125–161.Google Scholar
• Ouyang Y, Xu Y (2019) Lower Complexity Bounds of First-Order Methods for Convex-Concave Bilinear Saddle-Point Problems. Mathematical Programming, Series A (Spring, Cham, Switzerland), 1–35.Google Scholar
• Pee EY, Royset JO (2011) On solving large-scale finite minimax problems using exponential smoothing. J. Optim. Theory Appl. 148(2):390–421.Google Scholar
• Peng Z, Wu T, Xu Y, Yan M, Yin W (2016a) Coordinate-friendly structures, algorithms and applications. Ann. Math. Sci. Appl. 1(1):57–119.Google Scholar
• Peng Z, Xu Y, Yan M, Yin W (2016b) Arock: An algorithmic framework for asynchronous parallel coordinate updates. SIAM J. Sci. Comput. 38(5):A2851–A2879.Google Scholar
• Razaviyayn M, Hong M, Luo Z-Q (2013) A unified convergence analysis of block successive minimization methods for nonsmooth optimization. SIAM J. Optim. 23(2):1126–1153.Google Scholar
• Rigollet P, Tong X (2011) Neyman-pearson classification, convexity and stochastic constraints. J. Machine Learn. Res. 12(Oct):2831–2855.Google Scholar
• Rockafellar TR (1973) A dual approach to solving nonlinear programming problems by unconstrained optimization. Math. Programming 5(1):354–373.Google Scholar
• Rockafellar TR (1976) Augmented lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1(2):97–116.Link, Google Scholar
• Scott C, Nowak R (2005) A neyman-pearson approach to statistical learning. IEEE Trans. Inform. Theory 51(11):3806–3819.Google Scholar
• Tseng P, Yun S (2009) A coordinate gradient descent method for nonsmooth separable minimization. Math. Programming 117(1-2):387–423.Google Scholar
• Xu Y (2017) Accelerated first-order primal-dual proximal methods for linearly constrained composite convex programming. SIAM J. Optim. 27(3):1459–1484.Google Scholar
• Xu Y (2018) Hybrid jacobian and gauss–seidel proximal block coordinate update methods for linearly constrained convex programming. SIAM J. Optim. 28(1):646–670.Google Scholar
• Xu Y (2019a) Asynchronous parallel primal–dual block coordinate update methods for affinely constrained convex programs. Comput. Optim. Appl. 72(1):87–113.Google Scholar
• Xu Y (2019b) Iteration Complexity of Inexact Augmented Lagrangian Methods for Constrained Convex Programming Mathematical Programming, Series A (Springer, Cham, Switzerland), 1–46.Google Scholar
• Xu Y, Yin W (2013) A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion. SIAM J. Imaging Sci. 6(3):1758–1789.Google Scholar
• Xu Y, Zhang S (2018) Accelerated primal–dual proximal block coordinate updating methods for constrained convex optimization. Comput. Optim. Appl. 70(1):91–128.Google Scholar
• Xu Y, Akrotirianakis I, Chakraborty A (2016) Proximal gradient method for huberized support vector machine. PAA Pattern Anal. Appl. 19(4):989–1005.Google Scholar
• Yu H, Neely MJ (2016) A primal-dual type algorithm with the O(1/t) convergence rate for large scale constrained convex programs. IEEE 55th Conf. Decision Control (CDC) (IEEE, New York), 1900–1905.Google Scholar
• Yu H, Neely MJ (2017) A primal-dual parallel method with o(1/∈) convergence for constrained composite convex programs. Preprint, submitted July 30, https://arxiv.org/abs/1708.00322v1.Google Scholar
• Zhao L, Zhu D (2018) First-order primal-dual method for nonlinear convex cone programs. Preprint, submitted December 31, https://arxiv.org/abs/1801.00261v4.Google Scholar