From 3f5da2c3b157f1109cb1baa9b7b98a9c257222a6 Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 8 Nov 2018 23:13:05 +0100 Subject: [PATCH] First pass on the slides. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- .../Slides_ProjetOptimRO.tex" | 344 ++++++++++-------- rapport/ProjetOptimRO.tex | 2 +- 2 files changed, 202 insertions(+), 144 deletions(-) diff --git "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" index a7880f2..4f9d807 100644 --- "a/pr\303\251sentation/Slides_ProjetOptimRO.tex" +++ "b/pr\303\251sentation/Slides_ProjetOptimRO.tex" @@ -46,11 +46,10 @@ %\usepackage{MyMnSymbol} \usepackage{comment} %\usepackage{etex} -%usepackage{mathtools} +%\usepackage{mathtools} %\usepackage{fourier} \usepackage{ragged2e} -\justifying % Setup TikZ \usepackage{tikz} @@ -83,6 +82,7 @@ $}} \newcommand{\bluebrace}{{\color{blue}\left\{}} +\newcommand{\norme}[1]{\left\Vert #1 \right\Vert} \definecolor{mycvblue}{rgb}{0.302,0.537,0.737} @@ -104,13 +104,11 @@ $}} -\title[]{\LARGE{\textsc{Familles denses de courbes modulaires, nombres premiers\\ et \\rang de tenseur symétrique uniforme de la multiplication dans les corps finis}}} +\title[]{\LARGE{\textsc{Méthode de Programmation Quadratique Séquentielle ou PQS\\ en\\ Optimisation non linéraire sous contraintes}}} -\author[Alexey {\textsc Zykin}]{\textbf{Alexey {\textsc Zykin}$^{\dag}$} \\ (\textbf{1984 - 2017}) \\Laboratoire GAATI \\Université de la Polynésie Française\\ -{\small National Research University Higher School of Economics} \\ Institute for Information Transmission Problems of the Russian Academy of Sciences\\\vspace{1em}\textbf{\textcolor{mycvblue}{en collaboration avec}}\\ \vspace{1em} \textbf{Stéphane {\textsc Ballet}}\\ Equipe Arithmétique et Théorie de l'Information\\ Institut de Mathématiques de Marseille \\ Aix-Marseille Université} +\author[Jérôme {\textsc Benoit} \& Sylvain {\textsc Papa}]{\textbf{Jérôme {\textsc Benoit}\\ \textbf{Sylvain {\textsc Papa}}}} - -\date[]{\\ \vspace{2em} {\bf Séminaire GAATI}\\ {\bf UPF} \\{\small Avril 2017}} +\date[]{{\bf HUGo}\\ {\bf Polytech'Marseille} \\{\small Novembre 2018}} \newtheorem{defin}{Définition} \newtheorem{theoreme}{Théorème} @@ -145,19 +143,19 @@ $}} \addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}} -% -%\AtBeginSubsection[] { -%\begin{frame} -%\frametitle{Plan} -%\tableofcontents[currentsection,currentsubsection] -%\end{frame} -%} -%\AtBeginSection[] { -%\begin{frame} -%\frametitle{Plan} -%\tableofcontents[currentsection]%,currentsubsection] -%\end{frame} -%} + +% \AtBeginSubsection[] { +% \begin{frame} +% \frametitle{Plan} +% \tableofcontents[currentsection,currentsubsection] +% \end{frame} +% } +% \AtBeginSection[] { +% \begin{frame} +% \frametitle{Plan} +% \tableofcontents[currentsection]%,currentsubsection] +% \end{frame} +% } \setbeamertemplate{sections/subsections in toc}[sections numbered] %\setbeamertemplate{sections in toc}[sections numbered] @@ -198,138 +196,199 @@ $}} \section{Introduction} -\subsection{Définitions} +\subsection{Principe général} %%%%% SLIDE 1 -\begin{frame}{Définition formelle I} - +\begin{frame}{Principe général I} + \begin{defin} + Résoudre le problème $ \mathcal{P} $ : + $$ + \mathcal{P} \left \{ + \begin{array}{l} + \displaystyle\min_{x \in \mathbb{R}^n} J(x) \\ + g(x) \leq 0 \\ + h(x) = 0 + \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. $$ + \end{defin} \end{frame} -%%%%% SLIDE 2 -\begin{frame}{Définition formelle II} - +%%%%% 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} \end{frame} %%%%% SLIDE 3 -\begin{frame}{Définition formelle III} - -\end{frame} - -\subsection{Quantités asymptotiques} - -%%%%% 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} - +\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} \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} - +\section{Algorithme PQS} + +%%%%% SLIDE 4 +\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. + \newline + \textit{Sortie}: une approximation $ x_k $ de la solution $ x^\ast $ du problème $ \mathcal{P} $. + \begin{enumerate} + \item $ k := 0 $. + \item Tant que $ \norme{\nabla L(x_k,\lambda_k,\mu_k)} > \varepsilon $, + \begin{enumerate} + \item Résoudre le sous-problème quadratique : + $$ + \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 . + $$ + et obtenir la solution primale $ d_k $ et les multiplicateurs $ \lambda^{\prime} $ et $ \mu^{\prime} $ associé aux contraintes d’inégalité et d’égalité respectivement. + \item $ x_{k+1} = x_k + d_k; \ \lambda_{k+1} = \lambda^{\prime}; \ \mu_{k+1} = \mu^{\prime}; \ k := k + 1 $. + \end{enumerate} + \item Retourner $ x_k $. + \end{enumerate} + \end{block} \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} +% %%%%% 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} %%%%% SLIDE DE FIN @@ -339,12 +398,11 @@ $}} upper=block title,% shadow=true]{} \begin{center} - {\Large \textbf{{\color{mycvblue}Thank you for your attention.}}}\\ + {\Large \textbf{{\color{mycvblue}Merci pour votre attention.}}}\\ \vspace{3em} {\Large \textbf{{\color{mycvblue}Questions?}}}\\ \end{center} \end{beamerboxesrounded} - \end{frame} \end{document} diff --git a/rapport/ProjetOptimRO.tex b/rapport/ProjetOptimRO.tex index b81b605..e66ed41 100644 --- a/rapport/ProjetOptimRO.tex +++ b/rapport/ProjetOptimRO.tex @@ -720,7 +720,7 @@ En posant $ d = x - x_k $ et $ H_k = H[L](x_k,\lambda_k,\mu_k) $, on obtient le \hrulefill \newline -ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INEGALITÉ. +ALGORITHME PQS AVEC CONSTRAINTES D'ÉGALITÉ ET D'INÉGALITÉ. \newline \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. \newline -- 2.34.1