# Conditions required for strong duality to hold for SDPs

Operations Research Asked on August 19, 2021

According to Wikipedia, strong duality holds when "the primal optimal objective and the dual optimal objective are equal."

What are the necessary conditions for strong duality to hold in semidefinite programming?

I would think this question would be easy to answer with a quick search, but instead I have ended up with many sources saying seemingly slightly different things. Let’s go over them:

1. Lecture notes from CMU course. The relevant section is 12.3.1 The Strong Duality Theorem for SDPs.

Theorem 12.9. Assume both primal and dual have feasible solutions. Then $$v_{text{primal}} ≥ v_{text{dual}}$$,
where $$v_{text{primal}}$$ and $$v_{text{dual}}$$ are the optimal values to the primal and dual respectively. Moreover,
if the primal has a strictly feasible solution (a solution $$x$$ such that $$x succ 0$$ or $$x$$ is positive
definite) then
1) The dual optimum is attained (which is not always the case for SDPs) and
2) $$v_{text{primal}}$$ = $$v_{text{dual}}$$.
Similarly, if the dual is strictly feasible, then the primal optimal value is achieved, and equals
the dual optimal value. Hence, if both the primal and dual have strictly feasible solutions,
then both $$v_{text{primal}}$$ and $$v_{text{dual}}$$ are attained.

The first part of this seems to imply that all you need is for the primal or the dual to have a strictly feasible solution. But then the very last line throws me off as it seems to imply that both need a strictly feasible solution.

2. Lecture notes from Berkeley course. The relevant section is 12.3.2 Strong Duality.

From Slater’s theorem, strong duality will hold if the primal problem is strictly feasible, that
is, if there exist $$X succ 0$$ such that $$langle A_i, X rangle = b_i, i = 1, ldots , m$$.
Using the same approach as above, one can show that the dual of problem (13.5) is
precisely the primal problem (13.2). Hence, if the dual problem is strictly feasible, then
strong duality also holds. Recall that we say that a problem is attained if its optimal set is
not empty. It turns out that if both problems are strictly feasible, then both problems are
attained.

I have the exact same problem with this one. It first seems to say you only need one of the two to be strictly feasible. Then it seems to imply that actually both must be strictly feasible. Or is it possible for strong duality to hold even when one of the two has an empty optimal set? I don’t see how this makes sense.

3. Lecture notes from IIT Kanpur. The relevant section is 4 Extra reading: Strong duality, Slater’s condition.

Theorem 1. Given a semidefinite program in standard form with parameters $$C, A_i , b$$, suppose the feasible
set of primal is $$P$$ and feasible set of dual is $$D$$. Then strong duality holds if either
$$D ne emptyset$$ and there exists a strictly feasible $$X ∈ P$$, i.e., $$X succ 0$$, $$Ai • X = b_i forall i$$
or
if $$P ne emptyset$$ and there exists a strictly feasible $$y in D$$, i.e., $$sum_i y_i A_i – C succ 0$$.

This throws in an extra condition that neither of the previous two have. You need one of the two to be strictly feasible, and you need the other one to simply have some feasible solution.

I have also taken a look at Slater’s condition which seems to imply that you just need either the primal or the dual to be strictly feasible.

Thanks in advance for helping me out! I only know the basics of SDP, so some level of detail would be appreciated. Also, any references to sources that better explain this stuff than the ones above would be appreciated.

The following is from Section 2.2 of Semidefinite Programming for Combinatorial Optimization by Christoph Helmberg. Let's define begin{align*} p^* &= inf{langle C,Xrangle,:,Xtext{ primal feasible}},\ d^* &= sup{langle b,yrangle,:,ytext{ dual feasible}}. end{align*} In particular, $$p^*=infty$$ if the primal is infeasible, $$d^*=-infty$$ if the dual is infeasible, $$p^*=-infty$$ if the primal is unbounded and $$q^*=infty$$ if the dual is unbounded. Then the situation can be summarized as follows (Corollary 2.2.6 in the reference cited above).

1. If the primal is strictly feasible and $$p^*$$ is finite, then $$p^*=d^*$$ and there is a dual solution that achieves this value.
2. If the dual is strictly feasible and $$d^*$$ is finite, then $$p^*=d^*$$ and there is a primal solution that achieves this value.
3. If both the primal and the dual are strictly feasible, then $$p^*=d^*$$ and the value is attained for both problems.

So in order to guarantee $$p^*=d^*$$ it is sufficient that either one of the two problems is strictly feasible, but if we want a primal solution that achieves the value $$p^*$$ we should ask for a strictly feasible solution of the dual.

Correct answer by Thomas Kalinowski on August 19, 2021

## Related Questions

### How to optimize a utility function that contains step function?

1  Asked on January 5, 2022

### How to display the range of coefficients in docplex log?

1  Asked on January 1, 2022 by ehsank

### Scenario based approach to value-at-risk optimization using mixed-integer programming

1  Asked on January 1, 2022

### Multiple Knapsacks with splitting

1  Asked on December 20, 2021 by cesar-canassa

### How to balance the workload of teachers in OR-Tools (maximization of the minimum)

1  Asked on December 18, 2021 by neverletgo

### How to linearize a quadratic constraint to add it then via a callback function

2  Asked on December 9, 2021 by farouk-hammami

### Decision variable transformation in Gurobi

2  Asked on December 5, 2021

### Possibility of indexing decision variables with 2 indices using a set of tuples in Pyomo

3  Asked on November 24, 2021

### View of Constraints and Decision Variables in Pyomo

1  Asked on November 17, 2021

### CPLEX Python API Manual with References

1  Asked on November 4, 2021

### Are Python and Julia used for optimization in industry?

15  Asked on August 19, 2021

### How to improve the quality of code in OR?

3  Asked on August 19, 2021

### How would you characterize “optimization data?”

4  Asked on August 19, 2021 by marco-lbbecke

### How to simulate computational execution time?

2  Asked on August 19, 2021 by matheus-digenes-andrade

### Local optimum of dual of non-linear program

2  Asked on August 19, 2021

### Combinatorial Optimization using AMPL

2  Asked on August 19, 2021 by user3831

### Parallel nonlinear solvers

3  Asked on August 19, 2021 by josh-allen

### Tips on How to Review Operations Research Literature Effectively?

2  Asked on August 19, 2021 by ehsan

### Polynomially solvable cases of zero-one programming

1  Asked on August 19, 2021

### Error evalution for linear fits

1  Asked on August 19, 2021 by jane

### Ask a Question

Get help from others!