Closed form solution for the optimization problem

Question

How do I solve the following optimisation problem where $A$ is a PSD matrix ?

$$\max\limits_{x \in \mathbb R^n\setminus \{0\}} \frac{x^T (a_1 -a_2)} { \sqrt{x^TAx}}$$

Is it a concave optimization problem?

Answer 1

This is nothing but the dual norm of the the norm $x \mapsto \|x\|_A:= \langle x, Ax\rangle^{1/2} = \|A^{1/2}x\|_2$ induced by the postive-definite matrix (p.d) $A$, evaluated at the point $a := a_1-a_2$. The value can be computed analytically as $\|A^{-1/2}a\|_2$ and is attained by setting $x = \frac{1}{\|A^{-1/2}a\|_2}A^{-1/2}a$ in the quotient $\langle x, a\rangle /\|x\|_A$. Indeed,

$$ \begin{aligned} \max_{x \ne 0} \frac{\langle x, a\rangle}{(x^TAx)^{1/2}} &= \max_{y \ne 0}\frac{\langle A^{-1/2}y,a\rangle}{\|y\|_2} = \max_{\|y\|_2 \le 1} \langle y, A^{-1/2}a\rangle = \|A^{-1/2}a\|_2. \end{aligned} $$ where we've used the change of variable $y = A^{1/2}x$.

In particular, we've shown that the dual of the norm induced by a p.s.d matrix is the norm induced by it's inverse. That is, that induced norms $\|.\|_A$ and $\|.\|_{A^{-1}}$ are duals to each other.

N.B. Your problem doesn't make sense if $A$ is not strictly positive-definite, because for positive semi-definite matrices, the denominator $x^TAx$ can be equal zero for non-zero $x$.

Answer 2

Since $A$ is positive definite, it's convenient to use the Cholesky factorization of $A$ to write $A$ as $A=R^{T}R$. Then, let $z=Rx$. After solving for $z$, you can recover $x$ with $x=R^{-1}z$. This change of variables is often very helpful with problems involving $\sqrt{x^{T}Ax}$.

Next, solve $c^{T}R=(a_{1}-a_{2})^{T}$ to obtain a vector $c$.

Your problem can now be written as

$\max_{z \neq 0} \frac{c^{T}z}{\| z \|_{2}} $

You can scale any non-zero $z$ by a positive scaling factor without changing the value of the fraction $c^{T}z/\| z \|_{2}$. Thus without loss of generality, you can scale the solution so that $\| z \|_{2}=1$.

We can rewrite the problem as

$\max c^{T}z$

subject to

$\| z \|_{2}=1$.

The solution to this problem is obviously $z=c/\| c \|_{2}$. You can then convert $z$ back into $x$. Any positive multiple of that solution will also be optimal.