Méthode de projection

Projection et activation

Dans ce cours, nous présentons quelques méthodes d’optimisation dans lequel le critère est non linéaire et les contraintes sont suffisamment simples. Elles s’inspirent directement des techniques de descente en optimisation sans contrainte, en utilisant la notion de direction de descente et en faisant décroître le critère à chaque itération. Elles ont aussi la caractéristique de maintenir la suite des itérés {xk} dans l’ensemble admissible X. Si l’approche est générale, elle ne trouvera son efficacité que si les contraintes sont affines, si bien que le problème devra pouvoir être mis sous la forme suivante :  min f(x) Ax 6 b, (12.1) où f : R n → R est une fonction régulière, A est une matrice m × n et b ∈ R m. Une direction de descente de f en un point qui n’est pas dans l’ensemble admissible X est de peu d’utilité : si elle permet de faire décroître f, elle n’est d’aucune aide pour ramener les itérés dans l’ensemble admissible. Par conséquent, si on désire utiliser des directions de descente de f, on est forcé de générer des suites {xk} admissibles, c’est-à-dire contenues dans X. On est alors amené à introduire la notion de direction de descente admissible dk. De petits pas le long de ces directions permettent de faire décroître f tout en restant dans X. Alors on peut par exemple définir la suite {xk} par xk+1 = xk + αkdk, avec αk suffisamment petit pour que f décroisse et que xk+1 soit dans X. Cette méthode est attrayante par sa simplicité, mais elle n’est pas convergente. On connaît en effet un contre-exemple, dû à Wolfe [625 ; 1972]. Nous n’allons pas le décrire en détail, mais il est instructif de comprendre ce qui s’y passe. Dans celui-ci (voir figure 12.1), on minimise sur l’orthant positif (X = {x ∈ R 3 : x > 0}) une fonction convexe de 3 variables; on utilise la méthode ci-dessus, en prenant dk = −gk comme direction de descente admissible; on prend le pas optimal si celui-ci laisse xk+1 dans X, sinon on prend le plus grand pas possible de manière à rester dans X. On constate que l’algorithme construit une suite {xk} oscillant entre deux faces de l’orthant positif et convergeant vers un point non stationnaire (!) situé sur l’intersection des deux faces. Que se passe-t-il ? Une façon d’interpréter ce résultat est de dire que les bornes (x > 0) de l’ensemble admissible forcent le pas à être trop petit et provoquent ainsi la « fausse » convergence de la suite. On a vu, en effet, au chapitre 6.3, qu’un des devoirs de la recherche linéaire est d’empêcher le pas d’être trop petit afin d’assurer la convergence des méthodes à directions de descente. La présence des contraintes d’inégalité empêche ici de satisfaire cette propriété. On peut trouver plusieurs remèdes pour éviter cette fausse convergence. L’un d’eux consiste à poursuivre la recherche du pas au delà du point d’activation xk + ˆαkdk du chemin α 7→ xk + αdk sur le bord de X. Comme l’on veut que les itérés restent dans X, la recherche se poursuit alors, non pas le long de dk, mais le long du chemin α 7→ xk +αdk projeté sur X. On parle de méthodes de projection. Cette approche sera examinée à la section 12.1. On comprend que pour que celle-ci soit efficace, il faut que la projection sur X soit peu coûteuse. C’est le cas notamment des ensembles X définis par des contraintes de borne : X = {x ∈ R n : a 6 x 6 b}, a et b ∈ R n . (12.2) Une autre approche consiste à bloquer certaines contraintes pendant quelques itérations (cas où X est donné par des contraintes d’inégalité affines), c’est-à-dire de considérer certaines contraintes d’inégalité comme des contraintes d’égalité. On parle alors de méthodes différentiation automatique, aussi appelées méthodes de pivotage dans les problèmes de complémentarité [141] (section 12.2). Ces méthodes sont surtout utilisées en optimisation quadratique, c’est-à-dire pour la minimisation de fonctions quadratiques en présence de contraintes affines : X = {x ∈ R n : Ax 6 b}, A : m × n, b ∈ R m.

Méthode de projection

Dans cette section, nous étudions les méthodes dans lesquelles le chemin de recherche de l’itéré suivant est obtenu en projetant sur X le chemin affine α 7→ xk + αdk : xk(α) := PX(xk + αdk), (12.4) où dk ∈ R n, α > 0 et PX est un opérateur de projection sur X (voir figure 12.2). Par conséquent, α 7→ xk(α) est un chemin de recherche admissible et en prenant xk+1 = xk(αk), αk > 0, (12.5) on générera une suite {xk} admissible, c’est-à-dire avec xk ∈ X. 

Méthode du gradient projecté 

