On se place dans \( \mathbb{R}^n\) , \( n<\infty\) considéré comme un espace vectoriel normé muni de la norme euclidienne notée \( \left\lVert .\right\rVert \) . On considérera des fonctions différentiables ou deux fois différentiables \( f:{\mathbb{R}^n}\mapsto \mathbb{R}\) . On notera \( \Omega\) un ouvert de \( {\mathbb{R}^n}\) .

On ne considérera que des problèmes de minimisation (calculs de minimum), les problèmes de maximisation étant obtenus en considérant l’opposé de la fonction \( f\) .

1.1.1 Existence d’un minimum

1.1.2 Conditions nécessaires d’optimalité sur un ouvert

1.1.3 Conditions suffisantes d’optimalité sur un ouvert

1.1.4 Importance de la convexité

1.1.5 Notions avancées

1.1.6 Vitesses de convergence

1.2.1 Méthodes sans dérivées

1.2.2 Méthode utilisant la dérivée

1.2.3 Recherche linéaire

1.2.4 Méthode utilisant le Hessien: méthode de Newton

1.2.5 Méthode de quasi-Newton

1.2.6 Méthode du gradient conjugué

1.3.1 Contraintes égalités

On s’intéresse maintenant au problème de la minimisation dans \( \mathbb{R}^{n}\) , \( n<\infty\) d’une fonction différentiable (fonction co^{u}t) \( \mathbb{R}^{n}\ni x \mapsto f(x)\in\mathbb{R}\) sous la contrainte \( c(x)\leq 0\) définie par une fonction différentiable \( \mathbb{R}^{n} \ni x \mapsto c(x)\in \mathbb{R}^m\) , \( m<\infty\) (on ne spécifie plus de variable par rapport à laquelle cette fonction sera inversible, et on ne fait pas d’hypothèse sur les entiers \( n\) et \( m\) ).

1.4.1 Conditions de Karush-Kuhn-Tucker

1.4.2 Dualité

1.4.3 Algorithme de minimisation sous contraintes utilisant la dualité

1.4.4 Méthode de contraintes actives pour les problèmes de programmation quadratique

2.1.1 Historique

2.1.2 Notions fondamentales

2.1.3 Conditions nécessaires d’extrémalité

On s’intéresse désormais au problème de la minimisation d’une fonctionnelle \( X \times U \ni (x,u) \mapsto J(x,u)\in \mathbb{R}\) où \( X\times U\) est un espace vectoriel normé. Ici, \( X\) est l’espace des fonctions continues à dérivées continues \( \mathbb{R} \supset [t_1,t_2] \longrightarrow {\mathbb{R}^n}\) , \( n<\infty\) muni de la norme \( X\ni x \mapsto \left\lVert x\right\rVert _D=\max_{t\in[t_1,t_2]} \left\lVert x(t)\right\rVert +\max_{t\in[t_1,t_2]} \left\lVert \dot x(t)\right\rVert \) . \( U\) est l’espace des fonctions définies sur \( [t_1,t_2]\longrightarrow \mathbb{R}^m\) . Les fonctions \( x\) et \( u\) sont contraintes par une équation différentielle

où \( \mathbb{R}^{n+m}\ni(x,u)\mapsto f(x,u)\in\mathbb{R}^n\) est une fonction de classe \( {\mathcal C}^1\) . En outre on impose la contrainte

On va chercher une caractérisation des solutions du problème

On considérera des fonctionnelles du type

où \( \mathbb{R}^n\times \mathbb{R} \ni (x,t) \mapsto \varphi(x,t) \in \mathbb{R}\) est de classe \( {\mathcal C}^1\) et \( \mathbb{R}^n\times \mathbb{R}^m \times \mathbb{R} \ni (x,t) \mapsto L(x,u,t) \in \mathbb{R}\) est de classe \( {\mathcal C}^1\) . Pour tenir compte de la condition initiale (31), on considère qu’une variation admissible \( (\delta x,\delta u)\in X \times U\) doit vérifier \( \delta x(t_1)=0\) . Comme dans le cas de l’optimisation continue de dimension finie traité au chapitre 1, on va chercher à résoudre le problème d’optimisation sous contrainte en adjoignant les contraintes à la fonction co^{u}t.

On forme alors \( X\times U \times M \ni (x,u,\lambda)\mapsto \bar J(x,u,\lambda)\) où \( M\) est l’espace des fonctions \( \mathbb{R}\longrightarrow {\mathbb{R}^n}\) différentiable par

En notant

qu’on appellera Hamiltonien du problème (32), il vient

Supposons que les équations (35), (36), (37) et (38) soient vérifiées. Calculons la variation de la fonctionnelle \( J\) .

2.2.1 Problème aux deux bouts

2.2.2 Contraintes finales

2.2.3 Résolution numérique du problème aux deux bouts

2.2.4 Principe du minimum

Il est possible d’exhiber une structure reliant les trajectoires optimales de problèmes d’optimisation voisins. Le but de cette section est de présenter cette structure au travers de l’équation aux dérivées partielles de Hamilton-Jacobi-Bellman.

On considère une fois de plus le problème suivant (d’autres généralisations sont possibles)

où \( \mathbb{R}^n\times \mathbb{R} \ni (x,t) \mapsto \psi(x,t) \in \mathbb{R}^q\) , \( 1<q\leq n\) est une fonction de classe \( {\mathcal C}^1\) . On considérera des fonctionnelles du type

où \( \mathbb{R}^n\times \mathbb{R} \ni (x,t) \mapsto \varphi(x,t) \in \mathbb{R}\) est de classe \( {\mathcal C}^1\) et \( \mathbb{R}^n\times \mathbb{R}^m \times \mathbb{R} \ni (x,u,t) \mapsto L(x,u,t) \in \mathbb{R}\) est de classe \( {\mathcal C}^1\) .

En conséquence, il existe une extrémale passant par tous les points de \( U\) .

Les extrémales vérifient la propriété suivante.

Grâce à cette propriété, il est possible d’établir une équation aux dérivées partielles satisfaites par \( {\mathcal J}\) . On suppose disposer d’un champs d’extrémales \( \mathcal E\) pour le problème d’optimisation (48). Considérons \( (x,t)\in\mathcal E\) . Il correspond à la fonction de retour optimal évaluée en ce point \( J^0(x,t)\) une commande optimale \( \mathbb{R} \supset [t,t_2]\ni l \mapsto u^0(l)\in {\mathbb{R}^m}\) que nous supposerons (pour simplifier) unique. Pour toute commande \( u\) proche de \( u^0\) on peut calculer une fonction co^{u}t à partir de la trajectoire \( \mathbb{R} \supset[t_1,t_2] \ni t \mapsto x(t)\in {\mathbb{R}^n}\) (proche de la trajectoire optimale) issue de \( x(t_1)=x^0\) . Il vient

avec

Choisissons comme candidat d’appliquer \( u\) une commande différente de la commande optimale \( u^0\) pendant \( \delta t\) puis optimale sur \( [t_1+\delta t,t_2]\) . On peut évaluer

Un développement au premier ordre donne

L’équation (49) donne

Un passage à la limite lorsque \( \delta t \rightarrow 0\) donne

On reconnaît ici l’Hamiltonien (33) et on écrit finalement l’équation de Hamilton-Jacobi-Bellman

Il s’agit d’une équation aux dérivées partielles hyperbolique dont la condition limite est donnée sur l’ensemble \( {\mathcal V}=\{(x,t)\in \mathbb{R}^n\times \mathbb{R} \text{ t.q. } \psi(x,t)=0 \}\) par \( \mathbb{R}^n\times \mathbb{R} \ni (x,t) \mapsto {\mathcal J}(x,t)=\varphi(x,t)\) . On la résoudra en général par une propagation (rétrograde) depuis l’ensemble \( {\mathcal V}\) . Cette résolution sera par exemple menée le long d’un réseau quadrillant le plan (lorsque \( x\) est à valeur dans \( \mathbb{R}^2\) ) par la méthode de la programmation dynamique.

Calculer le gradient \( \nabla f(x)\) et le Hessien \( \nabla^2 f(x)\) de la fonction de Rosenbrock

Montrer que \( x^*=(1,1)^T\) est l’unique minimum local de cette fonction et qu’à ce point le Hessien est défini positif.

Soit \( a\) un vecteur de \( \mathbb{R}^n\) et \( A\) une matrice \( n\times n\) symétrique. Calculer le gradient et le Hessien de \( f_1(x)ā^T x\) et \( f_2(x)=x^T A x\) .

Soit \( f\) une fonction convexe. Montrer que l’ensemble des minimiseurs globaux de \( f\) est convexe.

Soit la suite \( (x_k)_{k\in \mathbb{N}}\) définie par

Cette suite est-elle convergente de type Q-superlinéaire? Est-elle Q-quadratique ou R-quadratique.

Note: on pourra utiliser la suite majorante \( \nu_k=(\frac{1}{2})^{2^k}\) .

Avec les notations du cours, montrer en utilisant la fonction \( f(x)=x^2\) et \( x_0=1\) que si \( 0<c_2<c_1<1\) il peut ne pas exister de pas satisfaisant les conditions de Wolfe.

La méthode de dichotomie présentée en cours n’est pas optimale au sens où pour un nombre fixé d’évaluations de la fonction à minimiser elle n’aboutit pas à l’intervalle réduit de taille minimale. On propose ici une méthode optimale.

On note \( \Delta_k\) la taille de l’intervalle de recherche à l’itération \( k\) , que l’on note \( [a_k,d_k]\) . On évalue la fonction à minimiser en deux points intermédiaires \( b_k\) et \( c_k\) ce qui nous donne donc \( 4\) valeurs. En utilisant l’unimodalité on peut éliminer un des deux sous-intervalles \( [a_k,b_k]\) ou \( [c_k,d_k]\) .

• Montrer que si on veut que la longueur de l’intervalle \( \Delta_{k+1}\) soit indépendante des valeurs de la fonction à minimiser on doit choisir \( b_k\) et \( c_k\) disposés symétriquement par rapport au milieu de \( [a_k,d_k]\) .
• Montrer \( \Delta_k=\Delta_{k+1}+\Delta_{k+2}\) si on veut n’avoir à recalculer qu’une seule valeur de la fonction à minimiser à chaque itération

• Soit \( \Delta_{N-1}\) l’intervalle obtenu au bout de \( N\) calculs, définissons \( F_0\) ,\( F_1\) ,...,\( F_{N-1}\) par

  \[ \Delta_k=F_{N-k}\Delta_{N-1} \]

  Montrer qu’on a alors

  \[ F_n=F_{n-1}+F_{n-2} \]

  pour \( n=3,...,N-1\) et \( F_1=1\) .

• Montrer que

  \[ F_{n+2}=n F_2+n-1 \]

  et que \( F_2\leq 2\) .
• Conclure alors que pour réduire le plus les intervalles en \( N\) calculs il faut choisir \( F_2=2\)

• La suite obtenue est la suite de Fibonacci. Pour l’utiliser on choisit d’abord un rapport de réduction pour l’intervalle final et on détermine ainsi \( N\) . Montrer que pour un rapport de réduction de \( 1000\) il faut choisir \( N=16\) . Montrer comment procéder aux itérations en commençant par

  \[ \Delta_1/\Delta_2=F_{N-1}/F_{N-2} \]

On admet les deux résultats suivants:

1. si \( A\) matrice \( p \times n\) est de rang \( n\) alors \( A^T A\) est inversible
2. une matrice \( M\) est symétrique définie positive si et seulement si elle se factorise comme \( M=H^T H\) avec \( H\) inversible.

On cherche à résoudre le problème dit des “moindres carrés”

où \( A\) est une matrice \( p \times n\) , \( b\in \mathbb{R}^p\) et en général \( p\geq n\) .

• Montrer que ce problème est convexe
• On suppose que la norme considérée est la norme euclidienne \( \|x\|^2=x^Tx\) , calculer le gradient de la fonction à minimiser.
• Quel est alors un point candidat pour être minimum? Calculer le Hessien en ce point, conclure.
• Reprendre l’expression du minimum lorsque le problème est “pondéré” c’est à dire \( \|x\|=x^T Q x\) où \( Q\) est une matrice symétrique définie positive.

On considère la fonction

Calculer la première itération de l’algorithme de Newton en partant de \( (1,1)^T\) (réponse: \( (0.5, 0.5)^T\) ).

On considère la fonction quadratique

Calculer les deux itérations de l’algorithme du gradient conjugué en partant de \( (0,0)^T\) et montrer qu’on aboutit au minimum global \( (2/7, 3/7)^T\) .

