Convex Combination of Optimal Solutions¶

Proposition¶

If $\boldsymbol{x}^{(1)},\ldots,\boldsymbol{x}^{(k)}$ are optimal solutions of the same LP and $\alpha_j\ge0$ with $\displaystyle \sum_{j=1}^k\alpha_j=1$ $1$ , then

\boldsymbol{x}=\sum_{j=1}^k\alpha_j\boldsymbol{x}^{(j)}

is also optimal. Such a weighted average is a convex combination.

Interpretation¶

The proposition says that optimal solutions of a linear program never come as an isolated pair: if two points are optimal, so is every point on the segment between them. A convex combination is a weighted average with nonnegative weights that add up to $1$ , and for two points these averages fill exactly that segment.

The feasible pentagon with two optimal corners (0, 80) and (20, 60) and the point (15, 65) on the edge between them, a convex combination that is also optimal.

With objective $2x_s+2x_t$ the optimal objective line lies along the edge from $\boldsymbol{x}^{(1)}=(0,80)$ to $\boldsymbol{x}^{(2)}=(20,60)$ $(20, 60)$ , so both corners have value $160$ . The marked point $(15,65)=\tfrac{1}{4}\boldsymbol{x}^{(1)}+\tfrac{3}{4}\boldsymbol{x}^{(2)}$ lies three quarters of the way from $(0,80)$ towards $(20,60)$ , and its value $2\cdot15+2\cdot65$ is again $160$ .

For any $\alpha\in[0,1]$ the mixture $\alpha \boldsymbol{x}^{(1)}+(1-\alpha)\boldsymbol{x}^{(2)}$ of the two optimal corners is feasible and has the same optimal $z$ .

Two facts make this work, shown for weights $\alpha$ and $1-\alpha$ $α$ . If both points satisfy a constraint $\displaystyle \sum_ja_jx_j\le b$ $b$ , multiplying the two inequalities by $\alpha$ and $1-\alpha$ and adding them shows that the average satisfies it too. This needs nonnegative weights, since multiplying an inequality by a negative number reverses it. And because the objective is linear, the value of the average is the same average of the two values, again the optimum $z^*$ .

Hence an LP has no optimal solution, exactly one, or infinitely many, never exactly two: multiple optimal solutions fill at least a whole segment. The argument needs continuous variables: $\max(x_1+x_2)$ with $x_1+x_2\le1$ and binary $x_1,x_2$ is an integer program with exactly the two optimal solutions $(1,0)$ and $(0,1)$ , since their midpoint $(\tfrac{1}{2},\tfrac{1}{2})$ is not allowed.

Key Results¶

Weights must be nonnegative and sum to one.
For two points use $\alpha$ and $1-\alpha$ $α$ , with $0\le\alpha\le1$ $1$ .
The property concerns continuous LP feasibility; averaging integer solutions need not preserve integrality.

Examples¶

For the illustrated objective $2x_s+2x_t$ $2 x_{t}$ , the edge between $(0,80)$ and $(20,60)$ is optimal with value 160. The displayed combination $\tfrac{1}{4}(0,80)+\tfrac{3}{4}(20,60)=(15,65)$ has the same value. In general, the combined value is $\displaystyle \sum_j\alpha_jz^*=z^*$ $z^{*}$ .

Combining $(5,0)$ and $(3,4)$ gives $(3+2\alpha,4-4\alpha)$ $4 α)$ , all with value 20.
Combining $(2,3)$ and $(0,6)$ gives $(2\alpha,6-3\alpha)$ $3 α)$ ; $\alpha=1/2$ gives $(1,9/2)$ .

Prerequisites¶

Multiple Optimal Solutions
Weighted averages

Sources¶

OR Modelling · Week 3

Symbols: alpha, element of, sum

Last updated: 20 October 2026 03:02