Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Lecture 5. The Linear Programming Problem

Motivating example
Extreme points
Properties of LP problem
Simplex method for solving LP problem
Transformation into a linear programming problem

1 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Motivating example

Manufacturing Problem
m: number of types of resources.
bi : value of i th resource, i = 1, . . . , m
n: number of products
aij : units of i th resource to produce 1 unit of j th product
(i = 1, . . . , m, j = 1, . . . , n)
pj : price of 1 unit of j th product (j = 1, . . . , n)
Question: Construct the problem to find the number of each
product to maximize revenue.

2 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Motivating example

Problem
Let xj be units of j th product (j = 1, . . . n).
n
X
maximize pj xj
j =1
 n
X
 aij xj ≤ bi (i = 1, . . . , m),


j =1

x ≥ 0

(j = 1, . . . , n).
j

3 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Forms of general LP problem

n
X
f (xx ) = cj xj → min(max)
i =1
n

X
 aij xj ≤ bi i ∈ I1





j =1


 n
X
 aij xj ≥ bi
 i ∈ I2
j =1 (1)

X n



 aij xj = bi i ∈ I3


j =1

x ∈ Rn , bi ∈ R

(i ∈ I1 ∪ I2 ∪ I3 )


where I1 , I2 , I3 are disjoint index sets and I = I1 ∪ I2 ∪ I3 , |I | = m.

4 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Extreme points

Consider a general linear programming problem (1).

Equality constraints are binding constraints.
Inequality constraints (≤, ≥) are non-binding constraints.
A constraint is said to be active/binding at the feasible point
x 0 if an inequality constraint holds with equality at x 0 .
A constraint is said to be inactive/non-binding at the feasible
point x 0 if an inequality constraint holds as a strict inequality
at x 0 .
x 0 ∈ D is an extreme point of D if whenever points y , z ∈ D
and λ ∈ (0, 1) are such that x 0 = λy + (1 − λ)zz , then we have
y = z = x 0.
5 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Extreme points

x 0 ∈ D is an extreme point of D if there are at least n linear

independent active constraints at x 0 .
If there are exactly n active constraints at x 0 , then x 0 is a
non-degenerate extreme [Link] there are more than n active
constraints at x 0 , then x 0 is a degenerate extreme point.
If every extreme point of a linear programming problem is
non-degenerate, then the problem is said to be
non-degenerate.

6 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Extreme points

Example
Given a problem: f (xx ) = 2x1 − x2 + 3x3 → max

−x1 + 3x2 + 3x3 ≤4










2x1 − x2 − x3 =2

x1 + 3x2 ≥ −1 (2)



x1 − x2 + x3 ≥0







x1 , x3 ≥0


and the vectors

x 0 = (2;0;2), x 1 = (2; −1;3), x 2 = (0; −3;1), x 3 = (2;2;0).
Which vectors are feasible solutions? Which are extreme points?
Are they degenerate or non-degenerate? 7 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Properties of linear programming problems

Property 1: If a linear programming problem has feasible

solutions and the rank of its constraint matrix is n, then it has
an extreme point.
Example: Does a problem that has a feasible domain




x = (x1 , x2 ) ∈ R2

x1 ≥ −2


x1 ≤ 2‘


has a feasible solution? An extreme point?

Comment: If a standard problem has feasible solutions then it
always has extreme points.
Property 2: If D ̸= ; and f (xx ) is bounded on D then the
problem has an optimal solution (solvable). 8 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Properties of linear programming problems

Property 3: A problem having extreme points and solvable

has an optimal extreme solution.
In the case of standard problem, if it has feasible solutions and
the objective function is bounded on the feasible set, then it
has an optimal solution which is an extreme point.
Property 4: The number of extreme points of a problem (if
n.
exist) is at most Cm

9 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Properties of linear programming problems

Example 3
Given a linear programming problem:

f (xx ) = −4x1 + 6x2 − 3x3 → min




 2x1 −4x2 +x3 ≥ −1


 −3x1 +5x2 −2x3 ≥ 1



x1 +2x3 ≤ 1





 3x2 −x3 ≤ 4

 −x +x2 ≥ −2

1

Prove that the problem is solvable. Find the optimal value. Does
this problem has an optimal solution which is an extreme point?

10 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Standard forms of LP problem

Explicit form
n
X
f (xx ) = cj xj → min(max)
j =1
 n
X
 aij xj = bi i = 1, m


j =1 (3)

x ≥ 0

j = 1, n
j

Matrix form

f (xx ) = c T x → min(max)

Ax = b (bb ∈ Rm )
x
x ≥0 (xx ∈ Rn )
11 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Standard forms of LP problem

Vector form

f (xx ) = 〈c , x 〉 → min(max)
 n
(bb ∈ Rm )
X
 Aj xj = b


