Farkas's lemma for semidefinite programs

730 Views Asked by At

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!

1

There are 1 best solutions below

0
On BEST ANSWER

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.