Convex combination and lp's

[CarmineCortez]

Homework Statement

The question is "Show that in the case of any linear program, every convex combination of optimal extreme points is optimal."

Homework Equations

ok so if (x_1,...,x_n) is a list of the optimal points then
a_1(x_1)+ ...+a_n(x_n) is the convex combination st a_i>0 and sum of a's is 1

so the convex combination spans the list of optimal points.
their dimensions are the same so the convex combination is a basis for the optimum points...

The Attempt at a Solution

is this the right idea, i don't see how to show EVERY convex combinaiton is optimal

 

[mighty2000]

Thank you for your question regarding the optimality of convex combinations in linear programming. I am happy to assist you in understanding this concept.

Firstly, your idea is on the right track. It is true that a convex combination of optimal extreme points will also be an optimal solution. However, to fully prove this statement, we need to use some mathematical reasoning.

Let's start by defining what we mean by an optimal solution in linear programming. An optimal solution is a point that satisfies all the constraints of the problem and also maximizes (or minimizes) the objective function. In other words, it is the best possible solution that meets all the given conditions.

Now, let's consider a linear program with n optimal extreme points, as given in your question. Let's label these points as x_1, x_2, ..., x_n. As you correctly stated, any convex combination of these points can be written as a linear combination of the form a_1x_1 + a_2x_2 + ... + a_nx_n, where a_i>0 for all i and the sum of the coefficients a_i is equal to 1.

Now, let's suppose there exists another solution, say y, that is better than this convex combination. This means that y satisfies all the constraints and has a better objective function value than the convex combination. Since y is a better solution, it must also be an optimal solution.

But, we know that the convex combination also satisfies all the constraints and its objective function value is a weighted average of the objective function values of the optimal extreme points. Therefore, it is impossible for y to be a better solution than the convex combination, as the convex combination is a combination of the best possible solutions. This contradiction proves that the convex combination is also an optimal solution.

In conclusion, we have shown that any convex combination of optimal extreme points is also an optimal solution. This is because the convex combination satisfies all the constraints and its objective function value is a weighted average of the objective function values of the optimal extreme points. Therefore, it is impossible for any other solution to be better than the convex combination. I hope this explanation helps you understand the concept better.