= Equality slice of a feasible triangle
{title2=$F\cap\{(x,y):x-y=1\}$}
Keep the <feasible triangle with a squared-distance objective>, but add the <equation> $x-y=1$. An equality requires an exact relation, whereas an <inequality> allows a range. Here the equality selects a <line>, and intersecting that <line> with the original <feasible region> leaves just the <line segment> from $(1,0)$ to $(2,1)$:
$$
(x,y)=(t+1,t),\qquad0\leq t\leq1.
$$
The lower bound comes from $y\geq0$; the upper bound comes from $x+y=2t+1\leq3$. This is a nonempty <closed set> even though it has empty <interior> in the plane. An equality can reduce the <dimension> of the allowed decisions without making the <feasible region> empty.
The old optimum $(1.5,1.5)$ violates the added equality. On the surviving <line segment>, the <objective function> is
$$
q(t)=(t-1)^2+(t-2)^2=2(t-3/2)^2+1/2,
\qquad q'(t)=4t-6<0\quad(0\leq t\leq1).
$$
The <derivative> shows that the unique <global minimum> is at $t=1$, giving $(x,y)=(2,1)$ and value $1$. The nearest point on the entire equality <line> would be $(2.5,1.5)$, at $t=1.5$ with value $0.5$, but it violates $x+y\leq3$. Both the equality and the original <inequalities> must hold simultaneously.
\Image[/feasible-triangle-equality-slice.png]
{title=<Equality slice of a feasible triangle>: the allowed <line segment> ends at the optimum (2,1), while the nearest point on the entire <line> is infeasible}
Use $g=x+y-3$ and $h=x-y-1$ to fix the multiplier sign convention in the <optimization Lagrangian> $L=f+\lambda g+\nu h$; the <Lagrange multipliers> of $-x$ and $-y$ are again zero. At $(2,1)$, <Karush-Kuhn-Tucker conditions> hold with $\lambda=1$ and $\nu=-1$:
$$
\nabla f(2,1)+\lambda\nabla g+\nu\nabla h
=(0,-2)+(1,1)-(1,-1)=(0,0).
$$
The <Lagrange multiplier> of an equality has no nonnegativity restriction. For an independent global certificate, <completing the square> gives $f+g-h=(x-2)^2+(y-1)^2+1$. On the <feasible set>, $h=0$ and $g\leq0$, so $f\geq1$, with equality exactly at $(2,1)$.
Back to article page