j =1 (4)

x ≥ 0 (xx ∈ Rn )


Theorem 1
Consider the vector form of a standard problem (4).
Let x 0 = (x10 , x20 , . . . , xn0 ) be a feasible solution.
Denote J = {j : xj0 > 0}, AJ = {Aj : j ∈ J }
The feasible solution x 0 is an extreme point if and only if the
column vectors AJ are linear independent.
12 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Properties of the extreme point of a standard problem

Let x 0 be an extreme point of the standard problem (4). J0 is a

basis of the extreme point x 0 if J0 ⊇ J, J0 has exactly m
elements and the set of vectors AJ0 = {Aj : i ∈ J0 } is linear
independent.

Remark: If an extreme point x 0 is non-degenerate, then J = J0 . If

x 0 is a non-degenerate extreme point, then there exist many J0
containing J.
Definitions
A variable xj (j ∈ J0 ) is a basic variable.
A variable xk (k ∉ J0 ) is a non-basic varibale.
xj0 (j ∈ J0 ) is a basic component of the feasible solution x 0 .
x 0 (k ∉ J0 ) is a non-basic component of the canonical feasible 13 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Canonical form of LP problem

Canonical form
Given a linear programming problem and let x 0 be an extreme
point of the problem. Then we can always transform a standard
form of a LPP to its canonical form:

f (xx ) = f (xx 0 ) + ∆k xk → max

X
k ∉J0

xjk xk = xj0
X
xj + (j ∈ J0 )


k ∉J0 (5)

xj ≥ 0

∀j = 1, n

14 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Canonical form of LP problem

Example 4
Given a problem:

f (xx ) = 2x1 + x2 + x3 + 2x4 − x5 → max




 x1 −x2 +x4 +2x5 = 3

2x2 +x3 −x5 = 5




 −x2 +x3 −x4 +2x5 = 2


 x1 , x2 , x3 , x4 , x5 ≥ 0

a. Is the vector x 0 = (4;1;3;0;0) an extreme point?

b. Transform the problem to its canonical form.

15 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

George Dantzig (1914-2005)

Ph.D. in Statistics, University of California, Berkeley (1946)
During World War II, he served in the United States Air Force
doing route planning for military aircraft.
He invented the simplex method.
Two linear programming scholars, Leonid Kantorovich and
Tjalling Koopmans, are awarded the 1975 Nobel Memorial
Prize in Economic Sciences.

16 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

The problem is solvable and has an extreme point, then it has

an optimal solution which is an extreme point.
One of the extreme points is the optimal solution.
Consider an extreme point x 0 , verify if x 0 is an optimal
solution. If it is, then we stop the algorithm. If it’s not, find a
way to move from x 0 to another extreme point x 1 "better"
than x 0 .
If the number of extreme point is finite, then after finite steps,
we will either find the optimal solution which is an extreme
point or show that the problem doesn’t have an optimal
solution.
17 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

Consider a standard linear programming problem (4)), x 0 is

an extreme point with the basic J0 , AJ0 is the basic of Rm .
The vectors Ak ∈ Rm , k ∉ J0 can be written in a unique way as
a linear combination of elements of AJ0 :
X
Ak = xjk Aj , k ∉ J0
j ∈J0

Replace this into equivalent constraints of a (4) we have:

à !
X X
xj + xjk xk Aj = b
j ∈J0 k ∉J0

On the other hand, since x 0 is a feasible solution,

n
xj0 Aj = b or
X X 0
xj Aj = b
j =1 j ∈J0
18 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

Since b ∈ Rm , the vector b can be written in a unique way as a

linear combination of Aj , j ∈ J0

xj = xj0 −
X
xjk xj , ∀j ∈ J0
k ∉J0

Then all basic variables can be written in the form of

non-basic variables.
Replace the linear combination of AJ0 above into f (xx )
à !
cj xj0 −
X X X
f (xx ) = cj xjk − ck xk
j ∈J0 k ∉J0 j ∈J0

Let ∆k = − ck , ∆k is called the estimation of

P
i ∈J0 cj xjk
non-basic variables xk (k ∉ J0 )
19 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

The standard linear programming problem (4) can be transformed

to the canonical form:

f (xx ) = f (xx 0 ) − ∆k xk → max

X
k ∉J0

xjk xk = xj0
X
xj + (j ∈ J0 )


k ∉J0

xj ≥ 0

∀j = 1, n

with estimations ∆k calculated by the formula

∆k =
X
cj xjk − ck , k ∉ J0 .
i ∈J0

20 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

Theorem 2 (Optimization criteria)

If an extreme point x 0 with a basis J0 has ∆k ≥ 0, ∀k ∉ J0 then x 0
is an optimal extreme solution.

