1
$\begingroup$

In example 3.4 of Stephen Boyd & Lieven Vandenberghe's Convex Optimization, it is mentioned that the last condition of

$$\text{epi} = \left\{ (x,Y,t) \mid Y \succ 0, x^T Y^{-1} x \leq t \right\}$$

is a linear matrix inequality (LMI) in $(x,Y,t)$. However the linear matrix inequality is written as (in Eq. 2.11 of same book)

$$A(x) = x_1 A_1 + x_2 A_2 + \cdots + x_n A_n \preceq B$$

where $A_i$ and $B$ are symmetric matrices. How to show that $x^TY^{-1}x\leq t$ is a linear inequality in $(x,Y,t)$? Any help in this regard will be much appreciated. Thanks in advance.

$\endgroup$
2
$\begingroup$

Using the Schur complement [JG'10], if $\rm Y \succ O$ then $t - \rm x ^\top Y^{-1} x \geq 0$ is equivalent to the LMI

$$\begin{bmatrix} \mathrm Y & \mathrm x\\ \mathrm x^\top & t\end{bmatrix} \succeq \mathrm O$$


[JG'10] Jean Gallier, The Schur complement and symmetric positive semidefinite (and definite) matrices, December 10, 2010.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. But in the book the definition of LMI is as given in the second equation of my post. $\endgroup$ May 31 '18 at 9:40
  • $\begingroup$ I mean how the generalized inequality that you mentioned in your answer turns into the second generalized inequality in my post $\endgroup$ May 31 '18 at 9:43
  • 1
    $\begingroup$ If $\rm Y$ is $2 \times 2$, then $$\begin{align} \begin{bmatrix} y_{11} & y_{12} & x_1\\ y_{12} & y_{22} & x_2\\ x_1 & x_2 & t\end{bmatrix} &= y_{11} \begin{bmatrix} 1 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 0\end{bmatrix} + y_{12} \begin{bmatrix} 0 & 1 & 0\\ 1 & 0 & 0\\ 0 & 0 & 0\end{bmatrix} + y_{22} \begin{bmatrix} 0 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & 0\end{bmatrix} +\\\\\ &\,\, + x_{1} \begin{bmatrix} 0 & 0 & 1\\ 0 & 0 & 0\\ 1 & 0 & 0\end{bmatrix} + x_{2} \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 1\\ 0 & 1 & 0\end{bmatrix} + t \begin{bmatrix} 0 & 0 & 0\\ 0 & 0 & 0\\ 0 & 0 & 1\end{bmatrix}\end{align}$$ $\endgroup$ May 31 '18 at 9:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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