uniolympiads Ελληνικά

IMC 2002, Day 2, Problem 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.

Original from the official 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.

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

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).

Transcribed from the official solutions, page 4. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?