2025-11-19T02:19:13.103879

A projection-free dynamics for nonsmooth composite optimization

Ni, Qiu, Xiao
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.
academic

Une dynamique sans projection pour l'optimisation composite non-lisse

Informations fondamentales

  • ID de l'article: 2510.22173
  • Titre: A projection-free dynamics for nonsmooth composite optimization
  • Auteurs: Wei Ni, Yangfan Qiu, and Yanyan Xiao
  • Classification: math.OC (Optimisation et Contrôle)
  • Date de soumission: 25 octobre 2025 sur arXiv
  • Lien de l'article: https://arxiv.org/abs/2510.22173v1

Résumé

Cet article propose une méthode de dynamique primale-duale sans projection pour résoudre les problèmes d'optimisation composite non-lisse avec contraintes d'égalité et d'inégalité. Pour traiter les contraintes d'optimisation, l'article abandonne les méthodes de projection de gradient et utilise plutôt les idées de la descente miroir (mirror descent) pour concevoir une dynamique d'optimisation lisse en temps continu, ce qui facilite l'analyse de convergence et améliore l'efficacité de la simulation numérique. De plus, l'article étend la stratégie du Lagrangien augmenté proximal (PAL) pour incorporer des contraintes d'égalité-inégalité convexes générales et réalise la forte convexité-forte concavité des variables primales-duales, garantissant la convergence exponentielle de l'algorithme. Ce résultat de convergence étend la théorie de convergence exponentielle existante (considérant uniquement les cas sans contrainte ou avec contraintes linéaires affines) et améliore les résultats de convergence asymptotique sous contraintes convexes dépendant de schémas de projection de gradient complexes.

Contexte et motivation de la recherche

Problème à résoudre

Cet article étudie les problèmes d'optimisation composite avec un terme de régularisation non-lisse: min⁡x∈Rnf(x)+ϕ(Tx),subject to g(x)⪯0,h(x)=0\min_{x \in \mathbb{R}^n} f(x) + \phi(Tx), \quad \text{subject to } g(x) \preceq 0, h(x) = 0

où f(x)f(x) est une fonction différentiable, ϕ(Tx)\phi(Tx) est une fonction composite non-lisse, g(x)g(x) et h(x)h(x) représentent respectivement des contraintes d'inégalité convexes générales et des contraintes d'égalité affines.

Importance du problème

Cette classe de problèmes a des applications importantes dans plusieurs domaines:

  1. Apprentissage profond: minimisation du risque empirique avec régularisation non-lisse
  2. Traitement du signal: problèmes Lasso et récupération de signaux continus
  3. Problèmes inverses, estimation statistique, théorie du contrôle, etc.

Limitations des méthodes existantes

Défis du traitement de la non-lissité:

  • Les méthodes de sous-gradient convergent lentement
  • Les méthodes de lissage deviennent complexes lorsque les paramètres tendent vers zéro
  • Les méthodes d'opérateur proximal sont difficiles à appliquer directement à la fonction composite ϕ∘T\phi \circ T

Dilemmes du traitement des contraintes:

  1. Méthodes de projection: produisent des systèmes dynamiques discontinus, l'analyse de convergence est complexe, nécessitant des outils d'analyse non-lisse (comme les inclusions différentielles)
  2. Méthodes d'opérateur max: bien qu'elles évitent les projections explicites, elles produisent toujours une dynamique non-lisse
  3. Cadre IQC: applicable uniquement aux contraintes d'égalité ou aux contraintes d'inégalité affines, incapable de traiter les contraintes convexes non-linéaires générales
  4. Méthodes de systèmes hybrides: ne peuvent garantir que la convergence asymptotique, impossible d'obtenir des taux de convergence exponentielle

Motivation de la recherche

Concevoir un système de dynamique d'optimisation complètement lisse capable de:

  1. Traiter les contraintes d'inégalité convexes générales (pas seulement les contraintes affines)
  2. Réaliser la convergence exponentielle (plutôt que la convergence asymptotique)
  3. Simplifier l'analyse de convergence et la mise en œuvre numérique

Contributions principales

  1. Proposition d'une dynamique d'optimisation lisse sans projection: en utilisant la montée miroir pour traiter les variables duales des contraintes d'inégalité, évitant les opérations de projection, obtenant un système de dynamique en temps continu complètement lisse
  2. Extension de la méthode PAL pour traiter les contraintes générales: extension de la méthode du Lagrangien augmenté proximal au cas avec des contraintes d'égalité-inégalité convexes générales, preuve que PAL possède une forte concavité sur les variables duales
  3. Réalisation de la convergence exponentielle: preuve de la stabilité exponentielle sous contraintes convexes non-linéaires générales, dépassant les résultats de convergence asymptotique ou semi-globale exponentielle des méthodes existantes
  4. Éviter les limitations du cadre IQC: ne dépendant pas de l'analyse IQC, preuve directe de la convergence exponentielle via les fonctions de Lyapunov et l'analyse convexe, dépassant les limitations de la méthode IQC applicable uniquement aux contraintes affines

Détails de la méthode

Définition de la tâche

Problème d'optimisation primaire (P):

undefined