= Feasible triangle with a squared-distance objective
{title2=$F=\{(x,y):x\geq0,\ y\geq0,\ x+y\leq3\}$}
Take the decision domain $D=\mathbb R^2$ and minimize the <objective function>
$$
f(x,y)=(x-2)^2+(y-2)^2
\qquad\text{subject to }x\geq0,\quad y\geq0,\quad x+y\leq3.
$$
Each <inequality> permits a <closed half-space>; their intersection is the filled <triangle> with vertices $(0,0)$, $(3,0)$ and $(0,3)$, including its edges. The <feasible region> is a <compact set> and a <convex set>. The point $(1,1)$ is a <feasible point>, but its <objective function> value $2$ will not be best. Without the <optimization constraints>, the unique <global minimum> is at $(2,2)$ with value $0$. That point is infeasible because $2+2>3$.
The <objective function> is the squared <Euclidean distance> from $(2,2)$. Its positive <level sets> are <circles> centered there. Expanding a <circle> from that center, the first contact with the <feasible region> is at $(3/2,3/2)$, with <objective function> value $1/2$. Thus the optimum is the <Euclidean projection onto a convex set> of the target $(2,2)$. Squaring a nonnegative <Euclidean distance> preserves which point is nearest.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§8.1.1, printed p. 398: squared Euclidean projection onto a polyhedron and half-space projection formula]{ref}
\Image[/feasible-triangle-objective-contours.png]
{title=<Feasible triangle with a squared-distance objective>: the first attainable <level set> has value 0.5 at (1.5,1.5)}
Here is a direct certificate, without relying on the picture. Put $s=x+y$ and $d=x-y$. The <objective function> becomes
$$
f(x,y)=\frac{(s-4)^2+d^2}{2}\geq\frac12
\qquad(0\leq s\leq3).
$$
Equality requires $s=3$ and $d=0$, so the unique optimum is $(3/2,3/2)$. At this point $x+y\leq3$ is an <active constraint>, while $x\geq0$ and $y\geq0$ are strict. An <active constraint> identifies a tight restriction at a specified point; it alone does not establish optimality. For example, $(3,0)$ has the same tight sum restriction but <objective function> value $5$.
For a check using the <Karush-Kuhn-Tucker conditions>, write the <inequalities> as $-x\leq0$, $-y\leq0$, $g=x+y-3\leq0$. Their <Lagrange multipliers> at the optimum are $(0,0,1)$. The <gradient> equation is
$$
\nabla f(3/2,3/2)+1\nabla g=(-1,-1)+(1,1)=(0,0).
$$
Feasibility, nonnegative <Lagrange multipliers> and <complementary slackness> also hold. With this <strictly convex function> and affine <optimization constraints>, the <Karush-Kuhn-Tucker conditions> certify the unique <global minimum>.<Convex Optimization by Stephen Boyd and Lieven Vandenberghe>[§5.5.3, printed pp. 243–244, equation (5.49) and sufficiency for convex problems]{ref}
Back to article page
