0
$\begingroup$

(A proof from Linear Algebra by G.Hadley)

Theorem III: A closed convex set which is bounded from below has extreme points in every supporting hyperplane.

The convex set of feasible solutions to a linear programming problem is closed and bounded from below by $0$ because $x_j > 0$ for all $j$.
Hence, the theorem states that if there is an optimal solution, at least one of the extreme points of the convex set of feasible solutions will be an optimal solution.

In $E^n$, as in $E^2$, $E^3$, the convex set of feasible solutions will have only a finite number of extreme points. X Hence, if we had the means of selecting the extreme points of the convex set of feasible solutions, only a finite number of points would have to be examined to find an optimal solution to the problem. And indeed, it is possible to determine analytically the extreme points. This is the basis of the simplex method. We move from one extreme point to a new one (having a value of $z$ at least as large as the preceding one) until an optimal solution is found.

We shall now prove Theorem III. The hyperplane $cx — z$ will be assumed to be a supporting hyperplane at $x_0$ to the closed convex set $X$ which is bounded from below. The intersection of X and the set S = {x|cx = z} will be denoted by T. The intersection is not empty because $x_0 \in T$; furthermore, since X and S are closed convex sets, so is T; T is also bounded from below since X is.

We shall show that any extreme point of T is also an extreme point of X.

If $t$ is any point in T, and if

$t = \lambda x_2 + (1 — \lambda)x_1$, $0 < \lambda < 1$,

where $x_1, x_2 \in X$, then $x_1, x_2 \in T$. This follows from the fact that

$ct = \lambda cx_2 + (1 — \lambda)cx_1 = z$,... (6-58)

and $cx_2 > z$, $cx_1 > z$ because $cx = z$ is a supporting hyperplane. Noting that $\lambda$, $(1 — \lambda) > 0$, we see that (6-58) will hold if and only if $cx_2 = z$, $cx_1 = z$, that is, if and only if $x_1, x_2 \in T$. Thus an extreme point of T cannot be represented as a convex combination of any two points in X with $0 < \lambda < 1$. Hence an extreme point of T is an extreme point of X.

We still have to prove that T actually has an extreme point; this will be accomplished by finding an extreme point. Out of all the points in T, choose the one with the smallest (algebraic) first component. There is at least one such point since T is closed and bounded from below.

If there is more than one point with a smallest first component, choose the point or points with the smallest first and second components. If again there is more than one point with the smallest first and second
components,find the point or points with the smallest first, second, and third components, etc. Finally, a unique point will be obtained since only one point can have all its components of minimum algebraic value.

The unique point $t^*$ determined by the above process is an extreme point.

If $t^*$ were not an extreme point, we could write

$t^* = t_1 + (1 - \lambda)t_2$, $0 < \lambda < 1$; $t_1 \neq t_2 \in T$... (6-59)

Suppose the unique $t^*$ was determined on minimizing the $j^{th}$ component. If $t_{ji}$, $t_{j2}$ are the $j^{th}$ components of $t_1$, $t_2$, then the $j^{th}$ component of (6-59) is

$t^*_j =\lambda t_{j1} + (1 -\lambda)t_{j2}$, $0 < \lambda < 1$..... (6-60)

Furthermore (why?)

$t^*_i = t_{i1} = t_{i2} (i = 1, . . . , j - 1)$.

But then (6-60) requires that $t^*_j = t_{j1} = t_{j2}$, for otherwise $t^* > min [t_{jl}, t_{j2}]$. However, this result contradicts the fact that there is only one point with this $t^*$ when all components $1, ... ,j — 1$ are at their minimum values. Consequently, t* cannot be represented as a convex combination of any two other points in T $(0 < \lambda < 1)$. Hence $t^*$ is an extreme point and the theorem is proved, f The above proof also
demonstrates that a strictly bounded convex set has extreme points in every supporting hyperplane.

S o my question is why $t^*_i = t_{i1} = t_{i2} (i = 1, . . . , j - 1)$. And also why $t^*_j = t_{j1} = t_{j2}$ I understand this $t_{j1} ,t_{j2}$ cannot be smaller than $t^*_j$.We know $t_1$ and $t_2$ has all the $1…j-1$ component same and equal to that of $t^*$’s,If $t_{j1} , t_{j2}$ is smaller than $t^*_j$,it will be contradiction to $t^*$ with minimum $j^{th}$ component.But this $t_{j1} , t_{j2}$ could be greater than $ t^*_j $? Then Why $t^*_j = t_{j1} = t_{j2}$?

I am extremely sorry,while editing i saw i did much mistakes.

$\endgroup$
0
$\begingroup$

By construction you have $t_j^*=\lambda t_{j1}+(1-\lambda) t_{j2}$ where $\lambda \in (0,1)$. That means that $t_j^*$ is in the convex hull of $t_{j1}$ and $t_{j2}$. The convex hull of two real numbers is the interval between those real numbers.

WLOG assume $t_{j1} \leq t_{j2}$. Then you must have $t_{j1} \leq t_j^* \leq t_{j2}$ since $t_j^*$ is in the convex hull of $t_{j1}$ and $t_{j2}$ (and those inequalities are strict if $t_{j1} \neq t_{j2}$ since you took $\lambda \in (0,1)$).

We already know $t_{j1}$ cannot be less than $t_j^*$ from the choice of $t^*$, therefore we must have $t_{j1}=t_{j}^*$. If $t_{j2}$ is strictly larger than $t_{j1}$, then since $\lambda \in (0,1)$ we would have $$ \lambda t_{j1}+ (1-\lambda) t_{j2}= \lambda t_{j1}+ (1-\lambda) (t_{j1}+t_{j2}-t_{j1})=t_{j1}+(1-\lambda)(t_{j2}-t_{j1}) > t_{j1}=t_j^*, $$ a contradiction.

$\endgroup$
  • $\begingroup$ they said at last,"However, this result contradicts the fact that there is only one point with this $t^∗$ when all components $1,...,j—1$ are at their minimum values".I think it should be,"However, this result contradicts the fact that there is only one point with this $t^∗$ when all components $1,...,j—1,j$ are at their minimum values".Because since $t^∗i=t_{i1}=t_{i2}(i=1,...,j−1)$,by $t^∗_j=t_{j1}=t_{j2}$ we get $t^*,t_1 and t_2$ with all its components $1,...,j—1,j$ at their minimum values. $\endgroup$ – math student Oct 1 '19 at 14:15
  • $\begingroup$ I don't really understand what you mean to say here. I think that what you originally submitted is pretty confusing, so if thats verbatim the proof you were reading, I would not be at all surprised if there are typos. But the point of the argument is that if you try to express $t^*$ as a convex combination of elements of the face, then those elements must have the same values as $t^*$ in the first $j$ positions. But $t^*$ is the unique element with those values in the first $j$ positions so you must have $t_1=t_2=t^*$. The reason the values must be the same is in my original answer. $\endgroup$ – Eric Oct 1 '19 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.