LECTURE 3:
GEOMETRY OF LP
1. Terminologies
2. Background knowledge
3. Graphic method
4. Fundamental theorem of LP
Terminologies
• Baseline model:
• Feasible domain
• Feasible solution
• Consistency
Terminologies
• Bounded feasible domain:
In this case, we say “LP has bounded feasible domain.”
• Bounded LP:
• Question:
Terminologies
• Optimal solution:
x* is an optimal solution if
• Optimal solution set
• We say
Background knowledge
• Observation 1: each equality constraint in the standard
form LP is a “hyperplane” in the solution space.
- What does the equation represent
in the 2-d Euclidean space?
Definition:
Hyperplane
• Geometric representation
Properties of hyperplanes
• Property 1: The normal vector a is orthogonal to all
vectors in the hyperplane H.
• Proof:
Properties of hyperplane
• Property 2: The normal vector is directed toward the
upper half space.
• Proof:
Properties of feasible solution set
• Definition:
A polyhedral set or polyhedron is a set formed by the
intersection of a finite number of a closed half spaces.
If it is nonempty and bounded, it is a polytope.
• Property 3:
The feasible domain of a standard form LP
is a polyhedral set.
Properties of optimal solutions
• Property 4:
Example
• Give the following LP
• Covert to standard form
Graphic Solution
Graphic Method
Pros and Cons
• Advantages:
- Geometrically simple.
• Disadvantages
- Algebraically difficult
How many vertices are there?
How to identify each vertex?
Any better way?
• Simplex method
A way to generate and manage the vertices of the
feasible solution set, which is a polyhedral set.
Background knowledge
• Definition: Let , and
we say x is a linear combination of .
• If , we say x is an affine combination of .
• If , we say x is a conic combination of .
• If , we say x is a convex combination of
.
Sets generated by different combinations
of two points
Affine set, convex set, and cone
• Definition: Let S be a subset of .
If the affine combination of any two points of S falls in S,
then S is an affine set.
If the convex combination of any two points of S falls in S,
then S is a convex set.
If for all and , then S is a cone.
Example
• Which one is convex? Which one is affine?
Example
• What’s the geometric meaning of the feasible domain ?
1. P is a polyhedral set.
2. P is a convex set.
3. P is the intersection of m hyperplanes and the cone of
the first orthant.
4. “Ax = b and x 0” means that the rhs vector b falls in the
cone generated by the columns of constraint matrix A.
Example - continue
5. Actually, the set
is a convex cone generated by the columns of matrix A.
Interior and boundary points
• Given a set, what’s the difference between
an interior point and a boundary point?
• Definition: Given a set , a point
is an interior point of S, if ,
the ball
Otherwise, x is a boundary point of S.
• We denote that
Boundary points of convex sets
• What’s special about boundary points of a convex set?
• Separation Theorem:
Question
• Can you now see that if an LP (in two or three
dimensions) has a finite optimal solution, then one vertex
of P is optimal ?
• Hint: Consider the supporting hyperplane
• How about higher dimensional case?
- This leads to the Fundamental Theorem of LP.
Are all boundary points the same?
• Some sits on the shoulders of others, and some don’t.
• Definition: x is an extreme point of a convex set S if
x cannot be expressed as a convex combination of
other points in S.
Geometrical meaning of extreme points
• Definition:
• Theorem:
Representation of extreme points
• For the feasible domain P of an LP, its vertices are the
extreme points. How can we take this advantage to
generate and manage all vertices?
Learning from example
What’s special?
• Vertices
• Edge Interior
Observations
• Ax = b has n variables in m linear equations.
• When n > m , we only need to consider m variables in m
equations for solving a system of linear equations.
• An extreme point of P is obtained by setting n - m
variables to be zero and solving the remaining m
variables in m equations.
• the columns of A corresponding to the non-zero (positive)
variables better be linear independent!
Example
• System of equations
• Linear independence of the columns
Finding extreme points
• Theorem:
A point x is an extreme point
of P if and only if the columns of A corresponding to the
positive components of x are linearly independent.
• Proof:
Without loss of generality, we may assume that the first p
components of x are positive and rest are zero, i.e.,
Proof - continue
Proof - continue
Managing extreme points algebraically
• Let A be an m by n matrix with , we say A has full
rank (full row rank) if A has m linearly independent
columns.
• In this, we can rearrange
• Definition: (basic solution and basic feasible solution)
Example of basic and basic feasible
solutions
Further results
• Observation: When A does not have full rank, then either
(1) Ax = b has no solution and hence , or
(2) some constraints are redundant.
For the second case, after removing the redundant constraints, new A has full rank.
• Corollary: A point x in P is an extreme point of P if and
only if x is a bfs corresponding to some basis B.
• Corollary: The polyhedron P has only a finite number of
extreme points.
Are there many vertices for LP?
• Yes!
• This is not a small number, when n and m become
large. Please try it out by taking n = 100 and m = 50.
What do extreme points bring us?
• Observation:
When
is a nonempty polytope, then
any point in P can be represented
as a convex combination of the
extreme points of P.
Question: Can it be more general?
Extremal direction for unboundedness
• When P is unbounded, we need a direction leading to
infinity.
• Definition:
• A vector is an
extremal direction of P, if
for all ..
• Observations:
Resolution theorem
• Theorem:
• We can also write
s d, for some s .
Implications of resolution theorem
• Corollary:
If P is bounded (a polytope) , then any x in P can be
expressed as a convex combination of its extreme points.
• Corollary:
If P is nonempty, then it has at leas one extreme point.
Note that s d implies that the objective value
of x is determined by the objective values of extreme points
and extremal direction.
Fundamental theorem of LP
• Theorem: For a standard form LP, if its feasible domain P
is nonempty, then the optimal objective value of
is either unbounded below, or it is attained
at (at least) an extreme point of P.
• Proof:
By the resolution theorem, there are two cases:
Case 1:
Proof - continue
• Case 2:
• In both cases,
Hence the minimum of z is attained at one extreme point!
