Lecciones
Acceder a Diane

Optimisation, Convexité et Différentiabilité

80 tarjetas

Dans ce document, nous explorons les concepts de convexité, différentiabilité et optimisation dans divers espaces mathématiques, y compris les espaces de Hilbert. Il aborde la définition des ensembles convexes, des fonctions convexes et leurs propriétés, ainsi que la différentielle et le gradient d'une fonction. Les théorèmes d'existence et d'unicité des solutions pour les problèmes d'optimisation sont également discutés, en tenant compte des contraintes et des propriétés des fonctions telles que la coercivité et la stricte convexité. Les exemples incluent des cas en dimension finie et infinie, ainsi que des applications dans la programmation linéaire, quadratique et convexe.

80 tarjetas

Repasar
La repetición espaciada te muestra cada tarjeta en el momento óptimo para memorizar a largo plazo, con repasos cada vez más espaciados.
Pregunta
Quand une fonction est-elle dite coercive ?
Respuesta
Une fonction ff est dite coercive si lim⁡∣x∣→+∞f(x)=+∞\lim_{|x| \to +\infty} f(x) = +\infty.
Pregunta
Quand un minimum est-il considéré comme unique ?
Respuesta
Un minimum est unique si la fonction est strictement convexe.
Pregunta
Comment un ensemble ℂ est-il défini comme convexe ?
Respuesta
Un ensemble ℂ est dit convexe si pour tous points x et y dans ℂ, le segment [x, y] est entièrement contenu dans ℂ.
Pregunta
Quand une fonction f est-elle dite différentiable en x₀ ?
Respuesta
Une fonction f est différentiable en x₀ si f(x₀ + h) = f(x₀) + L(h) + o(||h||), où L est une application linéaire.
Pregunta
Qu'est-ce qu'une fonction convexe ?
Respuesta
Une fonction est convexe si le segment de droite entre deux points quelconques du graphe se situe au-dessus de la courbe.
Pregunta
Qu'est-ce qu'un minimum local ?
Respuesta
Un minimum local est un point où la fonction a la plus petite valeur dans un voisinage immédiat.
Pregunta
Comment définit-on l'argument minimum ?
Respuesta
L'argument minimum est la valeur d'entrée qui donnerait la sortie la plus faible.
Pregunta
Quel est le rôle du théorème de représentation de Riesz dans la généralisation du gradient ?
Respuesta
Le théorème de Riesz permet d'identifier la différentielle d'une fonction à un produit scalaire, généralisant ainsi la notion de gradient.
Pregunta
Qu'est-ce qu'une suite minimisante ?
Respuesta
Une suite (xk)(x_k) est minimisante pour ff sur KK si lim⁡k→∞f(xk)=inf⁡x∈Kf(x)\lim_{k \to \infty} f(x_k) = \inf_{x \in K} f(x).
Pregunta
Quand le minimum d'une fonction n'est-il pas nécessairement atteint ?
Respuesta
Le minimum n'est pas nécessairement atteint si la fonction n'est pas coercive sur un ensemble fermé et borné.
Pregunta
Qu'est-ce que la matrice Hessienne d'une fonction f ?
Respuesta
La matrice Hessienne d'une fonction f est la matrice de ses dérivées partielles secondes. Elle contient des informations sur la convexité locale de la fonction.
Pregunta
Dans le théorème de Taylor-Lagrange à l'ordre 1, comment s'écrit f(b) ?
Respuesta
f(b)=f(a)+f′(c)(b−a)f(b) = f(a) + f'(c)(b-a) où c∈]a,b[c \in ]a, b[.
Pregunta
Qu'est-ce que l'argument minimum d'une fonction ?
Respuesta
L'argument minimum d'une fonction est la valeur d'entrée qui produit la sortie minimale de la fonction.
Pregunta
Quand une fonction est-elle dite coercive ?
Respuesta
Une fonction ff est dite coercive si f(x)f(x) tend vers +∞+\infty quand la norme de xx tend vers +∞+\infty.
Pregunta
Qu'est-ce qu'une suite dite minimisante ?
Respuesta
Une suite (xk)(x_k) est dite minimisante si la limite de f(xk)f(x_k) quand kk tend vers l'infini est égale à l'infimum de ff sur KK.
Pregunta
Comment le gradient est-il généralisé en dimension infinie ?
Respuesta
En dimension infinie, le gradient est généralisé grâce au théorème de représentation de Riesz, identifiant l'application linéaire dfx0(h)df_{x_0}(h) à ⟨Df(x0),h⟩\langle Df(x_0), h \rangle où Df(x0)Df(x_0) appartient à l'espace de Hilbert VV.
Pregunta
Quand une fonction f est-elle différentiable en x₀ ?
Respuesta
Une fonction ff est différentiable en x0x_0 si sa variation f(x0+h)−f(x0)f(x_0 + h) - f(x_0) est approximée par une application linéaire L(h)L(h) de sorte que f(x0+h)=f(x0)+L(h)+o(∣∣h∣∣)f(x_0 + h) = f(x_0) + L(h) + o(||h||).
Pregunta
Quand une fonction f est-elle dite convexe ?
Respuesta
Une fonction f est dite convexe si sa courbe se situe sous la corde reliant deux points quelconques de la courbe. Mathématiquement, ∀x,y\forall x, y et ∀t∈[0,1]\forall t \in [0, 1], f((1−t)x+ty)≤(1−t)f(x)+tf(y)f((1-t)x + ty) \leq (1-t)f(x) + tf(y).
Pregunta
Qu'est-ce qu'une fonction α-convexe ?
Respuesta
Une fonction est α-convexe si elle satisfait une condition impliquant sa dérivée seconde ou une inégalité généralisant la convexité, souvent écrite comme $ \langle \nabla \xi(y) - \nabla \xi(x), y - x \rangle \geq \alpha \|y - x\|^2 $.
Pregunta
Comment un ensemble ℂ est-il défini comme convexe ?
Respuesta
Un ensemble est dit convexe si, pour deux points quelconques de l'ensemble, le segment de droite qui les relie est entièrement contenu dans cet ensemble.
Pregunta
Quand le minimum d'une fonction n'est-il pas nécessairement atteint ?
Respuesta
Le minimum d'une fonction convexe n'est pas nécessairement atteint si l'espace n'est pas fermé ou si la fonction n'est pas coercive.
Pregunta
Qu'est-ce qu'une suite dite minimisante ?
Respuesta
Une suite dite minimisante est une suite (xk)(x_k) telle que la limite de f(xk)f(x_k) est égale à l'infimum de f(x)f(x) sur l'ensemble KK.
Pregunta
Qu'est-ce que la matrice Hessienne d'une fonction f ?
Respuesta
La matrice Hessienne d'une fonction f est la matrice de ses dérivées partielles secondes. Elle représente la courbure locale de la fonction.
Pregunta
Quand un ensemble ℂ est-il dit convexe ?
Respuesta
Un ensemble ℂ est dit convexe si pour tous points x et y appartenant à ℂ, le segment de droite joignant x et y est entièrement contenu dans ℂ.
Pregunta
Quel est le rôle du théorème de représentation de Riesz dans la généralisation du gradient ?
Respuesta
Le théorème de Riesz étend le gradient aux espaces de Hilbert, identifiant l'application linéaire différentielle dfx0(h)df_{x_0}(h) à ⟨Df(x0),h⟩\langle Df(x_0), h \rangle, généralisant ainsi la notion usuelle de gradient.
Pregunta
Qu'est-ce qu'une fonction α-convexe ?
Respuesta
Une fonction xi\\xi est alpha\\alpha-convexe si xi(y)geqslantxi(x)+langlenablaxi(x),y−xrangle+fracalpha2∣y−x∣2\\xi(y) \\geqslant \\xi(x) + \\langle \\nabla \\xi(x), y - x \\rangle + \\frac{\\alpha}{2} \\|y - x\\|^2 pour tout x,yx, y dans son domaine.
Pregunta
Quand une fonction f est-elle différentiable en x₀ ?
Respuesta
Une fonction f est différentiable en x₀ si elle admet une application linéaire df(x₀) telle que f(x₀ + h) = f(x₀) + df(x₀)(h) + o(||h||).
Pregunta
Qu'est-ce que l'argument minimum d'une fonction ?
Respuesta
L'argument minimum d'une fonction ff est la valeur xx pour laquelle f(x)f(x) atteint sa valeur minimale (son minimum).
Pregunta
Qu'est-ce qu'une fonction coercive ?
Respuesta
Une fonction coercive est une fonction dont la valeur tend vers l'infini lorsque la variable tend vers l'infini.
Pregunta
Qu'est-ce qu'un minimum local ?
Respuesta
Un minimum local d'une fonction est un point où la valeur de la fonction est inférieure ou égale à celle de tous les points voisins.
Pregunta
Quand une fonction est-elle dite coercive ?
Respuesta
Une fonction ff est dite coercive si lim⁡∥x∥→+∞f(x)=+∞\lim_{\|x\| \to +\infty} f(x) = +\infty.
Pregunta
Qu'est-ce qu'un minimum global ?
Respuesta
Un minimum global est la plus petite valeur qu'une fonction peut prendre sur tout son domaine de définition. Cette valeur peut ne pas être atteinte.
Pregunta
Comment s'appelle l'ensemble des points minimisants X* ?
Respuesta
L'ensemble des points minimisants X* s'appelle l'argument du minimum.
Pregunta
Quelle est l'équivalence d'une fonction f α-convexe lorsqu'elle est deux fois différentiable ?
Respuesta
Une fonction f α-convexe et deux fois différentiable est convexe, et sa Hessienne H est telle que ⟨H(x)h,h⟩≥α∥h∥2\langle H(x)h, h \rangle \geq \alpha \|h\|^2 pour tout x et h.
Pregunta
Qu'est-ce qu'un ensemble ℂ convexe ?
Respuesta
Un ensemble ℂ est convexe si pour tous points appartenant à ℂ, le segment de droite reliant ces points est entièrement contenu dans ℂ.
Pregunta
Qu'est-ce qu'une suite dite minimisante ?
Respuesta
Une suite minimisante (χn\chi^n) est une suite telle que f(χn)f(\chi^n) tend vers l'infimum de ff lorsque nn tend vers l'infini.
Pregunta
Quand le problème d'optimisation en dimension infinie n'admet-il pas de solution ?
Respuesta
En dimension infinie, le problème d'optimisation n'admet pas de solution lorsque les ensembles fermés bornés ne sont pas nécessairement compacts.
Pregunta
Comment l'application linéaire df(x₀(h) est-elle identifiée par le théorème de Riesz ?
Respuesta
Le théorème de Riesz identifie l'application linéaire dfx0(h)df_{x_0}(h) à un produit scalaire ⟨Df(x0),h⟩\langle Df(x_0), h \rangle, où Df(x0)Df(x_0) est un vecteur de l'espace de Hilbert V.
Pregunta
Qu'est-ce qu'un espace de Hilbert ?
Respuesta
Un espace de Hilbert est un espace vectoriel muni d'un produit scalaire, dont la norme associée est complète (toute suite de Cauchy converge). Exemple : l2(R)l^2(\mathbb{R}) ou Rn\mathbb{R}^n.
Pregunta
Quand le minimum d'une fonction n'est-il pas nécessairement atteint ?
Respuesta
Le minimum d'une fonction n'est pas nécessairement atteint lorsque l'ensemble de définition n'est pas compact et que la fonction n'est pas coercive.
Pregunta
Comment est défini l'argument minimum d'une fonction ?
Respuesta
L'argument minimum est l'ensemble des points où la fonction atteint sa valeur minimale. On l'écrit : $ \text{arg min } f(x) = \{x \in k \mid f(x) = \inf_{y \in k} f(y)\} $.
Pregunta
Qu'est-ce qu'une fonction coercive ?
Respuesta
Une fonction ff est dite coercive si lim⁡∥x∥→+∞f(x)=+∞\lim_{\|x\| \to +\infty} f(x) = +\infty.
Pregunta
Quand un problème d'optimisation en dimension finie admet-il au moins une solution ?
Respuesta
Un problème d'optimisation en dimension finie admet au moins une solution si la fonction est coercive sur un ensemble non vide et fermé, ou si elle est bornée inférieurement.
Pregunta
Qu'est-ce qu'un espace de Hilbert ?
Respuesta
Un espace de Hilbert est un espace vectoriel muni d'un produit scalaire, complet pour la norme induite par ce produit scalaire. Les exemples incluent mathbbRn\\mathbb{R}^n en dimension finie et l2(mathbbR)l^2(\\mathbb{R}) en dimension infinie.
Pregunta
Qu'est-ce qu'une fonction α-convexe ?
Respuesta
Une fonction α-convexe est une fonction f telle que f(x) - (α/2)||x||² est convexe. Alternativement, pour $ \alpha > 0 $, $ \langle \nabla f(y) - \nabla f(x), y - x \rangle \geq \alpha \|y - x\|^2 $.
Pregunta
Quelle est l'équivalence d'une fonction f α-convexe lorsqu'elle est deux fois différentiable ?
Respuesta
Lorsqu'une fonction f deux fois différentiable est α-convexe, elle est équivalente à une fonction convexe dont l'Hessien est majoré par une forme définie positive liée à α.
Pregunta
Comment un ensemble ℂ est-il défini comme convexe ?
Respuesta
Un ensemble C\mathbb{C} est convexe si pour tout x,y∈Cx, y \in \mathbb{C} et tout t∈[0,1]t \in [0, 1], le point tx+(1−t)ytx + (1-t)y appartient aussi à C\mathbb{C}.
Pregunta
Quand une fonction f est-elle dite différentiable en x₀ ?
Respuesta
Une fonction f est différentiable en x₀ s'il existe une application linéaire df(x₀) telle que f(x0+h)=f(x0)+df(x0)(h)+o(∣∣h∣∣)f(x_0 + h) = f(x_0) + df(x_0)(h) + o(||h||).
Pregunta
Comment la formule de Taylor-Lagrange à l'ordre 0 est-elle appliquée pour prouver la convexité ?
Respuesta
La formule de Taylor-Lagrange à l'ordre 0, f(y)=f(x)+⟨∇f(x),y−x⟩f(y) = f(x) + \langle \nabla f(x), y - x \rangle, est la base de la convexité, dérivant de f(y)≥f(x)+⟨∇f(x),y−x⟩f(y) \geq f(x) + \langle \nabla f(x), y - x \rangle.
Pregunta
Quand le problème d'optimisation en dimension infinie n'admet-il pas de solution ?
Respuesta
Le problème d'optimisation en dimension infinie n'admet pas de solution lorsque l'espace de Hilbert n'est pas compact, même s'il est fermé et coercitif.
Pregunta
Quand un minimiseur local est-il aussi un minimiseur global ?
Respuesta
Un minimiseur local est aussi un minimiseur global si la fonction est convexe. S'il y a strictement convexe, le minimum est unique.
Pregunta
Qu'est-ce qu'une suite dite minimisante ?
Respuesta
Une suite minimisante est une suite (xk)(x_k) telle que f(xk)f(x_k) tend vers l'infimum de la fonction ff, même si cet infimum n'est pas atteint.
Pregunta
Comment le gradient est-il généralisé en dimension infinie grâce au théorème de Riesz ?
Respuesta
Dans un espace de Hilbert V, le théorème de Riesz identifie la différentielle dfx0df_{x_0} à un produit scalaire ⟨Df(x0),h⟩\langle Df(x_0), h \rangle, généralisant ainsi le gradient.
Pregunta
Qu'appelle-t-on la fonction "loi et coût" dans l'optimisation ?
Respuesta
Une fonction "loi et coût" correspond à la fonction objectif que l'on cherche à minimiser ou maximiser dans un problème d'optimisation.
Pregunta
Dans quelles conditions une fonction f est-elle dite différentiable en x₀ ?
Respuesta
Une fonction ff est différentiable en x₀ si sa variation f(x0+h)−f(x0)f(x₀ + h) - f(x₀) peut être approximée par une application linéaire df(x0)(h)df(x₀)(h) plus un terme négligeable lorsque hh tend vers 0.
Pregunta
Qu'est-ce qu'un minimum local ?
Respuesta
Un minimum local de f est un point x tel que f(x) est inférieur ou égal à f(y) pour tout y dans un voisinage de x.
Pregunta
Dans quels cas parle-t-on d'optimisation SANS contrainte ?
Respuesta
On parle d'optimisation sans contrainte lorsque la fonction objectif n'est soumise à aucune restriction sur les valeurs de ses variables.
Pregunta
Quand un ensemble ℂ est-il dit convexe ?
Respuesta
Un ensemble C\mathbb{C} est dit convexe si pour deux points quelconques x,yx, y dans C\mathbb{C}, tout point du segment [x,y][x, y] appartient aussi à C\mathbb{C}.
Pregunta
Quand une fonction f est-elle dite coercive ?
Respuesta
Une fonction ff est dite coercive si lim⁡∥x∥→+∞f(x)=+∞\lim_{\|x\| \to +\infty} f(x) = +\infty.
Pregunta
Comment un terme tel que maxf(x)max f(x) peut-il être converti en un problème de minimisation ?
Respuesta
Pour convertir un problème de maximisation max⁡f(x)\max f(x) en un problème de minimisation, on minimise l'opposé de la fonction : min⁡−f(x)\min -f(x).
Pregunta
Qu'est-ce qu'un minimum local ?
Respuesta
Un minimum local est un point où la fonction prend une valeur inférieure ou égale à celle de tous les points voisins.
Pregunta
Comment le problème maxf(x)max f(x) est-il converti en un problème de minimisation ?
Respuesta
Pour convertir un problème de maximisation max⁡f(x)\max f(x) en un problème de minimisation, on minimise sa fonction opposée : min⁡−f(x)\min -f(x).
Pregunta
Quand une fonction f est-elle dite coercive ?
Respuesta
Une fonction f est dite coercive si lim⁡∥x∥→+∞f(x)=+∞\lim_{\|x\| \to +\infty} f(x) = +\infty.
Pregunta
Comment est défini l'argument minimum d'une fonction ?
Respuesta
L'argument minimum est l'ensemble des x∈Kx \in K tels que f(x)f(x) est le minimum de la fonction ff sur l'ensemble KK.
Pregunta
Quand le problème d'optimisation en dimension infinie n'admet-il pas de solution ?
Respuesta
Le problème d'optimisation en dimension infinie n'admet pas de solution lorsque l'espace n'est pas compact, même si la fonction est coercive. Les ensembles fermés bornés ne sont pas forcément compacts en dimension infinie.
Pregunta
Qu'est-ce qu'une suite dite minimisante (xkx^k) ?
Respuesta
Une suite minimisante (χk\chi^k) d'une fonction ff sur un ensemble KK est une suite telle que lim⁡k→∞f(χk)=inf⁡x∈Kf(x)\lim_{k \to \infty} f(\chi^k) = \inf_{x \in K} f(x).
Pregunta
Qu'est-ce qu'une fonction α-convexe ?
Respuesta
Une fonction ff est dite α-convexe si elle est différentiable, et sa seconde dérivée Hess(f)(x)Hess(f)(x) vérifie ⟨Hess(f)(x)h,h⟩≥α∥h∥2\langle Hess(f)(x) h, h \rangle \geq \alpha \|h\|^2 pour tout x,hx, h. Alternativement, f−α2∥⋅∥2f - \frac{\alpha}{2} \| \cdot \|^2 est convexe.
Pregunta
Qu'est-ce qu'une fonction f différentiable en x0x_0 ?
Respuesta
Une fonction 'f' est différentiable en x₀ si elle admet une application linéaire 'df(x₀)' telle que f(x₀ + h) = f(x₀) + df(x₀)(h) + o(||h||).
Pregunta
Qu'est-ce qu'un espace de Hilbert ?
Respuesta
Un espace de Hilbert est un espace vectoriel muni d'un produit scalaire, qui est complet pour la norme induite par ce produit scalaire. Les suites de Cauchy y convergent.
Pregunta
Comment un ensemble ℂ est-il défini comme convexe ?
Respuesta
Un ensemble C\mathbb{C} est convexe si pour tout segment reliant deux points de C\mathbb{C}, ce segment reste entièrement dans C\mathbb{C}.
Pregunta
Qu'est-ce qu'une fonction α-convexe ?
Respuesta
Une fonction α-convexe est une fonction ff dont la fonction g(x)=f(x)−α2∥x∥2g(x) = f(x) - \frac{\alpha}{2} \|x\|^2 est convexe. Cela implique que la fonction est coercive.
Pregunta
Quand une fonction \(\xi\) est-elle dite coercive ?
Respuesta
Une fonction \(f: E \to \mathbb{R}\) est dite coercive si \(\lim_{\|\mathbb{X}\| \to +\infty} f(x) = +\infty\).
Pregunta
Quand un ensemble \(\mathbb{C}\) est-il considéré comme convexe ?
Respuesta
Un ensemble C\mathbb{C} est convexe si pour tout couple de points dans C\mathbb{C}, le segment de droite reliant ces points est entièrement contenu dans C\mathbb{C}.
Pregunta
Dans quelles conditions un problème d'optimisation en dimension finie admet-il au moins une solution ?
Respuesta
Un problème d'optimisation en dimension finie admet une solution si la fonction objectif est coercive sur un ensemble K non vide et fermé, ou si K est un compact.
Pregunta
Quand une fonction \(f\) est-elle dite différentiable en \(x_0\) ?
Respuesta
Une fonction \(f\) est différentiable en \(x_0\) si sa variation peut être approchée par une application linéaire: \(f(x_0 + h) = f(x_0) + df(x_0)(h) + o(||h||)\).
Pregunta
Quel est le rôle du théorème de Zorn dans l'existence des minimiseurs ?
Respuesta
Le théorème de Zorn n'est pas directement mentionné comme rôle dans l'existence des minimiseurs dans ce contexte. L'existence est plutôt assurée par des conditions telles que la compacité du domaine ou la coercivité de la fonction dans Rn\mathbb{R}^n.
Pregunta
Comment le gradient est-il généralisé en dimension infinie ?
Respuesta
En dimension infinie, le gradient est généralisé grâce au théorème de Riesz, identifiant la différentielle dfx0(h)df_{x_0}(h) à un produit scalaire ⟨Df(x0),h⟩\langle Df(x_0), h \rangle, avec Df(x0)Df(x_0) dans l'espace de Hilbert.
Pregunta
Comment la formule de Taylor-Lagrange à l'ordre 0 est-elle appliquée pour prouver la convexité ?
Respuesta
La formule de Taylor-Lagrange à l'ordre 0 établit que f(y)=f(x)+⟨∇f(x),y−x⟩f(y) = f(x) + \langle \nabla f(x), y - x \rangle pour une fonction convexe, ce qui démontre la propriété de convexité.
Pregunta
Qu'est-ce qu'un minimiseur global ?
Respuesta
Un minimiseur global est un point où une fonction atteint sa plus petite valeur sur son domaine. Les fonctions convexes ont la propriété que tout minimum local est aussi un minimum global.
Pregunta
Qu'est-ce qu'un espace de Hilbert ?
Respuesta
Un espace de Hilbert est un espace vectoriel munis d'un produit scalaire, complet pour la norme issue de ce produit scalaire. Les espaces de dimension finie (Rn\mathbb{R}^n) et infinie (l2l^2) en sont des exemples.

