Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

enter image description here

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?

share|cite|improve this question
what if you do +0.5 and then square it? – user66081 Jan 14 '14 at 13:52

2 Answers 2

up vote 2 down vote accepted

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$.

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.