Kybernetika 61 no. 5, 610-634, 2025

A projection-free dynamics for nonsmooth composite optimization

Wei Ni, Yanyan Xiao and Yangfan QiuDOI: 10.14736/kyb-2025-5-0610

Abstract:

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.

Keywords:

composite optimization, proximal augmented Lagrangian, projection-free

Classification:

90C25, 90C30, 90C90

paper.pdf

References:

  1. B. Abbas and H. Attouch: 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:10.1080/02331934.2014.971412
  2. A. A. Adegbege and M. Y. Kim: Saddle-point convergence of constrained primal-dual dynamics. IEEE Control Systems Lett. 5 (2021), 4, 1357-1362.   DOI:10.1109/LCSYS.2020.3037876
  3. M. V. Afonso, J. M. Bioucas-Dias and M. A. T. Figueiredo: Fast image recovery using variable splitting and constrained optimization. IEEE Trans. Image Process. 19 (2010), 9, 2345-2356.   DOI:10.1109/TIP.2010.2047910
  4. K. J. Arrow, L. Hurwicz and H. Uzawa: Studies in Linear and Non-Linear Programming. Stanford University Press, 1958.   CrossRef
  5. P. A. Bansode, V. Chinde, S. R. Wagh, R. Pasumarthy and N. M. Singh: On the exponential stability of projected primal-dual dynamics on a riemannian manifold.    arXiv:1905.04521, 2019.
  6. T. Başar and G. J. Olsder: Dynamic Noncooperative Game Theory. SIAM, 1998.   CrossRef
  7. A. Beck and M. Teboulle: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM Jo. Imaging Sci. 2 (2009), 1, 183-202.   DOI:10.1137/080716542
  8. A. Ben-Tal, L. El Ghaoui and A. Nemirovski: Robust optimization. In: Robust Optimization, Princeton University Press, 2009.   CrossRef
  9. M. Benzi, G. H. Golub and J. Liesen: Numerical solution of saddle point problems. Acta Numerica 14 (2005), 1-137.   DOI:10.1017/S0962492904000212
  10. P. J. Bickel and E. Levina: Regularized estimation of large covariance matrices. Ann. Statist. 36 (2008), 1, 199-227.   DOI:10.1214/009053607000000758
  11. M. Bin, I. Notarnicola and T. Parisini: Semiglobal exponential stability of the discrete-time Arrow-Hurwicz-Uzawa primal-dual algorithm for constrained optimization. Math. Programm. 208 (2024), 1, 629-660.   DOI:10.1007/s10107-023-02051-2
  12. J. Bolte and M. Teboulle: Barrier operators and associated gradient-like dynamical systems for constrained minimization problems. SIAM J. Control Optim. 42 (2003), 4, 1266-1292.   DOI:10.1137/S0363012902410861
  13. S. Boyd and L. Vandenberghe: Convex Optimization. Cambridge University Press, 2004.   DOI:10.1017/S275390670000070X
  14. S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein and et al.: Distributed optimization and statistical learning via the alternating direction method of multipliers. Found. Trends Machine Learn. 3 (2011), 1, 1-122.   DOI:10.1561/2200000016
  15. L. M. Bregman: 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:10.1016/0041-5553(67)90040-7
  16. F. E. Browder: Multi-valued monotone nonlinear mappings and duality mappings in banach spaces. Trans. Amer. Math. Soc. 118 (1965), 338-351.   DOI:10.1090/S0002-9947-1965-0180884-9
  17. R. E. Bruck Jr.: 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:10.1016/0022-247x(77)90152-4
  18. C. Charalamous: Nonlinear least pth optimization and nonlinear programing. Math. Program 12 (1977), 1, 195-225.   DOI:10.1007/bf01593788
  19. A. Cherukuri, B. Gharesifard and J. Cortes: Saddle-point dynamics: conditions for asymptotic stability of saddle points. SIAM J. Control Optim. 55 (2017), 1, 486-511.   DOI10.1137/15M1026924
  20. A. Cherukuri, E. Mallada and J. Cortés: Asymptotic convergence of constrained primal-dual dynamics. Systems Control Lett. 87 (2016), 10-15.   DOI:10.1016/j.sysconle.2015.10.006
  21. A. Cherukuri, E. Mallada, S. Low and J. Cortés: The role of convexity in saddle-point dynamics: Lyapunov function and robustness. IEEE Trans. Automat. Control 63 (2018), 8, 2449-2464.   DOI:10.1109/TAC.2017.2778689
  22. P. Cisneros-Velarde, S. Jafarpour and F. Bullo: Distributed and time-varying primal-dual dynamics via contraction analysis.    arXiv:2003.12665, 2021.
  23. P. L. Combettes and V. R. Wajs: Signal recovery by proximal forward-backward splitting. Multiscale Model. Simul. 4 (2005), 4, 1168-1200.   DOI:10.1137/050626090
  24. N. K. Dhingra, S. Z. Khong and M. R. Jovanović: The proximal augmented Lagrangian method for nonsmooth composite optimization. IEEE Trans. Automat. Control 64 (2019), 7, 2861-2868.   DOI:10.1109/TAC.2018.2867589
  25. N. K. Dhingra, S. Z. Khong and M. R. Jovanovic: A second order primal-dual method for nonsmooth convex composite optimization. IEEE Trans. Automat. Control 67 (2021), 8, 4061-4076.   DOI:10.1109/TAC.2021.3115449
  26. D. Ding and M. R. Jovanovic: 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.   CrossRef
  27. J. Douglas and H. H. Rachford: On the numerical solution of heat conduction problems in two and three space variables. Trans. Amer. Math. Soc. 82 (1956), 2, 421-439.   DOI:10.1090/S0002-9947-1956-0084194-4
  28. J. Eckstein and Ch. Yu: Two innovations in inexact augmented Lagrangian methods for convex optimization.    arXiv preprint arXiv:2503.11809, 2025.
  29. M. Fazlyab, A. Ribeiro, M. Morari and V. M. Preciado: Analysis of optimization algorithms via integral quadratic constraints: Nonstrongly convex problems. SIAM J. Optim. 28 (2018), 3, 2654-2689.   DOI:10.1137/17M1136845
  30. D. Feijer and F. Paganini: Stability of primal-dual gradient dynamics and applications to network optimization. Automatica 46 (2010), 12, 1974-1981.   DOI:10.1016/j.automatica.2010.08.011
  31. M. A. T. Figueiredo, R. D. Nowak and S. J. Wright: 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:10.1109/jstsp.2007.910281
  32. G. França, D. P. Robinson and R. Vidal: Gradient flows and proximal splitting methods: A unified view on accelerated and stochastic optimization. Physical Rev. E 103 (2021), 5, 053304.   DOI:10.1103/physreve.103.053304
  33. D. Goldsztajn and F. Paganini: Proximal regularization for the saddle point gradient dynamics. IEEE Trans. Automat. Control 66 (2021), 9, 4385-4392.   DOI:10.1109/TAC.2020.3045124
  34. I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville and Y. Bengio: Generative adversarial nets. Commun. ACM 63 (2020), 11, 139-144.   DOI:10.1145/3422622
  35. S. Hassan-Moghaddam and M. R. Jovanović: Distributed proximal augmented Lagrangian method for nonsmooth composite optimization. In: 2018 Annual American Control Conference 2018, pp. 2047-2052.   CrossRef
  36. S. Hassan-Moghaddam and M. R. Jovanovic: Global exponential stability of the douglas-rachford splitting dynamics. IFAC-PapersOnLine 53 (2020), 2, 7350-7354.   DOI:10.1016/j.ifacol.2020.12.1254
  37. S. Hassan-Moghaddam and M. R. Jovanović: Proximal gradient flow and douglas-rachford splitting dynamics: global exponential stability via integral quadratic constraints. Automatica 123 (2021), 109311.   DOI:10.1016/j.automatica.2020.109311
  38. M. Hast, K. J. {\AA}ström, B. Bernhardsson and S. Boyd: Pid design by convex-concave optimization. In: 2013 European Control Conference 2013, pp. 4460-4465.   DOI:10.23919/ecc.2013.6669312
  39. M. R. Hestenes: Multiplier and gradient methods. J. Optim. Theory Appl. 4 (1969), 5, 303-320.   DOI:10.1007/BF00927673
  40. J. B. Hiriart-Urruty and C. Lemaréchal: Fundamentals of Convex Analysis. Springer Science and Business Media, 2004.   CrossRef
  41. X. Ju, H. Che, Ch. Li and X. He: Solving mixed variational inequalities via a proximal neurodynamic network with applications. Neural Process. Lett. 54 (2022), 1, 207-226.   DOI:10.1007/s11063-021-10628-1
  42. H. K. Khalil: Nonlinear Systems. Prentice-Hall, Upper Saddle River, NJ 1996.   CrossRef
  43. T Kose: Solutions of saddle value problems by differential equations. Econometrica, J. Econometr. Soc. 1956, pp. 59-70.   CrossRef
  44. Y. LeCun, Y. Bengio and G. Hinton: Deep learning. Nature 521 (2015), 7553, 436-444.   DOI:10.1038/nature14539
  45. L. Lessard, B. Recht and A. Packard: Analysis and design of optimization algorithms via integral quadratic constraints. SIAM J. Optim. 26 (2016), 1, 57-95.   DOI:10.1137/15M1009597
  46. F. Lin, M. Fardad and M. R. Jovanović: Design of optimal sparse feedback gains via the alternating direction method of multipliers. IEEE Trans. Automat. Control 58 (2013), 9, 2426-2431.   DOI:10.1109/TAC.2013.2257618
  47. M. Mäkelä: Survey of bundle methods for nonsmooth optimization. Optim. Methods Software 17 (2002), 1, 1-29.   DOI:10.1080/10556780290027828
  48. G. J. Minty: Monotone (nonlinear) operators in hilbert space. Duke Math. J. 29 (1962), 3, 341-346.   CrossRef
  49. J.-J. Moreau: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. France 93 (1965), 273-299.   CrossRef
  50. A. Nemirovski, A. Juditsky, G. Lan and A. Shapiro: Robust stochastic approximation approach to stochastic programming. SIAM J. Optim. 19 (2009), 4, 1574-1609.   DOI:10.1137/070704277
  51. A. S. Nemirovsky and D. B. Yudin: Problem Complexity and Method Efficiency in Optimization. John Wiley and Sons, Chichester 1983.   CrossRef
  52. Y. Nesterov: Smooth minimization of non-smooth functions. Math. Programm. 103 (2005), 1, 127-152.   DOI:10.1007/s10107-004-0552-5
  53. J. v Neumann: Zur theorie der gesellschaftsspiele. Math. Ann. 100 (1928), 1, 295-320.   DOI:10.1007/BF01448847
  54. J. Nocedal and S. J. Wright: Numerical Optimization. Springer, 1999.   CrossRef
  55. G. B. Passty: Ergodic convergence to a zero of the sum of monotone operators in Hilbert space. J. Math. Anal. Appl. 72 (1979), 2, 383-390.   DOI:10.1016/0022-247x(79)90234-8
  56. M. J. D. Powell: A method for nonlinear constraints in minimization problems. Optimization (1969), 283-298.   CrossRef
  57. G. Qu and N. Li: On the exponential stability of primal-dual gradient dynamics. IEEE Control Systems Lett. 3 (2019), 1, 43-48.   DOI:10.1109/LCSYS.2018.2851375
  58. M. Raginsky and J. Bouvrie: Continuous-time stochastic mirror descent on a network: variance reduction, consensus, convergence. In: 51st IEEE Conference on Decision and Control 2012, pp. 6793-6800.   CrossRef
  59. R. T. Rockafellar: Convex Analysis. Princeton University Press, 1970.   CrossRef
  60. R. T. Rockafellar: Augmented Lagrangians and applications of the proximal point algorithm in convex programming. Math. Oper. Res. 1 (1976), 2, 97-116.   CrossRef
  61. R. T. Rockafellar: Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14 (1976), 5, 877-898.   DOI:10.1137/0314056
  62. N. Z. Shor: Minimization Methods for Non-differentiable Functions. Springer Science and Business Media, 2012.   CrossRef
  63. M. Sion: On general minmax theorems. Pacific J. Math. 8 (1958), 1, 171-176.   CrossRef
  64. Y. Tang, G. Qu and N. Li: Semi-global exponential stability of augmented primal-dual gradient dynamics for constrained convex optimization. Systems Control Lett. 144 (2020), 104754.   DOI:10.1016/j.sysconle.2020.104754
  65. R. Tibshirani: Regression shrinkage and selection via the lasso. J. Royal Statist. Society: Series B (Methodological) 58 (1996), 1, 267-288.   DOI:10.1111/j.2517-6161.1996.tb02080.x
  66. P. Tseng: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control Optim. 38 (2000), 2, 431-446.   DOI:10.1137/S0363012998338806
  67. G. Wachsmuth: On LICQ and the uniqueness of Lagrange multipliers. Oper. Res. Lett. 41 (2013), 1, 78-80.   DOI:10.1016/j.orl.2012.11.009
  68. Z. Wang, W. Wei, Ch. Zhao, Z. Ma, Z. Zheng, Y. Zhang and F. Liu: Exponential stability of partial primal-dual gradient dynamics with nonsmooth objective functions. Automatica 129 (2021), 109585.   DOI:10.1016/j.automatica.2021.109585