Voici une note exhaustive sur les concepts fondamentaux de l'optimisation, de la convexité et de la différentiabilité, rédigée en français et structurée pour l'apprentissage.

Introduction aux Problèmes d'Optimisation

L'optimisation mathématique consiste à trouver le meilleur élément dans un ensemble de candidats, selon un critère donné. On cherche typiquement à minimiser ou maximiser une fonction sur un domaine spécifique.

1. Formulation du Problème

Soit V un espace vectoriel normé. Un problème d'optimisation classique se formule comme suit :

Trouver tel que soit la plus petite valeur possible, où est un sous-ensemble de (appelé ensemble des contraintes) et est la fonction objectif (ou fonction coût).

Ce problème est noté : \sup_{x \in K} f(x)\inf_{x \in K} (-f(x)).</p><ulclass="tight"data−tight="true"><li><pstyle="text−align:left;"><strong>Optimisationsanscontrainte</strong>:quand<spandata−latex="K=V"data−type="inline−math"></span>.</p></li><li><pstyle="text−align:left;"><strong>Optimisationsouscontraintes</strong>:quand<spandata−latex="K"data−type="inline−math"></span>estunsous−ensemblestrictde<spandata−latex="V"data−type="inline−math"></span>.</p></li></ul><h3style="text−align:left;">2.ConceptsCleˊs</h3><ulclass="tight"data−tight="true"><li><pstyle="text−align:left;"><strong>Infimum(m)</strong>:Laplusgrandedesbornesinfeˊrieuresdel′ensembledesvaleursde<spandata−latex="f(x)"data−type="inline−math"></span>.Onnote<spandata−latex="m=inf⁡x∈Kf(x)"data−type="inline−math"></span>.Cettevaleurn′estpastoujoursatteinte,c′est−aˋ−direqu′iln′existepasforceˊmentde<spandata−latex="x∗∈K"data−type="inline−math"></span>telque<spandata−latex="f(x∗)=m"data−type="inline−math"></span>.Parexemple,si<spandata−latex="m=−∞"data−type="inline−math"></span>.</p></li><li><pstyle="text−align:left;"><strong>Suiteminimisante</strong>:Me^mesileminimumn′estpasatteint,onpeutsouventtrouverunesuite<spandata−latex="(xk)k∈N⊂K"data−type="inline−math"></span>tellequelasuitedesvaleursdelafonctiontendeversl′infimum.<spandata−latex=".</p><ul class="tight" data-tight="true"><li><p style="text-align: left;"><strong>Optimisation sans contrainte</strong> : quand <span data-latex="K = V" data-type="inline-math"></span>.</p></li><li><p style="text-align: left;"><strong>Optimisation sous contraintes</strong> : quand <span data-latex="K" data-type="inline-math"></span> est un sous-ensemble strict de <span data-latex="V" data-type="inline-math"></span>.</p></li></ul><h3 style="text-align: left;">2. Concepts Clés</h3><ul class="tight" data-tight="true"><li><p style="text-align: left;"><strong>Infimum (m)</strong> : La plus grande des bornes inférieures de l'ensemble des valeurs de <span data-latex="f(x)" data-type="inline-math"></span>. On note <span data-latex="m = \inf_{x \in K} f(x)" data-type="inline-math"></span>. Cette valeur n'est pas toujours atteinte, c'est-à-dire qu'il n'existe pas forcément de <span data-latex="x^* \in K" data-type="inline-math"></span> tel que <span data-latex="f(x^*) = m" data-type="inline-math"></span>. Par exemple, si <span data-latex="m = -\infty" data-type="inline-math"></span>.</p></li><li><p style="text-align: left;"><strong>Suite minimisante</strong> : Même si le minimum n'est pas atteint, on peut souvent trouver une suite <span data-latex="(x_k)_{k \in \mathbb{N}} \subset K" data-type="inline-math"></span> telle que la suite des valeurs de la fonction tende vers l'infimum. <span data-latex=" \lim_{k \to \infty} f(x_k) = m " data-type="inline-math"></p></li><li><pstyle="text−align:left;"><strong>Minimiseur(ousolution)</strong>:C′estunpoint<spandata−latex="x∗∈K"data−type="inline−math"></span>quiatteintl′infimum,c′est−aˋ−dire<spandata−latex="f(x∗)=m"data−type="inline−math"></span>.S′ilexiste,onditqueleminimumest<em>atteint</em>.</p></li><li><pstyle="text−align:left;"><strong>Argumentduminimum(argmin)</strong>:C′estl′ensembledetouslesminimiseurs.<spandata−latex="</p></li><li><p style="text-align: left;"><strong>Minimiseur (ou solution)</strong> : C'est un point <span data-latex="x^* \in K" data-type="inline-math"></span> qui atteint l'infimum, c'est-à-dire <span data-latex="f(x^*) = m" data-type="inline-math"></span>. S'il existe, on dit que le minimum est <em>atteint</em>.</p></li><li><p style="text-align: left;"><strong>Argument du minimum (argmin)</strong> : C'est l'ensemble de tous les minimiseurs. <span data-latex=" \arg\min_{x \in K} f(x) = \{ x^* \in K \mid f(x^*) = \inf_{y \in K} f(y) \} " data-type="inline-math">x^*\arg\min_{x \in K} f(x) = x^*.</p></li></ul><h3style="text−align:left;">3.MinimumLocalvs.MinimumGlobal</h3><ulclass="tight"data−tight="true"><li><pstyle="text−align:left;">Unpoint<spandata−latex="x∗∈K"data−type="inline−math"></span>estun<strong>minimiseurglobal</strong>si<spandata−latex="f(x∗)≤f(x)"data−type="inline−math"></span>pourtout<spandata−latex="x∈K"data−type="inline−math"></span>.</p></li><li><pstyle="text−align:left;">Unpoint<spandata−latex="x∗∈K"data−type="inline−math"></span>estun<strong>minimiseurlocal</strong>s′ilexisteunvoisinage<spandata−latex="V"data−type="inline−math"></span>de<spandata−latex="x∗"data−type="inline−math"></span>telque<spandata−latex="f(x∗)≤f(x)"data−type="inline−math"></span>pourtout<spandata−latex="x∈K∩V"data−type="inline−math"></span>.</p></li></ul><pstyle="text−align:left;">Toutminimiseurglobalestunminimiseurlocal.Lareˊciproquen′estvraiequesouscertainesconditions,notammentlaconvexiteˊ.</p><h2style="text−align:left;">Rappelsd′Analyse:OutilsFondamentaux</h2><pstyle="text−align:left;">Pourgarantirl′existenceetl′uniciteˊdessolutions,ons′appuiesurdesproprieˊteˊscleˊsdelafonctionobjectifetdel′ensembledescontraintes.</p><h3style="text−align:left;">1.Diffeˊrentiabiliteˊ</h3><pstyle="text−align:left;">Ladiffeˊrentiabiliteˊpermetdeconstruiredesapproximationslocaleslineˊairesdelafonction,cequiestessentielpourlesalgorithmesd′optimisation.</p><blockquote><pstyle="text−align:left;"><strong>Deˊfinition(Diffeˊrentiabiliteˊ)</strong>:Soient<spandata−latex="E"data−type="inline−math"></span>et<spandata−latex="F"data−type="inline−math"></span>deuxespacesvectorielsnormeˊs,<spandata−latex="U"data−type="inline−math"></span>unouvertde<spandata−latex="E"data−type="inline−math"></span>et<spandata−latex="x0∈U"data−type="inline−math"></span>.Unefonction<spandata−latex="f:U→F"data−type="inline−math"></span>estdite<strong>diffeˊrentiable</strong>en<spandata−latex="x0"data−type="inline−math"></span>s′ilexisteuneapplicationlineˊairecontinue,noteˊe<spandata−latex="df(x0):E→F"data−type="inline−math"></span>,telleque:<spandata−latex=".</p></li></ul><h3 style="text-align: left;">3. Minimum Local vs. Minimum Global</h3><ul class="tight" data-tight="true"><li><p style="text-align: left;">Un point <span data-latex="x^* \in K" data-type="inline-math"></span> est un <strong>minimiseur global</strong> si <span data-latex="f(x^*) \leq f(x)" data-type="inline-math"></span> pour tout <span data-latex="x \in K" data-type="inline-math"></span>.</p></li><li><p style="text-align: left;">Un point <span data-latex="x^* \in K" data-type="inline-math"></span> est un <strong>minimiseur local</strong> s'il existe un voisinage <span data-latex="\mathcal{V}" data-type="inline-math"></span> de <span data-latex="x^*" data-type="inline-math"></span> tel que <span data-latex="f(x^*) \leq f(x)" data-type="inline-math"></span> pour tout <span data-latex="x \in K \cap \mathcal{V}" data-type="inline-math"></span>.</p></li></ul><p style="text-align: left;">Tout minimiseur global est un minimiseur local. La réciproque n'est vraie que sous certaines conditions, notamment la convexité.</p><h2 style="text-align: left;">Rappels d'Analyse : Outils Fondamentaux</h2><p style="text-align: left;">Pour garantir l'existence et l'unicité des solutions, on s'appuie sur des propriétés clés de la fonction objectif et de l'ensemble des contraintes.</p><h3 style="text-align: left;">1. Différentiabilité</h3><p style="text-align: left;">La différentiabilité permet de construire des approximations locales linéaires de la fonction, ce qui est essentiel pour les algorithmes d'optimisation.</p><blockquote><p style="text-align: left;"><strong>Définition (Différentiabilité)</strong> : Soient <span data-latex="E" data-type="inline-math"></span> et <span data-latex="F" data-type="inline-math"></span> deux espaces vectoriels normés, <span data-latex="U" data-type="inline-math"></span> un ouvert de <span data-latex="E" data-type="inline-math"></span> et <span data-latex="x_0 \in U" data-type="inline-math"></span>. Une fonction <span data-latex="f: U \to F" data-type="inline-math"></span> est dite <strong>différentiable</strong> en <span data-latex="x_0" data-type="inline-math"></span> s'il existe une application linéaire continue, notée <span data-latex="df(x_0): E \to F" data-type="inline-math"></span>, telle que : <span data-latex=" f(x_0 + h) = f(x_0) + df(x_0)(h) + o(\|h\|_E) " data-type="inline-math">o(\|h\|_E)\|h\|_Edf(x_0)$ est la différentielle de en .

  • Dérivée directionnelle : Si est différentiable en , sa dérivée dans la direction est donnée par : </p></li><li><pstyle="text−align:left;"><strong>Gradient(endimensionfinieoudansunHilbert)</strong>:Sil′espacededeˊpartest<spandata−latex="Rn"data−type="inline−math"></span>(ouplusgeˊneˊralementunespacedeHilbert)etl′espaced′arriveˊeest<spandata−latex="R"data−type="inline−math"></span>,ladiffeˊrentiellepeute^trerepreˊsenteˊeparunproduitscalaire.Le<strong>gradient</strong>de<spandata−latex="f"data−type="inline−math"></span>en<spandata−latex="x0"data−type="inline−math"></span>,noteˊ<spandata−latex="∇f(x0)"data−type="inline−math"></span>,estlevecteuruniquetelque:<spandata−latex="</p></li><li><p style="text-align: left;"><strong>Gradient (en dimension finie ou dans un Hilbert)</strong> : Si l'espace de départ est <span data-latex="\mathbb{R}^n" data-type="inline-math"></span> (ou plus généralement un espace de Hilbert) et l'espace d'arrivée est <span data-latex="\mathbb{R}" data-type="inline-math"></span>, la différentielle peut être représentée par un produit scalaire. Le <strong>gradient</strong> de <span data-latex="f" data-type="inline-math"></span> en <span data-latex="x_0" data-type="inline-math"></span>, noté <span data-latex="\nabla f(x_0)" data-type="inline-math"></span>, est le vecteur unique tel que : <span data-latex=" df(x_0)(h) = \langle \nabla f(x_0), h \rangle " data-type="inline-math"></p></li><li><pstyle="text−align:left;"><strong>MatriceHessienne</strong>:Si<spandata−latex="f:Rn→R"data−type="inline−math"></span>estdeuxfoisdiffeˊrentiable,sadiffeˊrentiellesecondeestuneformebilineˊairesymeˊtriquerepreˊsenteˊeparla<strong>matriceHessienne</strong>,noteˊe<spandata−latex="Hess f(x0)"data−type="inline−math"></span>.Sescoefficientssontlesdeˊriveˊespartiellessecondes:<spandata−latex="</p></li><li><p style="text-align: left;"><strong>Matrice Hessienne</strong> : Si <span data-latex="f: \mathbb{R}^n \to \mathbb{R}" data-type="inline-math"></span> est deux fois différentiable, sa différentielle seconde est une forme bilinéaire symétrique représentée par la <strong>matrice Hessienne</strong>, notée <span data-latex="\text{Hess } f(x_0)" data-type="inline-math"></span>. Ses coefficients sont les dérivées partielles secondes : <span data-latex=" (\text{Hess } f(x_0))_{ij} = \frac{\partial^2 f}{\partial x_i \partial x_j}(x_0) " data-type="inline-math"></p></li><li><pstyle="text−align:left;"><strong>FormulesdeTaylor</strong>:Ellesapprochentlafonctionlocalement.</p><ulclass="tight"data−tight="true"><li><pstyle="text−align:left;"><strong>Ordre1</strong>:<spandata−latex="f(x0+h)=f(x0)+⟨∇f(x0),h⟩+o(∥h∥)"data−type="inline−math"></span></p></li><li><pstyle="text−align:left;"><strong>Ordre2</strong>:<spandata−latex="f(x0+h)=f(x0)+⟨∇f(x0),h⟩+12⟨(Hess f(x0))h,h⟩+o(∥h∥2)"data−type="inline−math"></span></p></li></ul></li></ul><h3style="text−align:left;">2.Coerciviteˊ</h3><pstyle="text−align:left;">Lacoerciviteˊassurequelafonctionnepeutpas"s′eˊchapper"versdesvaleursbassesaˋl′infini,contraignantainsilesminimiseursaˋsetrouverdansunereˊgionborneˊe.</p><blockquote><pstyle="text−align:left;"><strong>Deˊfinition(Coerciviteˊ)</strong>:Unefonction<spandata−latex="f:K→R"data−type="inline−math"></span>deˊfiniesurunepartienonborneˊe<spandata−latex="K"data−type="inline−math"></span>d′unespacenormeˊ<spandata−latex="E"data−type="inline−math"></span>estdite<strong>coercive</strong>si:<spandata−latex="</p></li><li><p style="text-align: left;"><strong>Formules de Taylor</strong> : Elles approchent la fonction localement.</p><ul class="tight" data-tight="true"><li><p style="text-align: left;"><strong>Ordre 1</strong>: <span data-latex="f(x_0 + h) = f(x_0) + \langle \nabla f(x_0), h \rangle + o(\|h\|)" data-type="inline-math"></span></p></li><li><p style="text-align: left;"><strong>Ordre 2</strong>: <span data-latex="f(x_0 + h) = f(x_0) + \langle \nabla f(x_0), h \rangle + \frac{1}{2} \langle (\text{Hess } f(x_0))h, h \rangle + o(\|h\|^2)" data-type="inline-math"></span></p></li></ul></li></ul><h3 style="text-align: left;">2. Coercivité</h3><p style="text-align: left;">La coercivité assure que la fonction ne peut pas "s'échapper" vers des valeurs basses à l'infini, contraignant ainsi les minimiseurs à se trouver dans une région bornée.</p><blockquote><p style="text-align: left;"><strong>Définition (Coercivité)</strong> : Une fonction <span data-latex="f: K \to \mathbb{R}" data-type="inline-math"></span> définie sur une partie non bornée <span data-latex="K" data-type="inline-math"></span> d'un espace normé <span data-latex="E" data-type="inline-math"></span> est dite <strong>coercive</strong> si : <span data-latex=" \lim_{\|x\| \to +\infty, x \in K} f(x) = +\infty " data-type="inline-math"></p></blockquote><h3 style="text-align: left;">3. Ensembles et Fonctions Convexes</h3><p style="text-align: left;">La convexité est la propriété la plus puissante en optimisation, simplifiant radicalement l'analyse des problèmes.</p><table style="min-width: 50px;"><colgroup><col style="min-width: 25px;"><col style="min-width: 25px;"></colgroup><tbody><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Ensemble Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Un ensemble <span data-latex="K" data-type="inline-math"></span> est <strong>convexe</strong> si pour tous <span data-latex="x, y \in K" data-type="inline-math"></span>, le segment <span data-latex="[x, y]" data-type="inline-math"></span> est entièrement inclus dans <span data-latex="K" data-type="inline-math"></span>. Autrement dit :<br><span data-latex="\forall x, y \in K, \forall t \in [0, 1], \quad (1-t)x + ty \in K" data-type="inline-math"></span></p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Fonction Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Soit <span data-latex="K" data-type="inline-math"></span> un ensemble convexe. Une fonction <span data-latex="f: K \to \mathbb{R}" data-type="inline-math"></span> est <strong>convexe</strong> si son épigraphe est un ensemble convexe, ou de façon équivalente, si pour tous <span data-latex="x, y \in K" data-type="inline-math"></span> et <span data-latex="t \in [0, 1]" data-type="inline-math"></span> :<br><span data-latex="f((1-t)x + ty) \leq (1-t)f(x) + tf(y)" data-type="inline-math"></span><br><em>Géométriquement, la corde entre deux points du graphe est toujours au-dessus du graphe.</em></p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Fonction Strictement Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">La même inégalité, mais stricte pour <span data-latex="x \neq y" data-type="inline-math"></span> et <span data-latex="t \in (0, 1)" data-type="inline-math"></span> :<br><span data-latex="f((1-t)x + ty) &lt; (1-t)f(x) + tf(y)" data-type="inline-math"></span></p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Fonction Fortement Convexe (ou </strong><span data-latex="\alpha" data-type="inline-math"></span><strong>-convexe)</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Il existe une constante <span data-latex="\alpha &gt; 0" data-type="inline-math"></span> telle qu'une version renforcée de l'inégalité de convexité est vérifiée :<br><span data-latex="f((1-t)x + ty) \leq (1-t)f(x) + tf(y) - \frac{\alpha}{2}t(1-t)\|x-y\|^2" data-type="inline-math"></span><br><em>Cela signifie que la fonction est "plus courbée" qu'une parabole de coefficient </em><span data-latex="\alpha" data-type="inline-math"></span><em>. Une fonction </em><span data-latex="\alpha" data-type="inline-math"></span><em>-convexe est forcément strictement convexe.</em></p></td></tr></tbody></table><blockquote><p style="text-align: left;"><strong>Propriété fondamentale</strong> : Une fonction <span data-latex="f" data-type="inline-math"></span> est <span data-latex="\alpha" data-type="inline-math"></span>-convexe si et seulement si la fonction <span data-latex="g(x) = f(x) - \frac{\alpha}{2}\|x\|^2" data-type="inline-math"></span> est convexe.</p></blockquote><h2 style="text-align: left;">Caractérisation de la Convexité pour les Fonctions Différentiables</h2><p style="text-align: left;">Lorsque la fonction objectif <span data-latex="f" data-type="inline-math"></span> est différentiable, la convexité peut être caractérisée par des conditions sur son gradient et sa Hessienne.</p><h3 style="text-align: left;">1. Conditions du Premier Ordre (Gradient)</h3><p style="text-align: left;">Soit <span data-latex="f: K \to \mathbb{R}" data-type="inline-math"></span> une fonction différentiable sur un ouvert convexe <span data-latex="K" data-type="inline-math"></span>.</p><table style="min-width: 75px;"><colgroup><col style="min-width: 25px;"><col style="min-width: 25px;"><col style="min-width: 25px;"></colgroup><tbody><tr><th colspan="1" rowspan="1"><p style="text-align: left;">Type de Convexité</p></th><th colspan="1" rowspan="1"><p style="text-align: left;">Caractérisation équivalente (Inégalité)</p></th><th colspan="1" rowspan="1"><p style="text-align: left;">Interprétation géométrique/Analytique</p></th></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Pour tous <span data-latex="x, y \in K" data-type="inline-math"></span>:<br><span data-latex="f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle" data-type="inline-math"></span></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">La fonction est toujours au-dessus de son hyperplan tangent en n'importe quel point.</p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Pour tous <span data-latex="x, y \in K" data-type="inline-math"></span>:<br><span data-latex="\langle \nabla f(y) - \nabla f(x), y-x \rangle \geq 0" data-type="inline-math"></span></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">L'opérateur gradient <span data-latex="\nabla f" data-type="inline-math"></span> est monotone.</p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Strictement Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Pour tous <span data-latex="x, y \in K" data-type="inline-math"></span> avec <span data-latex="x \neq y" data-type="inline-math"></span>:<br><span data-latex="f(y) &gt; f(x) + \langle \nabla f(x), y-x \rangle" data-type="inline-math"></span></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">La fonction est strictement au-dessus de ses hyperplans tangents (sauf au point de tangence).</p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Fortement Convexe (</strong><span data-latex="\alpha" data-type="inline-math"></span><strong>-convexe)</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Pour tous <span data-latex="x, y \in K" data-type="inline-math"></span>:<br><span data-latex="f(y) \geq f(x) + \langle \nabla f(x), y-x \rangle + \frac{\alpha}{2}\|y-x\|^2" data-type="inline-math"></span></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">La fonction est au-dessus de ses tangentes avec une marge quadratique.</p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Fortement Convexe (</strong><span data-latex="\alpha" data-type="inline-math"></span><strong>-convexe)</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">Pour tous <span data-latex="x, y \in K" data-type="inline-math"></span>:<br><span data-latex="\langle \nabla f(y) - \nabla f(x), y-x \rangle \geq \alpha \|y-x\|^2" data-type="inline-math"></span></p></td><td colspan="1" rowspan="1"><p style="text-align: left;">L'opérateur gradient <span data-latex="\nabla f" data-type="inline-math"></span> est fortement monotone.</p></td></tr></tbody></table><h3 style="text-align: left;">2. Conditions du Second Ordre (Hessienne)</h3><p style="text-align: left;">Si <span data-latex="f" data-type="inline-math"></span> est deux fois différentiable sur un ouvert convexe <span data-latex="K \subset \mathbb{R}^n" data-type="inline-math"></span>.</p><table style="min-width: 50px;"><colgroup><col style="min-width: 25px;"><col style="min-width: 25px;"></colgroup><tbody><tr><th colspan="1" rowspan="1"><p style="text-align: left;">Type de Convexité</p></th><th colspan="1" rowspan="1"><p style="text-align: left;">Caractérisation (Hessienne)</p></th></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;"><span data-latex="\forall x \in K" data-type="inline-math"></span>, la matrice Hessienne <span data-latex="\text{Hess } f(x)" data-type="inline-math"></span> est <strong>semi-définie positive</strong>.<br>(<span data-latex="\forall h \in \mathbb{R}^n, \langle (\text{Hess }f(x))h, h \rangle \geq 0" data-type="inline-math"></span>)</p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Strictement Convexe</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;"><span data-latex="\forall x \in K" data-type="inline-math"></span>, si <span data-latex="\text{Hess } f(x)" data-type="inline-math"></span> est <strong>définie positive</strong>, alors <span data-latex="f" data-type="inline-math"></span> est strictement convexe.<br>(<span data-latex="\forall h \neq 0, \langle (\text{Hess }f(x))h, h \rangle &gt; 0" data-type="inline-math"></span>).<br><mark>Attention : la réciproque est fausse. Par exemple, </mark><span data-latex="f(x)=x^4" data-type="inline-math"></span><mark> est strictement convexe mais sa dérivée seconde </mark><span data-latex="12x^2" data-type="inline-math"></span><mark> est nulle en </mark><span data-latex="x=0" data-type="inline-math"></span><mark>.</mark></p></td></tr><tr><td colspan="1" rowspan="1"><p style="text-align: left;"><strong>Fortement Convexe (</strong><span data-latex="\alpha" data-type="inline-math"></span><strong>-convexe)</strong></p></td><td colspan="1" rowspan="1"><p style="text-align: left;"><span data-latex="\forall x \in K, \forall h \in \mathbb{R}^n" data-type="inline-math"></span>:<br><span data-latex="\langle (\text{Hess } f(x))h, h \rangle \geq \alpha \|h\|^2" data-type="inline-math"></span>.<br>(Ceci est équivalent à dire que la plus petite valeur propre de <span data-latex="\text{Hess } f(x)" data-type="inline-math"></span> est supérieure ou égale à <span data-latex="\alpha" data-type="inline-math"></span>).</p></td></tr></tbody></table><blockquote><p style="text-align: left;"><strong>Propriété</strong>: Si une fonction est <span data-latex="\alpha" data-type="inline-math"></span>-convexe sur <span data-latex="\mathbb{R}^n" data-type="inline-math"></span>, elle est nécessairement coercive.</p></blockquote><h2 style="text-align: left;">Théorèmes d'Existence et d'Unicité des Solutions</h2><h3 style="text-align: left;">1. Impact de la Convexité sur les Minimiseurs</h3><blockquote><p style="text-align: left;"><strong>Théorème 1</strong>: Si <span data-latex="f" data-type="inline-math"></span> est une fonction <strong>convexe</strong> sur un ensemble convexe <span data-latex="K" data-type="inline-math"></span>, alors tout minimiseur local est un <strong>minimiseur global</strong>. De plus, l'ensemble des minimiseurs <span data-latex="argmin_K f" data-type="inline-math"></span> est un ensemble <strong>convexe</strong>.</p></blockquote><blockquote><p style="text-align: left;"><strong>Théorème 2</strong>: Si <span data-latex="f" data-type="inline-math"></span> est une fonction <strong>strictement convexe</strong> sur un ensemble convexe <span data-latex="K" data-type="inline-math"></span>, alors le problème d'optimisation admet au plus <strong>un</strong> minimiseur. L'unicité est donc garantie s'il en existe un.</p></blockquote><h3 style="text-align: left;">2. Le Cas de la Dimension Finie (<span data-latex="\mathbb{R}^n" data-type="inline-math"></span>)</h3><p style="text-align: left;">En dimension finie, l'existence d'une solution est souvent garantie par le théorème de Weierstrass, qui stipule qu'une fonction continue sur un ensemble compact atteint ses bornes.</p><blockquote><p style="text-align: left;"><strong>Théorème d'existence en dimension finie</strong>: Soit <span data-latex="f: K \subset \mathbb{R}^n \to \mathbb{R}" data-type="inline-math"></span> une fonction <strong>continue</strong> et <span data-latex="K" data-type="inline-math"></span> un ensemble <strong>non vide et fermé</strong>. Si l'une des deux conditions suivantes est vérifiée :</p><ol class="tight" data-tight="true"><li><p style="text-align: left;"><span data-latex="K" data-type="inline-math"></span> est <strong>borné</strong> (et donc compact car fermé).</p></li><li><p style="text-align: left;"><span data-latex="f" data-type="inline-math"></span> est <strong>coercive</strong>.</p></li></ol><p style="text-align: left;">Alors le problème <span data-latex="\inf_{x \in K} f(x)" data-type="inline-math"></span> admet au moins <strong>une solution</strong> (minimiseur global).</p></blockquote><p style="text-align: left;"><em>Preuve (cas coercif)</em> : Soit <span data-latex="a \in K" data-type="inline-math"></span>. On considère le sous-ensemble <span data-latex="\bar{K} = \{ x \in K \mid f(x) \leq f(a) \}" data-type="inline-math"></span>. Tout minimiseur global doit être dans <span data-latex="\bar{K}" data-type="inline-math"></span>. Puisque <span data-latex="f" data-type="inline-math"></span> est continue, <span data-latex="\bar{K}" data-type="inline-math"></span> est fermé. Puisque <span data-latex="f" data-type="inline-math"></span> est coercive, <span data-latex="\bar{K}" data-type="inline-math"></span> est borné. <span data-latex="\bar{K}" data-type="inline-math"></span> est donc un compact non vide. D'après le théorème de Weierstrass, <span data-latex="f" data-type="inline-math"></span> atteint son minimum sur <span data-latex="\bar{K}" data-type="inline-math"></span>, qui est aussi le minimum global sur <span data-latex="K" data-type="inline-math"></span>.</p><h3 style="text-align: left;">3. Le Cas de la Dimension Infinie (Espaces de Hilbert)</h3><p style="text-align: left;"><strong><mark>Avertissement crucial</mark></strong><mark> : En dimension infinie, les ensembles fermés et bornés ne sont pas nécessairement compacts.</mark> Les résultats d'existence de la dimension finie ne se généralisent donc pas directement. La coercivité seule ne suffit plus pour garantir l'existence.</p><p style="text-align: left;"><strong>Exemple (Contre-exemple)</strong> : Considérons l'espace de Hilbert <span data-latex="\ell^2(\mathbb{N})" data-type="inline-math"></span> des suites de carré sommable, et la fonction : <span data-latex=" f(x) = (|x|^2 - 1)^2 + \sum_{i=0}^{\infty} \frac{x_i^2}{i+1} " data-type="inline-math">\ell^2(\mathbb{N})\inf_{x \in \ell^2(\mathbb{N})} f(x) = 0f(x)=0|x|^2=1x_i=0ix^{(k)}x_k^{(k)}=1x_i^{(k)}=0i \neq kf(x^{(k)}) = \frac{1}{k+1} \to 0) mais ne converge pas vers un minimiseur.</p><p style="text-align: left;">Pour garantir l'existence ET l'unicité en dimension infinie, une condition plus forte est nécessaire : la forte convexité.</p><blockquote><p style="text-align: left;"><strong>Théorème fondamental d'existence et d'unicité (Hilbert)</strong>: Soit <span data-latex="H" data-type="inline-math"></span> un espace de Hilbert, <span data-latex="K \subset H" data-type="inline-math"></span> un sous-ensemble <strong>non vide, fermé et convexe</strong>. Si la fonction <span data-latex="f: K \to \mathbb{R}" data-type="inline-math"></span> est <strong>continue</strong> et <strong>fortement convexe</strong> (i.e., <span data-latex="\alpha" data-type="inline-math"></span>-convexe pour un <span data-latex="\alpha &gt; 0" data-type="inline-math"></span>), alors le problème <span data-latex="\inf_{x \in K} f(x)" data-type="inline-math"></span> admet une <strong>solution unique</strong> <span data-latex="x^*" data-type="inline-math"></span>.</p></blockquote><p style="text-align: left;"><em>Idée de la preuve</em> : On montre qu'une suite minimisante <span data-latex="(x_k)_k" data-type="inline-math"></span> est une suite de Cauchy en utilisant la propriété de forte convexité. Comme <span data-latex="H" data-type="inline-math"></span> est un espace de Hilbert (complet), cette suite converge vers une limite <span data-latex="x^*" data-type="inline-math"></span>. Comme <span data-latex="K" data-type="inline-math"></span> est fermé, <span data-latex="x^* \in K" data-type="inline-math"></span>. Par continuité de <span data-latex="f" data-type="inline-math"></span>, <span data-latex="f(x^*) = \inf f" data-type="inline-math"></span>. L'unicité découle de la convexité stricte (impliquée par la forte convexité).</p><h2 style="text-align: left;">Classification des Problèmes d'Optimisation</h2><p style="text-align: left;">Le vocabulaire de l'optimisation varie selon la structure de la fonction objectif et des contraintes.</p><p style="text-align: left;"><strong>Contraintes</strong> : Un ensemble <span data-latex="K" data-type="inline-math"></span> est souvent défini par des fonctions : <span data-latex=" K = \{ x \in \mathbb{R}^n \mid g_i(x) \leq 0, \forall i \in \{1, \dots, p\}; h_j(x) = 0, \forall j \in \{1, \dots, q\} \} " data-type="inline-math">g_i(x) \leq 0$ est dite active en un point si .

    Type de Problème

    Description

    Programmation Linéaire

    La fonction objectif est linéaire et l'ensemble des contraintes est un polyèdre convexe (défini par des inégalités affines ).

    Programmation Quadratique

    La fonction objectif est quadratique () et est un polyèdre convexe.

    Optimisation Convexe

    La fonction objectif est convexe et l'ensemble des contraintes est convexe. C'est le cadre le plus "idéal" pour l'analyse théorique.

    Optimisation Différentiable

    Les fonctions , , sont différentiables. Permet l'utilisation d'algorithmes basés sur le gradient.

    Optimisation Non-différentiable

    Au moins une des fonctions n'est pas différentiable. Nécessite des outils plus avancés (comme le sous-différentiel).

    Synthèse : Existence et Unicité

    Le tableau suivant résume les conditions garantissant l'existence et/ou l'unicité d'une solution pour .

    Hypothèses sur

    Hypothèses sur

    Espace

    Conclusion

    Convexe

    Convexe

    Espace normé

    Tout min. local est global. L'ensemble des min. est convexe.

    Strictement convexe

    Convexe

    Espace normé

    Unicité : il y a au plus un minimiseur.

    Continue

    Compact (fermé + borné) non vide

    Espace normé

    Existence d'au moins un minimiseur. (Thm. de Weierstrass)

    Continue et coercive

    Fermé non vide

    (dim. finie)

    Existence d'au moins un minimiseur.

    Continue et coercive

    Fermé non vide

    Hilbert (dim. infinie)

    L'existence n'est pas garantie.

    Continue et fortement convexe

    Fermé, convexe, non vide

    Hilbert (dim. finie ou infinie)

    Existence ET Unicité d'un minimiseur.

