Consider a constrained minimization problem

where f₀ is convex and smooth and is convex and  compact. Clearly, a projected gradient or proximal gradient algorithm could be applied to this problem, if the projection onto X is easy to compute. When this is not the case, the following alternative algorithm has been proposed.

Initialize the iterations with some  Determine the gradient  and solve

Then, update the current point as.

whereand, in particular, we choose

Assume that f0 has a Lipschitz continuous gradient with Lipschitz
constant L, and that  for every x, y ∈ X. In this. exercise, you shall prove that

1. Using the inequality

which holds for any convex f₀ with Lipschitz continuous gradient, prove that

2. Show that the following recursion holds for δ_k:

for

3. Prove by induction on k the desired result (12.27).

Transcribed Image Text:

p* = min fo(x), XEX