1
$\begingroup$

One formulation of Farkas's Lemma for semidefinite programs is the following statement:

Let $A_1,\ldots,A_n$ be symmetric $m \times m$ matrices. The system $$ x_1A_1 + \cdots + x_nA_n \succ 0 $$ where $x_i\in\mathbb{R}$ is infeasible iff there exists a symmetric matrix $Y\neq 0$ such that $\mathrm{Tr}(A_i^\top Y) = 0$ for all $i = 1,\ldots,n$, and $Y \succeq 0$, where $A \succ B$ means $A - B$ is positive definite and $A \succeq B$ means $A - B$ is positive semidefinite.

I found this formulation here: http://www.ime.usp.br/~fmario/sdp/lovasz.pdf (page 16).

It appears from the proof that we could strengthen this statement by replacing "$x_1A_1 + \cdots + x_nA_n \succ 0$" with "$x_1A_1 + \cdots + x_nA_n \succeq 0$", but I'm leery of the subtle differences that arise when considering SDPs (as opposed to LPs). Is it also true that $x_1A_1 + \cdots + x_nA_n \succeq 0$ is infeasible iff there exists such a $Y$ as described above?

Thanks!

$\endgroup$
1
  • 1
    $\begingroup$ Small edit: it is imperative that you specify that $Y\neq 0$. Otherwise $Y=0$ is a trivial solution to the dual equations. $\endgroup$ Commented Aug 12, 2014 at 2:02

1 Answer 1

Reset to default
2
$\begingroup$

Believe me, if it could be relaxed, it would have been. But no, you cannot relax the strict inequality in the first LMI. While there are other formulations of the SDP Farkas Lemma, in all of them one of the inequalities is strict. Note also that strong duality does not always hold for semidefinite programs, either (these facts are, of course, related). For example, Section 12.3 from these notes offers this primal/dual pair with a non-zero duality gap: $$\begin{array}{ll} \text{minimize} & y_1 \\ \text{subject to} & \begin{bmatrix} 0 & y_1 & 0 \\ y_1 & y_2 & 0 \\ 0 & 0 & y_1 + 1 \end{bmatrix}\succeq 0\end{array}\qquad \begin{array}{ll} \text{maximize} & -X_{33} \\ \text{subject to} & X_{12}+X_{21}+X_{33}=1 \\ &X_{22} = 0 \\ &X\succeq 0\end{array}$$ I strongly suspect you could find a counterexample to your relaxed Farkas lemma by massaging this example.

$\endgroup$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.