Take the 2-minute tour ×
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|improve this question
    
what if you do +0.5 and then square it? –  user66081 Jan 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|improve this answer
    
Ah, yes, $b^T(YAY-Y)b=\|A^{1/2}Yb\|_2^2-b^TYb$. Good stuff. –  Michael Grant Jan 19 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 at 20:08
1  
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 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|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 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 at 14:34
    
Michael, please see my edit. –  Jubobs Jan 14 at 17:49
    
Now we have a more difficult, but also more interesting, problem! –  Michael Grant Jan 15 at 2:21
    
More difficult indeed :) –  Jubobs Jan 15 at 10:02

Your Answer

 
discard

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.