# What change of variables, if any, transforms this nonconvex problem into a convex one?

I'm looking for a convex reformulation, if any exists, of the following minimisation problem:

Let $A$ be a symmetric, positive definite $n \times n$ matrix, and $b \in \mathbb{R}^n$. Minimise $f(X) = - b^T (A+X)^{-T} X (A+X)^{-1} b$, where $X$ is a symmetric positive semidefinite $n \times n$ matrix.

The following is a plot of $-f$ for a toy version of the problem: $n=2$; diagonal $X$; $A$ and $b$ left unspecified.

By inspection, $-f$ is not even a quasiconvex function of $(X_{11}, X_{22})$. Therefore, quasiconvex-optimisation techniques would not, in general, be applicable.

Although I haven't proved it, my intuition tells me that $f$ does have a unique minimum. This leads me to believe that a complex reformulation of the problem may exist... but I can't find any.

Can you think of some nonlinear change of variables that transform this nonconvex optimisation problem into a convex one?

-
what if you do +0.5 and then square it? – user66081 Jan 14 '14 at 13:52

Making the substitution $Y=(A+X)^{-1}$, the objective becomes $b^T(Y A Y - Y )b$, which is convex in $Y$. The semidefinite constraint $X\succeq 0$ is equivalent to $0 \prec Y \preceq A^{-1}$.

As a bonus, this transformation allows us to solve the problem in closed form. Denoting the transformed objective by $g(Y)$, its gradient is:

\begin{aligned}\nabla g(Y) &= bb^T YA + AYbb^T - bb^T \\ &= b \left(AYb - \frac{1}{2} b\right)^T + \left(AYb - \frac{1}{2} b\right) b ^T\end{aligned}

So the gradient is zero and the variable is feasible if and only if the following conditions hold:

$$Yb=\frac{1}{2} A^{-1}b, \quad 0 \prec Y \preceq A^{-1} \quad \Leftrightarrow \quad XA^{-1}b=b, \quad X \succeq 0$$

Since $g$ is convex, these give sufficient conditions for optimality. Furthermore, solutions to these conditions always exist; one example is given by $Y^* = \frac{1}{2}A^{-1} \Leftrightarrow X^* = A$.

-
Ah, yes, $b^T(YAY-Y)b=\|A^{1/2}Yb\|_2^2-b^TYb$. Good stuff. – Michael Grant Jan 19 '14 at 2:25
Sorry for getting back to you so late. I've only just seen your answer. Thanks a lot for that. Everything you wrote makes sense to me, except this: did you mean $0 \prec Y \preceq A^{-1}$ instead of $0 \preceq Y \preceq A^{-1}$? – Jubobs Jan 27 '14 at 20:08
You're right, my mistake. I corrected the answer and expanded the explanation of the solution space. Hopefully I didn't introduce any new mistakes. – p.s. Jan 28 '14 at 5:57

Minimizing $-x/(x^2+1)$ is equivalent to maximizing $x/(x^2+1)$. Furthermore, maximizing $x/(x^2+1)$ when $x>0$ is equivalent to minimizing $(x^2+1)/x=x+1/x$, which is convex on that positive interval.

-
Thanks, Michael. I should have specified I had thought of that trick. I'm looking for a reparameterisation here, because I'm actually interested in a multivariate version of this optimisation problem. CVX rocks, by the way! – Jubobs Jan 14 '14 at 14:22
Thanks! Then perhaps you should share this larger problem here. It still seems to me that looking for a diffeomorphism is unnecessarily limiting; the space of equivalent models is larger. – Michael Grant Jan 14 '14 at 14:34
Michael, please see my edit. – Jubobs Jan 14 '14 at 17:49
Now we have a more difficult, but also more interesting, problem! – Michael Grant Jan 15 '14 at 2:21
More difficult indeed :) – Jubobs Jan 15 '14 at 10:02