Principes Fondamentaux de l'Optimisation Mathématique

L'optimisation mathématique s'intéresse à la recherche des meilleures solutions possibles pour un problème donné. Elle consiste à trouver les valeurs des entrées (variables) qui minimisent ou maximisent une fonction objectif, tout en respectant un ensemble de contraintes.

1. Problème Général d'Optimisation

Soit un espace vectoriel normé. Le problème d'optimisation général s'écrit : où :

  • est la fonction objectif (ou fonction de coût).

  • est l'ensemble des solutions admissibles (ou réalisables).

Remarque : Étudier est équivalent à étudier . Nous nous concentrerons donc principalement sur les problèmes de minimisation.

Types de Problèmes

  • Optimisation sans contraintes : Lorsque . La recherche se fait sur tout l'espace.

  • Optimisation sous contraintes : Lorsque est un sous-ensemble propre de ().

Définitions Clés

  • Infimum (m) : La plus grande des bornes inférieures de la fonction sur , noté . Cette valeur n'est pas nécessairement atteinte.

  • Minimiseur (ou solution) : Un point est un minimiseur (ou argument minimum) si .

  • Suite minimisante : Une suite d'éléments de telle que . Une telle suite existe toujours, même si le minimum n'est pas atteint.

  • Ensemble des minimiseurs : L'ensemble de tous les points où le minimum est atteint, noté .

