📚 الرئيسية
دخول

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

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

⬇️ تحميل☆ حفظ

Concours national d'accès au Doctorat au titre de l'année 2019-2020 — Filière Mathématiques, Spécialité Optimisation et contrôle — Épreuve : Optimisation, Université Ferhat Abbas Sétif 1, Faculté des Sciences.

التمرين 1

Exercice 1 — Optimisation sous contraintes et conditions KKT

#optimization#lagrangian#kkt-conditions#constrained-optimization

Soit ω\omega l'ensemble défini par

ω={(x1,x2)∈R2:x1−1≥0,  3−x2≥0,  c1x1−c2x2≥0,  x1,x2≥0},\omega = \{(x_1, x_2) \in \mathbb{R}^2 : x_1 - 1 \geq 0, \; 3 - x_2 \geq 0, \; c_1 x_1 - c_2 x_2 \geq 0, \; x_1, x_2 \geq 0\},

avec c1,c2∈Rc_1, c_2 \in \mathbb{R}. On considère la fonction f:ω→R+f : \omega \to \mathbb{R}^+ définie par :

f(x1,x2)=2ln⁡(x1)+ln⁡(3−x2).f(x_1, x_2) = 2\ln(x_1) + \ln(3 - x_2).
  1. (2 pts) Définir le Lagrangien de ce problème.
  2. (2 pts) Étudier les points critiques du Lagrangien.
  3. (2 pts) Que peut-on conclure ?
◀الحل

1.

L(x,λ)=2ln⁡(x1)+ln⁡(3−x2)−λ1(1−x1)−λ2(x2−3)−λ3(c2x2−c1x1)−λ4(−x1)−λ5(−x2)L(x, \lambda) = 2\ln(x_1) + \ln(3-x_2) - \lambda_1(1-x_1) - \lambda_2(x_2-3) - \lambda_3(c_2 x_2 - c_1 x_1) - \lambda_4(-x_1) - \lambda_5(-x_2) avec λi≥0\lambda_i \geq 0.

2.

Conditions KKT : ∂L∂x1=2x1+λ1+c1λ3+λ4=0\frac{\partial L}{\partial x_1} = \frac{2}{x_1} + \lambda_1 + c_1\lambda_3 + \lambda_4 = 0, ∂L∂x2=−13−x2−λ2−c2λ3−λ5=0\frac{\partial L}{\partial x_2} = \frac{-1}{3-x_2} - \lambda_2 - c_2\lambda_3 - \lambda_5 = 0, plus les conditions de complémentarité.

3.

ff est concave (somme de logarithmes) sur le domaine convexe ω\omega. Donc tout point KKT est un maximum global. La solution dépend des valeurs de c1,c2c_1, c_2.

التمرين 2

Exercice 2 — Quotient de Rayleigh et matrices semi-définies positives

#optimization#rayleigh-quotient#eigenvalues#semi-definite-matrix

Soit A∈Sn+(R)A \in S_n^+(\mathbb{R}) l'ensemble des matrices symétriques semi-définies positives. On considère la fonction f:Rn∖{0}→Rf : \mathbb{R}^n \setminus \{0\} \to \mathbb{R} définie par

f(x)=⟨Ax,x⟩∥x∥2,f(x) = \frac{\langle Ax, x \rangle}{\|x\|^2},

où ⟨⋅,⋅⟩\langle \cdot, \cdot \rangle est le produit scalaire euclidien.

  1. (1,5 pts) Montrer que ff est C∞C^\infty sur son domaine.
  2. (1,5 pts) Montrer que inf⁡\inf et sup⁡\sup de ff sur Rn∖{0}\mathbb{R}^n \setminus \{0\} possèdent une solution.
  3. (1,5 pts) Déterminer l'ensemble des points critiques de ff.
  4. (1,5 pts) Résoudre les deux problèmes d'optimisation.
◀الحل

1.

f(x)=xTAx/xTxf(x) = x^T A x / x^T x. Le numérateur et dénominateur sont C∞C^\infty et le dénominateur ne s'annule pas sur le domaine.

2.

ff est continue et homogène de degré 0. Donc ff est constante sur chaque rayon et se réduit à une fonction continue sur la sphère Sn−1S^{n-1} (compacte). Par Weierstrass, inf⁡\inf et sup⁡\sup sont atteints.

3.

∇f(x)=0\nabla f(x) = 0 donne 2Ax∥x∥2−2⟨Ax,x⟩x=02Ax \|x\|^2 - 2\langle Ax,x \rangle x = 0, soit Ax=f(x)xAx = f(x) x. Donc les points critiques sont les vecteurs propres de AA.

4.

inf⁡f=λmin⁡(A),sup⁡f=λmax⁡(A)\boxed{\inf f = \lambda_{\min}(A), \quad \sup f = \lambda_{\max}(A)}

atteints aux vecteurs propres correspondants.