= Linear optimization on a convex hull
{title2=$\max_{x\in\operatorname{conv}(S)}c^{\mathsf T}x=\max_{s\in S}c^{\mathsf T}s$}
A <linear functional> cannot exceed its best original value by mixing. For a finite nonempty <set> $S$ and $x=\sum_i\lambda_i s_i$ in its <convex hull>,
$$
c^{\mathsf T}x=\sum_i\lambda_i c^{\mathsf T}s_i\leq\max_{s\in S}c^{\mathsf T}s.
$$
Every original point is itself in the <convex hull>, so equality between the two maxima follows. Moreover, a mixture attains the maximum exactly when all its positive weights are assigned to maximizing original points. Multiple maximizers can therefore produce a whole <line segment> or a higher-dimensional region of equally good choices.
For the eight samples above, use the <linear functional> $f(x,y)=x+y$. Its largest sample value is $f(C)=6$, and $C$ is the only maximizing sample. Thus the unique maximum over the whole <convex polygon> is also at $C$. The <line> $x+y=6$ is a <supporting line>: every point of the <convex hull> lies in the <half-space> $x+y\leq6$, and $C$ touches its <boundary>.
The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\leq x\leq4$, $0\leq y\leq3$, but $f(q)=6.3>6$. This single inequality certifies that $q$ is outside the <convex hull>. A weighted mixture could not have a larger <linear functional> value than all its ingredients.
\Image[/convex-hull-linear-support-certificate.png]
{title=A <linear functional> gives both an optimum and a <convex hull> exclusion certificate}
{description=Original eight-point example with objective $x+y$. The orange <supporting line> touches $C=(3,3)$, where the maximum is six. The red point $q=(3.8,2.5)$ has objective value $6.3$, excluding it from the <convex hull> despite lying inside the dotted coordinate-wise box.}
This explains a basic feature of <linear programming>: searching all mixtures of finitely many candidate <vectors> cannot improve the objective beyond the best candidate, though mixing equally good candidates can give more optimal choices. The conclusion depends on <linearity>. For the <concave function> $g(x,y)=-(x-2)^2-(y-1)^2$, the new point $p=(2,1)$ instead attains zero, strictly above its value at every original sample. A nonlinear objective can favor a mixture.
Back to article page
