🔢 mathematics

An augmented Lagrangian algorithm for constrained nonlinear least-squares

Cet article présente un algorithme de lagrangien augmenté à convergence globale pour la résolution de problèmes de moindres carrés non linéaires contraints avec des contraintes mixtes linéaires et non linéaires, qui emploie la projection de gradient pour les sous-problèmes et des approximations de la hessienne structurées.

Auteurs originaux : Pierre Borie, Fabian Bastin, Stéphane Dellacherie

Publié 2026-07-14

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Pierre Borie, Fabian Bastin, Stéphane Dellacherie

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de trouver l'endroit parfait pour installer une tente géante et bancale. Vous voulez que la tente corresponde à une forme spécifique (la partie « moindres carrés », ce qui signifie que vous voulez minimiser les écarts entre les poteaux de votre tente et la forme idéale), mais vous avez des règles strictes : la tente doit rester à l'intérieur d'un jardin clôturé, et certains poteaux doivent toucher des arbres ou des rochers spécifiques (les « contraintes »).

C'est exactement le problème que Pierre Borie, Fabian Bastin et Stéphane Dellacherie ont abordé dans leur article. Ils ont conçu un nouvel algorithme appelé TRAULLS (Trust Region Augmented nonLinear Least-squares Solver) pour résoudre ces puzzles complexes de « moindres carrés non linéaires sous contraintes ».

Voici comment leur méthode fonctionne, décomposée en une histoire que vous pouvez visualiser.

La stratégie en deux parties : La boîte de pénalité et la clôture

La plupart des anciennes méthodes essaient de résoudre le problème de la forme et le problème de la clôture en même temps, ce qui revient à essayer de jongler tout en marchant sur une corde raide. L'approche des auteurs est plus intelligente. Ils divisent le travail en deux couches :

La Clôture (Contraintes Linéaires) : Les règles concernant les limites du jardin et les arbres sont « linéaires ». Considérez-les comme une clôture rigide et immuable. L'algorithme les gère directement, comme un robot qui sait exactement comment glisser le long d'un mur sans le franchir.
La Boîte de Pénalité (Contraintes Non Linéaires) : La partie délicate est la forme « bancale » de la tente. Si la tente ne correspond pas à la forme idéale, l'algorithme ne se contente pas de l'ignorer ; il place la tente dans une « boîte de pénalité ». Chaque fois que la tente a une mauvaise forme, l'algorithme ajoute une « amende » énorme au score. C'est ce qu'on appelle l'Lagrangien Augmenté.

