-% %%%%% SLIDE 6
-% \begin{frame}
-%
-% \end{frame}
-%
-% \section{Algorithme de D.V. et G.V. Chudnovsky (1987)}
-%
-% \subsection{Avec des places rationnelles}
-%
-% %%%%% SLIDE 9
-% \begin{frame}{Algorithme original de Chudnovsky et Chudnovsky}
-%
-% \end{frame}
-%
-% \subsection{Principe}
-%
-% %%%%% SLIDE 8
-% \begin{frame}{Principe pour multiplier avec l'algorithme de Chudnovsky}
-%
-% \end{frame}
-%
-% \subsection{Avec des places de degré un et deux}
-%
-% %%%%% SLIDE 10
-% \begin{frame}{Evaluations sur des places de degré 1 et 2}
-%
-% \end{frame}
-%
-% \section{Conditions permettant l'utilisation de l'algorithme}
-%
-% \subsection{Conditions principales}
-%
-% %%%%% SLIDE 11
-% \begin{frame}{Conditions suffisantes pour appliquer l'algorithme}
-%
-% \end{frame}
-%
-% \subsection{Applications}
-%
-% %%%%% SLIDE 11
-% \begin{frame}{Le cas des extensions de petits degré}
-%
-% \end{frame}
-%
-% \begin{frame}{Algorithme de Chudnovsky sur un corps de fonctions hyperelliptique de genre 2}
-%
-% \end{frame}
-%
-%
-% \begin{frame}{Exemple pour les \textit{petites} extensions $\F_{16^n}$ de $\F_{16}$}
-%
-% \end{frame}
-%
-% \setbeamercovered{transparent}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
-%
-%
-% %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
-%
-%
-% %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
-%
-% \section{Nouveau résultats}
-%
-% \subsection{Bornes uniformes connues}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% \subsection{Nouvelles bornes uniformes}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% %%%%% SLIDE 14
-% \begin{frame}{Corps de fonctions sur $\F_{p^2}$}
-%
-% \end{frame}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% %%%%%%%%%%%%% T %%%%%%%%%%%%%%%
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% \begin{frame}
-%
-% \end{frame}
-%
-% \section{Conclusions et perspectives}
-%
-% \subsection{Problèmes et/ou travail en cours}
-%
-% %%%%% SLIDE 15
-%
-% \begin{frame}{Conclusion}
-%
-% \end{frame}
-%
-% \begin{frame}
-%
-% \end{frame}
+\subsection{La méthode PQS est une méthode de descente}
+
+%%%%% SLIDE 6
+\begin{frame}{Définition d'une méthode de descente}
+ \begin{defin}
+ Générer une suite d’itérés $ (x_k)_{k \in \mathbb{N}} $ de $ \mathbb{R}^n $ avec :
+ \begin{center}
+ $ x_0 \in \mathbb{R}^n $ arbitraire,
+ \end{center}
+ \begin{center}
+ $ x_{k+1} = x_k + s_kd_k $,
+ \end{center}
+ tel que :
+ $$ \forall k \in \mathbb{N} \ J(x_{k+1}) \leq J(x_k) $$
+ où
+ \begin{center}
+ $ s_k \in \mathbb{R}_{+}^{*} $ est le pas de descente
+ \end{center}
+ et
+ \begin{center}
+ $ d_k \in \mathbb{R}^n $ est la direction de descente.
+ \end{center}
+ \end{defin}
+\end{frame}
+
+%%%%% SLIDE 7
+\begin{frame}{Caractérisation d'une direction de descente}
+ \begin{proposition}
+ Soient $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable et $ d \in \mathbb{R}^n $.
+ \newline
+ d est un vecteur de descente de $ J $ en $ x_0 \in \mathbb{R}^n $ ssi :
+ $$ \nabla J(x_0)^\top d < 0 $$
+ De plus
+ $$ \forall \beta < 1 \in \mathbb{R}_{+} \ \exists \eta \in \mathbb{R}_{+}^{*} \ \forall t \in ]0,\eta] \ J(x_0 + td) < J(x_0) + t\beta \nabla J(x_0)^\top d < J(x_0) $$
+ \end{proposition}
+\end{frame}
+
+%%%%% SLIDE 8
+\begin{frame}{Algorithme de descente générique}
+ \begin{block}{ALGORITHME DE DESCENTE GÉNÉRIQUE.}
+ \textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable, $ x_0 \in \mathbb{R}^n $ point initial arbitraire.
+ \newline
+ \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème : $ \displaystyle\min_{x \in \mathbb{R}^n} J(x) $.
+ \begin{enumerate}
+ \item $ k := 0 $.
+ \item Tant que "test d’arrêt" non satisfait,
+ \begin{enumerate}
+ \item Trouver une direction de descente $ d_k $ telle que : $ \nabla J(x_k)^\top d_k < 0 $.
+ \item \textit{Recherche linéaire} : Choisir un pas $ s_k > 0 $ à faire dans cette direction et tel que : $$ J(x_k + s_kd_k) < J(x_k). $$
+ \item Mise à jour : $ x_{k+1} = x_k + s_kd_k; \ k := k + 1 $.
+ \end{enumerate}
+ \item Retourner $ x_k $.
+ \end{enumerate}
+ \end{block}
+\end{frame}
+
+%%%%% SLIDE 9
+\begin{frame}{Critère d'arrêt}
+ \begin{block}{}
+ \begin{center}
+ Critère d’arrêt $$ \parallel $$
+ \end{center}
+ \begin{tabular}{l l}
+ & Test d’optimalité satisfait ($\norme{\nabla J(x_k)} < \varepsilon$) \\
+ OU & (Stagnation de la valeur courante ($ \norme{x_{k+1} - x_k} < \varepsilon(1 + \norme{x_k}) $) \\
+ & ET Stagnation de la solution ($ |J(x_{k+1}) - J(x_k)| < \varepsilon(1 + |J (x_k)|) $)) \\
+ OU & Nombre d’itérations maximum autorisé dépassé ($ k < IterMax $)
+ \end{tabular}
+ \end{block}
+\end{frame}
+
+%%%%% SLIDE 10
+\begin{frame}{Recherche linéaire}
+ \begin{block}{RECHERCHE LINÉAIRE : PAS FIXE.}
+ $ s_k = s_{k-1} $
+ \end{block}
+ \begin{block}{RECHERCHE LINÉAIRE : PAS OPTIMAL.}
+ $ s_k $ solution du problème $ \displaystyle\min_{s \in \mathbb{R}_{+}^{*}} J(x_k + sd_k) $
+ \end{block}
+\end{frame}
+
+%%%%% SLIDE 11
+\begin{frame}{Application à l'algorithme PQS}
+ \begin{block}{Cas de l'algorithme PQS}
+ \begin{enumerate}
+ \item le critère d'arrêt est $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $;
+ \item le pas $ s_k $ est fixe tel que $ \forall k \in \mathbb{N} \ s_k = 1 $. Il est possible d'ajouter une étape de recherche linéaire d'un pas optimal;
+ \item la direction de descente $ d_k $ est une approximation de $ -H[J](x_k)^{-1} \nabla J(x_k) $.
+ \end{enumerate}
+ \end{block}
+\end{frame}
+
+\subsection{La méthode PQS est une méthode Newtonienne}
+
+%%%%% SLIDE 12
+\begin{frame}{Méthode Newtonienne I}
+ \begin{defin}
+ Une méthode de descente est dite Newtonienne si
+ $$ d_k = -H[J](x_k)^{-1} \nabla J(x_k). $$
+ Elles conduisent aux \textit{algorithmes Newtoniens}.
+ \end{defin}
+ La direction de descente $ d_k = -H[J](x_k)^{-1} \nabla J(x_k) $ est l'unique solution du problème :
+
+ $$ \underset{d \in \mathbb{R}^n}{\mathrm{argmin}} \ J(x_k) + \langle \nabla J(x_k),d \rangle + \frac{1}{2}\langle H[J](x_k)d,d \rangle $$
+
+ $ \iff d_k $ est le point de minimum global de l’approximation quadratique de $ J $ au voisinage du point courant $ x_k $.
+\end{frame}
+
+%%%%% SLIDE 13
+\begin{frame}{Méthode Newtonienne II}
+ \begin{tabular}{|p{15em}|p{15em}|}
+ \hline
+ Avantages & Inconvénients \\
+ \hline
+ sa convergence quadratique (le nombre de décimales exactes est multiplié par 2 à chaque itération). & \\
+ \hline
+ & les difficultés et le coût de calcul de la hessienne $ H[J](x_k) $ : l’expression analytique des dérivées secondes est rarement disponible dans les applications. \\
+ \hline
+ & le coût de résolution du système linéaire $ H[J](x_k )(x_{k+1} - x_k) = \nabla J(x_k) $. \\
+ \hline
+ & l’absence de convergence si le premier itéré est trop loin de la solution, ou si la hessienne est singulière. \\
+ \hline
+ & pas de distinction entre minima, maxima et points stationnaires. \\
+ \hline
+ \end{tabular}
+\end{frame}
+
+\subsection{Principe général de la méthode PQS}
+
+%%%%% SLIDE 14
+\begin{frame}{Principe général I}
+ Principe de résolution du problème $ \mathcal{P} $ en utilisant la méthode PQS :
+ \begin{enumerate}
+ \item Établir les conditions nécessaires et suffisantes d'existence et d'unicité d'une solution :
+ \begin{enumerate}
+ \item Conditions suffisantes \textit{KKT};
+ \item Conditions nécessaires $ H[J] $ définie positive;
+ \item Condition(s) de convexité de $ \mathcal{P} $.
+ \end{enumerate}
+ \item Approximation quadratique du Lagrangien $ L $ de $ \mathcal{P} $ par Taylor-Young à l'ordre 2 en $ x_k $:
+ $$ L(x,\lambda,\mu) \approx L(x_k,\lambda_k,\mu_k) + \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) $$
+ $$ + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
+ \item Approximation linéaire de $ g $ et $ h $ par Taylor-Young à l'ordre 1 en $ x_k $ :
+ $$ g(x) \approx g(x_k) + \nabla g(x_k)^\top(x - x_k) $$
+ $$ h(x) \approx h(x_k) + \nabla h(x_k)^\top(x - x_k) $$
+ \item Condition d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
+ $$ \nabla L(x_k,\lambda_k,\mu_k)^\top (x - x_k) + \frac{1}{2} (x - x_k)^\top H[L](x_k,\lambda_k,\mu_k) (x - x_k) $$
+ \end{enumerate}
+\end{frame}
+
+%%%%% SLIDE 15
+\begin{frame}{Principe général II}
+ \begin{block}{}
+ Résoudre le sous-problème quadratique $ \mathcal{PQ}_k $ avec contraintes linéaires :
+ $$
+ \mathcal{PQ}_k \left \{
+ \begin{array}{l}
+ \displaystyle\min_{d \in \mathbb{R}^n} \nabla J(x_k)^\top d + \frac{1}{2}d^\top H_k d \\
+ g_j(x_k) + \nabla g_j(x_k)^\top d \leq 0, \ \forall j \in \{1,\ldots,p\} \\
+ h_i(x_k) + \nabla h_i(x_k)^\top d = 0, \ \forall i \in \{1,\ldots,q\}
+ \end{array}
+ \right .
+ $$
+ où $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $ symétrique (Schwarz).
+ \end{block}
+ \begin{center}
+ $ \implies $ La solution $ d_k $ est la valeur optimale de direction de descente.
+ \end{center}
+\end{frame}
+
+\subsection{Optimisation quadratique sous contraintes linéaires}
+
+%%%%% SLIDE 16
+\begin{frame}{}
+ \begin{block}{ALGORITHME OPTIMAL}
+ \end{block}
+\end{frame}