+La recherche d'une méthode permettant de trouver la solution au problème $ \mathcal{P} $ dans $ \mathcal{C} $ est l'activité principale de l'optimisation.
+\newline
+Si la modélisation de la problèmatique $ \mathcal{P} $ est considérée comme un art, la recherche d'une solution au problème $ \mathcal{P} $ dans $ \mathcal{C} $ est, elle, une science.
+
+\subsection{Quelques définitions annexes}
+
+Définissons quelques notions supplémentaires de base nécessaires à la suite :
+\begin{Def}
+ 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{Def}
+\begin{Def}
+ Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
+ \newline
+ On dit que $ x^\ast $ est \textbf{intérieur} à $ A $ si $ A $ est un voisinage de $ x^\ast $. On appelle intérieur de $ A $ l'ensemble des points intérieurs à $ A $ et on le note $ \mathring{A} $.
+\end{Def}
+\begin{Rmq}
+ $ A \subset \mathbb{R}^n $ est un ouvert $ \iff A = \mathring{A} $.
+\end{Rmq}
+\begin{Def}
+ Soient $ \mathbb{R}^n $ un espace topologique, $ A \subset \mathbb{R}^n $ et $ x^\ast \in \mathbb{R}^n $.
+ \newline
+ On dit que $ x^\ast $ est \textbf{adhérent} à $ A $ si et seulement si $ \forall V \in \mathcal{V}(x^\ast) \ A \cap V \neq \emptyset $. On appelle adhérence de $ A $ l'ensemble des points adhérents à $ A $ et on le note $ \overline{A} $.
+\end{Def}
+\begin{Rmq}
+ $ A \subset \mathbb{R}^n $ est un fermé $ \iff A = \overline{A} $.
+\end{Rmq}
+\begin{Def}
+ Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ et $ x^\ast \in \mathbb{R}^n $.
+ \newline
+ On dit que $ f $ est continue en $ x^\ast $ si
+ $$ \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \exists \alpha \in \mathbb{R}_{+}^{*} \ \forall x \in \mathbb{R}^n \ \norme{x - x^\ast} \leq \alpha \implies |f(x) - f(x^\ast)| \leq \varepsilon $$
+\end{Def}
+\begin{Def}
+ Soient $ k \in \{ 1,\ldots,n \} $ et une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $.
+ \newline
+ On dit que la $ k^{ième} $ dérivée partielle de $ f $ existe au point $ x^\ast \in \mathbb{R}^n $ si l’application
+ $$ t \longmapsto f(x^\ast_1,\ldots,x^\ast_{k-1},x^\ast_k + t,x^\ast_{k+1},\ldots,x^\ast_n) $$
+ définie sur un voisinage de $ 0 $ dans $ \mathbb{R} $ et à valeurs dans $ \mathbb{R} $ est dérivable en $ 0 $.
+ \newline
+ Dans ce cas on note
+ $$ \frac{\partial f}{\partial x_k}(x^\ast) $$ ou $$ \partial_k f(x^\ast) $$
+ cette dérivée.
+\end{Def}
+\begin{Def}
+ Soient une fonction $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $
+ et $ x^\ast, h \in \mathbb{R}^n $.
+ \newline
+ On dit que $ f $ est différentiable en $ x^\ast $ si il existe une application linéraire $ d_{x^\ast}f $ de $ \mathbb{R}^n $ dans $ \mathbb{R} $ telle que
+ \[
+ f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \underset{h \rightarrow 0}{\mathrm{o}}(\norme{h})
+ \]
+ Autrement dit il existe une application $ \varepsilon_{x^\ast} $ définie sur le voisinage de $ 0 $ dans $ \mathbb{R}^n $ et à valeurs dans $ \mathbb{R} $
+ telle que $ \lim\limits_{h \rightarrow 0} \varepsilon_{x^\ast}(h) = 0 $ et
+ \[
+ f(x^\ast + h) = f(x^\ast) + d_{x^\ast}f(h) + \norme{h}\varepsilon_{x^\ast}(h)
+ \]
+ On appelle $ d_{x^\ast}f $ la différentielle de $ f $ en $ x^\ast $.
+\end{Def}
+\begin{Rmq}
+ On peut démontrer que : $$ d_{x^\ast}f = \sum_{i=1}^n\frac{\partial f}{\partial x_i}(x^\ast) $$.
+\end{Rmq}
+\begin{Def}
+ 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{Def}
+\begin{Rmq}
+ $ \forall h \in \mathbb{R}^n \ d_{x^\ast}f(h) = \langle \nabla f(x^\ast),h \rangle = \nabla f(x^\ast)^\top h $
+\end{Rmq}
+\begin{Def}
+ Soit $ f: \mathbb{R}^n \longrightarrow \mathbb{R} $ un fonction de classe $ \mathcal{C}^2 $.
+ On définit la matrice hessienne de $ f $ en $ x^\ast $ par :
+ $$ H[f](x^\ast) =
+ \begin{pmatrix}
+ \frac{\partial^2 f}{\partial x_1^2}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_1\partial x_n}(x^\ast) \\
+ \vdots & & \vdots \\
+ \frac{\partial^2 f}{\partial x_n\partial x_1}(x^\ast) & \cdots & \frac{\partial^2 f}{\partial x_n^2}(x^\ast)
+ \end{pmatrix} $$
+\end{Def}
+\begin{Prop}
+ \begin{enumerate}
+ \item $ H[f](x^\ast) $ est une matrice symétrique (Théorème de symétrie de Schwarz).
+ \item On a le développement de Taylor-Young à l'ordre 2 en $ x^\ast $ suivant :
+ $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} v^\top H[f](x^\ast) v + \varepsilon(v) $$
+ ou
+ $$ f(x^\ast + v) = f(x^\ast) + \langle \nabla f(x^\ast),v \rangle + \frac{1}{2} \langle H[f](x^\ast)v,v \rangle + \varepsilon(v) $$
+ avec $ \frac{|\varepsilon(v)|}{\norme{v}} \rightarrow 0 $ quand $ \norme{v} \rightarrow 0 $.
+ \end{enumerate}
+\end{Prop}
+\begin{proof}
+ Elle repose entièrement sur deux autres théorèmes dont les preuves sont connues et de la réécriture de formulation de résultat.
+\end{proof}
+
+\subsection{Conditions d'existence d'un extremum}
+
+On peut démontrer que $ \mathcal{C }$ est un ensemble fermé de $ \mathbb{R}^n $ si $ g $ et $ h $ sont continues.
+On peut en déduire que si $ J $ est continue, $ \mathcal{C } $ est un ensemble fermé et borné de $ \mathbb{R}^n $.
+\begin{Th}[Théorème de Weierstrass]
+ Soient $ \mathcal{C} \neq \emptyset \subset \mathbb{R}^n $ un fermé borné et $ f : \mathcal{C} \longrightarrow \mathbb{R} $ une fonction continue.
+ \newline
+ Alors : $$ \exists x^\ast \in \mathcal{C} \ \forall x \in \mathcal{C} \ f(x) \geq f(x^\ast) $$
+ Autrement dit $ x^\ast $ est un minimum global de $ J $ sur $ \mathcal{C} $.
+ \newline
+ De la même façon, il existe un maximum global de $ J $ sur $ \mathcal{C} $.
+\end{Th}
+On en déduit que $ \mathcal{P} $ admet au moins une solution dans le cas où $ J, g ,h $ sont continues \cite{LJK,RON}. L'étude de la convexité de $ J $ sur $ \mathcal{C} $ permet d'explorer l'unicité de la solution \cite{LJK,RON}.
+
+\subsection{Conditions de caractérisation d'un extremum}
+
+Dans le cas où $ J, g, h $ sont continûment différentiable et ses dérivées sont continues (c'est à dire de classe $ \mathcal{C}^1 $), la recherche du mimimum consiste à faire des descentes par gradient [section \ref{descente}] de $ J $ sur $ \mathcal{C} $ avec comme critère d'arrêt : $ x_i = \displaystyle\min_{x \in \mathcal{C}} J(x) \iff \forall \varepsilon \in \mathbb{R}_{+}^{*} \ \norme{\nabla J(x_i)} < \varepsilon $, $ i \in \mathbb{N} $ \cite{FEA}.
+\newline
+On peut en déduire que une condition nécessaire et suffisante pour que $ x^\ast \in \mathring{\mathcal{C}} $ soit un des extremums locaux de $ J $ est que $ \nabla J(x^\ast) = 0 $. Mais si $ x^\ast \in \overline{\mathcal{C}}\setminus\mathring{\mathcal{C}} $ (la frontière de $ \mathcal{C} $) alors $ \nabla J(x^\ast) $ n'est pas nécessairement nul. Il sera par conséquent nécessaire de trouver d'autres caratérisations d'un extremum local \cite{FEA,WAL}.
+
+\subsubsection{Conditions de Karuch-Kuhn-Tucker}\label{KKT}
+
+\begin{Th}
+ Soient $ 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 :
+ \newline
+ \newline
+ \centerline{$ \{ \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.}
+ \newline
+ \newline
+ et
+ $$ \forall i \in I \ \exists \mu_i \in \mathbb{R}_{+} \land \forall j \in J \ \exists \lambda_j \in \mathbb{R} \ \nabla J(x^\ast) + \sum_{i \in I}\mu_i{\nabla g_i(x^\ast)} + \sum_{j \in J}\lambda_j{\nabla h_j(x^\ast)} = 0 \land \forall i \in I \ \mu_i \nabla g_i(x^\ast) = 0 $$
+ On appelle $ (\mu_i)_{i \in I}$ les multiplicateurs de Kuhn-Tucker et $ (\lambda_j)_{j \in J}$ les multiplicateurs de Lagrange.
+\end{Th}
+\begin{proof}
+ Elle repose sur le lemme de Farkas \cite{FEA,RON}.
+\end{proof}
+Il est à noter que une condition d'égalité peut se répresenter par deux conditions d'inégalité : $ \forall x \in \mathbb{R}^n \ \forall i \in \{ 1,\ldots,q \} \ h_i(x) = 0 \iff h_i(x) \leq 0 \land h_i(x) \geq 0 $ \cite{FEA}, ce qui peut permettre de réécrire le problème $ \mathcal{P} $ en éliminant les contraintes d'égalités et change la forme des conditions \textit{KKT} à vérifier mais rajoute $ 2q $ conditions d'inégalités et donc $ 2q $ multiplicateurs de Kuhn-Tucker.