L'optimisation non-linéaire dans MEF++

Introduction

Problème non-linéaire

où, la fonction coût,  et , les contraintes, sont supposées au moins C¹ et les bornes peuvent prendre des valeurs infinies (ce qui correspond a l'absence de borne).

La nature des données du problème (,,  et ) joue un rôle important sur le type de méthode employée pour résoudre le problème.

• Si ,  et  sont linéaires on a un problème de programmation linéaire et des méthodes spécifiques, tel que le simplexe, sont bien adaptées à ces problèmes.
• Si la variable d'optimisation (de décision, de design, etc), , est restreinte au nombre entier on a un problème de programmation en nombre entier et dans ce cas aussi on peut trouver des méthodes spécialement conçues pour ces problèmes (génération de colonne par exemple).

Optimalité

On a d'abord la Condition (nécessaire) d'ordre un (appelée Kuhn-Tucker, Karush-Kuhn-Tucker, KKT): soit  le point solutionnant le problème. Moyennant certaines conditions (dites de régularité) on a le résultat suivant: il existe  dans  et  dans   tel que

et la condition (nécessaire) d'ordre deux:

On a aussi une condition (suffisante) d'ordre deux: si

• dans ,  dans  et  dans  satisfont:

• est défini positif sur T

Remarque:

• Si  et   sont linéaires alors 
• Si  (on a pas de contrainte) alors les conditions énoncées plus haut (KKT et autres) se restreignent à des conditions sur  et .

Approche générique pour la résolution numérique

Un schéma sera donc composé de 3 phases principales:

• initialisation et vérification des conditions d'optimalité
• calcul d'une direction de descente. Cette direction pourra dépendre de , , des contraintes, des équations de KKT, etc
• calcul du nouveau point (ou de ). Ici encore le pas peut dépendre de la fonction coût et des contraintes au point .

Line Search

Les contraintes et les bornes jouent aussi un rôle dans le calcul du pas. Il est possible d'ignorer les contraintes pour le calcul du pas mais alors le nouveau point obtenu n'est pas admissible (il ne satisfait pas au contraintes). Dans le cas contraire les contraintes imposent des restrictions sur la longueur de pas.

On cherchera à utiliser la valeur minimisant la fonction mérite, , comme longueur de pas. En général l'obtention de  est aussi difficile que le problème initial. C'est pourquoi, sauf dans de très rare cas, on se limite à obtenir une approximation  de   satisfaisant

Pour le moment dans MEF++ nous avons implémenté
 

Méthode Fixe:	On impose un pas de longueur constante ou une proportion constante du pas maximal :  le point de départ,  la direction choisie, et  les contraintes d'inégalités imposées. Attention: ces contraintes ne correspondent pas nécessairement aux contraintes  !  1) On fixe, , la valeur maximale que peut prendre le pas dans le cas où l'on a des bornes dans le problème. Si le problème ne comporte pas de bornes on choisi une valeur arbitraire pour . 2) Partant de  on cherche  tel que  soit vérifiée:      tant que  . 3) On pose  où  est une constante positive plus petite que 1. Les paramètres de la recherche sont donc  raffinement de la recherche d'un pas admissible proportion constante du pas admissible Remarques: Cette méthode ne vérifie pas que la fonction mérite diminue, de plus il est possible que le pas retenu soit trop petit; aussi les schémas utilisant cette recherche peuvent ne pas converger! Le point obtenu par cette méthode sera admissible i.e. il vérifiera les conditions imposées  (bornes, contraintes d'inégalités).
Méthode Linéaire:	recherche simple d'un pas en partant du pas maximal : soit  le point de départ,  la fonction mérite ,  la direction choisie, et  les contraintes d'inégalités imposées. Attention ces contraintes ne correspondent pas nécessairement aux contraintes  ! 1) On fixe, , la valeur maximale que peut prendre le pas dans le cas où l'on a des bornes dans le problème. Si le problème ne comporte pas de bornes on choisi une valeur arbitraire pour . 2) On fixe le sens de la recherche, , (1 pour croissant, -1 décroissant), ainsi que la méthode de construction des points (points équidistants ou par progression géométrique). 3) On cherche  tel que les contraintes  et la diminution de  soit vérifiés:      tant que      ou  et  pour une recherche géométrique      ou  pour une progression linéaire.  Les paramètres de la recherche sont donc  raffinement de la recherche d'un pas admissible le sens de parcours des points la méthode de construction des points Remarques: Avec cette méthode il est possible que le pas retenu soit trop petit ou que la recherche échoue; aussi les schémas utilisant cette recherche peuvent ne pas converger! Le point obtenu par cette méthode sera admissible i.e. il vérifiera les conditions imposées (bornes, contraintes d'inégalités).
Méthode Quadratique:	on approxime la fonction mérite par une fonction quadratique que l'on minimise: soit  le point de départ,  la direction choisie. Cette méthode s'applique aux problèmes sans contraintes ou avec uniquement des bornes sur les variables. Sachant que  est décroissante autour de 0 (dans le cas  = ) on cherche trois points par lesquels on peut passer un polynôme de degré deux convexe et on prend la racine du polynôme comme longueur de pas.   1) On fixe, , la valeur maximale que peut prendre le pas dans le cas où l'on a des bornes dans le problème. Si le problème ne comporte pas de bornes on choisi une valeur arbitraire pour . 2) On fait un redimensionnement de  pour assurer une décroissance suffisante, pour avoir un nombre minimal d'évaluations et pour satisfaire les bornes (si présentes). 3) On calcul  ,  jusqu'a ce que  4) On calcul le minimum du polynôme passant par A,B et C. Les paramètres de la recherche sont donc  raffinement de la recherche d'un pas admissible  le nombre minimal d'évaluations exigées Remarques: Cette méthode n'exige pas de dérivée de la fonction mérite et ne s'applique pas aux problèmes avec contraintes autres que des bornes. Le point obtenu par cette méthode sera admissible i.e. il vérifiera les bornes (si elles sont imposées).
Méthode Type Armijo:	on cherche un pas satisfaisant des conditions particulières encadrant avec plus ou moins de précision le minimum de la fonction mérite. Soit  la fonction mérite,  le point de départ,  la direction choisie, et  les contraintes d'inégalités imposées. Attention ces contraintes ne correspondent pas nécessairement aux contraintes  ! On cherche  satisfaisant avec .  Cette condition (dite d'Armijo) donne une borne supérieure sur la longueur de pas. En prenant un pas suffisamment grand satisfaisant cette inégalité on a convergence.  Plutôt que de se baser sur la méthode de recherche pour avoir un point assez grand on peut ajouter une condition donnant une borne inférieure sur :       au moins une des  conditions suivantes est satisfaites ,  C'est le critère de Wolfe. On pourra alors réduire ou agmenter la valeur du pas suivant que l'inégalité d'Armijo ou Wolfe n'est pas vérifiée. Enfin pour s'assurer que le nouveau point est intérieur on peut imposer une condition supplémentaire. Soit  un vecteur de contrôle (dans des méthodes de type Newton, il s'agit habituellement d'une approximation du multiplicateur de Lagrange). On impose que le pas satisfasse    si       si  Présentement il y a trois variantes de cette méthode dans MEF++:     LSArmijo recherche simple d'un pas satisfaisant la condition d'Armijo. LSWolfeBissect recherche d'un pas satisfaisant Armijo et Wolfe en utilisant une méthode de type bissection pour obtenir le pas. LSWolfeCubique recherche d'un pas satisfaisant Armijo et Wolfe en utilisant le minimum d'une approximation cubique lors de la recherche du pas.  Les paramètres de la recherche sont    vu plus haut raffinement de la recherche du pas indication de la condition de point intérieur Remarques: En pratique la valeur de  est petite (0.001) et la valeur de  pres de 1. Le point obtenu par cette méthode sera admissible i.e. il vérifiera les bornes  (si elles sont imposées).