Minimum Local vs. Global

  • Minimum Global : Un point est un minimum global si pour tout .

  • Minimum Local : Un point est un minimum local s'il existe un voisinage de tel que pour tout .

2. Rappels d'Analyse et Concepts Fondamentaux

Différentiabilité

Soient et deux espaces vectoriels normés réels, un ouvert de et .

Définition (Différentiabilité) : Une fonction est dite différentiable en s'il existe une application linéaire continue telle que :

L'application est la différentielle de en .

  • Dérivée directionnelle : Si est différentiable en , alors sa dérivée dans la direction est donnée par :

  • Cas d'un espace de Hilbert : Si est un espace de Hilbert et , le théorème de représentation de Riesz permet d'identifier la différentielle à un vecteur de , appelé gradient et noté . On a alors :

Ensembles et Fonctions Convexes

Définition (Ensemble Convexe) : Un sous-ensemble d'un espace vectoriel est convexe si pour tous et tout , le point appartient aussi à . Autrement dit, le segment est entièrement contenu dans .

Définition (Fonction Convexe) : Soit un ensemble convexe. Une fonction est convexe si pour tous et tout :

Géométriquement, la corde entre deux points du graphe de est toujours au-dessus du graphe.

Variantes de la Convexité

  • Strictement Convexe : L'inégalité est stricte pour et .

  • -convexe (ou fortement convexe) : Il existe tel que pour tous et : Une fonction -convexe est une fonction convexe à laquelle on a "ajouté" une forte courbure quadratique.

    Propriété : Une fonction est -convexe si et seulement si la fonction est convexe.

