Article
Full entry |
PDF
(0.7 MB)
Feedback
PDF
(0.7 MB)
Feedback
Keywords:
composite optimization; proximal augmented Lagrangian; projection-free
composite optimization; proximal augmented Lagrangian; projection-free
Summary:
This paper proposes a projection-free primal-dual dynamics for the nonsmooth composite optimization problems with equality and inequality constraints. To deal with optimization constraints, this paper departs from the use of gradient projection method, but resorts to the idea of mirror descent to design a continuous-time smooth optimization dynamics which advantageously leads to easier convergence analysis and more efficient numerical simulation. Also, the strategy of proximal augmented Lagrangian (PAL) is extended to incorporate general convex equality-inequality constraints and the strong convexity-concavity of the primal-dual variables is achieved, ensuring exponential convergence of the resulting algorithm. Furthermore, the convergence result in this paper extends existing exponential convergence which either takes no account of constraints or considers only affine linear constraints, and it also enhances existing asymptotic convergence under convex constraints which unfortunately depends on the complex gradient projection scheme.
References:
[1] Abbas, B., Attouch, H.: Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator. Optimization 64 (2015), 10, 2223-2252. DOI
[2] Adegbege, A. A., Kim, M. Y.: Saddle-point convergence of constrained primal-dual dynamics. IEEE Control Systems Lett. 5 (2021), 4, 1357-1362. DOI
[3] Afonso, M. V., Bioucas-Dias, J. M., Figueiredo, M. A. T.: Fast image recovery using variable splitting and constrained optimization. IEEE Trans. Image Process. 19 (2010), 9, 2345-2356. DOI
[4] Arrow, K. J., Hurwicz, L., Uzawa, H.: Studies in Linear and Non-Linear Programming. Stanford University Press, 1958.
[5] Bansode, P. A., Chinde, V., Wagh, S. R., Pasumarthy, R., Singh, N. M.: On the exponential stability of projected primal-dual dynamics on a riemannian manifold. DOI
[6] Başar, T., Olsder, G. J.: Dynamic Noncooperative Game Theory. SIAM, 1998.
[7] Beck, A., Teboulle, M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Jo. Imaging Sci. 2 (2009), 1, 183-202. DOI
[8] Ben-Tal, A., Ghaoui, L. El, Nemirovski, A.: Robust optimization. In: Robust Optimization, Princeton University Press, 2009.
[9] Benzi, M., Golub, G. H., Liesen, J.: Numerical solution of saddle point problems. Acta Numerica 14 (2005), 1-137. DOI
[10] Bickel, P. J., Levina, E.: Regularized estimation of large covariance matrices. Ann. Statist. 36 (2008), 1, 199-227. DOI
[11] Bin, M., Notarnicola, I., Parisini, T.: Semiglobal exponential stability of the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm for constrained optimization. Math. Programm. 208 (2024), 1, 629-660. DOI
[12] Bolte, J., Teboulle, M.: Barrier operators and associated gradient-like dynamical systems for constrained minimization problems. SIAM J. Control Optim. 42 (2003), 4, 1266-1292. DOI
[13] Boyd, S., Vandenberghe, L.: Convex Optimization. Cambridge University Press, 2004. DOI | Zbl 1058.90049
[14] Boyd, S., Parikh, N., Chu, E., Peleato, B., Eckstein, J., al., et: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Machine Learn. 3 (2011), 1, 1-122. DOI
[15] Bregman, L. M.: The relaxation method of finding the common points of convex sets and its application to the solution of problems in convex programming. USSR Comput. Math. Math. Phys. 7 (1967), 3, 200-217. DOI
[16] Browder, F. E.: Multi-valued monotone nonlinear mappings and duality mappings in banach spaces. Trans. Amer. Math. Soc. 118 (1965), 338-351. DOI
[17] Jr., R. E. Bruck: On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. J. Math. Anal. Appl. 61 (1977), 1, 159-164. DOI
[18] Charalamous, C.: Nonlinear least pth optimization and nonlinear programing. Math. Program 12 (1977), 1, 195-225. DOI
[19] Cherukuri, A., Gharesifard, B., Cortes, J.: Saddle-point dynamics: conditions for asymptotic stability of saddle points. SIAM J. Control Optim. 55 (2017), 1, 486-511. DOI
[20] Cherukuri, A., Mallada, E., Cortés, J.: Asymptotic convergence of constrained primal-dual dynamics. Systems Control Lett. 87 (2016), 10-15. DOI
[21] Cherukuri, A., Mallada, E., Low, S., Cortés, J.: The role of convexity in saddle-point dynamics: Lyapunov function and robustness. IEEE Trans. Automat. Control 63 (2018), 8, 2449-2464. DOI
[22] Cisneros-Velarde, P., Jafarpour, S., Bullo, F.: Distributed and time-varying primal-dual dynamics via contraction analysis. DOI
[23] Combettes, P. L., Wajs, V. R.: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4 (2005), 4, 1168-1200. DOI
[24] Dhingra, N. K., Khong, S. Z., Jovanović, M. R.: The proximal augmented Lagrangian method for nonsmooth composite optimization. IEEE Trans. Automat. Control 64 (2019), 7, 2861-2868. DOI
[25] Dhingra, N. K., Khong, S. Z., Jovanovic, M. R.: A second order primal-dual method for nonsmooth convex composite optimization. IEEE Trans. Automat. Control 67 (2021), 8, 4061-4076. DOI
[26] Ding, D., Jovanovic, M. R.: Global exponential stability of primal-dual gradient flow dynamics based on the proximal augmented Lagrangian: a Lyapunov-based approach. In: Proc. 59th IEEE Conference on Decision and Control, Jeju Island, 2020.
[27] Douglas, J., Rachford, H. H.: On the numerical solution of heat conduction problems in two and three space variables. Trans. Amer. Math. Soc. 82 (1956), 2, 421-439. DOI
[28] Eckstein, J., Yu, Ch.: Two innovations in inexact augmented Lagrangian methods for convex optimization. DOI
[29] Fazlyab, M., Ribeiro, A., Morari, M., Preciado, V. M.: Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM J. Optim. 28 (2018), 3, 2654-2689. DOI
[30] Feijer, D., Paganini, F.: Stability of primal-dual gradient dynamics and applications to network optimization. Automatica 46 (2010), 12, 1974-1981. DOI | Zbl 1205.93138
[31] Figueiredo, M. A. T., Nowak, R. D., Wright, S. J.: Gradient projection for sparse reconstruction: application to compressed sensing and other inverse problems. IEEE J. Selected Topics Signal Process. 1 (2007), 4, 586-597. DOI
[32] França, G., Robinson, D. P., Vidal, R.: Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization. Physical Rev. E 103 (2021), 5, 053304. DOI
[33] Goldsztajn, D., Paganini, F.: Proximal regularization for the saddle point gradient dynamics. IEEE Trans. Automat. Control 66 (2021), 9, 4385-4392. DOI
[34] Goodfellow, I., Pouget-Abadie, J., Mirza, M., Xu, B., Warde-Farley, D., Ozair, S., Courville, A., Bengio, Y.: Generative adversarial nets. Commun. ACM 63 (2020), 11, 139-144. DOI
[35] Hassan-Moghaddam, S., Jovanović, M. R.: Distributed proximal augmented Lagrangian method for nonsmooth composite optimization. In: 2018 Annual American Control Conference 2018, pp. 2047-2052.
[36] Hassan-Moghaddam, S., Jovanovic, M. R.: Global exponential stability of the douglas-rachford splitting dynamics. IFAC-PapersOnLine 53 (2020), 2, 7350-7354. DOI
[37] Hassan-Moghaddam, S., Jovanović, M. R.: Proximal gradient flow and douglas-rachford splitting dynamics: global exponential stability via integral quadratic constraints. Automatica 123 (2021), 109311. DOI
[38] Hast, M., {\AA}ström, K. J., Bernhardsson, B., Boyd, S.: Pid design by convex-concave optimization. In: 2013 European Control Conference 2013, pp. 4460-4465. DOI
[39] Hestenes, M. R.: Multiplier and gradient methods. J. Optim. Theory Appl. 4 (1969), 5, 303-320. DOI
[40] Hiriart-Urruty, J. B., Lemaréchal, C.: Fundamentals of Convex Analysis. Springer Science and Business Media, 2004.
[41] Ju, X., Che, H., Li, Ch., He, X.: Solving mixed variational inequalities via a proximal neurodynamic network with applications. Neural Process. Lett. 54 (2022), 1, 207-226. DOI
[42] Khalil, H. K.: Nonlinear Systems. Prentice-Hall, Upper Saddle River, NJ 1996. Zbl 1194.93083
[43] Kose, T: Solutions of saddle value problems by differential equations. Econometrica, J. Econometr. Soc. 1956, pp. 59-70. DOI 10.2307/1905259
[44] LeCun, Y., Bengio, Y., Hinton, G.: Deep learning. Nature 521 (2015), 7553, 436-444. DOI
[45] Lessard, L., Recht, B., Packard, A.: Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim. 26 (2016), 1, 57-95. DOI
[46] Lin, F., Fardad, M., Jovanović, M. R.: Design of optimal sparse feedback gains via the alternating direction method of multipliers. IEEE Trans. Automat. Control 58 (2013), 9, 2426-2431. DOI
[47] Mäkelä, M.: Survey of bundle methods for nonsmooth optimization. Optim. Methods Software 17 (2002), 1, 1-29. DOI
[48] Minty, G. J.: Monotone (nonlinear) operators in hilbert space. Duke Math. J. 29 (1962), 3, 341-346. DOI 10.1215/S0012-7094-62-02933-2
[49] Moreau, J.-J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. France 93 (1965), 273-299. DOI 10.24033/bsmf.1625
[50] Nemirovski, A., Juditsky, A., Lan, G., Shapiro, A.: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19 (2009), 4, 1574-1609. DOI
[51] Nemirovsky, A. S., Yudin, D. B.: Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons, Chichester 1983.
[52] Nesterov, Y.: Smooth minimization of non-smooth functions. Math. Programm. 103 (2005), 1, 127-152. DOI
[53] Neumann, J. v: Zur theorie der gesellschaftsspiele. Math. Ann. 100 (1928), 1, 295-320. DOI
[54] Nocedal, J., Wright, S. J.: Numerical Optimization. Springer, 1999. Zbl 1104.65059
[55] Passty, G. B.: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72 (1979), 2, 383-390. DOI
[56] Powell, M. J. D.: A method for nonlinear constraints in minimization problems. Optimization (1969), 283-298.
[57] Qu, G., Li, N.: On the exponential stability of primal-dual gradient dynamics. IEEE Control Systems Lett. 3 (2019), 1, 43-48. DOI
[58] Raginsky, M., Bouvrie, J.: Continuous-time stochastic mirror descent on a network: variance reduction, consensus, convergence. In: 51st IEEE Conference on Decision and Control 2012, pp. 6793-6800.
[59] Rockafellar, R. T.: Convex Analysis. Princeton University Press, 1970. Zbl 1011.49013
[60] Rockafellar, R. T.: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1 (1976), 2, 97-116. DOI 10.1287/moor.1.2.97
[61] Rockafellar, R. T.: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976), 5, 877-898. DOI | Zbl 0358.90053
[62] Shor, N. Z.: Minimization Methods for Non-differentiable Functions. Springer Science and Business Media, 2012.
[63] Sion, M.: On general minmax theorems. Pacific J. Math. 8 (1958), 1, 171-176. DOI 10.2140/pjm.1958.8.171
[64] Tang, Y., Qu, G., Li, N.: Semi-global exponential stability of augmented primal-dual gradient dynamics for constrained convex optimization. Systems Control Lett. 144 (2020), 104754. DOI
[65] Tibshirani, R.: Regression shrinkage and selection via the lasso. J. Royal Statist. Society: Series B (Methodological) 58 (1996), 1, 267-288. DOI
[66] Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38 (2000), 2, 431-446. DOI
[67] Wachsmuth, G.: On LICQ and the uniqueness of Lagrange multipliers. Oper. Res. Lett. 41 (2013), 1, 78-80. DOI
[68] Wang, Z., Wei, W., Zhao, Ch., Ma, Z., Zheng, Z., Zhang, Y., Liu, F.: Exponential stability of partial primal-dual gradient dynamics with nonsmooth objective functions. Automatica 129 (2021), 109585. DOI
Search
Partner of