Classe LineSearch et Hessien

• l'utilisation de l'information sur, la manière dont on vérifie les équations de KKT, la manière dont on utilise l'information fournie par KKT
• la méthode utilisée pour le calcul de la longueur de pas
• la manière dont on calcul le gradient et la matrice hessienne de (si nécessaire)

Hessien

void Hessien::calculHessien(MatriceDyn<DReel>& pH, VectDyn<DReel>& pXk1,
                                         VectDyn<DReel>& pXk0,VectDyn<DReel>& pGradXk1,
                                         VectDyn<DReel>& pGradXk0)

qui produit la matrice hessienne pH au point pXk1. Notons que dans la plupart des schémas on s'intéresse à la matrice hessienne du Lagrangien (problème avec contraintes). Pour le moment sont implémentées

Classes:
 

HessienFixe:	on donne une valeur constante à la matrice hessienne.
HessienBFGS:	on utilise la méthode de Broyden, Fletcher, Goldfarb et Shanno pour approximer la matrice hessienne.
HessienExact:	on fourni la valeur exacte en chaque point.

Une description détaillée de ces classes se trouve dans les fichiers include respectif.

LineSearch

void LineSearch::calculNouveauPoint(DReel& pAlphaMax, DReel& pFXk, VectDyn<DReel>& pXk,
                                                      VectDyn<DReel>& pYk, VectDyn<DReel>& pGradFXk)

qui calcul le pas pAlphaMax, et met à jour le point pXk, la fonction pFXk et si nécessaire le gradient pGradFXk. Mais le calcul du pas pouvant tenir compte aussi des variables duales (i.e. de  et ) on ajoute deux méthodes:

