\usefonttheme{professionalfonts}
-
% Setup appearance:
%\usetheme{Warsaw}
\usetheme{Darmstadt}
\definecolor{mycvblue}{rgb}{0.302,0.537,0.737}
-
\setbeamercolor{structure}{fg=mycvblue}
\setbeamercolor{palette primary}{fg=mycvblue}
\setbeamercolor{subsection in head/foot}{parent=palette primary}
%\renewcommand{\item}{\item[$\bullet$]}
-
-
\title[]{\LARGE{\textsc{Méthode de Programmation Quadratique Séquentielle ou PQS\\ en\\ Optimisation non linéraire sous contraintes}}}
\author[Jérôme {\textsc Benoit} \& Sylvain {\textsc Papa}]{\textbf{Jérôme {\textsc Benoit}\\ \textbf{Sylvain {\textsc Papa}}}}
\newcommand{\chch}{{C}hudnovsky-{C}hudnovsky}
\newcommand{\ch}{{C}hudnovsky}
-
-
\addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}}
% \AtBeginSubsection[] {
\section{Introduction}
-\subsection{Principe général}
+\subsection{Définition de la problèmatique}
%%%%% SLIDE 1
-\begin{frame}{Principe général I}
+\begin{frame}{Définition de la problèmatique}
\begin{defin}
Résoudre le problème $ \mathcal{P} $ :
$$
\end{array}
\right .
$$
- où $$ g: \mathbb{R}^n \longrightarrow \mathbb{R}^p,\ h: \mathbb{R}^n \longrightarrow \mathbb{R}^q\ et\ J: \mathbb{R}^n \longrightarrow \mathbb{R}\ de\ classe\ \mathcal{C}^2. $$
+ où
+ \begin{center}
+ $ g: \mathbb{R}^n \longrightarrow \mathbb{R}^p $ représente les contraintes d'inégalité,
+ \end{center}
+ \begin{center}
+ $ h: \mathbb{R}^n \longrightarrow \mathbb{R}^q $ représente les contraintes d'égalité,
+ \end{center}
+ et
+ \begin{center}
+ $ J: \mathbb{R}^n \longrightarrow \mathbb{R} $ est la fonction objectif ou coût.
+ \end{center}
+ en utilisant des méthodes numériques itératives.
+ \newline
+ On définit $ \mathcal{C} $ l'ensemble des contraintes par :
+ $$ \mathcal{C} = \left \{ x \in \mathbb{R}^n \ | \ g(x) \leq 0 \land h(x) = 0 \right \} $$
\end{defin}
\end{frame}
-%%%%% SLIDE 1
-\begin{frame}{Principe général II}
- \begin{enumerate}
- \item Conditions nécessaires et suffisantes d'existence et d'unicité d'une solution (\textit{KKT}, $ H[J] $ définie positive et convexité de $ \mathcal{P} $).
- \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) $$
- \end{enumerate}
+\subsection{Prérequis mathématiques}
+
+%%%%% SLIDE 2
+\begin{frame}{Prérequis mathématiques I}
+ \begin{defin}
+ On définit le Lagrangien associé à $ \mathcal{P} $ par :
+ $$ \begin{array}{r c l}
+ L : \mathbb{R}^n \times \mathbb{R}^q \times \mathbb{R}_+^p & \longrightarrow & \mathbb{R} \\
+ (x,\lambda,\mu) & \longmapsto & L(x,\lambda,\mu) = J(x) + \sum\limits_{i=1}^{q} \lambda_i h_i(x) + \sum\limits_{j=1}^{p} \mu_j g_j(x) \\
+ & & L(x,\lambda,\mu) = J(x) + \langle \lambda,h(x) \rangle_{\mathbb{R}^q} + \langle \mu,g(x) \rangle_{\mathbb{R}^p}
+ \end{array} $$
+ où l’on note $ \lambda $ et $ \mu $ les vecteurs de coordonnées respectives $ (\lambda_1,\ldots,\lambda_q) $ et $ (\mu_1,\ldots,\mu_p) $.
+ \end{defin}
+ \begin{defin}
+ Soit une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ différentiable.
+ \newline
+ Le gradient de $ f $, noté $\nabla f$, en $ x^\ast \in \mathbb{R}^n$ se définit par :
+ \[
+ \nabla f(x^\ast) = (\frac{\partial f}{\partial x_1}(x^\ast),\ldots,\frac{\partial f}{\partial x_n}(x^\ast))
+ \]
+ \end{defin}
\end{frame}
%%%%% SLIDE 3
-\begin{frame}{Principe général III}
- Conditions d'optimalité sur le Lagrangien $ L $ de $ \mathcal{P} $ :
- \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{frame}{Prérequis mathématiques II : Conditions nécessaires d'optimalité de Karuch-Kuhn-Tucker ou \textit{KKT}}
+ \begin{theoreme}
+ Soient $ J, g, h $ de classe $ \mathcal{C}^1 $, $ x^\ast \in \mathbb{R}^n $, $ I = \{ 1,\ldots,p \} $ et $ J = \{ 1,\ldots,q \} $.
+ \newline
+ Les conditions nécessaires pour que $ x^\ast \in \mathcal{C}$ soit un minimum local de $ J $ sont :
+ \begin{center}
+ $ \{ \nabla g_1(x^\ast),\ldots,\nabla g_p(x^\ast),\nabla h_1(x^\ast),\ldots,\nabla h_q(x^\ast) \} $ sont linéairement indépendants.
+ \end{center}
+ et
+ \begin{center}
+ $ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} $ tels que :
+ \end{center}
+ \begin{center}
+ $ \nabla J(x^\ast) + \sum\limits_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum\limits_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $
+ \end{center}
+ \begin{center}
+ $ \iff \nabla L(x^\ast,\lambda,\mu) = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $ où $ \lambda = (\lambda_1,\ldots,\lambda_q) $ et $ \mu = (\mu_1,\ldots,\mu_p) $.
+ \end{center}
+ On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
+ \newline
+ On nomme également les conditions \textit{KTT} conditions nécessaires d'optimalité du premier ordre.
+ \end{theoreme}
\end{frame}
-\section{Algorithme PQS}
-
%%%%% SLIDE 4
+\begin{frame}{Prérequis mathématiques II : Conditions suffisantes d'optimalité}
+\end{frame}
+
+\section{Méthode PQS}
+
+\subsection{Algorithme PQS}
+
+%%%%% SLIDE 5
\begin{frame}{Algorithme PQS}
\begin{block}{ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ.}
\textit{Entrées}: $ J : \mathbb{R}^n \longrightarrow \mathbb{R} $, $g: \mathbb{R}^n \longrightarrow \mathbb{R}^p$, $ h : \mathbb{R}^n \longrightarrow \mathbb{R}^q $ différentiables, $ x_0 \in \mathbb{R}^n $ point initial arbitraire, $ \lambda_0 \in \mathbb{R}_+^p $ et $ \mu_0 \in \mathbb{R}_+^q $ multiplicateurs initiaux, $ \varepsilon > 0 $ précision demandée.
\end{block}
\end{frame}
-% %%%%% 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). $$
+ Ce type de méthodes conduit 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 $ de $ \mathcal{PQ}_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}
%%%%% SLIDE DE FIN
repositories / Projet_Recherche_Operationnelle.git / blobdiff