%\usepackage{MyMnSymbol}
\usepackage{comment}
%\usepackage{etex}
-%usepackage{mathtools}
+%\usepackage{mathtools}
%\usepackage{fourier}
\usepackage{ragged2e}
-\justifying
% Setup TikZ
\usepackage{tikz}
\newcommand{\bluebrace}{{\color{blue}\left\{}}
+\newcommand{\norme}[1]{\left\Vert #1 \right\Vert}
\definecolor{mycvblue}{rgb}{0.302,0.537,0.737}
-\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}
\addtobeamertemplate{footline}{\texttt{\hfill\insertframenumber/{\inserttotalframenumber}}}
-%
-%\AtBeginSubsection[] {
-%\begin{frame}<beamer>
-%\frametitle{Plan}
-%\tableofcontents[currentsection,currentsubsection]
-%\end{frame}
-%}
-%\AtBeginSection[] {
-%\begin{frame}<beamer>
-%\frametitle{Plan}
-%\tableofcontents[currentsection]%,currentsubsection]
-%\end{frame}
-%}
+
+% \AtBeginSubsection[] {
+% \begin{frame}<beamer>
+% \frametitle{Plan}
+% \tableofcontents[currentsection,currentsubsection]
+% \end{frame}
+% }
+% \AtBeginSection[] {
+% \begin{frame}<beamer>
+% \frametitle{Plan}
+% \tableofcontents[currentsection]%,currentsubsection]
+% \end{frame}
+% }
\setbeamertemplate{sections/subsections in toc}[sections numbered]
%\setbeamertemplate{sections in toc}[sections numbered]
\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
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}
repositories / Projet_Recherche_Operationnelle.git / commitdiff
