×

A fast dual proximal-gradient method for separable convex optimization with linear coupled constraints. (English) Zbl 1352.90071

Summary: In this paper we consider a class of separable convex optimization problems with linear coupled constraints arising in many applications. Based on Nesterov’s smoothing technique and a fast gradient scheme, we present a fast dual proximal-gradient method to solve this class of problems. Under some conditions, we then give the convergence analysis of the proposed method and show that the computational complexity bound of the method for achieving an \(\varepsilon\)-optimal feasible solution is \(\mathcal{O}(1/\varepsilon)\). To further accelerate the proposed algorithm, we utilize a restart technique by successively decreasing the smoothing parameter. The advantage of our algorithms allows us to obtain the dual and primal approximate solutions simultaneously, which is fast and can be implemented in a parallel fashion. Several numerical experiments are presented to illustrate the effectiveness of the proposed algorithms. The numerical results validate the efficiency of our methods.

MSC:

90C25 Convex programming
90C52 Methods of reduced gradient type

Software:

NESTA
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Aybat, N.S., Iyengar, G.: A first-order smoothed penalty method for compressed sensing. SIAM J. Optim. 21, 287-313 (2011) · Zbl 1219.90123 · doi:10.1137/090762294
[2] Aybat N.S., Wang Z.: A parallel method for large scale convex regression problems. In: 53rd IEEE Conference on Decision and Control, pp. 5710-5717. (2014). doi:10.1109/CDC.2014.7040283
[3] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183-202 (2009) · Zbl 1175.94009 · doi:10.1137/080716542
[4] Becker, S., Bobin, J., Candès, E.J.: NESTA: a fast and accurate first-order method for sparse recovery. SIAM J. Imaging Sci. 4, 1-39 (2011) · Zbl 1209.90265 · doi:10.1137/090756855
[5] Bertsekas, D.P., Tsitsiklis, J.N.: Parallel and Distributed Computation, Numerical Methods. Prentice-Hall, Englewood Cliffs (1989) · Zbl 0743.65107
[6] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Foundations and Trends \[@\]@ in. Mach. Learn. 3, 1-122 (2011) · Zbl 1229.90122 · doi:10.1561/2200000016
[7] Cai, X.J., Gu, G.Y., He, B.S.: On the \[O(1/t)O\](1/t) convergence rate of the projection and contraction methods for variational inequalities with Lipschitz continuous monotone operators. Comput. Optim. Appl. 57, 339-363 (2014) · Zbl 1304.90203 · doi:10.1007/s10589-013-9599-7
[8] Chen, G., Teboulle, M.: A proximal-based decomposition method for convex minimization problems. Math. Program. 64, 81-101 (1994) · Zbl 0823.90097 · doi:10.1007/BF01582566
[9] Connejo, A.J., Mínguez, R., Castillo, E., García-Bertrand, R.: Decomposition Techniques in Mathematical Programming: Engineering and Science Applications. Springer, Berlin (2006)
[10] Devolder, O., Glineur, F., Nesterov, Y.: Double smoothing technique for large-scale linearly constrained convex optimization. SIAM J. Optim. 22, 702-727 (2012) · Zbl 1257.90047 · doi:10.1137/110826102
[11] Dinh, Q.T., Savorgnan, C., Diehl, M.: Combining lagrangian decomposition and excessive gap smoothing technique for solving large-scale separable convex optimization problems. Comput. Optim. Appl. 55(1), 75-111 (2013) · Zbl 1295.90048 · doi:10.1007/s10589-012-9515-6
[12] Gilpin, A., Pena, J., Sandholm, T.: First-order algorithm with \[O(\ln (1/\varepsilon ))O\](ln(1/ε)) convergence for \[\varepsilon\] ε-equilibrium. Math. Program. 133, 279-298 (2012) · Zbl 1243.91004 · doi:10.1007/s10107-010-0430-2
[13] Goldfarb, D., Ma, S.: Fast multiple splitting algorithms for convex optimization. SIAM J. Optim. 22, 533-556 (2012) · Zbl 1254.65075 · doi:10.1137/090780705
[14] He, N., Juditsky, A., Nemirovski, A.: Mirror Prox algorithm for multi-term composite minimization and semi-separable problems. Comput. Optim. Appl. (2015). doi:10.1007/s10589-014-9723-3 · Zbl 1321.65105 · doi:10.1007/s10589-014-9723-3
[15] He, B.S., Tao, M., Yuan, X.M.: Alternating direction method with Gaussian back substitution for separable convex programming. SIAM J. Optim. 22, 313-340 (2012) · Zbl 1273.90152 · doi:10.1137/110822347
[16] Li, J., Wu, C., Wu, Z., Long, Q., Wang, X.: Distributed proximal-gradient method for convex optimization with inequality constraints. J. ANZIAM 56, 160-178 (2014) · Zbl 1315.90029 · doi:10.1017/S1446181114000273
[17] Li, J., Wu, C., Wu, Z., Long, Q.: Gradient-free method for nonsmooth distributed optimization. J. Global Optim. 61, 325-340 (2015) · Zbl 1341.90135 · doi:10.1007/s10898-014-0174-2
[18] Li, J., Wu, Z., Wu, C., Long, Q., Wang, X.: An inexact dual fast gradient-projection method for separable convex optimization with linear coupled constraints. J. Optim. Theory Appl. (2015). doi:10.1007/s10957-015-0757-1 · Zbl 1332.90199 · doi:10.1007/s10957-015-0757-1
[19] Low, S.H., Lapsley, D.E.: Optimization flow control. I. Basic algorithm and convergence. IEEE/ACM Trans. Netw. 7, 861-874 (1999) · doi:10.1109/90.811451
[20] Necoara, I., Suykens, J.: Application of a smoothing technique to decomposition in convex optimization. IEEE Trans. Autom. Control 53, 2674-2679 (2008) · Zbl 1367.90085 · doi:10.1109/TAC.2008.2007159
[21] Necoara, I., Suykens, J.: Interior-point lagrangian decomposition method for separable convex optimization. J. Optim. Theory Appl. 143(3), 567-588 (2009) · Zbl 1184.90126 · doi:10.1007/s10957-009-9566-8
[22] Necoara, I., Nedelcu, V., Dumitrache, I.: Parallel and distributed optimization methods for estimation and control in networks. J. Process Control 21(5), 756-766 (2011) · doi:10.1016/j.jprocont.2010.12.010
[23] Nedic, A., Ozdaglar, A.: Approximate primal solutions and rate analysis for dual subgradient methods. SIAM J. Optim. 19, 1757-1780 (2009) · Zbl 1191.90037 · doi:10.1137/070708111
[24] Nesterov, Y.: Introductory Lectures on Convex Optimization: A Basic Course. Kluwer Academic Publishers, Boston (2004) · Zbl 1086.90045 · doi:10.1007/978-1-4419-8853-9
[25] Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Program. 103, 127-152 (2005) · Zbl 1079.90102 · doi:10.1007/s10107-004-0552-5
[26] Oliveira, L.B., Camponogara, E.: Multi-agent model predictive control of signaling split in urban traffic networks. Transp. Res. Part C 18, 120-139 (2010) · doi:10.1016/j.trc.2009.04.022
[27] Patrinos, P., Bemporad, A.: An accelerated dual gradient-projection algorithm for embedded linear model predictive control. IEEE Trans. Autom. Control 59(1), 18-33 (2014) · Zbl 1360.93400 · doi:10.1109/TAC.2013.2275667
[28] Rosa, C.H., Ruszczyński, A.: On augmented Lagrangian decomposition methods for multistage stochastic programs. Ann. Oper. Res. 64, 289-309 (1996) · Zbl 0857.90096 · doi:10.1007/BF02187650
[29] Samadi, P., Mohsenian-Rad, A., Schober, R., Wong, V.W.S., Jatskevich, J.: Optimal real-time pricing algorithm based on utility maximization for smart grid. In: Proceedings of IEEE International Conference on Smart Grid Communications, pp. 415-420 (2010) · Zbl 1219.90123
[30] Samadi, P., Mohsenian-Rad, A., Schober, R., Wong, V.W.S.: Advanced demand side management for the future smart grid using mechanism design. IEEE Trans. Smart Grid 3, 1170-1180 (2012) · doi:10.1109/TSG.2012.2203341
[31] Tseng, P.: On accelerated proximal gradient methods for convex-concave optimization. Department of Mathematics, University of Washington, Seattle, WA 98195, USA (2008)
[32] Wang, X., Hong, M., Ma, S., Luo, Z.: Solving multiple-block separable convex minimization problems using two-block alternating direction method of multipliers. http://arxiv.org/pdf/1308.5294v1 (2013) · Zbl 1332.65080
[33] Yang, J., Zhang, Y.: Alternating direction algorithms for \[\ell_1\] ℓ1-problems in compressive sensing. SIAM J. Sci. Comput. 33, 250-278 (2011) · Zbl 1256.65060 · doi:10.1137/090777761
[34] Zhao, G.: A Lagrangian dual method with self-concordant barriers for multistage stochastic convex programming. Math. Program. 102, 1-24 (2005) · Zbl 1058.90043 · doi:10.1007/s10107-003-0471-x
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.