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

مسابقة دكتوراه 2013 — Université Abdelhamid Ibn Badis - Mostaganem — الموضوع 05

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

⬇️ تحميل☆ حفظ✓ تم الحل

Épreuve Écrite du Concours d'Accès en 3ième Cycle LMD en Mathématiques — Option : Optimisation, Ondelettes et Calcul Fractionnaire — Épreuve 1, Université Abdel Hamid Ibn Badis Mostaganem, Faculté des Sciences Exactes et de l'Informatique, Département de Mathématiques et d'Informatique — Mercredi 09 Octobre 2013 (Durée 1 Heure 30 Minutes).

التمرين 1

Exercice 1 — Minimum local, global et convexité

#optimization#convexity#local-minimum#global-minimum

Soit la fonction f:Rn→Rf : \mathbb{R}^n \to \mathbb{R}, et considérons le problème

(P){min⁡f(x)x∈Rn(P) \begin{cases} \min f(x) \\\\ x \in \mathbb{R}^n \end{cases}
  1. Donner la définition d'un minimum local et un minimum global pour (P)(P).
  2. Donner un exemple sur le quel (P)(P) admet à la fois un minimum local et global.
  3. Supposons que la fonction objectif ff est convexe. Montrer que si x∗x^* est un minimum local de ff alors x∗x^* est un minimum global.
◀الحل

1.

Minimum local : ∃δ>0\exists \delta \gt 0, f(x∗)≤f(x)f(x^*) \leq f(x) ∀x\forall x avec ∥x−x∗∥<δ\|x - x^*\| \lt \delta. Minimum global : f(x∗)≤f(x)f(x^*) \leq f(x) ∀x∈Rn\forall x \in \mathbb{R}^n.

2.

f(x)=x2f(x) = x^2 : x∗=0x^* = 0 est à la fois minimum local et global.

3.

Par l'absurde : si ∃y\exists y avec f(y)<f(x∗)f(y) \lt f(x^*), alors par convexité f(x∗+t(y−x∗))≤(1−t)f(x∗)+tf(y)<f(x∗)f(x^* + t(y - x^*)) \leq (1-t)f(x^*) + tf(y) \lt f(x^*) pour t>0t \gt 0 petit, contredisant la localité.

Minimum local=minimum global pour f convexe\boxed{\text{Minimum local} = \text{minimum global pour } f \text{ convexe}}

التمرين 2

Exercice 2 — Algorithme du gradient conjugué

#conjugate-gradient#quadratic-optimization#line-search

Soit le problème d'optimisation sans contraintes

{min⁡12xTQx−xTbx∈Rn\begin{cases} \min \frac{1}{2} x^T Q x - x^T b \\\\ x \in \mathbb{R}^n \end{cases}

où Q∈M(n,n)(R)Q \in \mathcal{M}_{(n,n)}(\mathbb{R}) est symétrique définie positive et b∈M(m,1)(R)b \in \mathcal{M}_{(m,1)}(\mathbb{R}). La direction d(k+1)d^{(k+1)} est calculée comme combinaison linéaire de la direction précédente d(k)d^{(k)} et le gradient au point x(k+1)x^{(k+1)}. Le coefficient β(k)=∇f(x(k+1))TQd(k)d(k)TQd(k)\beta^{(k)} = \frac{\nabla f(x^{(k+1)})^T Q d^{(k)}}{d^{(k)T} Q d^{(k)}} assure la QQ-conjugaison.

  1. Calculer explicitement α(k)\alpha^{(k)}, en fonction de ∇f(x(k))\nabla f(x^{(k)}), d(k)d^{(k)} et QQ.
  2. Rappeler les étapes de l'algorithme du gradient conjugué.
  3. Montrer que la constante βk\beta_k vaut aussi ∇f(x(k+1))T[∇f(x(k+1))−∇f(x(k))](d(k))T[∇f(x(k+1))−∇f(x(k))]\frac{\nabla f(x^{(k+1)})^T [\nabla f(x^{(k+1)}) - \nabla f(x^{(k)})]}{(d^{(k)})^T [\nabla f(x^{(k+1)}) - \nabla f(x^{(k)})]}.
◀الحل

1.

α(k)=−∇f(x(k))Td(k)d(k)TQd(k)\alpha^{(k)} = -\frac{\nabla f(x^{(k)})^T d^{(k)}}{d^{(k)T} Q d^{(k)}} (recherche linéaire exacte pour la quadratique).

2.

Initialisation : x(0)x^{(0)}, d(0)=−∇f(x(0))d^{(0)} = -\nabla f(x^{(0)}). Itération : calculer α(k)\alpha^{(k)}, x(k+1)=x(k)+α(k)d(k)x^{(k+1)} = x^{(k)} + \alpha^{(k)} d^{(k)}, β(k)\beta^{(k)}, d(k+1)=−∇f(x(k+1))+β(k)d(k)d^{(k+1)} = -\nabla f(x^{(k+1)}) + \beta^{(k)} d^{(k)}.

3.

Comme ∇f(x(k+1))−∇f(x(k))=Q(x(k+1)−x(k))=α(k)Qd(k)\nabla f(x^{(k+1)}) - \nabla f(x^{(k)}) = Q(x^{(k+1)} - x^{(k)}) = \alpha^{(k)} Q d^{(k)}, on substitue Qd(k)=1α(k)[∇f(x(k+1))−∇f(x(k))]Qd^{(k)} = \frac{1}{\alpha^{(k)}}[\nabla f(x^{(k+1)}) - \nabla f(x^{(k)})] dans β(k)\beta^{(k)}.

βk=∇f(x(k+1))T[∇f(x(k+1))−∇f(x(k))](d(k))T[∇f(x(k+1))−∇f(x(k))]\boxed{\beta_k = \frac{\nabla f(x^{(k+1)})^T [\nabla f(x^{(k+1)}) - \nabla f(x^{(k)})]}{(d^{(k)})^T [\nabla f(x^{(k+1)}) - \nabla f(x^{(k)})]}}

التمرين 3

Exercice 3 — Problème d'affectation et dualité

#assignment-problem#linear-programming#duality

Soit le problème d'optimisation suivant :

min⁡∑i,j=1ncijxij\min \sum_{i,j=1}^{n} c_{ij} x_{ij} {∑i=1nxij=1∀j=1,…,n∑j=1nxij=1∀i=1,…,nxij≥0∀i,j\begin{cases} \sum_{i=1}^{n} x_{ij} = 1 \quad \forall j = 1, \ldots, n \\\\ \sum_{j=1}^{n} x_{ij} = 1 \quad \forall i = 1, \ldots, n \\\\ x_{ij} \geq 0 \quad \forall i, j \end{cases}
  1. Ce problème est-il linéaire ? Justifier.
  2. Donner le nombre de variables et de contraintes pour ce problème.
  3. Écrire le problème dual associé.
◀الحل

1.

Oui, la fonction objectif et les contraintes sont toutes linéaires en xijx_{ij}.

2.

n2n^2 variables et 2n2n contraintes d'égalité (plus n2n^2 contraintes de non-négativité).

3.

Dual : max⁡∑i=1nui+∑j=1nvj\max \sum_{i=1}^n u_i + \sum_{j=1}^n v_j sous ui+vj≤ciju_i + v_j \leq c_{ij} ∀i,j\forall i, j, avec ui,vju_i, v_j libres.

max⁡∑ui+∑vj s.c. ui+vj≤cij\boxed{\max \sum u_i + \sum v_j \text{ s.c. } u_i + v_j \leq c_{ij}}
→السابقConcours Doctorat 2013 — Université Frères Mentouri - Constantine 1 — Épreuve N°05التاليConcours Doctorat 2013 — Université des Sciences et de la Technologie Houari Boumediène (USTHB) — Épreuve N°05←