= Quadratic minimization with a moving upper bound
{title2=$x_*(b)=\min(2,b)$}
Consider the <minimization problem>
$$
V(b)=\min_{x\leq b}(x-2)^2,\qquad b\in\mathbb R.
$$
The <objective function> is a <strictly convex function> with its <unconstrained optimization> minimum at $x=2$. If $b<2$, it decreases throughout the <feasible set> until the bound $x=b$ is reached. If $b\geq2$, the <feasible set> already contains $2$. Hence
$$
x_*(b)=\min(2,b),\qquad V(b)=\bigl(\max(2-b,0)\bigr)^2.
$$
With $g(x)=x-b$, the <optimization Lagrangian> and <KKT conditions> are
$$
L=(x-2)^2+\lambda(x-b),\qquad
x\leq b,\quad \lambda\geq0,\quad
2(x-2)+\lambda=0,\quad \lambda(x-b)=0.
$$
Substituting $x_*(b)$ gives the unique inequality <Lagrange multiplier>
$$
\lambda_*(b)=2\max(2-b,0).
$$
For $b<2$, the <active constraint> has $\lambda_*>0$. For $b>2$, there is strict slack $b-x_*=b-2$ and $\lambda_*=0$. At $b=2$, the <active constraint> has zero <Lagrange multiplier>: the boundary happens to pass through the unconstrained optimum. Feasibility and <complementary slackness> must both be checked; solving only $2(x-2)+\lambda=0$ would allow infeasible candidates.
\Image[/kkt-quadratic-feasible-objective.png]
{title=The same quadratic objective with active, just-touching and inactive upper bounds}
An independent certificate follows by <completing the square>:
$$
L=\left(x-2+\frac{\lambda}{2}\right)^2+\lambda(2-b)-\frac{\lambda^2}{4},\qquad
d_b(\lambda)=\inf_{x\in\mathbb R}L=\lambda(2-b)-\frac{\lambda^2}{4}.
$$
The <Lagrange dual function> is a <concave function> of $\lambda$. Its maximum over $\lambda\geq0$ occurs at $\lambda_*(b)$ and equals $V(b)$. Thus every case has an explicit lower bound attained by a <feasible point>; the <KKT conditions> provide a certificate that can be checked without searching all <real numbers>.
Back to article page
