uniolympiads English

IMC 2002, Ημέρα 2, Θέμα 6

Let f ⁣:Rn→Rf\colon \mathbb{R}^n \to \mathbb{R} be a convex function whose gradient ∇f=(∂f∂x1,…,∂f∂xn)\nabla f = \left(\frac{\partial f}{\partial x_1}, \dots, \frac{\partial f}{\partial x_n}\right) exists at every point of Rn\mathbb{R}^n and satisfies the condition

∃L>0 ∀x1,x2∈Rn∥∇f(x1)−∇f(x2)∥≤L∥x1−x2∥.\exists L > 0\ \forall x_1, x_2 \in \mathbb{R}^n \quad \|\nabla f(x_1) - \nabla f(x_2)\| \le L\|x_1 - x_2\|.

Prove that

∀x1,x2∈Rn∥∇f(x1)−∇f(x2)∥2≤L⟨∇f(x1)−∇f(x2),x1−x2⟩.(1)\forall x_1, x_2 \in \mathbb{R}^n \quad \|\nabla f(x_1) - \nabla f(x_2)\|^2 \le L\langle \nabla f(x_1) - \nabla f(x_2), x_1 - x_2 \rangle. \qquad (1)

In this formula ⟨a,b⟩\langle a, b \rangle denotes the scalar product of the vectors aa and bb.

Πρωτότυπο από το επίσημο PDFLet f : R n → R be a convex function whose gradient ∇f = ∂f ∂f n ∂x 1 , . . . , ∂x n exists at every point of R and satisfies the condition ∃L > 0 ∀x 1 , x 2 ∈ R n k∇f (x 1 ) − ∇f (x 2 )k ≤ Lkx 1 − x 2 k. Prove that ∀x 1 , x 2 ∈ R n k∇f (x 1 ) − ∇f (x 2 )k 2 ≤ Lh∇f (x 1 ) − ∇f (x 2 ), x 1 − x 2 i. (1) In this formula ha, bi denotes the scalar product of the vectors a and b.

Η μεταγραφή συγκρίθηκε σύμβολο προς σύμβολο με το πρωτότυπο, όχι ακόμα από άνθρωπο.

Χρόνος σε αυτό το θέμα 0:00

Δούλεψε τουλάχιστον 45 λεπτά πριν ανοίξεις τη λύση.

Επίσημη λύση

Solution. Let g(x)=f(x)−f(x1)−⟨∇f(x1),x−x1⟩g(x)=f(x)-f(x_1)-\langle\nabla f(x_1),x-x_1\rangle. It is obvious that gg has the same properties. Moreover, g(x1)=∇g(x1)=0g(x_1)=\nabla g(x_1)=0 and, due to convexity, gg has 0 as the absolute minimum at x1x_1. Next we prove that

g(x2)≥12L∥∇g(x2)∥2.(2)g(x_2)\ge\frac{1}{2L}\|\nabla g(x_2)\|^2.\tag{2}
Let y0=x2−1L∥∇g(x2)∥y_0=x_2-\frac1L\|\nabla g(x_2)\| and y(t)=y0+t(x2−y0)y(t)=y_0+t(x_2-y_0). Then
g(x2)=g(y0)+∫01⟨∇g(y(t)),x2−y0⟩ dt==g(y0)+⟨∇g(x2),x2−y0⟩−∫01⟨∇g(x2)−∇g(y(t)),x2−y0⟩ dt≥≥0+1L∥∇g(x2)∥2−∫01∥∇g(x2)−∇g(y(t))∥⋅∥x2−y0∥ dt≥≥1L∥∇g(x2)∥2−∥x2−y0∥∫01L∥x2−g(y)∥ dt==1L∥∇g(x2)∥2−L∥x2−y0∥2∫01t dt=12L∥∇g(x2)∥2.\begin{aligned}g(x_2)&=g(y_0)+\int_0^1\langle\nabla g(y(t)),x_2-y_0\rangle\,dt=\\&=g(y_0)+\langle\nabla g(x_2),x_2-y_0\rangle-\int_0^1\langle\nabla g(x_2)-\nabla g(y(t)),x_2-y_0\rangle\,dt\ge\\&\ge0+\frac1L\|\nabla g(x_2)\|^2-\int_0^1\|\nabla g(x_2)-\nabla g(y(t))\|\cdot\|x_2-y_0\|\,dt\ge\\&\ge\frac1L\|\nabla g(x_2)\|^2-\|x_2-y_0\|\int_0^1L\|x_2-g(y)\|\,dt=\\&=\frac1L\|\nabla g(x_2)\|^2-L\|x_2-y_0\|^2\int_0^1t\,dt=\frac{1}{2L}\|\nabla g(x_2)\|^2.\end{aligned}

Substituting the definition of gg into (2), we obtain

f(x2)−f(x1)−⟨∇f(x1),x2−x1⟩≥12L∥∇f(x2)−∇f(x1)∥2,f(x_2)-f(x_1)-\langle\nabla f(x_1),x_2-x_1\rangle\ge\frac{1}{2L}\|\nabla f(x_2)-\nabla f(x_1)\|^2,
∥∇f(x2)−∇f(x1)∥2≤2L⟨∇f(x1),x1−x2⟩+2L(f(x2)−f(x1)).(3)\|\nabla f(x_2)-\nabla f(x_1)\|^2\le2L\langle\nabla f(x_1),x_1-x_2\rangle+2L(f(x_2)-f(x_1)).\tag{3}
Exchanging variables x1x_1 and x2x_2, we have
∥∇f(x2)−∇f(x1)∥2≤2L⟨∇f(x2),x2−x1⟩+2L(f(x1)−f(x2)).(4)\|\nabla f(x_2)-\nabla f(x_1)\|^2\le2L\langle\nabla f(x_2),x_2-x_1\rangle+2L(f(x_1)-f(x_2)).\tag{4}
The statement (1) is the average of (3) and (4).

Μεταγραφή από το επίσημο κείμενο λύσεων, σελίδα 4. Η μεταγραφή δεν έχει ελεγχθεί δεύτερη φορά· αν έχεις αμφιβολία, κοίτα το πρωτότυπο.

Θέμα αρχείου: η εκφώνηση είναι το επίσημο κείμενο (μεταγραμμένο, με το πρωτότυπο παραπάνω). Η ταξινόμηση ανά αντικείμενο και η δυσκολία εκτιμήθηκαν αυτόματα· υποδείξεις και λύση στα ελληνικά προστίθενται σταδιακά.

Πώς πήγε;