Coercivité

Définition (Fonction Coercive) : Une fonction est coercive sur un ensemble non borné si :

Intuitivement, une fonction coercive "ne peut pas être minimale à l'infini". Cette propriété est essentielle pour garantir l'existence de solutions dans des ensembles non bornés.

3. Caractérisations pour les Fonctions Différentiables

Lorsque les fonctions sont différentiables, la convexité peut être caractérisée à l'aide de leurs dérivées. Soit une fonction différentiable sur un ouvert convexe .

Caractérisations du premier ordre (C¹)

Type de Convexité

Caractérisation par la sous-tangente

Caractérisation par la monotonie du gradient

Convexe

pour tous

pour tous

Strictement Convexe

pour tous

pour tous

-Convexe

pour tous

pour tous

Propriété importante : Si une fonction est -convexe, alors elle est coercive.

Caractérisations du second ordre (C²)

Si est deux fois différentiable, on utilise la matrice Hessienne, notée ou , qui est la matrice des dérivées partielles secondes : . Cette matrice est symétrique (théorème de Schwarz).

  • Convexité : est convexe si et seulement si sa matrice hessienne est semi-définie positive pour tout .

  • -Convexité : est -convexe si et seulement si Ceci est équivalent à dire que les valeurs propres de sont toutes supérieures ou égales à .

  • Stricte Convexité : Si est définie positive pour tout , alors est strictement convexe.
    Attention, la réciproque est fausse. Par exemple, est strictement convexe, mais sa dérivée seconde s'annule en .

