[SOLVED] Si251 – convex optimization homework 3

1. (50 pts) L-smooth functions. Suppose the function f : R
n → R is convex and differentiable. Please prove that the following relations holds for all x, y ∈ R if f with an
L-Lipschitz continuous conditions,
[1] ⇒ [2] ⇒ [3]
[1] ⟨∇f(x) − ∇f(y), x − y⟩ ≤ L∥x − y∥
2
,
[2] f(y) ≤ f(x) + ∇f(x)
T
(y − x) + L
2
∥y − x∥
2
,
[3] f(y) ≥ f(x) + ∇f(x)
T
(y − x) + 1
2L
∥∇f(y) − ∇(x)∥
2
, ∀x, y,2. (50 pts) Backtracking line search. Please show the convergence of backtracking line
search on a m-strongly convex and M-smooth objective function f as
f

x
(k)

− p
⋆ ≤ c
k

f

x
(0)
− p
⋆

where c = 1 − min{2mα, 2βαm/M} < 1.