The proximal optimality condition gives

\frac{x _{k} - x _{k + 1}}{t} \in \partial f (x_{k + 1}) .

The subgradient inequality therefore yields, for every

u

f (u) \geq f (x_{k + 1}) + \frac{1}{t} (x_{k} - x_{k + 1})^{T} (u - x_{k + 1}) .

ii

Solution

Rearranging part i and using the polarization identity gives

t [f (x_{k + 1}) - f (u)] \leq (x_{k} - x_{k + 1})^{T} (x_{k + 1} - u) = \frac{1}{2} (∥ u - x_{k} ∥^{2} - ∥ u - x_{k + 1} ∥^{2} - ∥ x_{k} - x_{k + 1} ∥^{2}) .

Dropping the final nonpositive term proves

t [f (x_{k + 1}) - f (u)] \leq \frac{1}{2} (∥ u - x_{k} ∥^{2} - ∥ u - x_{k + 1} ∥^{2}) .

The defining minimization, compared with the candidate

x_{k}

, shows that

f (x_{k + 1}) \leq f (x_{k})

. Put

u = x^{*}

in part ii and sum from

j = 0

k - 1

. The squared distances telescope, while monotonicity gives

k t [f (x_{k}) - f^{*}] \leq t \sum_{j = 0}^{k - 1} [f (x_{j + 1}) - f^{*}] \leq \frac{1}{2} ∥ x_{0} - x^{*} ∥^{2} .

Hence

f (x_{k}) - f^{*} \leq \frac{∥ x _{0} - x ^{*} ∥ ^{2}}{2 k t} .

There are no discussions about this article yet.

There are currently no matching articles.