L'algorithme joue un jeu de « chaud et froid ». Il essaie de trouver le meilleur endroit à l'intérieur de la clôture tout en minimisant les amendes. Si la tente est encore trop bancale (si l'amende est trop élevée), l'algorithme augmente la taille de l'amende pour le tour suivant, forçant la tente à adopter la bonne forme.

La danse des « étapes » : Cauchy et le sous-espace

Une fois que l'algorithme a décidé de faire un pas vers un meilleur endroit, il ne devine pas au hasard. Il utilise une danse en deux étapes :

L'étape de Cauchy : D'abord, il fait un pas rapide et prudent en descente. C'est comme regarder la pente et faire un pas sûr dans la direction qui semble la plus abrupte. Cela garantit que l'algorithme ne reste jamais bloqué ou ne repart pas en arrière.
La Minimisation de Sous-Espace : Après ce pas de sécurité, il explore plus en profondeur. Il explore un « tunnel » spécifique (un sous-espace) défini par les règles qu'il touche actuellement. Il utilise un outil spécial appelé Gradient Conjugué Projeté pour zoomer sur le meilleur endroit à l'intérieur de ce tunnel.

La recette secrète : Le Hessien « structuré »

C'est ici que l'article est particulièrement ingénieux. Pour savoir dans quelle direction aller « vers le bas », l'algorithme a besoin d'une carte du terrain, appelée le Hessien.

L'ancienne méthode : Certaines méthodes utilisent une carte grossière (Gauss-Newton) qui suppose que le sol est plat. C'est rapide, mais cela peut être erroné si le terrain est accidenté.
La méthode « complète » : D'autres méthodes essaient de dessiner parfaitement l'intégralité du terrain accidenté. C'est précis, mais cela consomme tellement de mémoire et de temps que cela fait planter les ordinateurs ayant trop de variables.

L'innovation des auteurs est une mise à jour Quasi-Newton Structurée. Imaginez que vous avez un croquis du sol. Au lieu de redessiner tout le terrain à chaque fois, vous ne mettez à jour que les parties qui ont changé, en utilisant une règle spéciale (la mise à jour SR1) qui respecte la nature unique de « somme de carrés » du problème.

Ils ont testé une stratégie « Hybride » : si le sol semble plat, ils utilisent le croquis rapide. S'il semble accidenté, ils passent à la mise à jour détaillée.
Le résultat : Dans leurs tests sur 79 problèmes différents (allant de 2 à 1000 variables), cette approche SR1 Hybride a été la plus robuste. Elle n'a pas seulement fonctionné ; elle a mieux géré les problèmes « accidentés » que le croquis standard et s'est montrée plus fiable que d'autres méthodes complexes.

Ce qu'ils ont trouvé (et ce qu'ils n'ont pas trouvé)

Les auteurs ont fait tourner leur algorithme sur un ordinateur (un Mac mini avec un processeur M4) et l'ont comparé à deux autres solveurs célèbres : IPOPT et Percival.

La Vitesse : En termes de temps brut, leur nouveau solveur (TRAULLS) arrive juste derrière IPOPT. IPOPT était légèrement plus rapide sur les problèmes les plus faciles, mais à mesure que les problèmes devenaient plus difficiles, l'écart se réduisait.
L'Efficacité : IPOPT était le champion pour économiser les « évaluations de résidus » (vérifier la forme de la tente). C'est parce qu'IPOPT utilise des mathématiques exactes et lourdes pour chaque étape. TRAULLS, cependant, était bien meilleur que Percival (un autre solveur de Lagrangien Augmenté) et comparable à IPOPT sur de nombreux indicateurs.
Le Gagnant : L'article suggère que pour ce type de problème spécifique, utiliser la mise à jour SR1 Hybride est la meilleure stratégie globale. Elle offre un équilibre parfait entre vitesse et précision.

Ce qu'ils ont écarté

L'article argumente explicitement contre l'utilisation du Hessien « complet » (la carte parfaite) pour les problèmes de grande taille. Ils montrent que le calcul des termes de second ordre complets prend trop de temps et de stockage, ce qui rend la chose impraticable pour des problèmes comportant de nombreuses variables. Ils ont également montré que le simple croquis « Gauss-Newton » (ignorant les bosses) n'est pas assez précis en soi pour les problèmes où la « tente » est loin de sa forme idéale.

À quel point sont-ils sûrs ?

Les auteurs sont très confiants dans leurs résultats, mais ils restent prudents dans leurs propos.

Ils ont prouvé mathématiquement que leur méthode finira par trouver une solution (convergence globale) sous certaines hypothèses standards.
Ils ont mesuré la performance via des expériences numériques sur 79 instances de problèmes spécifiques.
Ils ne prétendent pas que leur méthode est le solveur le plus rapide de l'univers. Ils admettent que pour des problèmes « massifs » (où le nombre de variables est immense), leur méthode atteint une limite car la carte « structurée » nécessite toujours de stocker une matrice dense. Ils suggèrent qu'une version à « mémoire limitée » serait nécessaire pour ces cas gigantesques, mais ils ne l'ont pas encore construite.

En résumé, TRAULLS est une nouvelle façon ingénieuse de résoudre des problèmes d'ajustement complexes avec des règles. Il utilise une « boîte de pénalité » pour gérer les règles difficiles et un « croquis intelligent » pour naviguer sur le terrain, prouvant par des simulations qu'il est un concurrent solide et fiable pour résoudre ces puzzles mathématiques.

Résumé Technique : Un algorithme de Lagrangien Augmenté pour les Moindres Carrés Non Linéaires Contraints

Formulation du Problème
L'article traite le problème des moindres carrés non linéaires (NLS) contraints, défini par la minimisation de la somme des carrés des résidus $\frac{1}{2}\|r(x)\|^2$ sous l'effet d'un mélange d'égalités non linéaires $c(x)=0$ et de contraintes linéaires $x \in \Omega$ . L'ensemble $\Omega$ englobe les égalités linéaires ($Ax=b$) et les contraintes de bornes ( $l \le x \le u$ ). Les résidus $r(x)$ et les contraintes $c(x)$ sont supposés deux fois continûment dérivables. Le défi principal de la résolution de ces problèmes réside dans la gestion efficace de la structure NLS — spécifiquement, la décomposition de l'Hessien de l'objectif en un terme de premier ordre $J(x)^\top J(x)$ et un terme de second ordre impliquant les Hessiens des résidus individuels — tout en imposant des contraintes générales.

Méthodologie
L'algorithme proposé, implémenté en Julia sous le nom de TRAULLS, intègre le cadre du Lagrangien Augmenté (AL) avec des approximations quasi-Newton structurées (SQN) et des techniques de projection de gradient.

Cadre du Lagrangien Augmenté :
Les contraintes non linéaires sont incorporées dans la fonction objectif via un terme de pénalité AL, transformant le problème original en une séquence de sous-problèmes à contraintes linéaires. À chaque itération externe $K$ , l'algorithme minimise la fonction AL $\Phi(x, \lambda, \mu)$ sur l'ensemble polyédrique $\Omega$ .

Mise à jour des Multiplicateurs et de la Pénalité : Si la faisabilité non linéaire est suffisamment améliorée, les multiplicateurs de Lagrange sont mis à jour via l'ascension duale ( $\lambda_{K+1} = \lambda_K + \mu_K c(x_K)$ ). Si la faisabilité n'est pas améliorée, le paramètre de pénalité $\mu_K$ est augmenté pour imposer les contraintes plus strictement lors de l'itération suivante.
Minimisation Interne : Le sous-problème (minimisation de $\Phi$ sur $\Omega$ ) est résolu à l'aide d'une méthode de région de confiance. L'algorithme utilise une structure imbriquée où chaque itération externe déclenche une séquence d'itérations internes ( $k$ ), qui sont elles-mêmes composées d'itérations mineures ( $j$ ).

Minimisation Interne et Calcul de Pas :
La boucle interne utilise une technique de projection de gradient adaptée aux ensembles polyédriques.

Pas de Cauchy : Un pas de Cauchy est calculé en trouvant le premier minimiseur local d'un modèle quadratique le long du chemin du gradient projeté. Cela garantit la convergence globale.
Minimisation de Sous-espace : Pour accélérer la convergence, l'algorithme effectue une séquence d'itérations mineures au sein du sous-espace défini par les contraintes actives au point de Cauchy. Ces pas sont calculés à l'aide d'une méthode de Conjugate Gradient Projeté (PCG).
Région de Confiance : Une stratégie de région de confiance contrôle la qualité du pas, la région étant définie par une norme $\ell_\infty$ afin de maintenir la structure polyédrique des contraintes.

Approximation de l'Hessien Structuré :
Une contribution clé est l'approximation de l'Hessien de l'AL. Au lieu de calculer l'intégralité des termes de second ordre (ce qui est coûteux en calcul), la méthode approxime l'Hessien comme $H_k = B^{GN}_k + B_k$ , où :

$B^{GN}_k = J_k^\top J_k + \mu C_k^\top C_k$ est l'approximation de Gauss-Newton.
$B_k$ est une correction structurée approximant les termes de second ordre des résidus et des contraintes.
Règle de Mise à Jour : L'article emploie une mise à jour de type Symmetric Rank-1 (SR1) dérivée d'une équation sécante structurée adaptée à la structure NLS. Cette équation relie le changement des gradients au changement des variables via les Jacobiens des résidus et des contraintes.
Stratégie Hybride : L'algorithme bascule dynamiquement entre le modèle Gauss-Newton pur et le modèle SQN structuré en fonction de la magnitude des résidus (en utilisant un critère de commutation $\zeta_k$ ). Si les résidus sont faibles, le modèle GN est utilisé ; sinon, la correction structurée est appliquée pour améliorer la précision.

Principales Contributions

Intégration Algorithmique : L'article présente un solveur qui unifie le cadre du Lagrangien Augmenté avec des mises à jour quasi-Newton structurées spécifiquement conçues pour la structure de somme des carrés de l'objectif et du terme de pénalité.
Gestion des Contraintes Générales : Contrairement à de nombreux solveurs NLS existants qui se concentrent sur les contraintes de bornes, cette méthode gère directement un mélange d'égalités linéaires, de bornes et d'égalités non linéaires sans convertir toutes les contraintes en bornes.
Équation Sécante Structurée : La dérivation d'une équation sécante (Éq. 2.26) qui respecte la structure NLS permet l'approximation efficace de l'Hessien sans calculer les dérivées secondes complètes.
Convergence Globale : Les auteurs fournissent une preuve rigoureuse de la convergence globale vers un point critique de premier ordre, établissant que la méthode converge sous des hypothèses standards (dérivabilité deux fois, indépendance linéaire des contraintes actives).

Résultats Numériques
Les auteurs ont évalué TRAULLS sur 79 instances de problèmes allant de 2 à 1000 variables, incluant des problèmes issus de collections standards et de benchmarks spécifiques.

Comparaison de l'Approximation de l'Hessien : Les expériences comparant le Gauss-Newton (GN), le SR1 pur, le BFGS pur et leurs variantes hybrides ont montré que l'approche Hybride SR1 offrait le meilleur équilibre entre robustesse et efficacité. Bien que le GN soit le plus rapide par itération, l'approche hybride nécessitait moins d'itérations internes et démontrait une robustesse supérieure sur les problèmes avec de grands résidus.
Comparaison avec l'État de l'Art : TRAULLS a été comparé à IPOPT (un solveur de point intérieur à usage général) et Percival (un autre solveur basé sur l'AL).
- Performance : TRAULLS a obtenu des temps de calcul comparables à ceux d'IPOPT, bien qu'IPOPT nécessite généralement moins d'évaluations de fonctions grâce à l'utilisation de ses Hessiens exacts.
- Robustesse : TRAULLS a nettement surpassé Percival, démontrant que l'exploitation de la structure spécifique des moindres carrés produit de meilleures performances, même au sein du même cadre algorithmique (AL).
- Limitations : Le stockage dense requis pour la correction de l'Hessien structuré limite la scalabilité pour un très grand nombre de variables, un point que les auteurs reconnaissent.

Signification et Revendications
L'article affirme présenter un solveur spécifiquement conçu pour les problèmes NLS contraints qui équilibre efficacement l'exploitation de la structure des moindres carrés avec la flexibilité nécessaire pour gérer des contraintes générales. Les auteurs soulignent que leur approche évite le coût élevé du calcul des dérivées secondes complètes tout en maintenant la robustesse grâce aux mises à jour structurées. La signification réside dans la fourniture d'un outil spécialisé pour les problèmes d'ajustement de données et d'estimation de paramètres où la cohérence physique (imposée par les contraintes) est requise, offrant une alternative compétitive aux solveurs à usage général comme IPOPT et aux méthodes AL existantes comme Percival. Les auteurs notent modestement que si l'implémentation actuelle montre des performances prometteuses, les travaux futurs devront aborder la scalabilité via des variantes à mémoire limitée et un échantillonnage adaptatif pour les ensembles de résidus importants.