Linear Programming - Duality and Geometry

Dr Ramkrishna Pasumarthy

Professor, IIT Madras

Web MTech Program 2022

28 September, 2022

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 1 / 16

 Overview

1 Formulation

2 Standard Form

3 KKT Optimality Conditions

4 LP Duality

5 Duality Theorem

6 Geometry of an LP

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 2 / 16

 Formulation

Definition of a Linear Program

An optimization is a linear programming if both the objective function and
constraints are linear in the argument x ∈ Rn

Structure of a general linear program

minx∈Rn c T x
subject to Ax ≤ b
A ∈ Rm×n

NOTE: An equality constraint , say z = 3 can be written as two inequality

constraints z ≤ 3, −z ≤ 3

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 3 / 16

 Linear Program in Standard Form
A linear program in standard form refers to the following problem
minx∈Rn c T x
subject to Ax = b, x ≥ 0
A ∈ Rm×n
Any linear program can be converted into standard form:
Ax ≤ b is the same as Ax − b = z and z ≥ 0 (inequality → equality
and a non-negativity by additional slack variable z)
x = x + − x − where x + , x − ≥ 0 and
 +
x
c T x = c T −c T 0 x − 
 

z
 +
 x
A −A I x −  = b =⇒ Ax + z = b, z ≥ 0


z
Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 4 / 16
 Optimality Conditions

Writing the Lagrange function - multiplier: λ, s

L(x, λ, s) = c T x − λT (Ax − b) − s T x

Optimality (KKT) Conditons - Necessary and Sufficient:

Gradient Condition: AT λ + s = c
Feasibility: Ax = b
Feasibility: x ≥0
Inequality: s ≥ 0
Complementary Slackness: xi si = 0

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 5 / 16

 Rewriting the KKT conditions - Towards Duality

Let (x ∗ , λ∗ , s ∗ ) be the optimal point. Then by KKT conditions,

c T x ∗ = (AT λ∗ + s ∗ )T x = λ∗T (Ax) = λ∗T b

Let x̄ be any other feasible point - i.e. x̄ ≥ 0, Ax̄ = b. Then,

c T x̄ = (AT λ∗ + s ∗ )T x̄ = b T λ∗ + x̄ T s ∗ ≥ b T λ∗ = c T x ∗

So, we have that x̄ is optimal if and only if

x̄ T s ∗ = 0

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 6 / 16

 Dual Problem
Primal Problem:

minx∈Rn c T x
subject to Ax ≤ b , x ≥ 0

Dual Problem:

maxλ∈Rm b T λ
subject to AT λ ≤ c

Primal ↔ Dual (trick to remember):

x ↔λ
c↔b
A ↔ AT

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 7 / 16

 Optimality (KKT) conditions for the Dual Problem

maxλ∈Rm b T λ = minλ∈Rm − b T λ
subject to s := c − AT λ ≥ 0
Lagrangian L̄ for the dual problem : x−Lagrange multipler for the
constraint s = c − AT λ ≥ 0
L̄(λ, x) = −b T λ − x T (c − AT λ)
Optimality (KKT) conditions for the Dual problem:
Gradient Condition: Ax = b
Feasibility: s := c − AT λ≥ 0
Non-negativity: x ≥ 0
Complementary Slackness: xi si := xi (c − AT λ)i = 0
Definition of s: s = c − AT λ
Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 8 / 16
 Identical conditions

Observe the primal and dual KKT conditions side by side

They are identical - except that the titles are different!

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 9 / 16

 Strong Duality Theorem

Strong Duality Theorem

If the primal/dual problem is solvable , then so is the other
dual/primal problem
If the primal/dual problem is unbounded , then the other dual/primal
problem is infeasible
Proof:
Let (x ∗ , λ∗ , s ∗ ) have a solution for the primal/dual problem. But the
KKT conditions are identical for both.
Let the primal problem be bounded - ie. ∃xk such that c T xk → −∞
satisfying Axk = b and xk ≥ 0.
Let the dual be feasible with λ̄ such that AT λ̄ ≤ c. Then,

λ̄T b = λ̄T (Axk ) ≤ c T xk

which is a contradiction as k → ∞
Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 10 / 16
 Geometry of the Problem
Consider a problem min c T x in R2 with five inequality constraints Ax ≤ b
, i.e. A ∈ R5×2

Figure: Optimal point is obtained typically at a vertex

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 11 / 16

 Vertices

One sees that the feasible set defined by the constraint set Ax ≤ b is
a convex polygon in R2
We see that typically as we move along the black dotted contours of
c T x to minimize it, the minimum is hit at a vertex typically - if c is
parallel to one of the ai , then the minimum is obtained at a full edge
but still the vertices being a part of the edge , is a minimizer
What is mathematically a vertex? It is intersection of any two green
lines - where the inequality becomes equality
More precisely, a vertex of a polygon in R2 is a feasible point where
any two of the inequality constraints are satisfied with equality

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 12 / 16

 Importance of feasibility condition
In the definition of a vertex, feasibility is important as well. As an example,

Figure: A vertex should have two equality constraint and feasible as well - the
violet point is not a vertex as it is not feasible (not inside the polygon)

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 13 / 16

 Vertex: From R2 to a general LP
Consider the standard form LP1

minx∈Rn c T x
subject to Ax = b, x ≥ 0
A ∈ Rm×n , full rank with m < n

The set of solutions to Ax = b will form a n − m dimensional space

since rank of A is m. (n variables and m equations ⇒ n − m free
variables)
In this n − m dimensional feasible set, one needs n − m equations to
give a unique point.
In R 2 , a vertex was defined by two inequality constraints being
satisfied with equality. In this n − m dimensional space, a vertex
should hence be defined by n − m inequality constraints being
satisfied with equality
1
If m > n, then there exists only one or no feasible point in which case the problem is
trivial
Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 14 / 16
 Basic Feasible Point: Extension of a vertex
The notion of a basic feasible point is the extension of the definition of a
vertex
Basic Feasible Point
A point x is called a basic feasible point w.r.t a standard form LP if
x is feasible - Ax = b, x ≥ 0
there exists m indices B := {i1 , i2 , . . . , im } ⊂ {1, 2, · · · , n} such that

xi = 0 if i ∈
/B

The m × m matrix B defined by B := [Ai ]i∈B where Ai is the i th

column of A is non-singulara
a
As a consequence, the set of n − m equations xi ≥ 0 for i ∈
/ B and the m equations
Ax = b has a unique solution which is the basic feasible point x

Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 15 / 16

 Theorem of solvability by basic feasible points
It turns out that under just trivial conditions, LP problems can be solved
by just basic feasible points
Fundamental Theorem of LP
If the LP is feasible and bounded, then it has atleast one optimal
solution x ∗
Atleast one point in the optimal solution is a basic feasible point
If the LP is feasible, then it has basic feasible points

As a consequence, it is enough to solve

minx∈B c T x
x ≥ 0 , Ax = b
where B is the set of all basic feasible points
But the set of basic feasible points is finite as subsets of {1, 2, . . . , n}
are finite and each such subset B generates a unique basic feasible
point - so it is now a search among finitely many points!
Dr Ramkrishna Pasumarthy (IIT Madras) Optimization 28 September, 2022 16 / 16