Remark
If ∆k > 0, ∀k ∉ J0 then x 0 is the unique optimal solution of the
problem.
If there exists ∆k = 0 then there is a sequence of feasible
solutions at which the objective function obtains its optimal
value.

21 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex method

Theorem 3
If at the extreme point x 0 with basis J0 , the corresponding
cannonical problem has ∆k < 0 then x 0 is not the optimal solution,
and there are two cases:
If there exist index k with ∆k < 0 and xjk ≤ 0 ∀j ∈ J0 then there
exists a sequence of feasible solutions at which the objective
function is unbounded above or the problem is insolvable.
If for all ∆k < 0, there exists xjk > 0 then we can change from
x 0 to the feasible solution x 1 "better" than x 0 .

22 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex algorithm

Consider a standard problem having extreme point x 0 with basis J0 .

f (xx ) = 〈c , x 〉 → max
 n
 Aj xj = b (b ∈ Rm )
 X

j =1

x ≥ 0 (x ∈ Rn )


Without loss of generality, we can assume that {J0 = 1, 2, . . . , m}.

Then this problem can be transformed into canonical form:
n
f (xx ) = f (xx 0 ) − ∆k xk → max
X
k =m+1
n

xjk xk = xj0
X
xj + (j ∈ J0 )


k =m+1

xj ≥ 0

∀j = 1, n 23 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex algorithm

Step 1. Construct a simplex table with extreme point x 0

