Simplifying vector norms in a proof

Question

Consider the optimization problem $$ \min _{y \in \mathbb{R}^{n}} f(y):=\frac{1}{2}\|A y-b\|_{2}^{2} $$ Let y be a feasible solution and $y^{*}$ be the optimal solution. The goal is to prove that $$ f(y)-f\left(y^{*}\right)=\frac{1}{2}\left\|A y-A y^{*}\right\|_{2}^{2}, \forall y \in \mathbb{R}^{n} $$ I am getting confused when simplifying vector norm terms, which I think is necessary in this proof. My attempt: $$f(y)=\frac{1}{2}\|A y-b\|_{2}^{2}$$ $$f(y^{*})=\frac{1}{2}\|A y^{*}-b\|_{2}^{2}$$ So, $$\frac{1}{2}\|A y-b\|_{2}^{2} - \frac{1}{2}\|A y^{*}-b\|_{2}^{2} = \frac{1}{2}\left\|A y-A y^{*}\right\|_{2}^{2}$$ $$\left(\|Ay\|_{2}^{2} - 2\|Ay\|_2\|b\|_2 + \|b\|_2^{2}\right)-\left(\|Ay^{*}\|_{2}^{2} - 2\|Ay^{*}\|_2\|b\|_2 + \|b\|_2^{2}\right) = \|A y-A y^{*}\|_{2}^{2}$$ $$\|A y\|_2^{2} - \|A y^{*}\|_2^{2} = \|A y-A y^{*}\|_{2}^{2}$$ $$\|A y-A y^{*}\|_{2}^{2} = \|A y-A y^{*}\|_{2}^{2}$$ Not very sure about the last two steps. Maybe an application of the Triangle Inequality here?

Answer 1

• Because $y^*$ is optimal for the unconstrained optimization problem, we must have $\nabla f(y^*)=0$, i.e. $$A^\top (Ay^*-b)=0.$$
• You expanded the norms incorrectly: $\|v-w\|_2^2 = \|v\|_2^2 - 2 v^\top w + \|w\|_2^2$ (the middle term is not $\|v\|_2 \|w\|_2$).

---

Note that $$\|Ay-b\|_2^2 - \|Ay^* - b\|_2^2 = \|Ay\|_2^2 - 2 b^\top Ay - \|Ay^*\|_2^2 + 2 b^\top A y^*$$ and $$\|Ay-Ay^*\|_2^2 = \|Ay\|_2^2 + \|Ay^*\|_2^2 - 2 y^\top A^\top A y^*.$$ It suffices to show the difference is zero. The difference (halved) is \begin{align} &\|Ay^*\|_2^2 - y^\top A^\top A y^* + b^\top Ay - b^\top A y^* \\ &= \|Ay^*\|_2^2 - y^\top \underbrace{A^\top (Ay^*-b)}_{=0} - b^\top A y^* \\ &= \|Ay^*\|_2^2 - b^\top A y^* \\ &= (y^*)^\top \underbrace{A^\top (Ay^* - b)}_{=0}\ \\ &= 0. \end{align}