مسابقة دكتوراه 2017 — Université Ferhat Abbas - Sétif 1 — الموضوع 01

مسابقة تخصص · Analyse Numérique & Optimisation

⬇️ تحميل ☆ حفظ

Optimisation et Contrôle, 28/10/2017

التمرين 1

Optimisation quadratique sous contraintes paramétrées

#KKT#optimisation quadratique#contraintes

On considère dans $\mathbb R^2$ un problème de minimisation quadratique

$\min_{x\in C_k}f(x),$

où $f$ et l'ensemble admissible $C_k$ dépendent d'un paramètre réel $k$ .

Représenter graphiquement $C_k$ .
Montrer l'existence d'une solution.
Déterminer les points réguliers.
Écrire les conditions de Karush-Kuhn-Tucker.
Déterminer les solutions en fonction de $k$ .
Donner une interprétation géométrique.

◀الحل

L'ensemble admissible est fermé. Dans les cas du sujet, il est compact ou bien $f$ est coercive, donc le théorème de Weierstrass garantit l'existence d'un minimum.

Aux points réguliers, les gradients des contraintes actives sont linéairement indépendants. Les conditions KKT sont

$\nabla f(x)+\sum_i\lambda_i\nabla g_i(x)=0,$

\qquad\lambda_i\ge0, \qquad\lambda_i g_i(x)=0.$$ On résout les cas intérieur, une contrainte active, puis plusieurs contraintes actives. Lorsque le problème est convexe, toute solution KKT est un minimum global.

التمرين 2

Simplexe, dualité et programmation sur le simplexe

#programmation linéaire#simplexe#dualité

Résoudre par le simplexe

$\max(x_1-x_2)$

sous

$2x_1-x_2\le4,$

$x_1-2x_2\le2,$

$x_1+x_2\le5,$

avec les conditions de signe du sujet.

Trouver le dual de

$\max b^Ty$

sous

\qquad y\in T_n,$$ où $$T_n=\left\{y\in\mathbb R^n:y\ge0, \sum_{i=1}^ny_i=1\right\}.$$

◀الحل

Pour le premier problème, on introduit les variables d'écart et on pivote jusqu'à ce que tous les coûts réduits satisfassent le critère d'optimalité.

Pour le second, on associe un multiplicateur $z\ge0$ à $B^Ty\le0$ et un multiplicateur libre $\alpha$ à $\mathbf1^Ty=1$ . Le lagrangien est

$L(y,z,\alpha)=b^Ty-z^TB^Ty+\alpha(1-\mathbf1^Ty).$

La borne supérieure en $y\ge0$ est finie lorsque

$b-Bz-\alpha\mathbf1\le0.$

Le dual est donc

$\min_{\alpha\in\mathbb R,\ z\ge0}\alpha$

sous

$Bz+\alpha\mathbf1\ge b.$