IFT 3512: DEVOIR 3 Patrice Marcotte À au début du cours du mardi 12 mars 2002

1 (25 points) Soit le programme

min_{d}  c^{t}d
Ad ≤ 0
∥d∥_{p} ≤ 1

où c ≠ 0 et ∥d∥_{p} = (∑_{j} |d_{j}|^{p})^{1/p}. Montrer que, si p > 1, le multiplicateur associé à la deuxième contrainte est non nul et que, si p = 1 le programme peut se ramener à un programme linéaire. Démontrer également ce résultat pour la norme:

∥d∥ = max_{j}{|d_{j}|}.

2 (75 points) Soit le programme

min_{x≥0}  x_{1}^{2} + x_{1}x_{2} + 2x_{2}^{2} − 6x_{1} − 2x_{2} − 12x_{3}
x_{1} + x_{2} + x_{3} = 2
−x_{1} + 2x_{2} ≤ 3.

1. Tracer le domaine réalisable.

2. Résoudre le système de Kuhn-Tucker.

3. Illustrer géométriquement la solution.

4. Effectuer 2 itérations (non triviales) de la méthode de Frank-Wolfe.

5. Effectuer 2 itérations (non triviales) des deux variantes de la méthode du gradient projeté.

6. Effectuer 2 itérations de la méthode du gradient réduit.