1

I would have a short question:

Let $A\in\mathbb R^{N\times N}$ be a symmetric and positive definite matrix, let $y\in \mathbb R^{N}$ and consider $$\alpha^{*} := \text{argmin}_{\alpha\in\mathbb R^{N}} \left\{\alpha^T \left( A^T A + \lambda A\right)\alpha - 2\alpha^T Ay \right\}, \qquad (\star)$$ where $\lambda > 0$. Then Wikipedia (under the Section "Applications") argues that since $A^TA + \lambda A$ is a positive definite matrix, that the Eq. $(\star)$ would have "a single global minima for this expression". Unfortunately, I have troubles understanding this. Yes, $A^T A + \lambda A$ is a positive definite matrix, but why then does the expression $\alpha^T \left( A^T A + \lambda A\right)\alpha - 2\alpha^T Ay$ have a unique gloabal minimum?

Hermi
  • 692
  • It might be useful to examine whether $\alpha^TB\alpha + \alpha^Tv$ has a global minimizer $\alpha$ for positive definite $B$ and arbitrary vector $v$. Basically the quadratic term grows faster than the linear term can drop, no matter which direction you go. – Paul Sinclair May 30 '21 at 23:30
  • Your argumentation is based upon the fact that $\alpha^T B \alpha$ is strictly increasing, i.e., for $\vert\vert \alpha_2\vert\vert_2 > \vert\vert \alpha_1\vert\vert_2$, where $\vert\vert \cdot\vert\vert_2$ denotes the Euclidean norm, we have that $\alpha_2^T B \alpha_2 > \alpha_1^T B \alpha_1$. Is there a way to prove this analytically? The function $F(\alpha) := \alpha^T B \alpha$ is not strictly convex, I think, so I am not sure about the way to go.. – Hermi Jun 01 '21 at 20:16
  • All I've done is suggest that you examine a simplified version of the problem, one that removes certain details that I think obscure what is going on. In this simplified version, I've given you a heuristic argument indicating why the problem has a global minimum (that it is unique is something separate). It follows because if $\alpha = tv$ for some $v$ with $|v| = 1$, then the first term is positive and varies with $t^2$ while the second only varies with $t$. To turn that into a complete proof, you also need to show that the expression is bounded on ${v \mid |v| = 1}$. – Paul Sinclair Jun 01 '21 at 23:37
  • I answered my own question. What do you think? – Hermi Jun 02 '21 at 13:10

1 Answers1

1

Let $B$ be a positive definte matrix. Then we can easily convince ourselves that the Hessian of the function $F(\alpha) := \alpha^T B \alpha - 2 \alpha^T A y$ is given by $2B$, so the Hessian is positive definite as well. This particularly means that $F$ is strictly convex. We can also convince ourselves that $F$ has one single local extremum point (either a local minimum, maximum or saddle point), by solving for $\nabla_{\alpha}F(\alpha) = 0$ and showing that the Hessian matrix is positive semi-definite at this local extremum point, we see that $F$ has a local minimum at this point. Together with $F$ being strictly convex, I believe it shows that $F$ has a unique global minimizer.

Hermi
  • 692