void LineSearch::donneeRecherchePointInterieur(VecteurR&)
void LineSearch::recherchePointInterieur(VecteurR& pXk0, VecteurR& pXk1,
                                                          VecteurR& pContrainte0, VecteurR& pContrainte1,
                                                          bool& pVerdict)

La première de ces méthodes fait l'assignation des variables duales. La seconde vérifie que le point pXk1 est à l'intérieur du domaine admissible défini par les contraintes en utilisant  , , le point précédent pXk0, et les contraintes aux deux points.

Classes:
 

LSPasFixe:	Voir plus haut.
LSLineaire:	Voir plus haut.
LSQuadratique:	Voir plus haut.
LSArmijo:	Recherche utilisant la condition d'Armijo (voir plus haut). Le pas est trouvé en faisant une recherche simple décroissante partant de .
LSWolfeBissect	Recherche utilisant la méthode d'Armijo et imposant pour borne inférieure la condition de Wolfe. Le pas est trouvé en utilisant une recherche de type bissection.
LSWolfeCubique:	Recherche utilisant la méthode d'Armijo et imposant pour borne inférieure la condition de Wolfe. Ici le point est trouvé en utilisant une interpolation cubique basée sur la fonction et sa dérivée.

Encore une fois pour des informations détaillées sur ces classes voir les fichiers include respectifs.
 

Schémas d'optimisation dans MEF++

• Problèmes avec des bornes seulement: méthode de projection des points
• Problèmes avec des contraintes linéaires seulement: méthode du gradient projeté
• Problèmes complets: famille de méthodes de type Newton (primal/dual)

Méthode de projection des points: ProjeteGradient

Il s'agit d'une méthode simple utilisée pour des problèmes d'optimisation où l'on a que des bornes comme contraintes. La méthode est une variation de la méthode de gradient où l'on fait une projection sur la "boite" créée par les bornes.

Partant de et .
1) on pose   et utilisant un line search on obtient 
2) on projette le point dans la boite formée des bornes: 
3) si

ou 

Méthode du gradient projeté: GradientProjete

Ici toutes les contraintes sont linéaires. On a abrégé la notation en incluant dans  les bornes, les inégalités ainsi que les égalités (dans cette ordre). Dans le cas où l'on a seulement des contraintes d'inégalité les équations d'optimalité (KKT) sont:

La méthode consiste, en chaque point, a projeté le gradient de la fonction sur le sous-espace des contraintes saturées.

Partant de et .

1) On construit .
2) On construit la matrice dont les lignes correspondent aux contraintes dans .
3) On construit la projection:

si  est nul on passe en 5).
4)  On fait  et on trouve la longueur de pas avec  comme fonction mérite et en imposant toutes les contraintes dans le Line Search ce qui nous donne  après quoi retour en 1).
5) Si pour les inégalités on a un minimum local et  est optimal. Sinon, soit  la composante la plus négative pour les inégalités, on pose

Méthode de type Newton à point intérieur

Ici toutes les contraintes sont des inégalités. Les conditions KKT sont alors

La méthode proposé consiste à appliquer la méthode de Newton aux conditions d'optimalité vu comme un système en . Soit  le point de départ d'une itération, on aura

où  est le hessien,  est une matrice diagonale avec  et  est une matrice diagonale avec . Si on note  on peut définir le système

où  est la direction dans l'espace primal,  est la nouvelle approximation de . La matrice est symétrique et définie positive et peut être remplacée par le hessien, une approximation "quasi-Newton" (BFGS par exemple) ou par une matrice constante. Malheureusement la direction  n'est pas toujours admissible; pour résoudre ce problème on considère une correction de la direction obtenu par le système auxiliaire:

et on obtient une direction admissible par

Enfin on peut appliquer une recherche de longueur de pas et obtenir le point . Différentes stratégies peuvent être choisie pour faire la mise à jour de . En résumé

Partant de ,  , et 
1) Résoudre le système en 

3) On fixe :

4) On construit  et 

5) On fait une recherche de longueur de pas avec une condition de point intérieur utilisant .
6) On construit ,  met à jour , , on pose  et on retourne en 1).

Suivant les règles utilisées pour les mises à jour et l'approximation du Hessien on aura convergence de vers le point satisfaisant les équations de KKT. Il est clairement évident que cette méthode s'apparente aux méthode de type SQP (Sequential Quadratic Programming).

Remarques

• Suivant le choix fait pour le hessien on aura différents type d'approximation:
• Méthode d'ordre 1 pour un hessien choisi constant (identité).
• Méthode quasi-Newton pour une approximation type BFGS.
• Méthode de Newton si on prend le hessien exact.
• Plusieurs méthodes peuvent être envisagées pour la mise à jour du multiplicateurs

Références