Strong duality and KKT for SDP with inequality constraints

karush kuhn tuckersemidefinite-programming

The standard form of semidefinite program (SDP) is
\begin{align*}
p^* = \inf C \bullet X\\
s.t. A_i \bullet X = b_i\\
X \succeq 0
\end{align*}
where $C, A_i$ are symmetric matrices. The dual SDP is
\begin{align*}
d^* = \sup y^T b\\
s.t. C – \sum y_i A_i \succeq 0
\end{align*}
It's known (for example, see Ben-Tal & Nemirovski, Lectures on Modern Convex Optimization) that when there exists $X \succ 0$ strictly feasible for the primal, $C – \sum y_i A_i\succ 0$ strictly feasible for the dual, then we have strong duality: optimizers for both problems exist, and $p^* = d^*$. Moreover, a primal dual pair is optimal if and only if it satisfies the KKT condition $X \bullet (C – \sum y_i A_i) = 0$.

My question: do the same results hold for SDP with inequality constraints (i.e., $A_i \bullet X = b_i$ replaced by $A_i \bullet X \leq b_i$)? Specifically, consider the primal
\begin{align*}
p^* = \inf C \bullet X\\
s.t. A_i \bullet X \leq b_i\\
X \succeq 0
\end{align*}
and dual
\begin{align*}
d^* = \sup y^T b\\
s.t. C – \sum y_i A_i \succeq 0\\
y_i \leq 0
\end{align*}
Assume there exists $X \succ 0$ feasible for the primal, and $y_i \leq 0$ such that $C – \sum y_i A_i \succ 0$. Is it true that

  1. optimal solutions for both the primal and dual are achieved
  2. $p^* = d^*$
  3. a primal dual pair $(X, y_i)$ is optimal iff $X \bullet (C – \sum y_i A_i) = 0$?

All of the literature I've seen only discusses strong duality for SDP with equality constraints, so I can't find an answer for my question.

Below are my thoughts: let $X' = \begin{pmatrix}
X & 0\\
0 & D
\end{pmatrix}$, $A_i' = \begin{pmatrix}
A_i & 0\\
0 & V_i
\end{pmatrix}$, $C' = \begin{pmatrix}
C & 0\\
0 & 0
\end{pmatrix}$, where $D$ is diagonal, $V_i$ has a $1$ at $ii$-entry, zero everywhere else. Then the primal can be reformulated as
\begin{align*}
p' = \inf C' \bullet X'\\
s.t. A_i' \bullet X' = b_i\\
X' \succeq 0
\end{align*}
and the dual of this new problem is
\begin{align*}
d' = \sup y^T b\\
s.t. C' – \sum y_i A_i' \succeq 0
\end{align*}
Since $C' – \sum y_i A_i' = \begin{pmatrix}
C – \sum y_i A_i & 0\\
0 & diag(-y_i)
\end{pmatrix} \succeq 0$, we know that $y_i \leq 0$. So this is just the dual of the original SDP.

For strong duality, suppose there exists $X \succ 0$ feasible for the original problem. I'd like to show that there exists $X' \succ 0$ feasible for the new primal. We can take $X' = \begin{pmatrix}
X & 0\\
0 & D
\end{pmatrix}$, with $D$ containing strictly positive diagonal entries. However, this is not going to work unless $A_i \bullet X < b_i$ for all $i$. This is one place where I am stuck.

Another place I'm unsure is the KKT condition. Assuming for now that the above assumption holds. Is it still true that $(X, y_i)$ optimal iff $X \bullet (C – \sum y_i A_i) = 0$? Here's my attempt.

First assume that $(X, y_i)$ is an optimal primal dual pair. Put $d_i = b_i – X \bullet A_i$, $X' = \begin{pmatrix}
X & 0\\
0 & diag(d_i)
\end{pmatrix}$. Then $(X', y_i)$ is an optimal primal dual pair for $p'$ and $d'$. We have
\begin{align*}
0 & = X' \bullet (C' – \sum y_i A_i')\\
& = X \bullet (C – \sum y_i A_i) – \sum y_i d_i
\end{align*}
since $X \succeq 0$, $C – \sum y_i A_i \succeq 0$, $d_i \geq 0$, $y_i \leq 0$, we must have $X \bullet (C – \sum y_i A_i) = 0$ and $\sum y_i d_i = 0$.

Conversely, assume that $X \bullet (C – \sum y_i A_i) = 0$. Put $d_i = b_i – X \bullet A_i$, $X' = \begin{pmatrix}
X & 0\\
0 & diag(d_i)
\end{pmatrix}$. Then
\begin{align*}
X' \bullet (C' – \sum y_i A_i') & = X\bullet( C – \sum y_i A_i) – \sum y_i d_i\\
& = – \sum y_i d_i
\end{align*}
Again, I am stuck at this step.

Best Answer

Brian Borchers' comment addresses the first question, pointing out that Slater's condition requires strict feasibility in all inequalities.

For the second question, the KKT conditions are more than just $X \bullet (C - \sum y_i A_i) = 0$ (stationarity) alone. Wikipedia additionally lists (adapting the general conditions to the case of SDPs, with your notation and sign conventions)

  • Primal feasibility: $d_i(X) = b_i - A_i \bullet X \geq 0$, $X \succeq 0$
  • Dual feasibility: $y_i \leq 0$, $C - \sum y_i A_i \succeq 0$
  • Complementary slackness: $\sum_i y_i d_i(X) = 0$

These, together with stationarity and a constraint qualification (such as Slater's condition), are jointly necessary conditions fulfilled by all optima.

Your proof of $(X, y_i)\text{ optimal }\Rightarrow \mathrm{KKT}(X, y_i)$ (KKT necessary) shows how optimality implies primal and dual feasibility at $X$, and uses it to prove complementary slackness, and then stationarity.

For $\mathrm{KKT}(X, y_i) \Rightarrow (X, y_i)\text{ optimal}$ (KKT sufficient), as you have noted, you need complementary slackness to prove the stationarity of $(X', y_i')$ from the stationarity of $(X, y_i)$. Since stationarity of $(X', y_i')$ alone is sufficient for its equality-constrained problem, whereas inequality-constrained problems require all KKT conditions to be fulfilled, it is not surprising that fulfilling some of the KKT conditions for $(X, y_i)$ does not imply fulfilling the condition for $(X', y_i')$.

As a side note, even for problems with only equality constraints, stationarity and primal feasibility are jointly necessary.

Related Question