= Lagrangian duality for a quadratic threshold
{c}
{title2=$\min_{x\geq4}((x-1)^2+2)=11$}
Choose the one-variable <quadratic program>
$$
\min_{x\in\mathbb R} f(x)=(x-1)^2+2
\qquad\text{subject to }g(x)=4-x\leq0.
$$
Without the <optimization constraint>, the <global minimum> is at $1$. On the <feasible set> $[4,\infty)$, write $x=4+s$ with $s\geq0$: then $f(x)=11+6s+s^2\geq11$. Hence $x_*=4$ is the unique primal optimizer and $p_*=11$.
For any $\lambda\geq0$, <completing the square> in the <optimization Lagrangian> gives
$$
L(x,\lambda)=(x-1)^2+2+\lambda(4-x)
=\left(x-1-\frac\lambda2\right)^2+2+3\lambda-\frac{\lambda^2}{4}.
$$
The inner <minimization problem> is over all <real numbers>, so its unique optimizer is $x_\lambda=1+\lambda/2$. Therefore
$$
q(\lambda)=2+3\lambda-\frac{\lambda^2}{4}
=11-\frac{(\lambda-6)^2}{4},\qquad\lambda\geq0.
$$
The best lower bound is $d_*=11$, attained at $\lambda_*=6$. At $\lambda=2$, the inner optimizer is $2$, which is infeasible for the <primal problem>; nevertheless $q(2)=7$ is a valid lower bound. At $\lambda=9$, the inner optimizer is $5.5$, which is feasible, but $q(9)=8.75$ is weaker than $11$. Feasibility of an inner optimizer alone does not make the bound exact.
\Image[/lagrangian-duality-quadratic-lower-bounds.png]
{title=<Lagrangian duality> finds the quadratic's exact lower bound at multiplier 6}
{description=Left: the <objective function>, three <optimization Lagrangians>, and the shaded <feasible set> $x\geq4$. Dots mark the global minima of the <optimization Lagrangians> over all <real numbers>; each yields a horizontal lower bound. Right: the <concave> <Lagrange dual function> reaches the primal value $11$. All parameters are chosen for this worked example.}
At $(x_*,\lambda_*)=(4,6)$, the <Karush-Kuhn-Tucker conditions> reduce to
$$
4-x_*=0,\qquad \lambda_*\geq0,\qquad
2(x_*-1)-\lambda_*=0,\qquad \lambda_*(4-x_*)=0.
$$
The last equality is <complementary slackness>. The strongest certificate is visible without solving another <optimization> problem: $L(x,6)=(x-4)^2+11$, so every <feasible point> satisfies
$$
f(x)\geq L(x,6)\geq11=f(4).
$$
The same <Lagrange multiplier> simultaneously makes the inner optimizer feasible and removes the slack between $L$ and $f$. This is a <convex KKT optimality certificate>; $x=5$ also verifies <Slater's condition>.
The domain in the inner <infimum> is essential. If one mistakenly keeps $x\geq4$ when computing $q(2)$, the restricted minimum becomes $L(4,2)=11$, whereas the actual <Lagrange dual function> has value $7$. Constraints deliberately retained in $X$ are allowed in a <Lagrangian relaxation>, but that is a different choice of which restrictions to dualize.
Back to article page
