Cours optimisation On appelle problème d’optimisation la donnée d’une instance de la forme minimiser/maximiser f (x) sous les condltions gi (x) e {1, avec f : Rp R une fonction objectif et gi fonctions de contraintes. L’ensemble des point (x e Rp I gi (x) SO VI est appelé ensemble solution du prob èm tout minimum/maxi or 12 Sni* to h] : RP R des vide, on appelle n f restreinte à cet ensemble de candidats, not . Dans ce cours, on étudie uniquement les problèmes de minimisation sans contraintes, c’est-à-dire avec m m O.
Ainsi, l’ensemble des candidats correspond ? l’espace Rp tout entier. Remarquons qu’un problème de maximisation max f (x) peut naturellement se transformer en un problème de minimisation mln —f (x). Pourquoi s’intéresser à ces problèmes d’optimisation ? Mettons- nous un instant dans la situation où l’on souhaite apprendre des données : Données But : (xi , yi) E Rn x Ni E {1, trouver un « modèle » y f (x) susceptible d’avoir généré les modèles potentiels, à savoir une famille (fe )ÊERp de fonctions Rn R régie par des paramètres a e Rp .
Notre objectif est alors de trouver le meilleur paramètre par exemple en minimisant la fonction d’erreur des sommes e carrés, c’est-à-dire de résoudre le problème d’optimisation : minimiser 2 ‘fa (Xi) – Yi 12 pour e E Rp. Avant de détailler les outils qui vont nous permettre de résoudre ces problèmes d’optimisation, notons qu’il est possible de restreindre nos attentes en cherchant un optimum local (et non global comme précédemment), eest-à-dire chercher une valeur qui optimise la fonction f sur un voisinage de x• et non sur l’espace tout entier.
Dans ce cas, on peut utiliser des méthodes de descente (si la fonction objectif est différentiable), par exemple basée sur le gradient, que nous développerons en Section 2, ou des méthodes telles que la méthode du simplexe (si la fonction objectif est linéaire) ou de recherches de motifs (si la fonction objectif n’est pas différentiable). À noter que dans le cas d’une fonction objectif prenant des valeurs discrètes, les méthodes sont tout à fait différentes et constituent le domaine de l’optimisation combinatoire.
Dans le cas des optima globaux, il est souvent nécessaire d’introduire du non-déterminisme our s’échapper des optima locaux, à moins bien sûr d 12 le prix d’une recherche exhaustive. À noter que le cas convexe que nous allons développer permet ‘assurer que le minimum local trouvé est en fait un minimum global : on trouvera de plus amples détails sur l’optimisation convexe dans [1] Outils mathématiques et conditions d’optimalité Afin de développer les méthodes d’optimisation, il est nécessaire de connaitre un minimum d’outils mathématiques relatifs au calcul différentiel.
Pour de plus amples informations ou exercices, on se reportera par exemple à [2]. Différentielle et gradient On se place dans des espaces vectoriels normés de dimension finie : on notera toujours • la norme, indépendamment de l’espace utilisé. Dans l’espace Rn , on , en) la base canonique et ote (el on identifie le plus souvent une application linéaire et sa matrice dans la base canonique. Par ailleurs, on notera AT la transposée d’une matrice A.
L’espace Rn est naturellement muni d’un produit scalaire canonique, noté • , et défini pour deux vecteurs x, y e Rn par x, y Définition 1 (différentielle). Soient LI un ouvert de Rn et a c U . une fonction f : IJ Rp est dite différentiable en a s’il existe une application linéaire continue L . Rn Rp et une fonction E : Rn R telles que PAGF 19 L existe, elle est unique : on la note Df (a) (ou f (a), df (a), Da f et on l’appelle différentielle de en a : dans la suite, on notera La fonction f est dite différentiable, si elle est différentiable en tout point de U Exemple 1 .
Si f est une application linéaire sur U = Rn alors f est différentiable de différentielle f Si f : Rn R est définie pour tout x E Rn par f (x) = Ax avec A une matrice n n à coefficients réels, alors f est différentiable de différentielle Df (a)h = aT (A + Théorème 1. Soient IJ un ouvert de Rn et a E IJ – Soient f, g : U — Rp deux fonctions différentiables en a et À c R. L’application f + hg est différentiable en a de différentielle D(f • Àg)(a) = Df (a) + ÀDg(a). Soient f : IJ Rp une application différentiable en a et g : f (IJ ) Rq une application différentiable en f (a).
Capplication g e f est différentiable en a de différentielle D(g f)(a) Dg(f Df G). Exercice 1. Soient IJ un ouvert de Rn , ae U , v e Rn et f : Rp une application différentiable en a. Montrer que l’application t CR f (a + tv) est définie sur un voisinage de t = O et est différentiable en 0. Que vaut sa différentielle en 0 ? Si f : U Rp est différentiable en a, on note Of taxi (a) (ou ai f (a)) le vecteur Df (a)ei E Rp . Grâce à la linéarité de la différentielle, on a pour tout h (hl hn)e Rn af (a)hi . 2 Of (a)h = axi Définition 2 (gradient).
On se place ici dans le cas où p = 1. On considère à nouveau un ouvert U de Rn . Si f est une application IJ R différentiable en un point a e IJ , telle que Df (a) n’est pas l’application nulle, alors il existe un unique vecteur f (a) Rn , appelé gradient de f en a, vérifiant pour tout h Rn , Df(a)h = f h. On peut aisément vérifier que f (a) = (ôf /ôxl (a), . , òf/òxn (a)). Exemple 2. Si f est une forme linéaire, de matrice uT e Rlxn (cela veut donc dire que f(x)=uTx pour tout x e Rn ), alors f (a) u. Si XT Ax, alors f (a) = (A+ Exercice 2.
Soit f : Rn — Rune application différentiable. Pour tout réel c, on appelle ligne de niveau c de f l’ensemble NC = {XE Rn I f (x) = c}. Soit x0E NC . Montrer que f (xo ) est orthogonal à NC enxO. 1. 2 Différentielle seconde et Hessienne On se limite dans cette sous-section aux fonctions numériques, pour simplifier l’exposé : il est bien sûr possible de généralise s et théorèmes suivants PAGF s 2 l’application Df: V — (Rn , u Df (u) (on note (Rn Hespace vectoriel des formes linéaires sur Rn , qui s’identifie par dualité à Rn lui-même) est différentiable
On note alors D2 f (a) = D(Df )(a) (application linéaire de Rn dans (Rn ) la différentielle seconde ainsi obtenue. Cette application linéaire est représentée dans les bases canoniques (base canonique de Rn et base duale canonique de (Rn ) par une matrice carrée appelée matrice Hessienne de f en a, souvent notée 2 f On note vérifier que 32f òxi ôxj (a) le vecteur òxj (a), et on abrège a2f ò2f axi ôxj axj Autrement dit, la matrice est symétrique, ou bien la forme bilinéaire D2 f (a) est symétrique. Théorème 3 (Formule de Taylor-Young à l’ordre 2).
Soit U un ouvert de Rn et a E LJ . Si f : IJ — R est deux fois différentiable en a, on a + h) – fla) – Df (a)h – D2 h) = h 2) lorsque h tend vers O dans Rn Rappelons au passage la formule de Taylor-l_agrange à l’ordre 2 pour les fonctions g : R R deux fois dérivables en a G R (dont la preuve repose sur le théorème de Rolle) : pour tout h R, il existe [0, 1] tel que g(a + h) = g(a) + g (a)h + g (a + 9h)h2 . Si f : IJ Rest une fonction différentiable sur un ouvert IJ de Rn , cette formule est en particulier applicable à la fonction g(t) = f (a + tv) pour tout a E IJ et v E Rn . Conditions d’optimalité 7 2 minimum. Théorème 4. Soient U un ouvert de Rn , et f : IJ R une fonction numérique. 1 Condition nécessalre (pas suffisante) du premier ordre : si f admet en a un extremum local et si f est différentiable en a, alors Of (a) = O. 2. Condition nécessaire (pas suffisante) du second ordre : si f admet en a un minimum local et si f est deux fois différentiable en a, alors Df (a) = O et D2 f h) O pour tout vecteur h e Rn . 3.
Condition suffisante (pas nécessaire) du second ordre : si f est deux fois différentiable en a, Of (a) = O et D2 f (a)(h, h) > O pour tout h E Rn — alors f admet en a un minimum local strict. 2. 1 Optimisation de fonctions quadratiques Solution analytique On considère le problème (1) dans le cas où l’expert choisit la catégorie des modèles affines : f (x) = wTx p avec w E Rn et E R Afin de simplifier les notations, on introduit le paramètre yi p . c de taille N Mn + 1). 9 appelee équations normales. Exercice 4.
Montrer (2). 2. 2 Régularisation Comme toujours dans un tel problème d’apprentissage, la tentation est grande de « surapprendre » les données. Pour éviter ce désagrément, il est possible d’introduire un terme de régularisation, empêchant le paramètre a de prendre des valeurs trop importantes : a-y pour e E Rn+l avec un paramètre À de régularisation. Dans ce cas particulier, on trouve également une solution optimale de manière analyti ue ui doit vérifier l’équation (XI + X T = X TV, avec la ma . PAGFGOF12 (xk ) (sauf si on a atteint le minimum, c’est-à-dire xk ) 3. 2 Cas des fonctions convexes On fixe dans toute la sous-section un ouvert convexe U de Rn et une fonction f : LJ R. On dit que f est convexe sur IJ si, pour tous x, y E IJ et pour tout t E [O, – (x) + tf(y) – t)x + ty) s (1 où (l — t)x + ty appartient à U , grâce à ‘hypothèse de convexité de IJ . Ceci revient à dlre que le graphe e f est au-dessous des cordes. Exemple 3.
Quelques exemples de fonctions convexes – les fonctions affines : f (x) = a, x + b ; – les fonctions quadratiques : f (x) = 1 x, Ax + a, x + b avec A une matrice symétrique positive ; – les normesp:xp=(n Ixi Ip )l/p pourl = maxi – l’opposé de la fonction entropie : f (x) — – n xi log xi (la fonction entropie est donc concave). Théorème S. – Si f est différentiable, alors f est convexe sur LI si et seulement Vx,yeU ce qui revient à dire (si n = 1) que le graphe de f est au-dessus des tangentes. – Si f est deux fois différe st convexe sur U si et
