Convex combination of extreme points

Question

The question asks me to "show that if the optimal value of the objective function of a linear programming problem is attained at several extreme points, then it is also attained at any convex combination of these extreme points."

I try to write a convex combination of all extreme points $$f=c_1x_1+…+c_nx_n.$$ However, a theorem of extreme point is that "not a convex combination of other points". This makes me confused. If a convex combination can not be an extreme point then how can I get the optimal value of the objective function？

Note that your objective function is linear in its arguments. Also note that the $c_k \ge 0$, $1\le k \le n$ and that $\sum_kc_k = 1$. — ncmathsadist, Jan 27 '18 at 22:51
A non extreme-point could be optimal as long as it was feasible and had the optimal objective value. — Brian Borchers, Jan 27 '18 at 22:57

score 0 · Accepted Answer · answered Jan 28 '18 at 15:42

Note: I changed your notations to more sensible ones.

Suppose $x^{(j)}, j \in \{1,N\}$ are such extreme points at which optimal value of the objective function $f$ is attained. Denote such optimal value $M = f(x^{(j)})$. Let $c = (c_1,\dots,c_n)^T$. Then $f(x) = \sum_{i=1}^n c_ix_i = c^T x$. Now let $x = \sum_{j = 1}^N \lambda_j x^{(j)}$ be a convex combination of $\{x^{(1)},\dots,x^{(N)}\}$ with $\lambda_j \ge 0$ and $\sum_{j=1}^N \lambda_j = 1$.

\begin{align} f(x) &= f\left( \sum_{j=1}^N \lambda_j x^{(j)} \right) \\ &= c^T \left( \sum_{j=1}^N \lambda_j x^{(j)} \right) \\ &= \sum_{j=1}^N \lambda_j c^T x^{(j)} \tag{$v \mapsto c^Tv$ is linear} \\ &= \sum_{j=1}^N \lambda_j f\left( x^{(j)} \right) \\ &= \sum_{j=1}^N \lambda_j M \\ &= M \tag{$\sum_{j=1}^N \lambda_j = 1$} \end{align} This confirms the first statement in the question body: any convex combination of "optimizers" is also an "optimizer".

Next, to address OP's doubt.

However, a theorem of extreme point is that "not a convex combination of other points". This makes me confused. If a convex combination [of two or more points in the feasible region] cannot be an extreme point then how can I get the optimal value of the objective function？

Optimal points and extreme points are two concepts. The former can be either finitely are infinitely many, but the later is finitely many (as long as the dimension of the feasible region is finite). From the Fundamental Theorem of Linear Programming, an LPP has optimal feasible solution if and only if it has optimal solution at the extreme points in the feasible region. Since we only have finitely many such extreme points, we can use an algorithm (notably the simplex algorithm) to find the optimal value of the objective function.

Convex combination of extreme points

1 Answers1

Linked

Related