Parmi les méthodes de quasi-Newton, la méthode SR1 est souvent retenue pour sa simplicité et la bonne approximation du Hessien qu’elle procure. Avec les notations du cours elle donne

Utiliser la formule de Sherman-Morrison-Woodbury pour montrer que la formule de mise à jour de \( H_k=B_k^{-1}\) est

Montrer que la formule SR1 précédente, ainsi que la formule de la méthode BFGS sont invariantes par transformation \( x=S z +s\) où \( S\) est une matrice inversible et \( s\) un vecteur. Pour cela on pourra considérer la fonction \( \tilde f(z)=f(Sz+s)\) , calculer son gradient, son Hessien, et montrer que si on initialise l’approximation du Hessien par \( S^T B_0 S\) et qu’on utilise un pas unitaire, on a \( x_k=S z_k +s\) à toutes les itérations.

Soit la fonction

En faisant intervenir les variables intermédiaires

construire un graphe binaire permettant d’évaluer \( f\) au point \( (x_1,x_2,x_3)=(1,2,\pi/2)\) .

En utilisant le fait qu’à chaque étape les opérations ne font intervenir que deux variables, montrer comment une propagation en avant puis en arrière des calculs permet de calculer de manière automatique et efficace le gradient de la fonction sans en calculer une expression littérale. C’est une méthode générale très utilisée en pratique car très efficace.

Une méthode simple à mettre en oeuvre pour résoudre un problème de minimisation sous contraintes égalités

consiste à chercher les solutions de

via la recherche du minimum de la fonction (dite de mérite)

En pratique cette méthode permet d’utiliser un code prévu pour la minimisation sans contraintes pour résoudre un problème avec contraintes.

Appliquer cette méthode à

et montrer qu’en plus de l’unique minimum local on trouve un maximum local et un autre point parasite (c’est la principale faiblesse connue de cette méthode).

Considérer le problème de programmation quadratique

où \( G\) est symétrique définie positive. Montrer que le problème dual est

qui peut se simplifier en

Résoudre par la méthode de sous-ensembles actifs le problème de programmation quadratique \( \min q(x)\) , \( q(x)=(x_1-1)^2+(x_2-2.5)^2\) sous les contraintes

Utiliser comme point de départ \( x^0=(2,0)^T\) et \( W^0=\{3,5\}\) .

Considérer le problème pénalisé à barrière logarithmique

provenant du problème

Résoudre (54), vérifier analytiquement que lorsque \( \mu\) tend vers 0, \( x^*(\mu)\) , l’optimum obtenu, converge vers la solution de (55).

La plus courte distance entre un point \( x_0\) et un hyperplan \( \{x, Ax=b\}\) où les lignes de \( A\) sont linéairement indépendantes, peut s’écrire comme un problème de programmation quadratique

Montrer que le multiplicateur à l’optimum est

et que la solution est

Montrer que dans le cas où \( A\) est un vecteur ligne, la plus petite distance entre \( x_0\) et l’hyperplan vaut

Ce problème est issu de l’Optimization Toolbox de Matlab [10]. On considère une tente de cirque comme une membrane élastique posée sur 5 mâts (le mât central étant plus haut que les autres). La forme prise par cette toile de tente minimise une énergie potentielle composée d’un terme de gravité auquel s’oppose un terme d’élasticité. Après avoir utilisé un schéma aux différences pour le gradient de la surface, on obtient un problème de programmation quadratique dont l’inconnue est l’altitude des différents points de la toile. Si on représente la surface de la toile par une grille de points, on désigne par \( x\) le vecteur constitué par les lignes de cette grilles mises bout à bout. Ainsi une grille de taille \( 30\times 30\) donne un vecteur de taille 900. Les contraintes expriment que la toile repose sur les mâts.

Les multiplicateurs de Lagrange et les contraintes correspondantes sont représentés par

Avec les paramètres choisis, on obtient un minimum de \( 0.44422\) , de combien faut-il modifier la hauteur du mât central pour faire décroître cette valeur à \( 0.43767\) ?

Le pilote d’un avion dont la vitesse \( V\) est constante par rapport au vent (de vitesse \( u\) ) cherche à maximiser l’aire contenue dans la surface fermée tracée au sol par sa trajectoire sur un intervalle \( [0,T]\) . Les équations de la dynamique sont

L’aire à maximiser est

Montrer que la courbe recherchée est une ellipse dont on précisera l’excentricité.

Considérons une chaîne de longueur \( 2L\) suspendue entre deux points de même altitude situés à une distance \( 2l\) l’un de l’autre (\( l \leq L\) ). Utiliser le calcul des variations pour trouver la forme qui minimise l’énergie potentielle (\( g\) la gravité est une constante).

Considérons un investisseur qui possède une somme \( S\) à la banque. N’ayant aucun autre revenu que les intérêts qui lui sont versés, il cherche quelle est la meilleure façon (au sens de son agrément) de dépenser son argent sur l’horizon \( [0,T]\) .

On suppose que son agrément est pour tout temps \( E=2\sqrt{r}\) . L’agrément futur compte moins que le présent. La fonction qu’il va maximiser est donc

Dans le même temps, la banque lui verse des intérêts proportionnels à son capital restant à la banque \( x(t)\) . L’équation régissant ses économies est donc

1. Montrer que le problème se ramène à trouver un point stationnaire de

   \[ J(x)īnt_0^T \exp(-\beta t) 2 \sqrt{\alpha x(t) - \dot x(t)} dt \]

   avec \( x(0)=S\) , \( x(T)=0\) .

2. Écrire l’équation de Euler-Lagrange equation correspondante et montrer que

   \[ \alpha x(t) - \dot x(t) =r(0) \exp (2(\alpha-\beta)t). \]

3. Supposer que \( \alpha > \beta > \alpha/2\) . Résoudre l’équation précédente. Montrer que la politique optimale de dépense est donnée par

   \[ x(t)=S \exp(2(\alpha-\beta) t)\frac{1-\exp((\alpha-2\beta)(T-t))}{1-\exp((\alpha-2\beta)T)}. \]
4. Représenter graphiquement cette fonction. Commenter.

En utilisant les conditions de Karush-Kuhn-Tucker, trouver le minimum de

sous les contraintes

Traiter tous les cas possibles pour \( a\) et \( b\) .

Résoudre le même problème en rajoutant le contrainte \( y_1+y_2\geq \frac{1}{2}\) .

Considérons une particule de masse \( m\) évoluant dans un plan sur laquelle agit une force d’amplitude \( ma\) dont l’orientation (par rapport à l’axe \( x\) ) est \( \beta(t)\) . Les équations de la dynamique sont

On suppose vouloir minimiser une fonction coût ne comportant qu’un terme final du type \( \varphi(x(t_f),y(t_f))\) . Montrer qu’alors la commande optimale est du type

Étant donné un ensemble de points dans un plan \( \{y_1,...,y_m\}\) , on cherche le point dont la somme des distances pondérées est minimum. Le problème s’écrit

où les poids \( m_i\) sont des constantes positives.

1. Montrer qu’il existe un minimum global à ce problème et qu’on peut le construire par le schéma représenté Figure 1.
2. Ce minimum est-il unique?

Considérons le côut

sous la contrainte

Écrire l’équation HJB associée.

Considérons le quadrilatère représenté sur la Figure 2 avec les notations telles que définies sur cette figure (\( (\theta_1,\theta_2) \in ]0, \pi[^2\) , \( a>0\) , \( b>0\) , \( c>0\) , \( d>0\) ). On cherche la configuration \( (\theta_1,\theta_2)\) fournissant l’aire maximale.

1. Montrer que le problème revient à trouver l’extremum de

   \[ (\theta_1,\theta_2)\mapsto a d \sin \theta_1 + b c \sin\theta_2 \]

   sous la contrainte

   \[ a^2+d^2-2 ad \cos \theta_1=b^2+c^2-2 bc \cos \theta_2 \]
2. Écrire le Lagrangien associé à ce problème et établir des conditions d’extrémalité.
3. Calculer les valeurs de \( (\theta_1,\theta_2)\) extremum.
4. Quelle figure obtient-on pour \( a=b=c=d=1\) ? Même question pour \( a=d=1\) et \( b=c=2+\sqrt 3\) .

On considère le maillage défini sur la Figure 3

