 Linear optimization on a convex hull

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,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\le 6$, and $C$ touches its boundary.

The point $q=(3.8,2.5)$ passes the coordinate-wise bounds $0\le x\le 4$, $0\le y\le 3$, 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.

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.