Venons-en maintenant à l’étude d’un algorithme de résolution du problème (12.1), basé sur (12.4)–(12.5). On suppose que X est un convexe fermé non vide de R n. La première question qui se pose est de savoir si l’on fait décroître f le long du chemin xk(α) défini en (12.4). En général, ce n’est pas le cas, tout au moins si dk est une direction de descente stricte quelconque de f (c.-à-d., une direction vérifiant g T k dk < 0, gk = ∇f(xk)). On peut en effet construire aisément un exemple où l’on n’a pas f(xk(α)) < f(xk), pour α > 0 petit. (12.6) La figure 12.3 illustre une telle situation. La direction dk est de descente car elle forme avec −gk un angle plus petit que π/2 (on suppose que gradient et angle font ici référence au produit scalaire euclidien), ce qui n’est pas le cas du chemin projeté α 7→ xk(α). Cependant, si l’on prend dk = −gk et donc xk(α) := PX(xk − αgk), (12.7) la condition (12.6) est vérifiée. Nous allons le voir. La méthode utilisant le chemin (12.7) comme chemin de descente porte le nom de méthode du gradient projecté. Elle a été introduite par Goldstein [262 ; 1964] et Levitin et Polyak [391 ; 1966]. Cette méthode n’est pratiquement utilisable que lorsque la projection sur l’ensemble des contraintes est facile à réaliser, par exemple dans le cas de contraintes de borne (12.2). Les lemmes 12.1, 12.2 et 12.3 donnent quelques propriétés fondamentales de cette méthode. 

Lemme 12.1 Soit X un convexe fermé non vide de R n . Alors, le point x¯ ∈ X est un point stationnaire du problème (12.1) si, et seulement si, x¯ = PX(¯x − α∇f(¯x)), (12.8) pour un (ou tout) α > 0.

Méthodes différentiation automatique 

La méthode que nous décrivons dans cette section est fondée sur une idée assez générale. Toutefois, d’un point de vue pratique, elle ne pourra être utilisée avec efficacité qu’en optimisation quadratique. Ces restrictions apparaîtront au cours de l’exposé. 

Motivation et schéma des méthodes 

Pour construire une suite minimisante {xk} admissible, c’est-à-dire contenue dans X, on peut s’appuyer sur la notion de direction de descente admissible. Définition 12.6 Soit x ∈ X. On dit que d est une direction admissible en x pour X si x + αd ∈ X pour tout α > 0 suffisamment petit (de manière plus précise : il existe α >¯ 0 tel que pour 0 6 α 6 α¯ on ait x + αd ∈ X). On dit que d est une direction de descente admissible en x pour le problème (12.1), s’il existe α > ¯ 0 tel que pour 0 6 α 6 α¯ : x + αd ∈ X et f(x + αd) 6 f(x). (12.14) Il s’agit donc d’une direction de descente (non stricte) de f telle qu’avec un petit déplacement dans cette direction, on reste dans X.On ne peut pas toujours trouver une direction vérifiant ces conditions, mais si X est convexe et xk n’est pas stationnaire, une telle direction existe toujours. En effet, du fait de la convexité de X, les directions de la forme dk = yk − xk, où yk ∈ X et yk 6= xk sont des directions admissibles pour X. Alors, s’il n’existait pas de direction de descente admissible en xk, cela voudrait dire que, pour yk ∈ X fixé, il existerait une suite de α i > 0, α i → 0, telle que f(xk + α i (yk − xk)) > f(xk). En passant à la limite, on trouverait hgk, yk − xki > 0, ∀yk ∈ X. Ceci impliquerait la stationnarité de xk (proposition 4.7). Nous supposerons donc que X est convexe pour pouvoir trouver à chaque étape une direction de descente admissible. Nous allons utiliser des directions admissibles dans une approche fondé sur la notion d’activation de contraintes (en anglais, Active Set Methods). L’idée est de bloquer — on dit aussi activer — certaines contraintes définissant X, c’est-à-dire que des contraintes d’inégalité seront considérées comme contraintes d’égalité pendant un certain nombre d’itérations (on évite ainsi l’oscillation qui se produit dans le contreexemple de Wolfe). Ceci n’est concevable que si les contraintes sont affines, sinon la réalisation de ci(xk) = 0 est trop coûteuse. Pour simplifier l’exposé, nous supposerons qu’il n’y a pas de contraintes d’égalité. Le problème (P) à résoudre dans cette section est donc (P)  min f(x) Ax 6 b, (12.15) où A est une matrice m × n et b ∈ R m. L’ensemble admissible est convexe (clair). Les équations d’optimalité s’écrivent en (¯x, λ¯) (les contraintes étant affines, elles sont qualifiées; on peut donc trouver un multiplicateur λ¯) :    ∇f(¯x) + ATλ¯ = 0, Ax¯ 6 b, λ¯ > 0, λ¯T(Ax¯ − b) = 0. (12.16) On note A(j) , la j-ième ligne de A. Si J ⊆ [1 : m] est un ensemble d’indices, on note AJ la matrice |J| × n, obtenue en extrayant de A ses lignes j ∈ J. On définit b(j) et bJ de manière analogue. Enfin, l’ensemble actif en xk, I 0 (xk), se notera ici simplement Ik = {j : 1 6 j 6 m, A(j)xk = b(j)}.