c1 c2 . . . cr . . . cm cm+1 . . . ck . . . cs . . . cn
Coef. Basis x1 x2 . . . xr . . . xm xm+1 . . . xk . . . xs . . . xn Sol
c1 x1 1 0 ... 0 ... 0 x1,m+1 . . . x1,k . . . x1,s . . . x1,n x10
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
cr xr 0 0 ... 1 ... 0 xr ,m+1 . . . xr ,k . . . [xr ,s ] . . . xr ,n xr0
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
cm xm 0 0 ... 0 ... 1 0
xm,m+1 . . . xm,k . . . xm,s . . . xm,n xm
f (xx ) 0 0 ... 0 ... 0 ∆m+1 . . . ∆k . . . ∆s . . . ∆n f (xx

24 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex algorithm

Step 2. Check the optimality of extreme point x 0

If ∆k ≥ 0, ∀k ∉ J0 thì x 0 is an extreme optimal solution −→
Stop the algorithm.
If there exists ∆k < 0 then move to Step 3.
Step 3. Check if the problem is solvable
If there exists ∆k < 0 and xjk ≤ 0 ∀j ∈ J0 then conclude that
this problem is unsolvable because the objective function is
unbounded on the feasible domain.
If for all ∆k < 0 there exists xjk ≥ 0, move to Step 4.
Step 4. Choose entering variable and leaving variable to the set of
basic variables
Find min {∆k : ∆k < 0, k ∉ J0 } = ∆s , then xs is an entering
variable. 25 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex algorithm

Step 5. Pivoting Form a new simplex table, in which, in basic

variable column replace xr by xs .
Divide r th row by xrs , the obtained row is called pivot and
write this row xs into the new table.
Transform the other rows in the old table into corresponding
rows in the new ones
Obtained result is a simplex table corresponding to a new extreme
point x 1 , better than x 0 .
Return to Step 2 and repeat the algorithm, after a finite number of
step, conclude that either the problem is unsolvable because the
objective function is unbounded or find the optimal solution which
is an extreme.
26 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex algorithm

Example 5
Solve linear programming problem:

f (xx ) = −2x1 + x2 − 4x3 + 3x4 → max




 −x2 −2x3 −x4 ≤ 1

 2x

−3x2 −x3 +2x4 ≤ 5
1


 −x1 +2x2 +x3 −2x4 ≤ 7


 x ,
1 x2 , x3 , x4 , ≥ 0

27 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Simplex algorithm

Example 6
Solve linear programming problem:

f (xx ) = x1 − 2x2 − x3 → max




 2x1 +3x2 −x3 −x4 ≤ 5

 x −2x2 +x3 +x4 ≤ 3

1


 x1 +x2 −x4 ≤ 6


 x1 , x2 , x3 , x4 , ≥ 0

28 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Two-Phases method to solve general LP

For the standard form LP:

f (xx ) = c T x → max

Ax = b (bb ∈ Rm )
x
x ≥0 (xx ∈ Rn )
Recall that A ∈ Rm×n . We define the auxiliary LP:

P(xx a ) = x1a + x2a . . . xm

a
→ min

Ax + x a = b (bb ∈ Rm )
x
x ≥ 0 , x a ≥ 0 (xx ∈ Rn , x a ∈ Rm )

29 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Two-Phases method to solve general LP

Phase I:
Find and apply simplex method on auxiliary LP with cost:
m
xa
X
min i
i =1

If the optimal value of auxiliary LP is

Zero: Extreme point of original LP found.
Positive: Original LP is infeasible.
Phase II
Take the extreme point found in Phase I to start Phase II.
Use coefficients of objective function in original LP to
compute.
Apply simplex method to original LP.
30 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Two-Phases method to solve general LP

Example 7.
Given a linear programming problem:

f (xx ) = 3x1 − x2 + 3x3 − 2x4 −→ max






4x1 − 3x2 − x3 + 2x4 ≤ 34


2x1 − 2x2 + 3x3

≤ 60



2x1 − 2x2 − 3x3 + 4x4 ≥ 32


x ≥ 0, j = 1, 4

j

a. Solve this problem using simplex method

b. Find the optimal solution of the problem with an addition
constraint f (x) ≤ 10.
31 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Convex piecewise-linear functions

f (xx ) = max a T
¡ ¢
i x + bi
i =1,...,m

f (x)
ai x + bi

minimize f (xx ) = max a T

¡ ¢
i x + bi i =1,...,m

32 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Equivalent linear optimization

minimize t
subject to a T
i x + bi ≤ t , i = 1, . . . , m

Matrix notation
minimize ceTxe
subject to A
e xe ≤ be
   
aT −1 −b1
 1
" # " #
x 0 . .. 

 . 
 
xe = , ce = , A  ..
e = .  , be =  .. 
t 1    
aT
m −1 −bm

33 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Data-fitting example
Fit a linear function f (z) = x1 + x2 z to m data points (zi , fi ):
Approximation problem Ax ≈ b where:
   
1 z1 f
 1
" #
 ..

.. 
 x1  .. 
A = . . , x= , b = . 
  x2  
1 zm fm
To find x , the least squares method solves: minimize∥Ax − b ∥22
obtaining a closed-form solution x ∗ , but x ∗ is sensitive to outliers.
To find a solution that is more robust to outliers, solve the problem

minimizer∥Ax − b ∥1

However, this problem has no closed-form solution.

34 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

1-norm approximation

minimizer∥Ax − b ∥1

The 1-norm of an vector y ∈ Rm is:

m
X m
X
∥y ∥1 = | yi | = max{yi , −yi }
i =1 i =1

Equivalent problem Matrix notation

m " #T " #
0 x
X
minimize ui minimize
i =1 1 u
subject to − u ≤ Ax − b ≤ u  " # " #
A x−I b
subject to   ≤
−A −I u −b
35 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

ℓ∞ -norm approximation

minimize ∥Ax − b ∥∞

The ∞-norm of an vector y ∈ Rm is

∥y ∥∞ = max |yi | = max max{yi , −yi }

i =1,...,m i =1,...,m

Equivalent problem Matrix notation

" #T " #
minimize t 0 x
minimize
subject to − t1 ≤ Ax − b ≤ t1 1 t
" #" # " #
A −1 x b
subject to ≤
A −1 t −b
36 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Example: Dimensionality reduction via ℓ1 -Norm

Idea:
Feature matrix: A ∈ Rn×p , b ∈ Rn ,
where, n is size of sample and p is the number of features. If p is
very large, then:
Many features are irrelevant or redundant (highly correlated).
The linear model Ax ≈ b is prone to overfitting and difficult to
interpret.

⇒ Need to select a small subset of the most relevant features while

still maintaining good predictive performance.

37 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Problem formulation (Lasso Regression):

1
min ∥Ax − b ∥22 + λ∥x ∥1
x 2n
Interpretation:
The ∥Ax − b ∥22 term ensures good data fitting.
The ∥x ∥1 = term encourages many coefficients to be
P
i | xi |
exactly zero.
Nonzero entries of x ∗ correspond to the most relevant
features.

Geometric intuition:
The ℓ1 constraint region has sharp corners (diamond shape).
The optimal point tends to lie on an axis ⇒ some xi = 0.
38 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Intuition of SVM
SVM is a supervised learning algorithm.
Given the training set {(xx i , yi )}ni=1 , where x i ∈ Rd (feature
vectors) and yi ∈ {−1, +1} (labels).
SVM finds a hyperplane that separates two classes with the
maximum margin.
w ⊤x i + b) ≥ 1,
yi (w i = 1, . . . , n

Margin: distance between the two supporting hyperplanes:

2
margin =
∥w ∥
Goal: choose (w
w , b) such that classes are correctly separated
and margin is largest.
39 / 40
Motivating example Extreme point Properties of LP problem Simplex method Transformation into a LP problem

Transformation into a LP problem

Key Idea
Large margin ⇒ better generalization ⇒ more robust classifier.

Hard-margin SVM:
1
min ∥w ∥2
w ,b 2
w ⊤x i + b) ≥ 1, i = 1, . . . , n.
s.t. yi (w

40 / 40