5

I'm studying

$$ F( (x,Q) ) = \langle x,Q^{-1}x\rangle $$

considered over $\mathbb{R}^n\times\mathbb{R}^{n\times n}_+$, where $\mathbb{R}^{n\times n}_+$ is the set of all positive definite $n\times n$ matrices. Here, $\langle x,y\rangle$ stands for the dot product.

I'm trying to prove that $F$ will be convex when considered over this set. That is, it's obvous that $F$ is convex in $x$ with fixed $Q$ (and in $Q$ with fixed $x$), but the trick is to prove that it will be convex with respect to the pair $(x,Q)$. It can be straightforwardly checked for $n=1$ (considering the Hessian), but how can it be done for an arbitrary $n$?

Rodrigo de Azevedo
  • 20,693
  • 5
  • 43
  • 100
Month
  • 83
  • 6
  • 1
    I'm afraid that's not true. Look here: http://math.stackexchange.com/questions/108393/is-the-composition-of-n-convex-functions-itself-a-convex-function – Month Dec 16 '14 at 02:42
  • Well, the dependancy on $Q$ is neither linear or bilinear because of the inversion. – Month Dec 16 '14 at 03:02
  • 2
    Yes, this is known to be convex. I will offer a proof when I get a chance, but the short answer is that you can prove that its epigraph can be represented using a linear matrix inequality. – Michael Grant Dec 16 '14 at 03:15

1 Answers1

4

This seems to be a little trickier than I thought first!

I'll be using the following lemma:

A function $f$ is convex if and only if its epigraph $$\text{epi}(f) = \{(p, t) | \; p \; \text{in domain of} \;f \; \text{and} \; f(p) \leq t\}$$

is a convex set.

Let $f(x, Q) = x^T Q^{-1}x$ with domain $\mathbb{R}^n \times S^n_{++}$ where $S^n_{++}$ is the set of $n$ by $n$ symmetric positive definite matrices over $\mathbb{R}.$ Now, its epigraph is

$$\{((x, Q), t) | \; Q \succ 0, \; x^TQ^{-1}x \leq t\}\stackrel{\text{Schur Complement}}{=}\{((x, Q), t) | \; Q \succ 0, \; \begin{pmatrix} Q & x \\ x^T &t \end{pmatrix} \succeq 0\}.$$ Last condition is an LMI in $(x,Q, t),$ so is convex.

Ehsan M. Kermani
  • 9,078
  • 2
  • 36
  • 54