0
$\begingroup$

Given some optimization problem

$$\min_{x \in S \subset \mathbb{R}^n} f_0(x) \quad \text{s.t.} \quad f_i(x) \leq 0, \quad 1\leq i\leq m$$

we can find the dual problem

$$\max_{\lambda\in\mathbb{R}^m} g(\lambda) \quad \text{s.t.} \quad \lambda \geq 0$$

Now, Slater's condition says if the primal is strictly feasible and convex, we have the optimal value of the primal problem equal to the optimal value of the dual problem. However, it does not say anything about attainment. The proof I'm aware of basically relies on a version of separating hyperplane and treating the dual variable as supporting hyperplanes, so attainment is not directly implied.

Now I have also heard that if we assume that the primal optimal is attained, then the dual optimal is attained as well (and equal by strong duality). However, I am not sure whether this is something special for slaters' condition, or does it hold in general whenever strong duality holds, or even more broadly when we have a duality gap?

This has been bothering me for some time, and it has finally shown up in research where I have to be precise. This is a very basic question, but based on my previously unsuccessful trend of asking on stack exchange of optimization problems, I decided to post here to attract more attention.

Also, in general, the dual of the dual might not be the primal (as the dual is always convex), so I guess even if this is true under strong duality, I'm not sure how to conclude dual optimal attained implies primal optimal attained

Improve this question
$\endgroup$
3
  • $\begingroup$ This is not true: the primal optimal value can be attained without the dual optimum being attained. For example, the semidefinite program "minimize $x$ subject to $\begin{bmatrix}x & 1 \\ 1 & y\end{bmatrix}$ being positive semidefinite" has optimal value $0$, that $0$ is not attained, but the optimal value of its dual is also $0$ and is attained. I'm not sure where examples like this first appeared, but it'd be worth checking Lovasz's notes on SDPs. $\endgroup$
    – Nathaniel Johnston
    Commented Dec 19, 2023 at 23:42
  • $\begingroup$ @NathanielJohnston Thank you for the example! Do you mean this note? Also, I guess strong duality is not sufficient, but what about slater's condition? In this case, I think the dual program does not have an interior point. $\endgroup$
    – patchouli
    Commented Dec 20, 2023 at 0:58
  • $\begingroup$ Just for reference to myself, slater's condition implies the dual optimal is attained, this result is in Stephen Boyd's Convex Optimization $\endgroup$
    – patchouli
    Commented Mar 14 at 17:19

0

Reset to default

You must log in to answer this question.