4. Existence et Unicité des Solutions

Propriétés liées à la Convexité

La convexité simplifie grandement la recherche de minima.

Théorème 1 : Soit une fonction convexe définie sur un ensemble convexe . Alors, tout minimum local de sur est un minimum global.

Théorème 2 : Soit une fonction strictement convexe sur un ensemble convexe . Si un minimum existe, il est unique.

Preuve de l'unicité : Soient et deux minimiseurs distincts, avec . Soit . Par stricte convexité : . C'est une contradiction car est le minimum. Donc .

Existence en Dimension Finie ()

En dimension finie, l'existence d'une solution est souvent garantie par le théorème de Weierstrass, qui stipule qu'une fonction continue sur un ensemble compact atteint ses bornes.

Théorème d'existence : Soit une fonction continue et un ensemble non vide et fermé. Le problème admet au moins une solution si l'une des conditions suivantes est vérifiée :

  1. est borné (et donc compact car fermé en dimension finie).

  2. n'est pas borné, mais est coercive.

Idée de la preuve pour le cas coercif : On montre que la recherche du minimum peut se restreindre à un sous-ensemble compact de .

Existence et Unicité en Dimension Infinie (Espaces de Hilbert)

En dimension infinie, les ensembles fermés et bornés ne sont pas nécessairement compacts. La coercivité seule ne suffit plus pour garantir l'existence.

