Prove that a strongly convex function imples $2c(F(w)-F_*) \leq ||\nabla F(w)||_2^2$

Question

The proof is given as follows:

My question is why is the unique minimizer $\bar{w}_* = w - \frac{1}{c} \nabla F(w)$?

Answer 1

Given \begin{align*} q(\bar w) & = F(w) + \nabla F(w)^T(\bar w - w) + \frac{c}{2}\|\bar w - w\|_2^2 \\ & = F(w) + \sum_{j=1}^d \frac{\partial F}{\partial w_j}\left(\bar w_j - w_j\right) + \frac{c}{2}\sum_{j=1}^d \left(\bar w_j - w_j\right)^2, \end{align*} its partial derivative with respect to $\bar w_j$ for any $j=1,\dots, d$ is \begin{align*} \frac{\partial q(\bar w)}{\partial\bar w_j} = \frac{\partial F}{\partial w_j} + \frac{c}{2}\Big(2\left(\bar w_j - w_j\right)\Big) = \frac{\partial F}{\partial w_j} + c\left(\bar w_j - w_j\right). \end{align*} Consequently, the gradient of $q(\bar w)$ is $$ \nabla q(\bar w) = \nabla F(w) + c(\bar w - w). $$ The critical point of $q(\bar w)$ is found by setting $\nabla q(\bar w) = 0$ and solving for $\bar w$: \begin{align*} \nabla F(w) + c\left(\bar w - w\right) & = 0 \\ c\left(\bar w - w\right) & = - \nabla F(w) \\ \bar w - w & = -\frac{1}{c}\nabla F(w) \\ \bar w & = w - \frac{1}{c}\nabla F(w) =\colon \bar w^* \end{align*} as desired. Note that this argument doesn't prove that $\bar w^*$ is the minimiser or maximiser.

Answer 2

There is an easier argument for quadratic functionals: completing the square. The following identity is just as easy to prove as the 1D version you know from highschool: $$ \alpha ‖x‖^2 + \beta · x = \alpha\left\|x+\frac1{2\alpha}{\beta} \right\|^2 - \frac{‖\beta‖^2}{4\alpha}$$ In your case, this yields (remember, $w$ is fixed, $\bar w$ is varying) with $$x = w - \bar w, \quad \alpha = \frac{c}{2},\quad \beta = \nabla F(w)$$ $$⟹ q(\bar w) = C(w) + \frac c{2}\left\|\bar w - \left(w-\frac1c∇ F(w)\right)\right\|^2 $$ where $C(w) = F(w)-\frac{‖∇ F(w)‖^2}{2c}$. Its now obvious what the minimiser and minimum is.