= Positive Lagrangian duality gap on a finite domain
{c}
{title2=$p_*=3,\quad d_*=0$}
A nonconvex <primal problem> can have a positive <duality gap> even when both optima are attained. Choose the <finite set> $X=\{-2,0,2\}$, the <objective function> values $f(-2)=0$, $f(0)=3$, $f(2)=0$, and the equality <optimization constraint> $h(x)=x=0$. The only <feasible point> is $0$, so $p_*=3$.
With unrestricted equality <Lagrange multiplier> $\nu$, the three possible <optimization Lagrangian> values and their <minimum> are
$$
L(-2,\nu)=-2\nu,\qquad L(0,\nu)=3,\qquad L(2,\nu)=2\nu,
\qquad q(\nu)=\min\{-2\nu,3,2\nu\}=-2|\nu|.
$$
The <concave> <Lagrange dual function> has unique maximizer $\nu_*=0$, with $d_*=0$. Thus the <duality gap> is $3$. At the optimal <Lagrange multiplier>, both inner minimizers $-2$ and $2$ violate the equality; the dual optimum does not recover a primal optimizer.
\Image[/lagrangian-duality-finite-domain-gap.png]
{title=A feasible finite problem has a duality gap of 3 despite dual attainment}
{description=Left: three allowed decisions shown as cost versus equality residual. For each indicated <Lagrange multiplier>, the <line> $t=q(\nu)-\nu x$ lies below every allowed cost. The dotted segment joining the two zero-cost points contains cost-residual pairs unavailable to any allowed decision. Right: maximizing $q(\nu)=-2|\nu|$ gives 0, below the primal value 3.}
Why can no slope close the gap? Any <affine function> $a+bx$ lying below the two endpoint costs obeys $a-2b\leq0$ and $a+2b\leq0$. Adding gives $a\leq0$, so its value at residual zero cannot reach the feasible cost $3$. A <convex combination> of the endpoint cost-residual pairs with equal weights has residual zero and average cost zero. This averaged pair is unattainable: the actual decision $x=0$ costs $3$. This geometry explains precisely what the dual bounds fail to distinguish. Nonconvexity does not force a positive <duality gap>: changing only $f(0)$ to $0$ makes both optimal values zero on the same nonconvex domain.
Back to article page
