[Math] When do constraint qualifications imply strong duality

convex optimizationkarush kuhn tuckeroptimization

Assumptions / Conventions

I am interested in problems of the form

$$ \inf_{x \in \mathbb{R}^n} ~ f_0(x) ~:~ f_i(x) \leq 0 ~\forall ~i \in [m], ~~ g_i(x) = 0 ~\forall ~i \in [k]$$

where $f_i$ are convex and differentiable, and $g_i$ are affine. I will use the convention that $\lambda \in \mathbb{R}^m_+$ are the dual variables associated with the inequality constraints, and $\mu \in \mathbb{R}^k$ are the dual variables associated with the equality constraints.

Slater's condition for strong duality says that if there is a point $x \in \mathbb{R}^n$ such that $f_i(x) < 0 ~\forall~i\in [m]$ and $g_i(x) = 0 ~\forall~i \in [k]$, then (1) primal and dual optimal solutions are attained, and (2) strong duality holds for the primal and dual problems.

High Level Question

Slater's condition is often referred to as "constraint qualification," but it's the only instance of constraint qualification I can find that implies strong duality.

Assuming we're working with an optimization problem of the form stated above, are there other constraint qualification conditions that imply strong duality? (Ignoring Sion's Theorem; see below.)

What I've looked into so far

Sion's Minimiax Theorem

Since I have assumed that the primal problem is convex, the most general result I can find on strong duality is Sion's theorem. Sion's theorem would imply strong duality if at least one of the primal feasible regions and dual feasible regions was compact. This is a powerful result, but I wonder if we can relax the assumptions to simply stating that the primal optimal solution is attained (perhaps also the dual optimal solution).

Someone on Math.SE has conjectured that if primal and dual optima are attained (perhaps also with the assumption that the optimizers form a compact set) then the result of Sion's theorem would still hold.

So I'm mostly unclear about if we can ensure strong duality while only checking properties of the primal problem, even when the primal feasible region is not a compact set.

LICQ and a some nitty-gritty questions

I've been looking into linearly independent constraint qualification (LICQ) to to offer some additional regularity. For convex problems, LICQ ensures that

  • $x^\star$ is primal optimal iff there exists $(\lambda,\mu) \in \mathbb{R}^m_+ \times \mathbb{R}^k$ such that $(x^\star,\lambda,\mu)$ satisfy the KKT conditions, and
  • if $x^\star$ is primal optimal, then there exist unique $\lambda,\mu$ such that $(x^\star,\lambda,\mu)$ satisfy the KKT conditions.

These properties lead me to the following questions:

  1. If $x^\star$ is primal optimal and LICQ holds, are the corresponding $\lambda$ and $\mu$ (arising from KKT conditions) dual optimal? What if we assume that $x^\star$ is unique?
  2. If primal and dual optima are attained when the primal problem satisfies LICQ, does strong duality hold? What if we assume that $x^\star$ is unique?

Best Answer

This is not a full answer, but it is relevant information. P. 30 of Convex Analysis and Nonlinear Optimization by Borwein and Lewis states:

...we need to impose a regularity condition or "constraint qualification", an approach which is another recurring theme. The easiest such condition in this context is simply the linear independence of the gradients of the active constraints $\{ \nabla g_i(\bar x) \mid i \in I(\bar x) \}$. The culminating result of this section uses the following weaker condition.

Assumption 2.3.7 (The Mangasarian-Fromovitz constraint qualification) There is a direction $d$ in $E$ satisfying $\langle \nabla g_i(\bar x), d \rangle < 0$ for all indices $i$ in the active set $I(\bar x)$.

Later, on p. 45, the book states that if the functions $f$ and $g_1,\ldots,g_m$ are differentiable at $\bar x$ then:

in this case it is easy to see that the Slater condition is equivalent to the Mangasarian-Fromovitz constraint qualification (Assumption 2.3.7).

Related Question