\documentclass{article}
\usepackage{titling}
\author{Laura \textsc{Gay}}
\include{preambule}

\newboxedtheorem{defi}{Définition}{compteur1}
\newboxedtheorem{prop}{Proposition}{}
\newboxedtheorem{lem}{Lemme}{}
\newboxedtheorem{coro}{Corollaire}{compteur3}
\newboxedtheorem{thm}{Théorème}{}
\newboxedtheorem{exe}{Exemple}{compteur5}


\renewenvironment{proof}[1][]{{\underline{\bfseries \proofname #1 :}\\ }}{\hfill $\blacksquare$\\}
\newcommand{\I}{\text{I}}

\begin{document}

\newcommand*{\sca}[1]{\langle #1  \rangle} %produit scalaire
\newcommand*{\scal}[2]{\langle #1 , #2 \rangle} %produit scalaire
\renewcommand{\proofname}{Preuve}

\begin{spacing}{2}
\setlength {\shadowsize }{2pt}
\begin{center} \shadowbox{\begin{minipage}{15cm}
\centering     \begin{huge} 
\textsc{Algorithme du gradient à pas optimal}\end{huge}
\end{minipage}} \end{center}\end{spacing}
~\\



\underline{Référence :} \textsc{Hiriart-Urruty} Optimisation et analyse convexe exercice II.8. p.52 et \textsc{FGNal3}\\
\underline{Leçons :} 162,232,233 \\

\begin{lem}[Inégalité de Kantorovitch]
Soit $A \in \mathcal S_n^{++}(\mathbb R)$ de valeurs propres minimale et maximale $\lambda_{\min}$ et $\lambda_{\max}$. Alors en posant $c(A):=\frac{\lambda_{\min}}{\lambda_{\max}}$ le conditionnement de $A$, 
$$\forall x \in \mathbb R, \quad \frac{\Vert x \Vert^4}{\sca{Ax,x}\sca{A^{-1}x,x}}\geqslant 4 \left(\sqrt{\frac{\lambda_{\max}}{\lambda_{\min}}} +\sqrt{\frac{\lambda_{\min}}{\lambda_{\max}}}\right)^{-2}=4\frac{c(A)}{(c(A)+1)^2}$$
 \end{lem}
\begin{proof}
Il suffit de montrer cette inégalité pour $x$ de norme 1, ce qu'on supposera dans la suite. $A$ est symétrique donc il existe une base $(e_1,\cdots,e_n)$ orthonormale de vecteurs propres de $A$. On note $x=\sum x_i e_i$ et $0<\lambda_1 \leqslant \cdots \leqslant \lambda_n$ les valeurs propres de $A$.
\begin{align*}
 \scal{Ax}{x} \scal{A^{-1}x}{x} &= \sum_{i=1}^n \lambda_i x_i^2 \sum_{i=1}^n \frac{1}{\lambda_i} x_i^2  
= \frac{\lambda_1}{\lambda_n} \sum_{i=1}^n \frac{\lambda_i}{\lambda_n} x_i^2 \sum_{i=1}^n \frac{\lambda_1}{\lambda_i} x_i^2  \\ & \leqslant \frac{\lambda_1}{4\lambda_n} \left( \sum_{i=1}^n \left( \frac{\lambda_i}{\lambda_n}+\frac{\lambda_1}{\lambda_i} \right) x_i^2 \right)^2.
\end{align*}
Après étude de la fonction $x \mapsto \frac{x}{\lambda_1}+\frac{\lambda_n}{x}$ qui atteint son maximum $1+\frac{\lambda_n}{\lambda_1}$ en $\lambda_1$ et en $\lambda_n$, on en déduit que
\begin{align*}
\scal{Ax}{x} \scal{A^{-1}x}{x} &\leqslant \frac{\lambda_1}{4\lambda_n}   \left( \left( 1+\frac{\lambda_n}{\lambda_1} \right) \sum_{i=1}^n x_i^2 \right)^2\\
&\leqslant \frac{\lambda_1}{4\lambda_n}   \left( 1+\frac{\lambda_n}{\lambda_1} \right)^2\\
&\leqslant \frac{\lambda_1}{4\lambda_n}\left( 1+2\frac{\lambda_n}{\lambda_1}+\frac{\lambda_n^2}{\lambda_1^2} \right)\\
&\leqslant \frac14 \left( \frac{\lambda_1}{\lambda_n}+2+\frac{\lambda_n}{\lambda_1} \right)\\
&\leqslant \frac14 \left( \sqrt{\frac{\lambda_1}{\lambda_n}} + \sqrt{\frac{\lambda_n}{\lambda_1}} \right)^2
\end{align*}
Il suffit d'inverser cette formule pour obtenir l'inégalité escomptée.

\end{proof}
\begin{thm}
\textbf{Problème:} Soit $A \in \mathcal{S}_n^++(\R)$ et $b \in \R^n$. On cherche à minimiser $f:x \mapsto \frac 12 \sca{Ax,x} + \sca{b,x}$ quand\footnote{On enlève le $c$ du livre qui n'apporte rien} $x$ parcourt $\R^n$. \\
Il existe une unique solution à ce problème, caractérisée par $\nabla f (\bar x)=0$.\\
De plus, l'algorithme défini par: $x_0 \in \R^n$ et pour $k \geq 0$ :
\begin{align*}
  \begin{cases}
d_k= - \nabla f (x_k)=-Ax_k - b\\
x_{k+1}=x_k+t_kd_k \end{cases}
\end{align*}
où $t_k$ est l'unique réel (positif) minimisant $g:t \mapsto f(x_k+td_k)$ sur $\R$\\
converge vers $\bar x$.
\end{thm}
\begin{proof}
\begin{description}
\item[Conditions de minimalité] (question 1)\\
Soit $\bar x$ un point minimal, alors $\nabla f(\bar x)=0$.\\
Or
\begin{align*}
f(x+h) &= \frac12 \sca{A(x+h),x+h}+\sca{b,x+h}\\
&=\frac12 \sca{Ax,x}+\sca{b,x} + \frac12 \left(\sca{Ax,h} + \sca{Ah,x} \right) + \sca{b,h} + \frac12 \sca{Ah,h}\\
&=\frac12 f(x) +\sca{Ax,h} + \sca{b,h} + \frac12 \sca{Ah,h}\text{~~~~~~~~car $A$ symétrique}\\
&=\frac12 f(x) +\sca{Ax+b,h} + o(\norm{h})
\end{align*}
Donc $\nabla f (x)= Ax+b$ et donc $\bar x = - A^{-1}b$.\\
Minimiser $f$ revient à inverser une matrice, de manière peut-être plus efficace.\\
D'autre part, 
\begin{align*}
\bar f := \min_{x \in \R^n} f(x)&=f(\bar x)= \frac12 \sca{A \bar x, \bar x} + \sca{b,x}\\
&=\frac12 \sca{A \bar x, \bar x} + \sca{-A \bar x, \bar x} \\
&=-\frac12 \sca{A \bar x, \bar x}  \\
&=-\frac12 \sca{A (-A^{-1}b), -A^{-1}b}  \\
&=-\frac12 \sca{-b, -A^{-1}b}  \\
&=-\frac12 \sca{A^{-1}b,b}  \\
\end{align*} 
De plus, $\bar x$ est bien le minimum car $f$ est strictement convexe\footnote{car la matrice hessienne de $f$ est $A$ qui est définie positive.}, coercive\footnote{\begin{align*}
\abs{f(x)}&\geq \frac12 \abs{\sca{Ax,x}}-\abs{\sca{b,x}}\\
&\geq \frac12 \lambda_{\min} \norm{x}^2-\norm{b}\norm{x} \\
&\underset{\norm{x} \rightarrow \infty}{\longrightarrow} \infty
\end{align*}} sur $\R^n$ donc il existe un unique minimum pour $f$.\\
Dans toute la suite de la preuve, on suppose $d_k \neq 0$ car sinon $Ax_k=-b$ et l'algorithme converge en temps fini.\\

\item[Calcul de $t_k$] (question 2)
\begin{align*}
g(t)=f(x_k+td_k) &=\frac 12 \sca{A(x_k+td_k),x_k+td_k} + \sca{b,x_k+td_k}\\
&=\frac 12 \sca{Ax_k,x_k}+ \frac 12 \sca{Atd_k,x_k} +\frac 12 \sca{Ax_k,td_k}+ \frac 12 \sca{Atd_k,td_k} + \sca{b,x_k}+\sca{b,td_k}\\
&=f(x_k)+\sca{\underbrace{Ax_k + b}_{-d_k},td_k} + \frac12\sca{Atd_k,td_k}\\
&=f(x_k)-t \norm{d_k}^2 + \frac12 t^2\sca{Ad_k,d_k}
\end{align*}
Donc $g'(t)=-\norm{d_k}^2+t\sca{Ad_k,d_k}$ et $g'(t)=0$ $\Leftrightarrow$ $t=t_k=\frac{\norm{d_k}^2}{\sca{Ad_k,d_k}}>0$ (on peut diviser par $\sca{Ad_k,d_k}$ car $d_k \neq 0$ et $A$ définie positive).\\
\item[Calcul de l'erreur sur $f(x_k)-\bar f$] (questions 2 et 3)
\begin{align*}
f(x_{k+1})=f(x_k+t_kd_k) &=f(x_k)- \frac{\norm{d_k}^2}{\sca{Ad_k,d_k}}\norm{d_k}^2 + \frac12 \frac{\norm{d_k}^4}{\sca{Ad_k,d_k}^2}\sca{Ad_k,d_k}\\
&=f(x_k)- \frac{\norm{d_k}^4}{\sca{Ad_k,d_k}} + \frac12 \frac{\norm{d_k}^4}{\sca{Ad_k,d_k}}\\
&=f(x_k) - \frac12 \frac{\norm{d_k}^4}{\sca{Ad_k,d_k}}
\end{align*}
Donc
$$
f(x_{k+1})-\bar f =f(x_k) -\bar f- \frac12 \frac{\norm{d_k}^4}{\sca{Ad_k,d_k}} =\left(f(x_k) -\bar f \right)\left(1- \frac{\norm{d_k}^4}{2\sca{Ad_k,d_k}\left(f(x_k) -\bar f \right)}\right)$$
Or : 
\begin{align*}
\sca{A^{-1}d_k,d_k} &= \sca{A^{-1}(Ax_k + b),Ax_k + b}\\
&= \sca{x_k + A^{-1}b,Ax_k + b}\\
&= \sca{x_k,Ax_k}+\sca{x_k,b}+\underbrace{\sca{A^{-1}b,Ax_k}}_{\sca{b,x_k}}+\underbrace{\sca{A^{-1}b,b}}_{-2\bar f}\\
&=2 \left( \underbrace{\frac12 \sca{x_k,Ax_k} + \sca{x_k,b}}_{f(x_k)} - \bar f \right)=2 \left( {f(x_k)} - \bar f \right)
\end{align*}
Donc finalement 
$$f(x_{k+1})-\bar f = \left(f(x_k) -\bar f \right)\left(1- \frac{\norm{d_k}^4}{\sca{Ad_k,d_k}\sca{A^{-1}d_k,d_k}}\right) $$
L'inégalité de Kantorovitch donne, 
$$\frac{\Vert d_k \Vert^4}{\sca{Ad_k,d_k}\sca{A^{-1}d_k,d_k}}\geqslant 4\frac{c(A)}{(c(A)+1)^2}$$
Donc 
$$f(x_{k+1})-\bar f \leq \left(f(x_k) -\bar f \right)\left( \frac{c(A)-1}{c(A)+1}\right)^2 \leq \cdots \leq \left(f(x_0) -\bar f \right)\left( \frac{c(A)-1}{c(A)+1}\right)^{2k}$$
\item[Calcul de l'erreur sur $\norm{x_k-\bar x}$] (question 3)\\
Par ailleurs, on a
\begin{align*}
\sca{A(x_k-\bar x),x_k-\bar x}&=\sca{Ax_k,x_k-\bar x}- \sca{A \bar x , x_k - \bar x}\\
&=\sca{Ax_k,x_k}-\sca{Ax_k,\bar x}- \sca{A \bar x , x_k}+ \sca{A \bar x , \bar x}\\
&=\sca{Ax_k,x_k}+\sca{Ax_k,A^{-1}b}+ \sca{A A^{-1}b , x_k}+ \sca{A A^{-1}b , A^{-1}b}\\
&=\underbrace{\sca{Ax_k,x_k}+\sca{x_k,b}+ \sca{b , x_k}}_{2f(x_k)}+ \underbrace{\sca{b , A^{-1}b}}_{-2 \bar f}
\end{align*}
Donc
$$
f(x_k)-\bar f = \frac12 \sca{A(x_k-\bar x),x_k-\bar x} \geq \frac12 \lambda_{\min} \norm{x_k-\bar x}^2 $$
Et finalement
$$\norm{x_k-\bar x}\leq \sqrt{\frac{2\left(f(x_0) -\bar f \right)}{\lambda_{\min}}}  \left( \frac{c(A)-1}{c(A)+1}\right)^{k}$$
\end{description}
Donc $x_k \underset{n \rightarrow +\infty}{\longrightarrow} \bar x$.
\end{proof}
~\\
\vspace{2cm}
\hrulefill \\
~\\
\underline{Notes:}\\
~\\ 
\checkmark ~\textbf{A l'oral}, on ne fait pas Kantorovitch. 14'36 allure normale (énoncer Kanto avec le conditionnement!)\\
\checkmark ~Lorsque $n=2$ $x_k$ converge en zigzags vers $\bar x$.\\
\checkmark ~Plus $c(A)$ est proche de 1, plus la méthode converge rapidement. A l'inverse lorsque $c(A)$ est loin de 1, la méthode est très lente.\\
Le cas limite serait celui où $c(A)=1$ (donc $A$ homothétie), ce qui suppose $2(f(x)-\bar f)=\lambda\norm{x-\bar x}^2$ auquel cas on atteint $\bar x$ dès la première itération. En effet, $d_0=-Ax_0-b=-\lambda x_0+\lambda \bar x$, donc $t_0=\frac{1}{\lambda}$ et on obtient bien $x_1=\bar x$ (ou sinon on utilise la dernière majoration...).


\end{document}