Contre-exemple : Dans l'espace de Hilbert , considérons la fonction . Cette fonction est continue et coercive, mais n'est jamais atteint. La suite minimisante (avec et ailleurs) n'est pas convergente.

Pour garantir l'existence et l'unicité, une condition plus forte est nécessaire : la forte convexité.

Théorème d'existence et d'unicité (Lax-Milgram / Stampacchia) : Soit un sous-ensemble convexe, fermé et non vide d'un espace de Hilbert , et une fonction continue et -convexe.
Alors, le problème admet une solution unique .

Idée de la preuve : On montre que toute suite minimisante est une suite de Cauchy. Comme est complet (par définition d'un Hilbert) et est fermé, la suite converge vers une limite . Par continuité, est le minimum. L'unicité découle de la stricte convexité (qui est impliquée par l' -convexité).

Tableau Récapitulatif : Existence et Unicité

Hypothèses sur K

Hypothèses sur f

Conclusion sur les Solutions

Valide en dim. infinie ?

Convexe

Convexe

Tout minimum local est global. L'ensemble des minimiseurs est convexe.

Oui

Convexe

Strictement Convexe

Unicité : il y a au plus un minimiseur.

Oui

Fermé, non vide, borné (dim. finie)

Continue

Existence : il y a au moins un minimiseur.

Non (compact requis)

Fermé, non vide (dim. finie)

Continue et Coercive

Existence : il y a au moins un minimiseur.

Non

Fermé, Convexe, non vide (Hilbert)

Continue et -convexe

Existence et Unicité d'un minimiseur.

Oui (Théorème clé)

5. Formulation des Problèmes et Vocabulaire

En pratique, l'ensemble des contraintes est souvent décrit par des fonctions.

  • Les sont des contraintes d'inégalité.

  • Les sont des contraintes d'égalité.

  • Une contrainte d'inégalité est dite active (ou saturée) en si .

Typologies de Problèmes

  • Programmation Linéaire : est linéaire et est un polyèdre convexe (défini par des contraintes linéaires).

  • Programmation Quadratique : et est un polyèdre convexe.

  • Optimisation Convexe : est une fonction convexe et est un ensemble convexe.

  • Optimisation Différentiable : Les fonctions , , et sont différentiables.

Empezar cuestionario

Prueba tus conocimientos con preguntas interactivas