2
$\begingroup$

I am following Lovasz' notes on semidefinite programming and I want to understand the proof of the Strong Duality theorem using the Farkas Lemma. Lovasz only proves one part of it, and I'm trying to figure out the rest.

Let $A_1,\dots,A_m$, and $C$ be $n\times n$ symmetric matrices and let $b\in\mathbb{R}^m$. Consider the semidefinite program \begin{align*} \text{maximize} \hspace{.5cm} & \mathrm{Tr}(XC)\\ \text{subject to}\hspace{.5cm}& X\succeq 0\\ & \mathrm{Tr}(XA_i)=b_i\, \forall i \end{align*} with primal optimal value given by $v_{\text{primal}}$ and its corresponding dual problem \begin{align*} \text{minimize} \hspace{.5cm} & \langle b,y\rangle\\ \text{subject to}\hspace{.5cm}& y\in\mathbb{R}^m\\ & y_1A_1+\cdots +y_mA_m-C\succeq 0 . \end{align*} with dual optimal value given by $v_{\text{dual}}$. By weak duality, it must hold that $v_{\text{primal}}\leq v_{\text{dual}}$.

The primal problem is said to be strictly feasible if there exists a positive definite $X\succ 0$ such that $\mathrm{Tr}(XA_i)=b_i$ for all $i\in\{1,\dots,m\}$. Similarly, the dual problem is strictly feasible if there exists a $y\in\mathbb{R}^m$ such that $\sum_{i=1}^n y_iA_i-C\succ 0$.

The strong duality theorem (see Theorem 3.4 in the notes) can then be stated as follows:

Theorem (Strong Duality for SDPs). Suppose that both $v_{\text{primal}}$ and $v_{\text{dual}}$ are finite. (That is, both the primal and dual problems are feasible.)

  1. If the primal problem is strictly feasible, then $v_{\text{primal}}=v_{\text{dual}}$. Furthermore, there exists a $y\in\mathbb{R}^m$ such that $y_1A_1+\cdots +y_mA_m-C\succeq 0$ and $\langle b,y\rangle = v_{\text{dual}}$.

  2. If the dual problem is strictly feasible, then $v_{\text{primal}}=v_{\text{dual}}$. Furthermore, there exists a $X\succeq 0$ such that $\mathrm{Tr}(XA_i)=b_i$ for all $i$ and $\mathrm{Tr}(XC) =v_{\text{primal}}$.

Lovasz essentially only proves part 2 of this theorem, where he makes use of the semidefinite Farkas Lemma:

Lemma (Farkas, nonhomogeneous semidefinite version). The following are equivalent:

(i) There exists $X\succeq 0$ such that $\mathrm{Tr}(XA_i)=b_i$ for all $i$ and $\mathrm{Tr}(XC)\geq0$.

(ii) For all $y\in\mathbb{R}^m$, it holds that $y_1A_1+\cdots+y_mA_m-C\not\succ 0$.

Lovasz then proves part 2 of the Strong Duality theorem as follows. Note that there cannot exist a $y\in\mathbb{R}^m$ such that $y_1A_1+\cdots+y_mA_m-C\succ 0$ and $\langle b,y\rangle <v_{\text{primal}}$. Hence if we define block matrices $$ A_i' = \begin{pmatrix} A_i& 0\\ 0& b_i \end{pmatrix} \qquad\text{and}\qquad C' = \begin{pmatrix} C& 0\\ 0& -v_{\text{primal}} \end{pmatrix} $$ then for all $y\in\mathbb{R}^m$ it holds that $y_1A'_1+\cdots+y_mA'_m-C'\not\succ 0$. The Farkas Lemma then allows us to find an $X\succeq0$ such that $\mathrm{Tr}(XA_i)=b_i$ for all $i$ and $\mathrm{Tr}(XC)\geq v_{\text{primal}}$. This proves the desired result since $v_{\text{primal}} \geq \mathrm{Tr}(XC)$.

My question: How can we prove part (1) of the Strong Duality theorem using the Farkas Lemma? The statement of the Farkas Lemma given here doesn't help. But is there another version of Farkas Lemma that can be used to prove the other part of strong duality?

Furthermore, can anyone point out another reference that proves both parts of strong duality SDPs (not just one like Lovasz did)? I can't seem to find a nice self-contained proof.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.