مسابقة دكتوراه 2017 — جامعة سطيف 1 — الموضوع 01

On considère le problème d'optimisation suivant dans $\mathbb{R}^2$ :

$$(P_k)\ \begin{cases} \min f(x) \\ \text{s.c.}\ x \in C \subset \mathbb{R}^2 \end{cases}$$

avec $f(x_1, x_2) = k^2 + x_1^2 + x_2^2 - 2kx_2$, où $k$ est un réel fixe, où

$$C = \{x \in \mathbb{R}^2 : g_1(x_1,x_2) \le 0,\ g_2(x_1,x_2) \le 0\}$$ $$g_1(x_1,x_2) = x_2 - 2x_1^2$$ $$g_2(x_1,x_2) = x_1^2 - x_2$$

1. Représenter l'ensemble des contraintes $C$ sur une figure.

2. Montrer que le problème $P_k$ admet une solution quel que soit $k$.

3. Quels sont les points réguliers de $C$ vis-à-vis des conditions de Karush-Kuhn-Tucker ?

4. Déterminer les points réguliers de $C$ qui vérifient les conditions de Karush-Kuhn-Tucker pour le problème $P_k$.

5. En déduire les solutions de $P_k$ en discutant en fonction du paramètre $k$.

6. Interpréter géométriquement le problème et retrouver à la main les solutions sur la figure pour les différents cas.

a) Résoudre le programme linéaire $(2)$ par la méthode du simplexe et donner des explications au résultat obtenu.

$$(2)\ \begin{cases} \max x_1 - x_2 \\ 2x_1 - x_2 \le 4 \\ x_1 - 2x_2 \le 2 \\ x_1 + x_2 \le 5 \end{cases}$$

b) Trouver le dual (avec justificatives) de :

$$(P1)\ \begin{cases} \max b^t y \\ By \le 0 \\ y \in T_n \end{cases}$$

où $T_n$ est le simplexe défini par $T_n = \{y \in \mathbb{R}^n : y \ge 0 \text{ et } \sum_{i=1}^{n} y_i = 1\}$, $b, y \in \mathbb{R}^n$, $B$ est une $m \times n$ matrice.