4
$\begingroup$

I'm taking my first class in Linear Programming. The book I am reading from is good in that it uses a lot of examples, but bad in that it provides few proofs. I need a proof for the following theorem.

Theorem:

If the constraint set $S$ of a canonical maximization or a canonical minimization linear programming problem is bounded, then the maximum or minimum value of the objective function is attained at an extreme point of $S$.

Glossary of Terms:

Definition 1

The problem

Maximize $f(x_1,x_2,\cdots,x_n)=c_1x_1+c_2x_2+\cdots+c_nx_n$

Subject to $a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n\leq b_1$

$a_{21}x_1+a_{22}x_2+\cdots+a_{2n}x_n \leq b_2$

$\cdots$

$a_{m1}x_1+a_{m2}x_2+ \cdots + a_{mn}x_n \leq b_n$

$x_1,x_2, \dots, x_n \geq 0$

is said to be a canonical maximization linear programming problem. The definition for minimization is analogous.

Definition 2

Let $x= (x_1,x_2,\cdots ,x_n), y=(y_1,y_2,\cdots ,y_n)\in$ R$^n$. Then $tx+(1-t)y$ for $0\leq t\leq 1$ is said to be the line segment between $x$ and $y$ inclusive.

Definition 3

The set of all points $(x_1,x_2, \cdots, x_n)$ satisfying the constraints of the canonical maximization problem is said to be the constraint set

Definition 4

Let $S$ be a subset of R$^n$. $S$ is said to be convex if, whenever $x$=$(x_1,x_2,\cdots,x_n)$,$y$$=(y_1,y_2,\cdots,y_n)\in S$, then

$tx+(1-t)y \in S$ for $0\leq t \leq 1$

Definition 5

A subset $S$ of R$^n$ is said to be bounded if there exists $r\geq 0$ such that every element of $S$ is contained in the closed ball of radius $r$ centered at the origin. A subset of R$^n$ is unbounded if it is not bounded.

Definition 6

The function $f(x_1,x_2,\cdots,x_n)$ is called the objective function of a canonical linear programming problem.

Definition 7

Any element of the constraint set is said to be a feasible point or feasible solution. Any feasible solution which maximizes/minimizes the objective function is said to be an optimal solution.

My Work

I genuinely have no idea how to do this problem. It wasn't assigned as homework, I just want to understand the reasoning behind it because that will help me do better in my course.

$\endgroup$
4
  • 1
    $\begingroup$ Need one more definition "extreme point". $\endgroup$
    – coffeemath
    Jan 15, 2016 at 17:27
  • $\begingroup$ @coffeemath I have added it under Definition 7. Apologies for the delay, I posted this question right before a lecture. $\endgroup$ Jan 15, 2016 at 18:30
  • $\begingroup$ A gaphical representation may help as in here:maaw.info/TOCClassProblem2.htm $\endgroup$
    – NoChance
    Jan 15, 2016 at 20:09
  • $\begingroup$ How I convince my freshman non-math major students(we only do 2 variable LP so I will use a plane section): I bring in a big piece of cardboard and chop it up so it looks like a feasible set. Then I mention that the objective function can be thought of as slanting the piece of cardboard(so embedding the feasible set in R^3 with the z coordinate given by the output of the Objective function). Could the highest point be anywhere other than a corner? This is non-rigorous, but intuitive(I hope). $\endgroup$ Jan 15, 2016 at 20:13

1 Answer 1

4
$\begingroup$

This is due to the fact that the function you are optimizing is linear, and defined on a compact space.

To understand why this is true, consider the mono variable case: $$ \mbox{Max}\quad f(x)=\alpha x \quad \mbox{subject to}\quad a\le x \le b $$

Draw the function and the interval $[a,b]$: it is clear that the optimum is in $x=b$, which is an extreme point of your polygon (a closed interval here).

You can do the same drawing if you have two variables (you will have to draw in 3D) to convince yourself that it is true in this case as well. This is exactly what user Sean English says in his comment above.

Now for a formal proof: since $f$ is continuous and defined on a compact space, it is bounded and attains its maximum and minimum at least once by the extreme value theorem . But since $f$ is linear, it can only attain it once, necessarily on the border of the compact space, namely the extreme points here.

$\endgroup$
5
  • $\begingroup$ What is a compact space? $\endgroup$ Jan 15, 2016 at 20:52
  • $\begingroup$ A closed and bounded one. $\endgroup$
    – Kuifje
    Jan 15, 2016 at 20:55
  • $\begingroup$ Consider the function $f(x,y):=y$ on the unit square $[0,1]^2$. It of course satisfies the claim, but takes its max at an infinity of points. $\endgroup$ Jan 18, 2016 at 16:48
  • $\begingroup$ Yes I agree. But the optimum is still on the $\textit{border}$ of the compact square. So to complete the proof, we would need to set apart two cases: there is a unique solution, or there are an infinity. In the first case, it will attain it on an extreme point, in the second on an edge. $\endgroup$
    – Kuifje
    Jan 18, 2016 at 17:01
  • 1
    $\begingroup$ Nonetheless, if the user is looking for AN optimal solution, there are still two at extreme points (1,0) and (1,1). $\endgroup$
    – Kuifje
    Jan 18, 2016 at 19:14

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .