3
$\begingroup$

By a theorem of Goldman and Tucker it is known that if a linear program (LP) has a finite valued optimal solution, then there is an optimal primal/dual pair $(x,z)$ satisfying not only complementary slackness (i.e. $x_iz_i=0$), but also strict complementary slackness (i.e. exactly one of $x_i$ and $z_i$ vanishs).

It is known that this property does not carry over to semidefinite programs (SDP). This means, if $(X,Z)$ is an optimal primal/dual pair of an SDP, where $X,Z\in\Bbb R^{n\times n}$ are symmetric positive semi-definite matrices, then we have complementarity (i.e. $XZ=0$), but in general no strict complementarity $\def\rank{\mathrm{rank}}\rank(X)+\rank(Z)=n$.

Now, I am especially interested in SDPs with finite valued optimal solutions and zero duality gap. Is there anything more we can say about strict complementary slackness in the case of strong duality? I actually have never seen an example where it fails, i.e. an example with above properties where all optimal primal/dual pairs $(X,Z)$ lack strict complementarity.

Most of my knowledge about strict complementarity comes from [1] where it is shown that it is a generic property (holds for almost all SDPs in a precise sense). Besides this, strict complementarity was mostly assumed to prove other properties.

[1] F. Alizadeh, J.A. Haeberly, M.L. Overton: Complementarity and nondegeneracy in semidefintie programming

$\endgroup$

2 Answers 2

5
$\begingroup$

Studying certain semidefinite programs arising in spectral graph theory, I discovered a semi-definite primal/dual pair satisfying strong duality but not strict complementarity.

Let $E=\{12,23,34\}$ (the edge set of the path graph $P_3$) and $E^{ij}:=(\mathbf e_i-\mathbf e_j)^\top(\mathbf e_i-\mathbf e_j)$. We use the inner product $ \def\<{\langle}\def\>{\rangle}\<X,Y\>:=\mathrm{tr}(XY)$ on the space of symmetric matrices $\mathbf S^n$.

$$ \llap{\mathrm{(P)}\qquad} \boxed{\begin{array}{rlr} p^*=\max & \sum_{ij\in E} w_{ij} \\ \mathrm{s.t.} & I-\sum_{ij\in E} w_{ij}E^{ij} \succeq0 \\ & w_{ij}\ge 0,\quad ij\in E \end{array}}$$

$$ \llap{\mathrm{(D)}\qquad} \boxed{\begin{array}{rlr} d^*=\min & \mathrm{tr}(X) \\ \mathrm{s.t.} & \<X,E^{ij}\>\ge 1,\quad ij\in E \\ & X\succeq 0 \end{array}}$$

The common optimal value is $p^*=d^*=1$, obtained for

$$w_{12}=w_{34}=\frac12,\quad w_{23}=0,$$

$$X=\frac14\begin{pmatrix} \phantom+1 & -1 & \phantom+1 & -1 \\ -1 & \phantom+1 & -1 & \phantom+1 \\ \phantom+1 & -1 & \phantom+1 & -1 \\ -1 & \phantom+1 & -1 & \phantom+1 \end{pmatrix} = \frac14 (\phantom+1,-1,\phantom+1,-1)^\top(\phantom+1,-1,\phantom+1,-1).$$

Both are the unique solutions of their respective problem (this can easily be seen when interpreting $\mathrm{(D)}$ as an embedding problem, but I will leave this out here). As seen, the dual positive semi-definite matrix $X$ has rank $1$. However, the corresponding matrix

$$Z:=I-\sum_{ij\in E} w_{ij}E^{ij} = \frac12 \begin{pmatrix} 1 & 1 & & \\ 1 & 1 & & \\ & & 1 & 1 \\ & & 1 & 1 \end{pmatrix}$$

is of rank $2$. Hence $\mathrm{rank}(X)+\mathrm{rank}(Z)=3<4$ and strict complementarity is not satisfied.

$\endgroup$
1
$\begingroup$

Take the SDP program

\begin{align*} \min~& x_3\\ s.t.~& X = \begin{bmatrix} x_1 & x_2 & 0 & 0 \\ x_2 & 0 & 0 & 0 \\ 0 & 0 & x_2 & 0 \\ 0 & 0 & 0 & x_3-2 \\ \end{bmatrix}\succeq \mathbf{0}\\ &x_1,~x_2,~x_3\in\mathbf{R} \end{align*} Its dual can be written as follows (see below why). \begin{align*} \max~& 2z_{44}\\ s.t.~& Z= \begin{bmatrix} 0 & 0 & 0 & 0 \\ 0 & a^2+\Delta^2& 0 & a \\ 0 & 0 & 0 & 0 \\ 0 & a & 0 & 1 \\ \end{bmatrix}\\ &Z\succeq 0 \end{align*}

Now notice that any feasible solution $\mathbf{x}$ of the primal satisfies $x_2=0$ because of the zero situated at position $(2,2)$; recall that any SDP matrix $A$ such that $A_{ii}=0$ has only zeros on row and column $i$.

Now check that $X$ and $Z$ share the eigenvector $ \left[\begin{smallmatrix} 0 & 0 & 1 & 0 \\ \end{smallmatrix} \right]^\top$ with eigenvalue 0, which actually answers the question. No linear combination of the rows of $X$ and $Z$ that can be equal to this eigenvector, i.e., the rows of $X$ and $Z$ do not cover the whole space $\implies rank(X)+rank(Z)<n$.

The only detail that remains to be filled is to show that the above expression of the dual is correct. Any feasible $Z$ satisfies $z_{11}=0$ because the coefficient of $x_1$ is zero in the primal objective function. This forces row 1 and column 1 of $Z$ to have only zeros. The dual constraint corresponding to $x_2$ is $2z_{12}+z_{33}=0$; since $z_{12}=0$, we have $z_{13}=0$. The dual constraint corresponding to $x_3$ imposes $z_4=1$. There is no constraint on $z_{24}=a$; $z_{22}$ needs to be greater than or equal to $a^2$ so as to have a non-negative principal minor corresponding to rows/columns 2 and 4; we can write $z_{22}=a^2+\Delta^2$. Finally, both programs have objective value 2.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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