Find the minimizer of over $t\in [0,1]$ $\phi((1-t)x+t\frac{Ax}{\|Ax\|})$, where $A$ is positive semidefinite and $\phi$ is quadratic.

Question

Let $A$ be a positive semidefinite matrix, and define the following quadratic form $$\phi(x):=-\dfrac{1}{2}x^{\intercal}Ax.$$ I want to compute the following minimizer: $$\arg\min_{t\in [0,1]}\phi\Big((1-t)x+t\dfrac{Ax}{\|Ax\|_{2}}\Big),\ \text{where}\ \|x\|_{2}\leq 1.$$

---

We define $g(t):=\phi((1-t)x+t\frac{Ax}{\|Ax\|_{2}})$. My idea is to simply write it out and compute the derivative. Note that $$-2g(t)=(1-t)^{2}x^{\intercal}Ax+2t(1-t)\|Ax\|+t^{2}\dfrac{x^{\intercal}AAAx}{\|Ax\|^{2}}.$$ Hence, $$-2\dfrac{dg}{dt}=-2(1-t)x^{\intercal}Ax+2(1-2t)\|Ax\|+2t\dfrac{x^{\intercal}AAAx}{\|Ax\|^{2}}.$$

I don't know how to solve $\frac{dg}{dt}=0$... Am I heading the wrong way?

Answer 1

From the definition of concave function: for any $x,y\in V$, $\phi$ is concave iff $$ \phi(tx + (1-t)y)\geq t\phi(x) + (1-t)\phi(y), $$ and equality occurs at $t = 0$ or $t = 1$. It is well known that $x^TAx$ is convex iff $A$ is PSD, thus $-x^TAx$ is concave. From all of this, we can conclude that the minimum occurs at either $x$ or $\frac{Ax}{\|Ax\|}$.

EDIT: since the OP asked, in fact the minimum occurs precisely at $\frac{Ax}{\|Ax\|}$. To prove this, note that $$ g'(t)=\nabla\phi(x + t(Ax/\|Ax\|-x))^T(Ax/\|Ax\|-x)=\\= -(x + t(Ax/\|Ax\|-x))^TA(Ax/\|Ax\|-x)=\\=-t\left(\frac{Ax}{\|Ax\|} - x\right)^TA\left(\frac{Ax}{\|Ax\|} - x\right)-x^TA\left(\frac{Ax}{\|Ax\|} - x\right). $$ This is an affine decreasing function, so it suffices to prove that $g'(0) \leq 0$, or that $x^TAx\leq\|Ax\|$, which is true from the Cauchy-Schwarz inequality, since $\|x\|\leq 1$. Therefore $g'(t)\leq 0$ for all $t\in[0,1]$, which implies that $g(t)$ is decreasing in $t$, establishing that $g(1)\leq g(0)$, or in other words that $\frac{Ax}{\|Ax\|}$ is the minimizer.

Answer 2

Here is a proof that the minimizer is attained at $t = 1$. The other answer already shows that the minimizer is attained at $t = 0$ or $t = 1$.

For a positive semidefinite matrix $A$ and a vector $x$ (not normalized), we have to show that $$ (x^\top A x) (x^\top A^2 x) \le (x^\top x) (x^\top A^3 x). $$ We make an Eigen decomposition of $A$, i.e., $$ A = \sum_i \lambda_i v_i $$ and get $x = \sum_i \xi_i v_i$. By using $\eta_i = \xi_i^2$, it remains to show \begin{equation} (\sum_i \eta_i \lambda_i) (\sum_i \eta_i \lambda_i^2) \le (\sum_i \eta_i) (\sum_i \eta_i \lambda_i^3). \qquad(1) \end{equation} For this, we can utilize Hölder's inequality \begin{align*} \sum_i \eta_i \lambda_i &= \sum_i (\eta_i^{2/3}) (\eta_i^{1/3} \lambda_i) \\ &\le (\sum_i(\eta_i^{2/3})^{3/2})^{2/3}) (\sum_i (\eta_i^{1/3} \lambda_i)^3)^{1/3} \\ &= (\sum_i \eta_i)^{2/3} (\sum_i \eta_i \lambda_i^3)^{2/3}. \end{align*} Similarly, $$ \sum_i \eta_i \lambda_i^2 \le (\sum_i \eta_i)^{1/3} (\sum_i \eta_i \lambda_i^3)^{1/3}. $$ Multiplication of both inequalities yields (1).