I am learning the book “Optimization Models” recently and I see a blogger recommends Prof. Shu-Cheng Fang’s course “Linear Programming” as a supplement. The OCW course video is found in Bilibili.
- Lecture 0 - Lecture 2: Introduction, Perliminaries
- Lecture 3: Geometry of LP
- Lecture 4: Simplex Method
Lecture 0 - Lecture 2: Introduction, Perliminaries
In linear programming (LP), we established a LP model to solve a realistic problem (in approximate way). To establish the LP model, the steps is as followed:
- What are the variables to be involved? (This is the first thing we should think about)
- What’s the objective function?
- How are the variables constrained? (The order of step 2 and 3 is not fixed, since they are independent)
Standard Form of LP Model
Including:
- n variables
- 1 objective function
- m constraints
- non-negative variables
Explicit Form
- Minimizing one objective function.
- Equality constrains.
- Non-negative variables.
Matrix Form
in which, is the cost vector, is the solution vector, is the right-hand-side vector and is the constrain matrix.
Embedded Assumptions in LP
-
Proportionality Assumption
- No discount
- No economy of return to scale
-
Additivity Assumption
- Total contribution = Sum of contributions of individual variables
-
Divisibility Assumption
- Any fractional value is allowed
-
Certainty Assumption
- Each parameter is know for sure
Converting to Standard LP
Rule 1: Unrestricted (free) variables
For any , we can divide it into a positive component and a negative component , which satisfy
Therefore, can be written as , in which . If we have an absolute valve in the LP model, it can be displaced by .
Notice: Such decomposition introduces an extra constraint: , which is important by usually ignored. This second-ordered constraint makes sure the uniqueness of the solution.
Rule 2: Inequality constraints
For
we introduce a slack variable and the original inequality constraint can be transformed to
in which .
Similarly, for
we introduce an excess variable and the original inequality constraint can be transformed to
in which .
Rule 3: Minimization of the Objective Funtion
Potential Problem caused by Standardizing
- One quadratic constraint is missing in the LP model
- Dimensionality increased
- One original solution corresponds to many new solutions
- Since is a convex function while is a concave function, maximize can only be solved when c is negative, or the solution lies on the infinite.
Lecture 3: Geometry of LP
Terminologies
Baseline model:
Feasible domain
Feasible solution
If , then x is a feasible solution.
Consistency
When , LP is consistent.
Background knowledge
Definition of hyperplane
Each equality constraint in the standard form LP is a “hyperplane” in the solution space. In the 2-D space, it is a line. In 3-D space, it is a plane.
For a vector and a scaler
is defined as a hyperplane, which divides the solution space into 3 parts, the open upper-half space (in which ), the hyperplane and the open lower-half space (in which ). The upper-half space , similarly for . is also called the bounded hyperplane of and .
The vector a is the normal of the hyperplane and it points to the upper-half in the direction which increases $(in which fastest.
Properties of hyperplanes
Property 1: The normal vector a is orthogonal to all vectors in the hyperplane H.
Property 2: The normal vector is directed toward the upper half space.
Properties of feasible solution set
Property 3: The feasible domain of a standard form LP
is a polyhedral set.
A polyhedral set or polyhedron is a set formed by the intersection of a finite number of closed half spaces. If it is nonempty or bounded, it is a polytope.
Properties of optimal solutions
Property 4:if and such that
then .
Moreover, if , then
Graphic method
Step 1:
Draw the feasible domain
Step 2:
Use as normal vector at each vertex to see if for some . If yes, then we found the optimal solution.
- Advantage: Intuitional / Geometrically simple
- Disadvantage: Impractical for large LP problems / Algebraically difficult
Fundamental theorem of LP
Background knowledge
Definition: Let , for
we say x is a linear combination of .
- If , w say x is an affine combination of .
If the affine combination of any two points of S falls in S, then S is an affine set. - If , we say x is a conic combination of .
If for all and , then S is a cone. - If , w say x is an convex combination of .
If the convex combination of ant two points of S falls in S, then S is a convex set.
The geometric meaning of the feasible domain
- P is a polyhedral set.
- P is a convex set
- P is the intersection of m hyperplanes and the cone of the first orthant.
Seeing in the column picture (see MIT 1806), if the vector b falls in the cone generated by the columns of constraint matrix A.
Interior and boundary points
Definition: Given a set , a point is an interior point of S if
called
Otherwise, x is a boundary point of S, we say .
How to define a convex set S
- For all interior point, the segment between any two interior points falls in the convex set S.
- For boundary point x, a hyperplane H that and S falls in .
- For outside point x, a hyperplane H that x lies in and S falls in the , or vise versa.
Difference among boundary points
x is defined as an extreme point of a convex set S if x cannot be expressed as a convex combination of other points in S.
The extreme points are not exactly the same as the vertices according to their definition. But for the feasible domain P of an LP, it vertices are the extreme points.
Finding extreme points
Theorem: A point 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 the rest are zero, i.e.,
also denote the first p column of A by then .
Suppose that the columns of are not linearly independent, then such that .
Notice that for is small enough
Hence,
and , i.e. x cannot be a vertex (extreme point) of P.
Thus, x is an extreme point when the columns of are linearly indeoendent.
Suppose that x is not an extreme point, then for some .
Since and , the last components of must be zero, i.e.
Now
and , which indicates that the columns of A are linearly dependent.
Thus, the theorem is proofed.
Managing extreme points algebraically
Full rank matrix: Let A be an m by n matrix with , we say A has full rank (since , full row rank) if A has m linearly independent columns.
Rearrange x as
- If we set and solve for then x is a (bs).
- Furthermore, if , then x is a .
We can see, when A does not have full rank, then either
- Ax = b has and hence , or
- some constraints are redundant (which can be avoided by preprocessing matrix A).
Thus,
- A point x in P is an extreme point of P if and only if x is a basic feasible solution corresponding to some basis B.
- The polyhedron P has only a finite number of extreme points (less than ).
What do extreme points bring us?
When is a nonempty polytope, then any point in P can be represented as a convex combination of the extreme points of P.
If P is unbounded, there exists an extremal direction.
- Definition: A vector is an extremal direction of P, if for all .
- d satisfies and .
Resolution theorem
Let be a set of extreme points of P, then for
where
and either or d is an extremal direction of P
Fundamental theorem of LP
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.
Lecture 4: Simplex Method
Basic Idea:
-
Phase 1:
- Step 1 (Starting): Find an initial extreme point (ep) or declare P in null.
-
Phase 2:
- Step 2 (Checking optimality): if the current eo is optimal, STOP.
- Step 3 (Pivoting): Move to a better ep, then return to Step 2.
If we do not repeat using the same extreme point, then the algorithm will always terminates in finite number of iterations.
But how to efficiently generate better extreme points?
In the algebra term, we just need to use basic feasible solution to replace extreme point above.
If there exists at least one basic variable becoming zero, the extreme point may correspond to more than one basic feasible solution, in this case we say the bfs is a degenerate one.
Nondegeneracy
Property 1:
If a bfs x is nondegenerate, then x is uniquely determined by n hyperplanes.
Let , M is a nonsingular matrix.
x is uniquely determined by n linearly independent hyperplanes since
in which,
We call (or M) the fundamental matrix of LP.
Property 2:
If a bfs x is degenerate, then x is overdetermined by more than n hyperplanes.
Other than n hyperplanes determined by non-basic variables, there exists at least one basic variable that , which indicates an extra hyperplane.
Simplex method under nondegeneracy
Basic idea:
Instead of considering all bfs at the same time, wo just consider some neighboring bfs, moving from one bfs to another with a simple pivoting scheme.
Definition
Two basic feasible solution are adjacent if they have basic variables in common.
Each bfs has adjacent neighbors, which can be reached by increasing one non basic variable from zero to positive and decrease one basic variable to 0, called pivoting.