Strict complementary slackness for semidefinite programs with strong duality

Question

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

Answer 1

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.

Answer 2

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.