À chaque segment du maillage est associé un coût. On cherche le meilleur chemin (plus petit coût total) pour aller de \( A\) à \( B\) , ainsi que de \( A'\) à \( B\) .

1. Calculer ces chemins par la méthode de la programmation dynamique. On rappelle que cette méthode consiste à construire un champs d’extrémales issues du point final de manière rétrograde.
2. Donner un champs d’extrémales.
3. On inverse maintenant le sens de parcours. Calculer le meilleur chemin de \( B\) à \( A\) et de \( B\) à \( A'\) . Quelle différence algorithmique constatez vous dans ce cas?

Vous devez rester à l’étranger pendant 3 années et vous avez besoin d’un véhicule pour aller travailler. Un véhicule se détériore avec le temps et son coût d’usage est une fonction croissante de son âge (entretien, pannes...). Chaque année vous pouvez conserver votre véhicule ou en acheter un autre neuf et revendre l’ancien. À l’issue des 3 années vous devez vous débarrasser de votre véhicule en le mettant à la casse pour un prix dépendant de son état. On note

• \( c(i)\) : côut d’usage d’un véhicule pendant 1 période, d’âge \( i\) au début de la période,
• \( p=50\) : prix d’un nouveau véhicule,
• \( t(i)\) : valeur marchande d’un véhicule d’âge \( i\) au début de la période,
• \( s(i)\) : valeur perçue lors de la mise à la casse d’un véhicule d’âge \( i\) .

1. À l’instant initial un ami vous donne une voiture qui a 2 ans d’âge. Quelle est la suite de décisions optimale? Montrer le champs d’extrémales.

   \( i\)	0	1	2	3	4
   c(i)	10	13	20	40	70
   t(i)		32	21	11	5
   s(i)		25	17	8	0

2. On se place maintenant du point de vue du vendeur de voitures qui peut faire les mêmes calculs de programmation dynamique que vous. Connaissant votre situation, comment peut-il augmenter son profit sans que vous puissiez rien y faire?

Lorsque vous achetez un billet d’avion aller retour, vous pouvez bénéficier d’une importante réduction si vous acceptez de rester le samedi soir sur place. Dans cet exercice on va étudier comment, dans un cas très simple, cette ristourne est calculée.

On considère deux populations: les touristes (avec les variables \( z_n\) , \( \alpha_n\) ) et les hommes d’affaires (avec les variables \( z_b\) , \( \alpha_b\) ).

On note \( z_n\) (resp. \( z_b\) ) l’agrément de passer la nuit chez soi le samedi, \( p_n\) (resp. \( p_b\) ) le prix du billet, \( \alpha_n\) (resp. \( \alpha_p\) ) la pénibilité de payer le prix du billet, et \( t\) l’agrément du séjour. On note \( p_n\) le prix d’un billet aller retour avec séjour sur place le samedi, et \( p_b\geq p_n\) le prix d’un billet aller retour sans séjour sur place le samedi.

1. Expliquer le sens des hypothèses (qu’on admettra dans la suite)

   \[ 0=z_n< z_b, ~ \alpha_n > \alpha_b \geq 0 \]

2. Expliquer pourquoi l’agrément total d’un individu s’exprime, suivant les cas, comme

   \[ u=z -\alpha p +t ~, \text{ où } u=-\alpha p +t \]

3. On souhaite donner l’envie aux touristes et aux hommes d’affaires de voyager. On souhaite choisir une politique tarifaire telle que les touristes aient envie de voyager en passant la nuit de samedi sur place et on souhaite encourager les hommes d’affaire à prendre un billet sans séjour du samedi. Expliquer qu’on aboutit aux relations

   \[ \begin{align}-\alpha_n p_n +t \geq 0 \end{align} \]

   (56)

   \[ \begin{align} z_b-\alpha_b p_b +t \geq 0 \end{align} \]

   (57)

4. On souhaite que des deux types de voyages le plus intéressant pour les touristes soit le voyage avec séjour du samedi, et que les hommes d’affaires privilégient les séjours sans séjour du samedi. Montrer qu’on aboutit à

   \[ \begin{align}-\alpha_n p_n \geq z_n-\alpha_n p_b \end{align} \]

   (58)

   \[ \begin{align} z_b-\alpha_b p_b \geq -\alpha_b p_n \end{align} \]

   (59)

5. Étant donnés les flux supposés égaux d’hommes d’affaires et de touristes on souhaite maximiser la fonction

   \[ p_n/2+p_b/2 \]

   Les variables de décisions étant \( p_n\) et \( p_b\) (la politique tarifaire), écrire le problème d’optimisation sous contraintes.
6. En utilisant les conditions de Karush-Kuhn-Tucker, combien y-a-t-il de cas à considérer pour résoudre ce problème?
7. Montrer que les conditions \( (57)\) et \( (58)\) sont redondantes avec \( (56)\) et \( (59)\) . Ré-écrire le problème d’optimisation sous contraintes correspondant.
8. Résoudre ce problème d’optimisation et montrer calculer, à l’optimum, \( p_b-p_n\) . Interpréter le résultat.
9. Reprendre l’étude si les flux de touristes et d’hommes d’affaires sont différents.
10. On suppose maintenant que la compagnie vend aussi des nuits d’hotel et que la nuit du samedi soir est facturée \( c\) . Comment doit-on modifier l’étude précédente pour maximiser le profit total?

Considérons une chaîne de longueur \( 2L\) suspendue entre deux points de même altitude situés à une distance \( 2l\) l’un de l’autre (\( l \leq L\) ). Utiliser le calcul des variations pour trouver la forme qui minimise l’énergie potentielle (\( g\) la gravité est une constante).

Avec les notations utilisées en cours, déterminer les équations à résoudre pour trouver un extremum du problème suivant

sous les contraintes

où \( t_f\) est une inconnue.

Le problème est de déterminer l’orientation \( \theta(t)\) qu’un nageur doit choisir pour minimiser le temps nécessaire pour traverser une rivière dont il connaît le courant. La rivière est définie comme \( \{(x,y), -l \leq y \leq l \}\) . \( \theta\) est l’angle entre le vecteur vitesse du nageur et l’axe \( x\) .

• Considérer le problème de traverser une rivière d’un point \( (x,y)=(0,-l)\) à un point final donné \( (0,l)\) où le courant est selon la direction \( x\) avec la vitesse

  \[ uū_0 (1-\frac{y^2}{h^2}) \]

  Expliquer comment on peut déterminer \( \theta(t)\) et \( t_f\) .
• Considérer le problème de traverser une rivière en partant de \( (x,y)=(0,-l)\) pour arriver en \( y=l\) (la valeur finale de \( x\) est libre). Expliquer comment trouver \( \theta(t)\) et \( t_f\) .

On considère le problème de minimisation de la fonctionnelle

où \( x\) est une fonction deux fois dérivable définie sur \( [0, 1]\) telle que

1. Former l’équation d’Euler-Poisson correspondante.
2. Calculer \( x^*\) extrémale du problème.

3. On veut montrer que \( x^*\) fournit effectivement un minimum de la fonctionnelle. Considérer

   \[ J(x^*+h)īnt_0^1 (\ddot x^*(t)+\ddot h(t))^2dt \]

   où \( h\) est une variation admissible. En procédant à une double intégration par partie, montrer que

   \[ J(x^*+h) \geq J(x^*) \]

   Conclure.

On cherche à montrer le résultat suivant. Soit \( Q\) une matrice symétrique définie positive de taille \( n \times n\) . Quel que soit \( x\) , on a

où \( a\) et \( A\) sont, respectivement, la plus petite et la plus grande des valeurs propres de \( Q\) .

1. Dans un premier temps, on considère que \( Q\) est une matrice diagonale dont les termes sont

   \[ 0 < a=\lambda_1\leq \lambda_2\leq ... \leq \lambda_n Ā \]

   Montrer que

   \[ q(x)=\frac{(\sum_{i=1,...,n} x_i^2)^2}{(\sum_{i=1,...,n} \lambda_ix_i^2)(\sum_{i=1,...,n} \frac{1}{\lambda_i} x_i^2)} \]

2. Montrer que

   \[ q(x)=\frac{1}{f(\lambda_1,...\lambda_n,x)g(\lambda_1,...\lambda_n,x)} \]

   avec

   \[ \begin{align*} f(\lambda_1,...\lambda_n,x)=\sum_{i=1,...,n}\lambda_i \frac{x_i^2}{\sum_{i=1,...,n} x_i^2}, ~g(\lambda_1,...\lambda_n,x)=\sum_{i=1,...,n} \frac{1}{\lambda_i}\frac{x_i^2}{\sum_{i=1,...,n} x_i^2} \end{align*} \]

3. En interprétant \( f\) et \( g\) définis précédemment comme les coordonnées d’un barycentre de points de coordonnées \( (\lambda_i,1/\lambda_i)\) , représenter dans un plan l’ensemble des points de coordonnées \( (f,g)\) lorsque \( x\) varie (les \( \lambda_i\) restant constants). Montrer, pour \( \lambda_1\) , ..., \( \lambda_n\) fixés, qu’il existe \( \alpha(x)\in[0,  1]\) tel que

   \[ f(\lambda_1,...\lambda_n,x)=(1-\alpha(x)) \lambda_1 +\alpha(x)\lambda_n \]
   \[ g(\lambda_1,...\lambda_n,x)\leq(1-\alpha(x)) \frac{1}{\lambda_1} +\alpha(x)\frac{1}{\lambda_n} \]

4. Déduire de ce qui précède que

   \[ f(\lambda_1,...\lambda_n,x)g(\lambda_1,...\lambda_n,x) \leq\frac{(\lambda_1+\lambda_n)^2}{4\lambda_1 \lambda_n} \]

   Conclure. Conclure dans le cas général où \( Q\) n’est pas diagonale.

5. On considère le problème de minimisation de la fonction quadratique

   \[ h(x)=\frac{1}{2} x^T Q x -b^T x \]

   où \( b\) est un vecteur colonne. Montrer que l’algorithme du gradient à pas optimal engendre les itérations

   \[ x^{k+1}=x^k-\frac{(g^k)^Tg^k}{(g^k)^TQ g^k}g^k \]

   avec \( g^k=Qx^k-b\) .

6. On note

   \[ E(x)=\frac{1}{2} (x-x^*)^T Q(x-x^*) \]

   où \( x^*\) est l’unique minimum de \( h\) . Calculer \( E(x^{k+1})\) en fonction de \( E(x^k)\) et de \( g^k\) . En utilisant l’inégalité de Kantorovich que vous venez d’établir, montrer que

   \[ E(x^{k+1}) \leq \left(\frac{A-a}{A+a}\right)^2 E(x^k) \]
7. Que peut-on en déduire sur la convergence de cette méthode de descente en fonction du conditionnement de la matrice \( Q\) ?

1. Considérer le problème (très simple)

   \[ \min_{x\in \mathbb{R}, ~ x\geq 1} |{x}| \]

   Quelle est sa solution? Former le Lagrangien du problème et considérer la fonction duale

   \[ f(x)=\sup_{\lambda \geq 0} \lambda (1-x) \]

   Expliciter les valeurs prises par cette fonction pour tout \( x\) . En déduire, par dualité, quelle est la solution du problème.

2. Considérer le problème

   \[ \min_{\begin{array}{l}x\in \mathbb{R}^n,\\ Ax=b,\\ x\geq 0\end{array}} c^Tx \]

   Montrer que son dual est

   \[ \max_{\begin{array}{l}(\lambda,\nu)\\ A^T \nu-\lambda+c=0\\ \lambda\geq 0\end{array}} -b^T \nu \]

   Préciser les dimensions de \( \lambda\) et \( \nu\) . Peut-on simplifier cette formulation duale?

3. Soit \( A\) une matrice de taille \( m \times n\) et \( b\) un vecteur colonne. On cherche \( x\in\mathbb{R}^n\) solution du problème

   \[ \min_{Ax\leq b} c^Tx \]

   Former le Lagrangien du problème. Par dualité, montrer que ce problème revient à

   \[ \max_{\begin{array}{c} A^T \lambda +c=0\\ \lambda\geq0\end{array}} -b^T \lambda \]

On considère une fonction \( J:\mathbb{R}^n\rightarrow \mathbb{R}\) qu’on suppose elliptique, c’est à dire qu’elle est continûment différentiable, que son gradient \( \nabla J\) est Lipschitzien avec comme constante \( M\) , et qu’il existe \( \alpha>0\) tel que

pour tout \( u\) et \( v\) . On s’intéresse à la minimisation de \( J\) sur le domaine

où les fonctions \( \phi_i:\mathbb{R}^n\rightarrow \mathbb{R}\) sont convexes.

1. Établir, en utilisant la formule de Taylor avec reste intégral pour évaluer \( J(v)-J(u)\) , et le fait que \( J\) est elliptique, la double inégalité suivante:

   \[ \nabla J(u)^T(v-u) +\frac{\alpha}{2} \left\lVert u-v\right\rVert ^2 \leq J(v)-J(u)\leq\nabla J(u)^T(v-u)+\frac{M}{2}\left\lVert v-u\right\rVert ^2 \]

2. En faisant le lien avec la convexité forte, démontrer l’existence et l’unicité de la solution du problème d’optimisation

   \[ \min_{u\in \mathcal U}J(u) \]
3. On définit le Lagrangien \( {\mathcal{L}}(u,\lambda)= J(u)+\lambda^T\phi(u)\) . Montrer que si \( (u,\lambda)\) est point selle du Lagrangien, alors \( u\) est solution du problème.

4. On note \( p:\mathbb{R} \rightarrow \mathbb{R}_+\) tel que \( p(x)=\left\{ \begin{array}{l} x \text{ si } x \geq 0\\ 0 \text{ sinon}\end{array}\right. \) , et \( P:\mathbb{R}^m\rightarrow\mathbb{R}^m\) tel que \( P(x=(x_1,...,x_m)^T)=\left(\begin{array}{c} p(x_1)\\ \vdots\\ p(x_m) \end{array} \right)\) l’opérateur de projection sur \( (\mathbb{R}_+)^m\) . Établir, en utilisant les conditions Karush-Kuhn-Tucker, l’équivalence suivante

   \[ \begin{align*}& \left\{\lambda=P(\lambda+\rho \phi(u)), \rho>0 \text{ fixé} \right\}\\ & \Leftrightarrow \left\{ \begin{array}{c} \lambda \in (\mathbb{R}_+)^m\\ \sum_i \phi_i(u) (\mu_i-\lambda_i) \leq 0 \text{ pour tout } \mu=(\mu_1,...,\mu_m)^T\in (\mathbb{R}_+)^m\end{array}\right.\end{align*} \]

5. En déduire (en utilisant certaines valeurs bien choisies de \( \mu_i\) ) l’équivalence

   \[ \begin{align*}&\left\{\lambda=P(\lambda+\rho \phi(u)), \rho>0 \text{ fixé} \right\}\\ & \Leftrightarrow \left\{ \begin{array}{c} \lambda \in (\mathbb{R}_+)^m \lambda^T\phi(u)=0\end{array}\right.\end{align*} \]

6. Vérifier que si \( (u,\lambda)\) est point selle du Lagrangien, alors \( \lambda=P(\lambda+\rho \phi(u))\) pour un certain \( \rho\) , et que

   \[ {\mathcal{L}}(u,\lambda)\leq {\mathcal{L}}(u+\theta (v-u),\lambda) \]

   pour tout \( v\) et pour tout \( \theta \in [0,1]\) . Faire le lien avec l’algorithme d’Uzawa.

7. En déduire, en utilisant un développement de Taylor que

   \[ \nabla J(u)^T(v-u) + \lambda^T \phi(v) \geq 0 \]

   pour tout \( v\) .

On souhaite établir le résultat suivant. Soit \( y: [0,1]\rightarrow \mathbb{R}\) une fonction régulière telle que \( y(0)=0\) . Pour tout \( k \in \mathbb{N}\) , on a:

avec \( C=\frac{1}{2k-1} \left( \frac{2k}{\pi} \sin \frac{\pi}{2k}\right)^{2k}\) . Pour cette démonstration, on va utiliser une méthode variationnelle.

1. Soit la fonctionnelle

   \[ \begin{align*} J(y)īnt_0^1 \left( C(y'(x))^{2k}-(y(x))^{2k}\right) dx \end{align*} \]

   Ecrire l’équation d’Euler-Lagrange associée à l’extrémalité de \( J\) . Montrer en particulier que

   \[ \begin{align*} (2k-1) C (y'(x))^{2k}=C'-(y(x))^{2k}, \forall x\in[0,1] \end{align*} \]

   avec \( C'\) une constante.
2. On s’intéresse désormais à l’extrémale \( Y\) telle que \( Y(0)=0\) , \( Y(1)=1\) .

1. montrer que

   \[ \begin{align*}1=\left((2k-1)C\right)^{\frac{1}{2k}} \int_0^1 \frac{dy}{\left(C'-y(x)^{2k}\right)^{\frac{1}{2k}}}\end{align*} \]

2. on rappelle

   \[ \int_0^1 \frac{dt}{\left(1-t^{2k}\right)^{\frac{1}{2k}}}=\frac{\pi}{2k} \left( \sin \frac{\pi}{2k} \right)^{-1} \]

   En déduire la valeur de \( C'\) .
3. montrer que \( Y'(1)=0\) .
3. Parmi les extrémales, celle précédemment calculée, \( Y\) , réalise effectivement le minimum de \( J\) .

1. Montrer que \( J(Y)=0\) . On pourra pour cela utiliser une intégration par parties en écrivant

   \[ \begin{align*}J(Y)īnt_0^1 \left( C Y'(x) Y'(x)^{2k-1} -Y(x)^{2k}\right) dx \end{align*} \]

   pour faire apparaître l’équation d’Euler-Lagrange.
2. En déduire le résultat recherché.

On considère le problème de transition en temps minimum entre deux points \( x_0\) , \( x_1\) pour un système linéaire scalaire (dans un premier temps) \( \dot x = a x + b u\) , avec \( a\neq 0\) , \( b \neq 0\) sous la contrainte \( u\in \mathcal U\) où \( \mathcal U\) est un sous ensemble convexe de \( \mathbb R\) . On cherche à démontrer que la commande réalisant le minimum est unique.

1. On suppose, sans perte de généralité, que \( x_1>x_0\) , \( a>0\) , \( b>0\) et que \( \mathcal U=[-\frac{a}{b}x_1-\epsilon, -\frac{a}{b} x_0 + \epsilon]\) , avec \( \epsilon>0\) . En considérant la loi horaire

   \[ \begin{align*} x(t)=\left\{ \begin{array}{l} x_0, \text{ si } t \leq 0\\ x_0+\frac{t}{T} (x_1-x_0), \text{ si } 0 < t < T\\ x_1 \text{ si } T\leq t \end{array}\right. \end{align*} \]

   où \( T>0\) est un paramètre à choisir, montrer que pour \( T\) suffisamment grand, la commande \( u(t)=\frac{\dot x(t)-a x(t)}{b}\) appartient à \( \mathcal U\) et permet de rallier \( x_0\) à \( x_1\) .
2. Déduire de ce qui précède que si \( T\) fournit une solution admissible, alors \( T'>T\) fournit aussi une solution admissible.
3. Considérer un temps \( t_1\) candidat à l’optimalité. On veut montrer que si deux lois horaires \( [0,t_1]\ni t \mapsto u_1(t)\) et \( [0,t_1]\ni t \mapsto u_2(t)\) sont optimales alors elles coincident.

1. montrer que pour toute loi commande \( u\) , on a

   \[ \begin{align*}x(t)= x_0 \exp(at)+\int_0^{t} \exp(a( t-\tau)) b u(\tau) d\tau \end{align*} \]

2. en déduire

   \[ \begin{align*}\int_0^{t_1} \exp(- a t ) b u_1(t) dt = \int_0^{t_1} \exp(- a t ) b u_2(t) dt\end{align*} \]

3. former l’Hamiltonien du problème (on notera \( \lambda\) l’état adjoint). Déduire du principe du minimum de Pontryagin que la ou les solutions optimales sont données par

   \[ arg\min \lambda(t) b u(t) \]
4. former l’équation différentielle adjointe satisfaite par \( \lambda\) .

5. montrer, par le lemme de l’adjoint, que

   \[ \begin{align*}\int_0^{t_1} \lambda(t) b u_1(t) dt = \int_0^{t_1}\lambda(t) b u_2(t) dt\end{align*} \]

6. déduire du principe du minimum de Pontryagin que \( \lambda(t) u_1(t) \leq \lambda (t) u_2(t)\) et que, d’après l’égalité précédente on a alors

   \[ \lambda(t) u_1(t) = \lambda(t) u_2(t) \]

   presque partout. En déduire sous quelle condition on peut conclure

   \[ u_1(t)ū_2(t) \]

   presque partout.
7. dans le cas où \( x\) est un vecteur et \( u\) un scalaire, proposer une généralisation.

On considère le problème de construire une route à pente limitée sur un relief constitué de collines. On représente le problème dans un plan vertical pour simplifier. On repère \( [O,L]\ni l \mapsto z(l)\) l’altitude du relief avant travaux, et \( [O,L]\ni l \mapsto x(l)\) l’altitude après les travaux. Les travaux consistent à creuser ou à remblayer le terrain pour définir l’altitude \( x\) qui minimise le critère

On souhaite que la route ait une pente limitée. On écrit cette contrainte sous la forme

1. Ecrire l’Hamiltonien de ce problème de commande optimale
2. Former le problème aux deux bouts. Montrer que la valeur finale de l’état adjoint \( \lambda\) est \( \lambda(L)=0\) .
3. En utilisant le principe de minimum de Pontryagin, montrer que
• si \( \lambda>0\) , \( u=-a\)
• si \( \lambda=0\) , \( u=\dot z\)
• si \( \lambda<0\) , \( uā\)

4. En déduire que la solution optimale consiste en une succession de travaux sur des intervalles \( [t_i, t_{i+1}]\) tels que

   \[ \int_{t_i}^{t_{i+1}} (z(l)-x(l))dl =0 \]

   On ne cherchera pas à calculer les \( t_i\) . Interpréter l’égalité précédente.

On considère un problème de minimisation du coût de trajet entre une destination et tous les points d’un graphe. Le graphe (non orienté) est représenté sur la figure 4. Le coût de trajet entre 2 cases est précisé sur le segment les reliant. A tout instant, il est possible de rester immobile sur une case, avec un coût 0 pendant l’arrêt.

Construire un champ d’extrémales par la méthode de la programmation dynamique en partant de la destination. On construira ainsi progressivement les chemins menant en \( 1\) , \( 2\) , \( 3\) , \( 4\) , étapes à la destination. D’après cette analyse, quel est le meilleur chemin pour aller de la case 3 à la case 5?

On s’intéresse au problème de minimisation (globale)

où \( f\) est une fonction à valeurs dans \( \mathbb{R}\) , continue par rapport à chacune de ses variables et où \( a,b : \mathbb{R} \rightarrow \mathbb{R}\) sont continues et vérifient en particulier la propriété suivante: \(   \forall \theta \in \mathbb{R}, \,\,\, a(\theta) < b(\theta)\) (pour assurer la bonne définition de l’intervalle considéré dans (60)). Le graphe d’une telle fonction \( f\) est représentée sur la figure 5.

On définit

Lorsque deux points donnent la même valeur minimale globale de \( f\) , alors l’ensemble \( x^*(\theta)\) contient ces deux points. Le but de l’exercice est d’étudier la régularité de la fonction \( f^{\star}\) .

1. Justifier que, pour tout \( \theta \in \mathbb{R}\) , l’ensemble \( x^{\star}(\theta)\) est non-vide.
2. Illustrer par un exemple (schéma) le fait que \( x^{\star}(\theta)\) peut varier non continûment en \( \theta\) .
1. Soit \( \theta \in \mathbb{R}\) . On considère une suite \( (\theta_n)\) convergente de limite \( \theta\) et \( (x_n)\) avec \( x_n \in x^{\star}(\theta_n)\) .
1. Justifier que l’on puisse considérer une sous-suite convergente de \( (x_n)\) , dont on notera \( x\) la limite.
2. Montrer par l’absurde que \( x \in x^{\star}(\theta)\) (on pourra exhiber une suite convergente de limite \( \hat x \in x^{\star}(\theta)\) , dont on justifiera l’existence).
3. Conclure que \( f^{\star}\) est continue en \( \theta\) .

Soit un intervalle \( [a,b]\) , \( a<b\) . On considère l’espace de Hilbert \( H=L_2[a,b]\) constitué des fonctions \( y:[a,b]\rightarrow \mathbb{R}^n\) de carré sommable

où on a utilisé la norme Euclidienne de \( \mathbb{R}^n\) sous l’intégrale.

On souhaite utiliser le théorème de projection suivant (voir Luenberger, Optimisation by vector spaces methods, Wiley-Interscience 1997): soit \( H\) un Hilbert et \( M\) un sous espace fermé de \( H\) , alors, à tout \( x\in H\) il correspond un unique \( x_0\in V\) où \( V\) est l’espace affine \( V=x+M\) tel que

Ce point \( x_0\) est orthogonal à \( M\) , on note \( x^0\in M^\bot\) .

1. On considère \( \{y_1,...,y_n\}\) un ensemble de \( n\) vecteurs (fonctions) indépendants de \( H\) et \( \{c_1,...,c_n\}\) \( n\) scalaires (constantes). On note \( M\) l’espace engendré par \( \{y_i\}_{i=1...n}\) et on considère \( V=\{x\in H   /   <x,y_i>=c_i, \forall i=1...n\}\) . Caractériser \( M^\bot\) et en déduire que \( V\) est un espace affine translaté de \( M^\bot\) .

2. En appliquant le théorème de projection ci-dessus à \( V\) , montrer qu’il existe un unique \( x_0\in V\) solution de

   \[ \min_{x\in V} \left\lVert x\right\rVert \]

3. En utilisant le fait que \( (M^\bot)^\bot=M\) , montrer que \( x_0=\sum_{i=1}^n \beta_i y_i\) où les \( \beta_i\) sont solutions du système linéaire

   \[ \left(<y_i,y_j>\right)_{i=1...n, j=1...n} \left(\begin{array}{c} \beta_1\\ \vdots\\ \beta_n\end{array} \right)= \left(\begin{array}{c} c_1 \\ \vdots \\ c_n\end{array} \right) \]

4. Application. On considère le problème suivant

   \[ \min_{u\in L_2[0,1]} \int_0^1 u^2(t) dt \]

   sous les constraintes

   \[ \dot x_1=x_2, ~ \dot x_2=-x_2+u, ~ x_1(0)=x_2(0)=0, ~ x_1(1)=1, ~ x_2(1)=0 \]
• par intégration, montrer que \( x_2(1)īnt_0^1 \exp(t-1) u(t) dt\) et que \( x_1(1)īnt_0^1(1-\exp(t-1))u(t) dt\)
• écrire les contraintes du problème ci-dessus sous la forme \( <u,y_1>=c_1,   <u,y_2>=c_2\) .
• en déduire que la solution du problème est \( u(t)=\beta_1 y_1(t)+ \beta_2 y_2(t)\) où \( \beta_1\) et \( \beta_2\) sont solutions d’un système d’équations linéaires qu’on précisera.

On cherche le meilleur antécédent d’un vecteur \( b\in\mathbb{R}^n\) par une matrice \( A\) de taille \( n\times n\) non inversible.

1. On considère le problème d’optimisation

   \[ \min_u \left\lVert Au-b\right\rVert \]

   où \( \left\lVert \cdot\right\rVert \) désigne la norme Euclidienne. Montrer que ce problème est convexe. En déduire que \( u\) réalise le minimum de la fonction objectif si et seulement si

   \[ A^T A u= A^T b \]
2. La matrice \( A\) étant non inversible, montrer que \( A^T A\) ne l’est pas non plus.

3. Montrer que la matrice \( A^TA\) est symétrique positive. On note \( \lambda_1, ..., \lambda_m\) ses \( m\) valeurs propres non nulles, avec \( m<n\) . En déduire que

   \[ A^T A=\sum_{i=1}^m \lambda_i v_i v_i^T \]

   où \( v_i\) sont des vecteurs propres orthonormaux de \( A^TA\) .

4. On considère la matrice

   \[ PĀ^TA\left(\sum_{i=1}^m \frac{1}{\lambda_i} v_i v_i^T \right) \]

   Montrer que \( \textrm{rang }P=m\) , \( P^2=P\) , et que \( \textrm{Im } P = \textrm{Im } A^T\) . En déduire que \( P\) est la projection orthogonale sur \( \textrm{Im } A^T\) .

5. En déduire que le vecteur suivant

   \[ u^*=\left(\sum_{i=1}^m \frac{1}{\lambda_i} v_i v_i^T \right)A^T b \]

   réalise l’optimum recherché. Montrer que si \( A\) est inversible, i.e. \( m=n\) , alors \( Au^*=b\) .

On s’intéresse au problème de programmation quadratique (QP) suivant

où \( P\) est une matrice \( n\times n\) symétrique définie positive, \( M\) une matrice \( m\times n\) , \( f\in \mathbb{R}^n\) , \( b\in \mathbb{R}^m\) , avec \( m>n\) .

L’objet de cet exercice est d’exposer la construction d’un algorithme dit de “points intérieurs”.

1. Montrer que le problème (63) admet une unique solution optimale.

2. On cherche à réécrire ce problème sous une forme canonique où les inégalités sont juste des relations de positivité des inconnues. Pour cela, on introduit un vecteur \( s\) de \( m\) inconnues positives ou nulles, et un vecteur \( y\) de \( 2n\) inconnues positives ou nulles. Chaque composante \( i\) de \( z\) est exprimable sous la forme

   \[ z_i=y_i-y_{i+n}, ~ y_i \geq 0, ~ y_{i+n} \geq 0 \]

   Montrer qu’on peut réécrire (63) sous la forme

   \[ \begin{equation}\left\{\begin{aligned}&\min \frac{1}{2} x^T Q x + c^T x\\ &Ax = b\\ &-x \leq 0\end{aligned}\right. \end{equation} \]

   (64)

   avec

   \[ x=\left( \begin{array}{c} y\\ s \end{array}\right), ~ Q=\left(\begin{array}{cc}N^T P N & 0_{2n\times m}\\ 0_{m \times 2n} &0_{m \times m}\end{array}\right), \]
   \[ c^T=\left(\begin{array}{cc} f^T N & 0_{1\times m}\end{array} \right), ~ A=\left(\begin{array}{cc} M N & I_m\end{array}\right) \]

   où \( N\) est une matrice qu’on explicitera.

3. Former le problème dual de (64) (on l’écrira comme un problème de maximisation sous contraintes). Pour cela, on formera le Lagrangien

   \[ L=\frac{1}{2} x^TQ x + c^T x + \lambda^T (b-Ax) -\mu^T x \]

4. Montrer que les conditions de Karush-Kuhn-Tucker pour le problème général

   \[ \left\{\begin{aligned}&\min f(x)\\ & d(x)=0, ~ e(x) \leq 0\end{aligned}\right. \]

   sont

   \[ \begin{equation}\left\{\begin{aligned}&\nabla f(x^*) +\sum \lambda_i^* \nabla {d_i}(x^*) + \sum \mu_i^* \nabla e_i(x^*)=0\\ &d(x^*)=0\\ &e(x^*)\leq 0\\ &\mu^* \geq 0\\ & \mu^*_i c_i(x^*)=0\end{aligned}\right. \end{equation} \]

   (65)

5. Former les conditions (65) pour le problème (64).

6. On va pénaliser les contraintes \( -x\leq 0\) dans le côut en considérant le problème, pour \( \varepsilon>0\) ,

   \[ \begin{equation}\left\{\begin{aligned}&\min \frac{1}{2} x^T Q x + c^T x - \varepsilon \sum \ln (x_i)\\ &Ax = b\\ \end{aligned}\right. \end{equation} \]

   (66)

   Montrer que le problème (66) possède une unique solution.

7. Former le Lagrangien associé à (66) et montrer que les conditions de Karush-Kuhn-Tucker sont

   \[ \begin{equation}\left\{\begin{aligned}&Ax=b\\ &-Qx+A^T \lambda +s=c\\ &x_i s_i=\varepsilon\\ &x_i \geq 0\\ & s_i \geq 0\end{aligned}\right. \end{equation} \]

   (67)

8. Montrer comment résoudre les conditions (67) par une méthode de Newton avec projection. Former pour cela le Jacobien de la fonction à annuler. Former la première itération de cet algorithme en exhibant le calcul de la direction et la procédure de projection.
9. Comment atteindre la solution de (65)?

10. Une méthode itérative consiste à considérer \( \epsilon=\sigma \frac{x^T s}{2n+m},   \sigma\in]0, 1[\) .

    Comment peut-on interpréter ce choix?

Dans un véhicule hybride, une question importante est celle du refroidissement de la batterie qui perd de son efficacité (et de sa disponibilité) si elle est trop chaude. On va chercher à établir une politique optimale de refroidissement sur un horizon de temps donné \( T>0\) (et une route connue à l’avance). Soit \( \theta_b\) la température interne de la batterie, \( \theta\) la température de son échangeur thermique, \( u\) son courant de sortie, et \( \xi\) sa charge. En tenant compte des échanges thermiques, de la consommation et de l’échauffement par effet Joule, on a les équations suivantes

où \( a,b,c,k\) sont des coefficients positifs (connus) et \( D(t)\) est une fonction connue du temps. Le système est initialisé au temps \( 0\) aux valeurs

1. On cherche à minimiser la température finale \( \theta_b(T)\) sous la contrainte de maintien de la charge \( \xi(T)=\xi(0)\) . Montrer qu’on peut formuler ce problème sous la forme

   \[ \min_{\left\{\begin{aligned} &\frac{d}{dt} \theta = c u - k \theta\\ &\frac{d}{dt} \xi = D(t)-u\\ &\xi(T)=\xi(0)\\ &\theta(0), \xi(0) \textrm{ donnés} \end{aligned}\right.} \int_0^T L(\theta,u) dt \]

   où on précisera \( L(\theta,u)\) .
2. Former l’Hamiltonien associé au problème et les équations différentielles du problème aux deux bouts.
3. Intégrer, au moyen de deux constantes qu’on notera \( \alpha\) et \( \beta\) les équations adjointes.
4. Donner l’expression de la commande optimale au cours du temps en fonction de \( \alpha\) et \( \beta\) .
5. Expliciter une première relation entre \( \alpha\) et \( \beta\) provenant de la contrainte \( \xi(T)=\xi(0)\) .
6. Trouver la valeur optimale de \( \alpha\) en utilisant la relation précédente et en invoquant la stationnarité de la fonction coût à l’optimum.

Soit \( f:I \rightarrow \mathbb R\) avec \( I\) intervalle de \( \mathbb R\) . On suppose que \( f\) est convexe sur \( I\) , et on considère \( \{ x_i, i=1,...n\}\) une famille d’éléments de \( I\) , \( n\) entier \( n>1\) .

1. Montrer (par exemple par récurrence) que

   \[ f(x_1)+...+f(x_n) \geq n f(\frac{x_1+...+x_n}{n}) \]

   On a égalité si et seulement si tous les \( x_i\) sont égaux.
2. En utilisant l’inégalité précédente pour \( f(x)=-\sin x\) et \( I=[0, \pi]\) , montrer que parmi les polygones à \( n\) c^{o}tés inscrits dans un cercle donné, les polygones réguliers ont le plus grand périmètre.

On se donne une collection d’arcs orientés reliant des points \( P_1\) , \( P_2\) , \( P_3\) , \( P_4\) , \( P_5\) . Tous les points ne sont pas connectés directement avec les autres. Les arcs sont orientés, c’est à dire qu’on peut aller de \( P_1\) à \( P_2\) directement, mais que le retour n’existe pas forcément. Les longueurs (co^{u}ts) des arcs sont rangés dans une matrice

Ainsi, l’arc reliant \( P_1\) à \( P_2\) a une longueur 3, alors qu’il n’y a pas d’arc (on note que la longueur est infinie) reliant \( P_1\) à \( P_4\) .

On cherche à établir une carte des plus courts chemins entre chaque point du graphe. Pour résoudre ce problème on va utiliser la programmation dynamique.

1. Dessiner tous les arcs du graphe reliant les points \( P_1\) , \( P_2\) , \( P_3\) , \( P_4\) , \( P_5\) . De combien d’arc le graphe est-il ainsi constitué?

2. On note \( M^k\) la matrice dont chaque coefficient \( M_{i,j}^k\) vaut la longueur totale de la séquence optimale de \( k\) arcs (ou moins) reliant \( P_i\) à \( P_j\) . En utilisant le principe d’optimalité de Bellman, montrer que

   \[ M_{i,j}^{k+1}=\min_{p=1,...,5}(M_{i,p}^1+M_{p,j}^k) \]
3. En déduire quel est le co^{u}t de la meilleure séquence pour aller de \( P_1\) à \( P_3\) .

On veut montrer que parmi les courbes fermées régulières du plan (simples: ne faisant pas de boucles) de longueur donnée, celles qui ont une aire intérieure maximale sont des cercles c’est la solution du célèbre problème de Dido de l’Antiquité.

On note \( \mathcal C\) une courbe dans le plan, fermée simple et régulière, et on la suppose paramétrée par son abscisse curviligne, en notant \( L\) sa longueur:

Cette courbe (dite de Jordan) sépare le plan en une partie intérieure \( \mathcal I\) et une partie extérieure.

1. La longueur \( L\) est solution de l’équation intégrale

   \[ L= \int_0^L \left\lVert \frac{dc}{ds}\right\rVert ds \]

   Vérifiez votre formule en calculant le périmètre d’un cercle de rayon \( r\) .

2. L’aire \( A\) de la zone \( \mathcal I\) est

   \[ A=\frac{1}{2} \int_0^L \det\left[c(s),\frac{dc}{ds}(s)\right] ds \]

   Utiliser cette formule pour calculer l’aire d’un disque de rayon \( r\) .

3. On considère une variation autour de \( c\) , en utilisant \( \nu(s)\) le vecteur normal (extérieur) à la courbe \( \mathcal C\) au point courant \( c(s)\) , et \( f\) une fonction régulière \( L\) -périodique à valeur dans \( \mathbb R\) . Ceci permet de construire, pour tout \( t\in \mathbb R\) ,

   \[ v(t,s)=c(s)+t f(s) \nu(s) \]

   Faire un dessin représentant \( c\) et \( v\) , mettant en évidence que lorsque \( \left\lvert t\right\rvert \) est suffisamment petit, \( s\mapsto v(t,s)\) définit encore une courbe fermée simple.

4. On note \( L_f\) et \( A_f\) la longueur et l’aire intérieure associées à \( s\mapsto v(t,s)\) . Montrer que la dérivée à \( t=0\) de \( t\mapsto \frac{L_f(t)^2}{A_f(t)}\) s’annule si et seulement si

   \[ \frac{d}{dt} L_f(0)=\frac{L}{2A} \frac{d}{dt} A_f(0) \]

5. Ré-écrire cette condition en utilisant le fait que

   \[ \frac{d}{dt} L_f(0)=-\int_0^L k(s) f(s) ds, ~ \frac{d}{dt} A_f(0)=-\int_0^L f(s) ds \]

   où \( k\) désigne la courbure de \( \mathcal C\) . On demande d’obtenir une condition que doit vérifier \( k(s)\) pour que \( \mathcal C\) réalise un extremum de \( \frac{L^2}{A}\) .
6. Conclure par le lemme de duBois-Reymond que \( \mathcal C\) est nécessairement un cercle.

On considère un problème de commande optimale où le co^ut à minimiser est

La particularité du problème est que \( x\) subit un saut en un instant \( \tau \in]0, 1[\) défini implicitement par la condition (on suppose \( \tau\) unique)

A l’instant \( \tau\) , l’état subit un saut de la forme

où \( \Delta\) est un vecteur de paramètres donné. Sur l’intervalle \( [0,\tau[\) , l’état satisfait une équation différentielle \( \dot x=f_1(x,u)\) , et sur l’intervalle \( ]\tau,1]\) , il satisfait \( \dot x=f_2(x,u)\) . La condition initiale \( x(0)=x^0\) est imposée.

1. On demande d’établir le problème aux deux bouts correspondant. Pour cela, on pourra adjoindre les contraintes, et faire intervenir deux intégrales pour distinguer le saut. On montrera que l’état adjoint subit lui aussi un saut.
2. Sans détailler les calculs, expliquer comment ce formalisme permet de traiter le problème suivant: lors de l’optimisation de trajectoire d’une fusée, on cherche à se débarrasser des protections thermiques (la coiffe) lorsqu’en sortant de l’atmosphère les frottements aérodynamiques deviennent suffisamment faibles.

Soit un ellipsoide défini par l’équation

avec \( a, b, c\) des scalaires non nuls. On cherche le parallélépipède rectangle dont les ar^etes sont parallèles aux axes ayant un volume maximal en restant contenu dans l’ellipsoïde. On note \( x\) , \( y\) , \( z\) les demi-longueurs de ses ar^etes, si bien que son volume est

1. Écrire les conditions de stationnarité pour ce problème sous contrainte. On pourra noter \( \lambda\) le multiplicateur associé à la contrainte \( c\) .
2. En utilisant que le volume du parallélépipède solution est de volume non nul, montrer que \( \lambda\) est non nul.
3. Montrer que le volume optimal s’exprime directement en fonction de \( \lambda\) .
4. Éliminer \( \lambda\) des équations pour obtenir \( xā/\sqrt 3\) . En déduire que le volume optimal est \( \frac{8 abc}{3 \sqrt{3}}\) .

On dispose d’un c^able semi-rigide de longueur \( L\) qu’on souhaite étaler sur le sol entre 2 points à connecter situés à une distance \( L/2\) . Le c^able est donc trop long.

Pour ne pas trop encombrer, on va chercher à trouver une disposition au sol qui ne prend pas trop de place tout en respectant les contraintes mécaniques du c^able. Pour déterminer cette disposition, on va résoudre un problème d’optimisation de trajectoires.

On considère l’axe \( x\) reliant le point de départ et le point d’arrivée. On complète le repère avec un axe orthogonal \( y\) et on résoud le problème suivant

sous les contraintes

avec \( K\) et \( \alpha\) des paramètres positifs.

1. Faire un schéma du problème et esquisser la solution.
2. Former le problème aux 2 bouts correspondant.
3. Comment doit-on choisir \( T\) pour prendre en compte la longueur donnée du c^able?
4. Quel paramètre du problème permet de prendre en compte la rigidité du c^able?
5. Quel paramètre permet d’assurer que \( x(T)\approx L/2\) ?

Lors d’un investissement public, deux options s’offrent en général aux décideurs:

1. investir dans un endroit possédant déja une forte activité économique
2. investir dans une zone défavorisée.

Considérant que chaque territoire du pays se voit attribuer un budget d’investissement économique \( x(z)\) où \( z\) désigne le territoire, on note \( f(x)\) la rentabilité de l’investissement (fonction supposée continue et différentiable avec \( f(0)=0\) ). Le décideur qui doit prendre une mesure à l’échelle nationale cherche à maximiser la rentabilité totale

Si on considère qu’un investissement est plus rentable sur un territoire pauvrement doté, on décrit

Montrer à cette hypothèse politique correspond au fait que \( f\) est concave et croissante.

Soit \( f:\mathbb R^n \rightarrow \mathbb R \) une fonction quadratique strictement convexe. Soit \( x\) , \( y_1\) ,...,\( y_n\) des vecteurs de \( \mathbb R^n\) .

1. Montrer que la fonction \( \mathbb R^n \ni (\lambda_1,...,\lambda_n) \mapsto f(x+\sum_{i=1}^n \lambda_i y_i)\) est également quadratique convexe.
2. Donner l’expression de son Hessien.
3. A quelle condition est-elle strictement convexe?

Soit la parabole d’équation \( 5 y= (x-1)^2\) . On cherche le point de la parabole de distance Euclidienne minimale avec le point de coordonnées \( (1,2)\) .

1. Définir un problčme de minimisation sous contraintes correspondant.
2. Trouver les points satisfaisant les conditions de Lagrange.
3. Déterminer la solution.
4. Procéder par substitution directe de \( y\) en fonction de \( x\) et formuler un problčme de minimisation de la seule variable \( x\) . Retrouver ainsi le résultat de la question précédente.

On considčre les trois problčmes suivants. Expliquer lesquels possèdent des solutions.

On s’intéresse ici ŕ une classe de méthodes permettant de résoudre un problčme de minimisation sous contraintes comme limite d’une séquence de problčmes sans contraintes. On note

oů on suppose que les fonctions \( J\) et \( g_i\) sont réguličres de \( \mathbb R^n\rightarrow \mathbb R\) , et que les contraintes définissent un ensemble compact non vide \( S\) , contenant une unique solution globale \( x^*\) , non isolée dans \( S\) . On veut résoudre le problčme en résolvant une séquence de problčmes sans contraintes dits “pénalisés” du type

oů \( \gamma\) est une fonction positive, régulière sur \( ]-\infty,0[\) , telle que \( \lim_{x\rightarrow 0-} \gamma(x)=+\infty\) . Par convention, \( \gamma(x)=+\infty\) , pour \( x\geq 0\) . On considčre une suite strictement décroissante \( (\epsilon_k)\) de réels strictement positifs et on note, pour tout \( k\)

On suppose que \( J_{k}\) admet un minimum sur \( \mathbb R^n\) en un point unique noté \( x_k\) .

1. Montrer que pour tout \( k\) , \( x_k\) est dans l’intérieur de \( S\) .

2. Montrer que pour tout \( k\) on a

   \[ \begin{align}J_{k}(x_k) \leq J_{k}(x_{k+1}) \end{align} \]

   (70)

   \[ \begin{align} J_{{k+1}}(x_{k+1}) \leq J_{{k+1}}(x_k) \end{align} \]

   (71)

3. Déduire, par une combinaison linéaire des lignes qui précčdent, que

   \[ \begin{align}J(x_{k+1}) \leq J(x_k)\end{align} \]

   (72)

4. Montrer, en utilisant (70) et la relation précédente que

   \[ p(x_k)\leq p(x_{k+1}) \]

5. Montrer, en utilisant (71) que

   \[ \begin{align}J_{{k+1}}(x_{k+1}) \leq J_{{k}}(x_{k})\end{align} \]

   (73)

6. Montrer que pour tout \( \delta >0\) , il existe \( x^\delta\in S\) tel que \( J(x^\delta)<J(x^*)+\delta/2\)

7. On choisit un entier \( l\) tel que

   \[ \epsilon_l p(x^\delta)< \delta/2 \]

   Montrer, en utilisant  (73), qu’on a, pour tout \( k>l\)

   \[ J_{{k}}(x_{k}) \leq J_{l}(x^\delta) \]

8. En déduire que

   \[ J(x^*)\leq J(x_{k})<J(x^*)+\delta \]

   pour tout \( k>l\) et que donc

   \[ \lim_{k\rightarrow \infty} J(x_k)=J(x^*) \]
9. Montrer enfin que \( (x_k)\) converge vers \( x^*\) .

La séquence des problčmes non contraints mais pénalisés génčre une suite qui converge donc vers la solution \( x^*\) du problčme contraint.

Le PSA est un type de contrat fréquemment utilisé dans le domaine des ressources naturelles, notamment dans l’industrie pétroličre. Un PSA définit pour la durée de vie d’un réservoir (typiquement 25 ans) la part du pétrole produit qui va revenir, ŕ chaque instant (année), ŕ l’exploitant du gisement et au pays propriétaire du gisement, respectivement. Deux données importantes sont ŕ prendre en compte dans le cas d’un réservoir pétrolier: i) si on produit beaucoup au début, on risque de “fatiguer” le réservoir, ce qui entraînera un épuisement rapide des réserves ultérieures ii) un exploitant cherchera naturellement ŕ rentabiliser le plus vite possible les investissements lourds qu’il a réalisés lors de l’équipement du réservoir (forage, cimenterie du puits, instrumentation, riser, etc...). Ces deux effets sont antagonistes.

On considčre que le problčme peut-ętre décrit au moyen de 2 variables d’état: \( r\) les réserves exploitables dans le réservoir, \( p\) le profit cumulé de l’exploitant. Ces deux variables satisfont les équations différentielles

oů \( u\in[0,1]\) désigne la production instantanée, \( h\) est une fonction d’épuisement positive croissante, \( \epsilon\) définit les intéręts du capital. Le contrat PSA définit la fonction \( v(t)\in[0,1]\) qui est la fraction de la production revenant ŕ l’exploitant. Le reste revient au pays propriétaire du gisement.

1. On considčre le point de vue de l’exploitant. Il souhaite maximiser son profit cumulé \( p(T)\) , oů \( T=25\)  ans. Le réservoir est initialement plein \( r(0)=1\) . Il est vide en fin d’exploitation \( r(T)=0\) . Le cumul du profit est initialement nul \( p(0)=0\) . Former le problčme d’optimisation sous contraintes. Former l’Hamiltonien du systčme.
2. On considčre \( \epsilon=0\) et \( v\) constante. Montrer que les états adjoints sont constants. Montrer, qu’il existe une production \( u\) constante satisfaisant le principe du minimum de Pontryaguine. Interpréter ce résultat.
3. Former le problčme aux deux bouts dans le cas général.

4. On considčre maintenant le point de vue du pays propriétaire du gisement. Son intéręt est de maximiser la quantité totale de pétrole qui lui revient produite au cours de toute la durée de vie du réservoir (jusqu’ŕ épuisement \( r(T)=0\) ). Montrer que le critčre ŕ minimiser est

   \[ \int_0^Tu(t)(v(t)-1)dt \]
5. Former le problčme aux deux bouts correspondant.

1. Soit \( f\) une fonction convexe définie sur un ensemble convexe \( E\) . Montrer que l’ensemble

   \[ L_t=\left\{ x \in E \text{ tel que } f(x) \leq t \right\} \]

   est un ensemble convexe.

2. Soit \( g_i\) , \( i=1,...,k\) des fonctions convexes définies sur \( \mathbb R^n\) . Montrer que l’ensemble

   \[ L =\left\{ x \text{ tel que } g_i(x) \leq 0, i=1,...,k \right\} \]

   est un ensemble convexe.
3. Soit \( f\) et \( g\) deux fonctions convexes \( \mathbb R \rightarrow \mathbb R\) . Montrer que \( h(x,y)=f(x)+g(y)\) est convexe.

On s’intéresse au polyn^{o}me de degré \( n-1\) approchant le mieux possible \( t\mapsto t^n\) . On considère ainsi le problème de minimisation

1. Montrer que \( x\mapsto f(x)\) est convexe.
2. Former la condition de stationnarité de \( f\) .
3. On considère le produit scalaire \( \int_{-1}^1 g(t) h(t) dt= <g,h>\) de l’espace \( L_2([-1,1])\) . Montrer que les conditions précédentes impliquent qu’un certain polyn^{o}me est orthogonal à toutes les puissances \( t^k\) , \( k=0, ..., n-1\) .

4. Montrer que le polyn^{o}me recherché est (polyn^{o}me de Rodrigues)

   \[ R(t)=t^n - \frac{n!} {(2n)!} \frac {d^n}{dt^n} (t^2-1)^n \]

   (on remarquera que \( R\) est de degré \( n-1\) ).
5. Quel est le polyn^{o}me de Rodrigues pour \( t^3\) ?

On cherche (voir [11]) à résoudre des problèmes d’optimisation de trajectoires généraux

où \( f\) est une fonction régulière, \( F\) et \( Q\) des matrices symétriques positives, \( R\) une matrice symétrique définie positive, \( x^0\) , \( t_1\) , \( t_2\) des paramètres donnés.

Pour cela, on propose une méthode d’approximation linéaire successive des équations de la dynamique, sous l’hypothèse (qu’on supposera vérifiée) que \( \dot x = f(x,u)\) peut s’écrire

avec \( A\) et \( B\) des fonctions (matricielles) régulières.

1. Former l’Hamiltonien du problème (74) en utilisant l’écriture (75).

2. Montrer que le problème aux deux bouts est

   \[ \left.\begin{aligned}&\dot xĀ(x) x + B(x) u,\\ & x(t_1)=x^0\\ & u =-R^{-1} B(x)^T \lambda\\ & \dot \lambda = -Qx +C(x,\lambda) \lambda, \\ & \lambda(t_2)=Fx(t_2)\end{aligned} \right\} \]

   avec \( C(x,\lambda)=-\frac{d}{dx}(A(x)x)^T-u^T \frac{d}{dx} B(x)^T\)

3. On introduit la séquence fonctionnelle \( (x^{[i]},\lambda^{[i]})_{i\in \mathbb N}\)

   \[ x^{[0]}(t)=x^0, ~ \lambda^{[0]}(t)=Fx^0 \]

   avec, pour \( i\geq 1\) ,

   \[ \begin{align*}&\frac{d}{dt} \xxiĀ(x^{[i-1]})x^{[i]} -B(x^{[i-1]})R^{-1} B(x^{[i-1]})^T\lambda^{[i]}\\ & x^{[i]}(t_1)=x^0\\ &\frac{d}{dt} \lambda^{[i]} = -Q x^{[i]} + C(x^{[i-1]},\lambda^{[i-1]})\lambda^{[i]}\\ &\lambda^{[i]}(t_2)=F x^{[i-1]}(t_2)\end{align*} \]

   Ecrire ce système sous une forme

   \[ \begin{align}\frac{d}{dt} z^{[i]}=\bar A (z^{[i-1]}) z^{[i]} \end{align} \]

   (76)

   avec

   \[ z^{[i]}=\left( \begin{array}{c} x^{[i]} \\ \lambda^{[i]} \end{array} \right) \]

   Préciser \( \bar A\) .

4. L’équation (76) définit un système linéaire instationnaire de la forme

   \[ \frac{d}{dt} y(t)=M(t) y(t) \]

   On introduit un état adjoint

   \[ \begin{align}\frac{d}{dt} \mu(t)=-M(t)^T \mu(t) \end{align} \]

   (77)

   Montrer, en utilisant le lemme de l’adjoint, que

   \[ y^T(t_2) \mu(t_2)=y^T(t_1) \mu(t_1) \]

5. Soit \( \delta_k=\left( 0\, … \, 0 \, 1\, 0 \, … \, 0 \right)^T\) où le \( 1\) est en position \( k\) avec \( n+1\leq k \leq 2n\) , avec \( n=\dim x\) .

   Montrer que la \( (k-n)\) -ième composante de \( \lambda^{[i]}(t_2)\) vaut \( y^T(t_1) \mu_k(t_1)\) où \( \mu_k\) est la solution de (77) avec la condition finale \( \mu_k(t_2)=\delta_k\) .

6. Former la condition terminale du problème aux deux bouts et montrer qu’elle est de la forme

   \[ \lambda(t_2)=\left(\begin{array}{c} x^T(t_1) \alpha_{n+1}(t_1) + \lambda^T(t_1) \beta_{n+1}(t_1)\\ x^T(t_1) \alpha_{n+2}(t_1) + \lambda^T(t_1) \beta_{n+2}(t_1)\\ \vdots \\ x^T(t_1) \alpha_{2n}(t_1) + \lambda^T(t_1) \beta_{2n}(t_1)\\ \end{array}\right) \]

   avec

   \[ y=\left(\begin{array}{c} x\\ \lambda \end{array}\right), ~ \mu=\left(\begin{array}{c} \alpha \\ \beta \end{array}\right) \]

   et que donc

   \[ \lambda^{[i]}(t_1) = \left(\begin{array}{c} \beta_{n+1}^T(t_1) \\ \beta_{n+2}^T(t_1) \\ \vdots \\ \beta_{2n}^T(t_1)\end{array}\right)^{-1} \left( F x^{[i-1]}(t_f)-\left(\begin{array}{c} (x^0)^T \alpha_{n+1}(t_1) \\ (x^0)^T \alpha_{n+2}(t_1) \\ \vdots \\ (x^0)^T \alpha_{2n}(t_1) \\ \end{array}\right)\right) \]
7. En déduire que le problème aux deux bouts devient résoluble, avec le schéma proposé, par la résolution successive de problèmes de Cauchy à préciser.

On considère le problème

pour le système dynamique

où \( a\) et \( b\) sont des vecteurs donnés, \( t_2>t_1\) des constantes.

1. Former l’Hamiltonien du problème.
2. Former les équations de l’état adjoint.
3. La condition \( \frac{\partial H}{\partial u}=0\) n’est pas directement exploitable pour déterminer \( u\) . Dériver cette condition autant de fois que nécessaire pour obtenir une expression de \( u\) .
4. Montrer que \( \frac{\partial }{\partial u}\frac{d^2}{dt^2}\left(\frac{\partial H}{\partial u}\right)\leq 0\) (cette condition est appelée condition de Legendre-Clebsch généralisée ou condition de Kelley).

On souhaite concevoir un réservoir cylindrique de contenance maximale au moyen d’une quantité limitée de matériau.

1. On note \( d\) le diamètre du disque de base du cylindre et \( h\) sa hauteur. Donner l’expression du volume \( V\) contenu dans le cylindre, et l’expression de sa surface \( S\) .
2. La surface du cylindre est constituée de plaques de t^ole d’une épaisseur constante (négligeable). Ainsi la grandeur \( S\) est contrainte. Former le problème d’optimisation de la contenance sous contrainte \( S=S^0\) et donner son Lagrangien.
3. Former les conditions de stationnarité et montrer que la hauteur optimale et le diamètre optimal sont égaux et valent \( \sqrt{\frac{2 S^0}{3\pi}}\) .

On considère (voir [12]) le problème

pour le système dynamique

où \( a<b\) et \( t_1\) sont des constantes, \( \alpha \neq \beta\) des vecteurs donnés, et \( t_2>t_1\) est libre.

1. Énoncer le principe de minimum de Pontryagin pour ce système.
2. Montrer que si \( u_1\) et \( u_2\) sont deux commandes optimales, produisant le même temps \( t_2-t_1\) , alors \( \frac{1}{2}(u_1 +u_2)\) est aussi admissible et optimale.
3. En déduire l’unicité de la commande optimale.

L’objet de cet exercice est de démontrer que l’image par une fonction régulière (à Jacobien inversible) d’une boule de taille suffisamment petite est convexe. Cette propriété a été établie dans des espaces de Hilbert généraux et est utilisée notamment dans l’étude des valeurs propres de matrices et d’opérateurs perturbés (voir [13]).

On établit d’abord un résultat préliminaire.

Soit une fonction \( P: \mathbb{R}^n\rightarrow \mathbb{R}^m\) régulière. On cherche à résoudre l’équation

au moyen d’une séquence

initialisée en \( x^0\) donné. On suppose que

1. \( P'\) le Jacobien de \( P\) est Lipschitzien avec comme constante \( L>0\)
2. la fonction \( Q_n\) vérifie \( \left\lVert P(x)-P'(x) Q_n(x)\right\rVert \leq \gamma \left\lVert P(x)\right\rVert \) , avec \( 0< \gamma <1\)
3. \( \left\lVert Q_n(x)\right\rVert \leq \lambda \left\lVert P(x)\right\rVert \) , pour un certain \( \lambda\geq 0\) ,
4. \( \gamma+\frac{L \lambda^2}{2} \left\lVert P(x^0)\right\rVert <1\)

On va montrer que la séquence (79) converge vers \( x^*\) solution de (78). Dans la suite, on utilise la norme Euclidienne et la norme induite.

1. Dans le cas où on cherche à résoudre un système linéaire \( Ax=b\) , avec \( P(x)Āx-b\) , et \( A\) inversible, montrer que les hypothèses ci-dessus sont vérifiées. On précisera le choix retenu pour \( Q_n\) , les valeurs de \( L\) , \( \gamma\) .

2. En utilisant le développement (formule de Taylor), et les propriétés (i-ii-iii),

   \[ P(x+y)=P(x)+\int_0^1 P'(x+ty) y dt \]

   entre les points \( x^n\) et \( x^{n+1}\) , montrer que

   \[ \begin{align} \left\lVert P(x^{n+1})\right\rVert \leq \gamma \left\lVert P(x^n)\right\rVert + \frac{L \lambda^2}{2} \left\lVert P(x^n)\right\rVert ^2 \end{align} \]

   (80)

3. On note \( (\delta^n)\) la suite de terme général \( \gamma+\frac{L \lambda^2}{2} \left\lVert P(x^n)\right\rVert \) . Déduire de (80) et de \( \delta^0<1\) que \( \delta^n\leq \delta^0\) pour tout \( n\) .

4. On note \( c_1=\frac{L \lambda^2 \left\lVert P(x^0)\right\rVert }{2 \gamma}\) . Montrer, en majorant \( \left\lVert P(x^n)\right\rVert \) que

   \[ \delta^n \leq \gamma \exp{(c_1 (\delta^0)^n)} \]

5. En déduire que

   \[ \left\lVert P(x^n)\right\rVert \leq \left\lVert P(x^0)\right\rVert \gamma^n \exp\left(\frac{c_1}{1-\delta^0}\right) \]
6. Montrer, en utilisant (iii), que la suite \( x^n\) est une suite de Cauchy. En déduire qu’elle converge vers \( x^*\) solution de (78).

7. On suppose désormais que \( P'\) est uniformément inversible si bien que il existe \( m>0\) tel que quels que soient \( x\) (localement), et \( y\) on a

   \[ \begin{align} \left\lVert P'(x) y\right\rVert \geq m \left\lVert y\right\rVert \end{align} \]

   (81)

   \[ \begin{align} \\\end{align} \]

   (82)

   Soit \( z\) tel que \( P'(x) z=P(x)\) , déduire de ce qui précède, avec \( Q(x)=\alpha z\) , avec \( 0<\alpha<2\) , que les hypothèses (ii) et (iii) sont vérifiées.

8. En déduire que si \( \left\lVert P(x^0)\right\rVert \) est suffisamment petite, alors la séquence

   \[ \begin{align}x^{n+1}=x^n-\alpha^n z^n, ~ z^n=P'(x^n)^{-1} P(x^n) \end{align} \]

   (83)

   \[ \begin{align} \\\end{align} \]

   (84)

   avec \( 0<\alpha_n<2\) converge.

9. En déduire, sous l’hypothèse supplémentaire précédente, par passage à la limite, l’existence d’une solution \( x^*\) de (78) et que

   \[ \left\lVert x^*-x^0\right\rVert \leq m \left\lVert P(x^0)\right\rVert \]

On considère maintenant une fonction régulière \( f:\mathbb{R}^n\rightarrow \mathbb{R}^m\) telle que son Jacobien est Lipschitzien de constante \( L\) et inversible avec la constante \( m\) . On veut montrer que l’ensemble \( F=\left\{ f(x) \text{ pour } x\in B(a,\epsilon)\right\}\) , avec \( B(a,\epsilon)=\left\{x \text{ tel que} \left\lVert x-a\right\rVert \leq \epsilon\right\}\) est un ensemble convexe pour tout \( a\) , pour \( \epsilon\) suffisamment petit.

Soient deux points \( x^1\) , \( x^2\) de \( B(a,\epsilon)\) et \( y^1\) , \( y^2\) de \( F\) leurs images par \( f\) . Soit \( y^0=\frac{1}{2}(y^1+y^2)\) . Pour montrer que \( F\) est convexe, il suffit de montrer que \( y^0\) appartient à \( F\) .

1. On note \( x^0=\frac{1}{2}(x^1+x^2)\) . Montrer que

   \[ y^i=f(x^0)+f'(x^0)(x^i-x^0)+\epsilon_i, ~ i=1, 2 \]

   avec

   \[ \left\lVert \epsilon_i\right\rVert \leq \frac{L}{8} \left\lVert x^1-x^2\right\rVert ^2 \]

2. Montrer que

   \[ y^0=f(x^0)+\epsilon^0, ~ \left\lVert \epsilon^0\right\rVert \leq \frac{L}{8} \left\lVert x^1-x^2\right\rVert ^2 \]

3. La fonction \( x\mapsto f(x)-y^0\) est telle que son Jacobien est Lipschitzien de constante \( L\) et inversible avec la constante \( m\) . En déduire, d’après la première partie de l’exercice, que si \( \epsilon\) est suffisamment petit, alors il existe \( x^*\) tel que \( f(x^*)=y^0\) et tel que

   \[ \left\lVert x^*-x^0\right\rVert \leq m \left\lVert f(x^0)-y^0\right\rVert \]
4. Montrer alors que pour \( \epsilon\) suffisamment petit, \( x^*\in B(a,\epsilon)\) .
5. Conclure que l’image par \( f\) de toute boule de taille \( \epsilon\) est convexe pour \( \epsilon\) suffisamment petit.

Application: On considère \( f(x)=\left(\begin{array}{c} x_1 x_2-x_1 \\ x_1x_2+x_2 \end{array}\right)\) .

1. Montrer que l’image par \( f\) de la boule \( B(0,\epsilon)\) est convexe pour \( \epsilon\) suffisamment petit (un calcul plus avancé montre que \( \epsilon \leq \frac{1}{2\sqrt{2}}\) est suffisant). La situation est illustrée en figure 6.

On s’intéresse ici à un système linéaire

où l’état \( x \in \mathbb{R}^n\) et la commande \( u \in \mathbb{R}^m\) . On considère le coût suivant avec pondération

où \( R\) est symétrique positive et \( Q\) est symétrique définie positive.

On ajoute à l’objectif de minimiser ce critère quadratique une contrainte finale

On se propose de déterminer la loi de commande solution à ce problème par deux méthodes différentes.

1. Formuler le problème aux deux bouts associé (où la commande n’apparaît plus). Justifier que ce problème a au plus une solution.

2. Méthode de balayage. Cette méthode consiste à ramener les conditions limites du poblème au même point. En notant \( \nu\) le multiplicateur associé à la contrainte finale, on se propose de chercher les adjoints et multiplicateurs sous la forme

   \[ \begin{align}\lambda(t) =& S(t) x(t) + V(t) \nu \end{align} \]

   (86)

   \[ \begin{align} x_f =& V^T(t) x(t) + H(t) \nu\end{align} \]

   (87)

1. Montrer que

   \[ \begin{align}V(t_f) = I \,, ~ H(t_f) = 0 ~ et ~ S(t_f) = 0\end{align} \]

   (88)

2. Montrer que

   \[ \begin{align}\dot S(t) =& -S(t) A(t) - A^T(t) S(t) + S(t)B(t) Q^{-1}B^T(t) S(t) - R \end{align} \]

   (89)

   \[ \begin{align} \dot V(t) =& - (A^T(t) - S(t) B(t) Q^{-1}B^T(t))V\end{align} \]

   (90)

3. Montrer enfin que

   \[ \begin{align}\dot H(t) = V^T(t) B(t) Q^{-1}B^T(t) V(t)\end{align} \]

   (91)

4. Exprimer la commande optimale en fonction de \( S,V\) et \( H\) .
3. Equation d’HJB. Il est possible ici de résoudre l’équation d’Hamilton-Jacobi-Bellman en cherchant une solution sous une certaine forme quadratique.
1. Expliciter l’équation HJB associée au problème considéré.

2. On cherche la fonction de retour optimal sous la forme

   \[ \begin{align*}\mathcal{I}(x,t) = \frac{1}{2}x^T S(t) x + x^T V(t) \nu + \frac{1}{2} \nu^T H(t) \nu - x_f^T \nu\end{align*} \]

   Retrouver les équations (88)–(91) en résolvant l’équation précédente.

4. On considère maintenant un système dynamique de dimension \( n=2\)

   \[ \begin{align*}\dot x(t) =& \left( \begin{array}{cc} 0 & 1 \\ -1/2 & 0 \end{array}\right) x(t)+ \left( \begin{array}{c} 0\\ 1 \end{array}\right) u(t)\end{align*} \]

   On souhaite calculer une commande \( t\in [0,3] \mapsto u(t)\) transférant le système de \( x_0 = [-0.5   1]^T\) à \( x_f = [-1   0]^T\) en minimisant le critère quadratique (85) avec \( R = I\) . On résout numériquement les équations obtenues précédemment pour deux réglages : \( Q = 1\) et \( Q = 1000\) . Associer ces réglages aux équations de la Figure 7.

On s’intéresse à la dynamique d’un véhicule équipé d’un moteur à courant continu dont on cherche à le faire parcourir une distance \( D\) en un temps donné \( T\) en minimisant l’énergie consommée, sous contraintes de vitesse initiale et finale nulles. Ce problème de contrôle optimal s’écrit ainsi

où \( x,v\) sont respectivement la position et vitesse du centre de masse du véhicule, \( u\) est le pourcentage utilisé du couple maximal fourni par le moteur, \( a_i, b_i\) (\( i = 0,...,2\) ) sont des constantes positives et \( \gamma\) une fonction réelle telles que :

• \( b_1 u(t)v(t) + b_2 u(t)^2\) représente la puissance instantanée du moteur
• \( a_1 u\) est le couple de traction des roues
• \( a_2 v^2\) le couple de frottement aérodynamique
• \( a_0\) représente le couple de roulement
• \( \gamma(x)\) la force de pesanteur, dépendant de la pente de la route et donc de la position

1. Écrire les équations du problème aux deux correspondant (où la commande n’intervient plus).
2. Montrer que \( v\) et \( u\) peuvent s’exprimer comme des fonctions de \( x,\dot x\) et \( \ddot x\) .
3. En utilisant le fait que \( \frac{\partial H}{\partial u} = 0\) pour tout \( t\in [0,T]\) , montrer que les deux états adjoints \( \lambda_1\) et \( \lambda_2\) s’écrivent également comme des fonctions de \( x,\dot x\) et \( \ddot x\) .

4. A partir de cette même condition de stationnarité, déduire que \( x\) satisfait

   \[ \begin{align}&A x^{(4)} + B(\dot x) x^{(3)} + C (x,\dot x, \ddot x) \ddot x + D(x,\dot x, \ddot x, x^{(3)}) \dot x - a_1 \lambda_2(x,\dot x,\ddot x) \dot \gamma(x) = 0 \end{align} \]

   (94)

   \[ \begin{align} &x(0) = \dot x(0) = \dot x(T) = 0 \,, ~ x(T) = D \end{align} \]

   (95)

   \[ \begin{align} \\\end{align} \]

   (96)

5. On considère que la route est horizontale, auquel cas \( \gamma = 0\) , et que les effets aérodynamiques sont négligeables, c.a.d. \( a_2 = 0\) . Comment se simplifie la dynamique (94) dans ce cas ? En déduire la commande optimale correspondante.

Un problème de programmation linéaire s’écrit (canoniquement) sous la forme

où \( c\in \mathbb{R}^n\) , et pour \( i=1,...,m>n\) , \( a_i \in \mathbb{R}^n\) , \( b_i \in \mathbb{R}\) . On s’intéresse dans cet exercice à un problème plus général, où chaque contrainte \( i\) est définie par des ensembles \( E_i\) et \( F_i\) pour \( i=1,...,m>n\) ,

Les ensembles \( F_i\) et \( E_i\) sont polyhédraux (supposés non vides), c.-à-d.

avec \( D_i\) une matrice \( k_i\times n\) , et \( d_i\in \mathbb{R}^{k_i}\) avec \( k_i> 1\) et \( \gamma_i< \mu_i\) . On cherche à montrer que le problème (98) est bien un problème du type (97) et à en trouver l’expression.

1. Montrer que pour tout \( i\) , l’ensemble \( E_i\) est convexe.

2. Montrer que (98) est équivalent au problème

   \[ \begin{equation} \begin{aligned} &\min_{x} c^T x\\ & t.q. ~ \begin{aligned} a_i^Tx \leq \gamma_i, ~ a_i \in E_i, ~ i=1,...,m \end{aligned} \end{aligned} \end{equation} \]

   (99)

3. Ré-écrire les contraintes de (99) en utilisant le problème auxiliaire

   \[ \begin{equation} \begin{aligned} & \max_{a_i} a_i^Tx \\ & t.q. ~ \begin{aligned} D_i a_i \leq d_i \end{aligned} \end{aligned} \end{equation} \]

   (100)

4. On va considérer le problème dual de (100). Former le Lagrangien \( {\mathcal L} (a_i,\lambda)\) de (100). Calculer \( \sup_{\lambda \geq 0}{\mathcal L}\) , en distinguant le cas \( D_i a_i\leq d_i\) et son complémentaire. De même, calculer \( \inf_{a_i} {\mathcal L}\) . Utiliser l’égalité du point selle. En supposant que \( \inf\) et \( \sup\) sont atteints, montrer que le problème dual de (100) s’écrit

   \[ \begin{equation} \begin{aligned} &\min_{\lambda\geq 0} d_i^T \lambda\\ & t.q. ~ \begin{aligned} D_i^T \lambda = x \end{aligned} \end{aligned} \end{equation} \]

   (101)

5. En utilisant cette formulation duale, montrer que la résolution de (99) revient à la résolution de

   \[ \begin{equation} \begin{aligned} &\min_{x} c^T x\\ & \left\{\begin{aligned} &\min_{\lambda_i\geq 0} \lambda_i^Td_i \\ & D_i^T \lambda_i = x \end{aligned} \right\} \leq \gamma_i ~ ~ i=1,...,m\end{aligned} \end{equation} \]

   (102)

6. Conclure que le problème (98) est équivalent au problème de programmation linéaire suivant

   \[ \begin{equation} \begin{aligned} &\min_{x,(\lambda_i)_{i=1,...,m}} c^T x\\ & \left\{\begin{aligned} \lambda_i^Td_i \leq \gamma_i, ~ &~ i=1,...,m,\\ D_i^T \lambda_i =x ~ &~ i=1,...,m,\\ \lambda_i\geq 0 ~ &~ i=1,...,m \end{aligned} \right.\end{aligned} \end{equation} \]

   (103)

Soit \( A\) une matrice à inverser de taille \( n\) . Soit \( A_0\) une matrice dont on connait l’inverse (par exemple l’identité). On considère les matrice \( A_iĀ_{i-1}+(A-A_{i-1})\, e_i e_i^T\) pour \( i=1,...,n\) où \( e_i\) est le \( i\) -ème vecteur de base. Montrer que \( AĀ_n\) . Appliquer \( n\) fois la formule de Sherman-Morrison-Woodbury pour en calculer l’inverse.

Notes

[1] J. Nocedal and S. J. Wright Numerical Optimization Springer 1999 Springer Series in Operations Research

[2] M. Minoux Programmation Mathématique. Théorie et algorithmes Dunod 1983 1, 2

[3] User's Guide for NPSOL 5.0: A Fortran Package for Nonlinear Programming P. E. Gill and W. Murray and M. A. Saunders and M. A. Wright Systems Optimization Laboratory Stanford University, Stanford, CA 94305 1998

[4] P. E. Gill and W. Murray and M. A. Saunders R. Bulirsch and D. Kraft Large-scale SQP Methods and their Application in Trajectory Optimization 1 Birkhäuser Verlag 1994

[5] V. M. Tikhomirov Stories about Maxima and Minima American Mathematical Society 1990 Mathematical World. Volume 1

[6] W. H. Press and B. P. Flanerry and S. A. Teukolsky and W. T. Vetterling Numerical Recipes: The Art of Scientific Computing New York:Cambridge University Press 1986

[7] F. Bonnans The Shooting Algorithm for Optimal Control Problems: A Review of Some Theoretical and Numerical Aspects INRIA 2002 Notes de cours, http://www-rocq.inria.fr/sydoco/cours/tutorial.html

[8] S. M. Roberts and J. S. Shipman Two-point boundary value problems: shooting methods American Elsevier 1972

[9] L. Pontryagin and et al. Théorie Mathématique de Processus Optimaux Editions Mir, Moscou 1974

[10] Mathworks Optimization Toolbox The Math Works Inc. 2002 User's guide, http://www.mathworks.com

[11] S. P. Banks and K. Dinesh Approximate Optimal Control and Stability of Nonlinear Finite- and Infinite-Dimensional Systems Annals of Operations Research 2000 98 1 19–44 10.1023/A:1019279617898

[12] J. R. Leigh Functional analysis and linear control theory Academic Press Inc. 1980

[13] B. T. Polyak Convexity of nonlinear image of a small ball with applications to optimization Set-Valued Analysis 2001 9 1-2 159–168

[14] J. J. Mor‚ and S. J. Wright Optimization Software guide SIAM 1993 Frontiers in Applied Mathematics

[15] D. P. Bertsekas Nonlinear programming Athena Scientific 1999 2

[16] J.-B. Hiriart-Urruty Optimisation et analyse convexe Presses Universitaires de France 1998

[17] S. Boyd and L. Vandenberghe Convex optimization Cambridge University Press 2004

[18] E. Polak Optimization - Algorithms and Consistent Approximations Springer-Verlag 1998

[19] D. G. Luenberger Optimization by vector spaces methods Wiley 1969

[20] I. M. Gelfand and S. V. Fomin Calculus of variations Dover 2000

[21] A. E. Bryson and Y. C. Ho Applied Optimal Control Ginn and Company 1969

[22] A. E. Bryson Dynamic Optimization Addison-Wesley 1999

[23] A. R. Forsyth Calculus of variations Cambridge at the University Press 1927

[24] L. V. Kantorovich and V. I. Krylov Approximate methods of higher analysis Interscience Publishers, Inc. - New York 1964

[25] H. J. Sussmann and J. C. Willems 300 years of optimal control: from the brachystochrone to the maximum principle IEEE 1997 32–44 disponible sur https://sites.math.rutgers.edu/ sussmann/

[26] A. D. Aleksandrov and A. N. Kolmogorov and M. A. Lavrent'ev Mathematics. Its contents, methods and meaning The M. I. T. Press 1969

[27] R. Courant and D. Hilbert Methods of Mathematical Physics Interscience 1962 2

[28] L. P. Lebedev and M. J. Cloud The calculus of variations and functional analysis World Scientific Publishing Co. 2003 12 Series on stability, vibration and control of systems

[29] G. Allaire Analyse numérique et optimisation. Cours de l'École Polytechnique École Polytechnique 2004

[30] D. P. Bertsekas Dynamic Programming and Optimal Control Athena Scientific 2001 1, 2 2

[31] S. E. Dreyfus and A. M. Law The art and theory of dynamic programming Academic Press 1977

[32] J.-Ch. Culioli Introduction à l'optimisation Ellipses 1994