0
$\begingroup$

I have the following minimization problem

$$\text{minimize} \quad f(x)= c^T F(x)^{-1} c$$

where $F : \mathbb R^n \to \mbox{Sym}_m (\mathbb R)$,

$$\mbox{dom} f = \{x \in \mathbb{R}^n \mid F(x) \succ 0 \}$$

and $c \in \mathbb{R}^m$. The task is to reformulate as an SDP.

I kind of know that I should use the Schur complement, but still not sure. This is my guess:

max. $ a $

s.t. $\begin{bmatrix} F(x) & c \\ c^T & a \end{bmatrix} \succ 0 $

$\endgroup$
2
  • $\begingroup$ If you maximize $a$, the "optimal" solution will be $\infty$. Is that what you want? You kinda know you should use the Schur complement because someone told you to? How about working it out? $\endgroup$ Commented Oct 17, 2019 at 22:25
  • 1
    $\begingroup$ Introduce a new optimization variable and write the minimization problem in epigraph form. $\endgroup$ Commented Oct 18, 2019 at 6:09

1 Answer 1

2
$\begingroup$

You can reformulate the problem by introducing a slack variable. Your problem is actually the following constrained optimization problem: $$\begin{array}{ll} \min_x & c^T F(x)^{-1}c \\ \text{subject to}& F(x)\succ 0. \end{array}$$

By introducing a slack variable $a$, you have the following problem: $$\begin{array}{ll} \min_{x,a} & a \\ \text{subject to} & F(x) \succ 0 \\ & c^\top F(x)^{-1} c \leq a. \end{array}$$

As you mentioned, you can apply the Schur complement to reformulate the two constraints as a single matrix inequality: $$\begin{cases} F(x) \succ 0 \\ c^\top F(x)^{-1}c - a \leq 0 \end{cases} \Rightarrow \begin{bmatrix} F(x) & c \\ c^\top & a \end{bmatrix} \succ 0$$

Hence, your problem can be reformulated as an optimization problem with a matrix inequality constraint: $$\begin{array}{ll} \min_{x,a} & a \\ \text{subject to} & \begin{bmatrix} F(x) & c \\ c^\top & a \end{bmatrix} \succ 0. \end{array}$$

If the function $F(x)$ is affine in $x$, the constraint becomes a linear matrix inequality in decision variables $x$ and $a$. Therefore, the reformulated problem is an SDP.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .