Skip to main content
added 16 characters in body
Source Link
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

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 $\rank(X)+\rank(Z)=3<4$$\mathrm{rank}(X)+\mathrm{rank}(Z)=3<4$ and strict complementarity is not satisfied.

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 $\rank(X)+\rank(Z)=3<4$ and strict complementarity is not satisfied.

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.

added 2 characters in body
Source Link
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

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 $\rank(X)+\rank(Z)=3<4$ and strict complementarity is not satisfied.

Studying certain semidefinite programs arising in spectral graph theory, I discovered 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 $\rank(X)+\rank(Z)=3<4$ and strict complementarity is not satisfied.

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 $\rank(X)+\rank(Z)=3<4$ and strict complementarity is not satisfied.

Source Link
M. Winter
  • 13.6k
  • 3
  • 29
  • 70

Studying certain semidefinite programs arising in spectral graph theory, I discovered 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 $\rank(X)+\rank(Z)=3<4$ and strict complementarity is not satisfied.