DDA 5002/CIE 6010 Optimization

Lecture 12 LP Duality Theory

Yuang Chen

School of Data Scienc

The Chinese University of Hong Kong, Shenzhen

March 5, 2025

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 1 / 51

Outline

1 Basic Solution and Basic Feasible Solution

2 Finding a Basic Solution in Standard Form LP

3 LP Duality

4 Table of Possibles and Impossibles

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 2 / 51

Outline

1 Basic Solution and Basic Feasible Solution

2 Finding a Basic Solution in Standard Form LP

3 LP Duality

4 Table of Possibles and Impossibles

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 3 / 51

Basic solution

Consider a polyhedron defined by linear equalities and linear inequalities,

and let x be an element of Rn . The vector x is a basic solution if:
There are n linearly independent, active constraints at x;
All equality constraints are active at x.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 4 / 51

Basic Feasible Solutions

Definition
If a basic solution x also satisfies all constraints, then we call it a basic
feasible solution (BFS).

To find a BFS
First find a basic solution x
Then check if it satisfies all constraints
Theorem
For a non-empty polyhedron, the followings are equivalent:
1 x is a vertex
2 x is an extreme point
3 x is a basic feasible solution

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 5 / 51

Existence of BFS

Definitions: A polyhedron contains a line if →x ↑ P and d ↑ Rn , such that

x + ωd ↑ P ↓ω

Theorem
P = {x ↑ Rn |Ax ↔ b} =
↗ !. P has a BFS if and only if P does not contain
a line.

Corollary
Polyhedron in standard form P = {x ↑ Rn |Ax = b, x ↔ 0} always has
a BFS.
Bounded polyhedron always has a BFS.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 6 / 51

Optimality of BFS

min c ↭x
s.t. x ↑ P = {x|Ax ↔ b}

Theorem
Suppose P has at least one extreme point. The LP is either unbounded or
there exists a extreme point which is optimal.

In order to find an optimal solution, we only need to look among

basic feasible solutions.
LP is a convex optimization problem, which means local optimal is
global optimal.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 7 / 51

Conceptual of Simplex Algorithm

Start from a extreme point

#
Move to a neighboring extreme point that improves the objective

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 8 / 51

Outline

1 Basic Solution and Basic Feasible Solution

2 Finding a Basic Solution in Standard Form LP

3 LP Duality

4 Table of Possibles and Impossibles

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 9 / 51

Standard Form LP

In the following, we consider LP in its standard form:

min c ↭x
s.t. Ax = b
x ↔0

x ↑ Rn , i.e. there are n variables

A ↑ Rm→n , i.e. there are m equality constraints
We always assume all the m equality constraints are linearly
independent ((or equivalently A has full rank m), otherwise we can
remove all redundant linearly dependent constraints.
Always assume n > m, i.e. more variables than constraints. (Why?)
3 equation 2 unknowns - a point or infeasible
Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 10 / 51
Main Question

A basic solution is the unique solution to n linearly independent active

constraints.
For a standard form LP, we already have m linearly independent
active constraints.
Need n ↘ m additional linearly independent active constraints. Where
to find them? From nonnegative constraints: xi ↔ 0. But which to
choose to make active?

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 11 / 51

Finding a Basic Solution in Standard Form LP

Procedures to find a basic solution:

1 Choose any m independent columns of A: AB(1) , ..., AB(m) and form
the basis matrix B = [AB(1) , ..., AB(m) ]. Denote the rest of A as
matrix N.
2 Let xi = 0 for all i ↗= B(1), ..., B(m).
3 Solve the equation Ax = b for the remaining xB(1) , ..., xB(m) .
The basic solution is x = [xB , xN ], where the basic variables are
xB = B ↑1 b and the nonbasic variables are xN = 0.
Since AB(1) , ..., AB(m) are linearly independent, the last step must
produce a unique solution.
Basic solution of an LP only depends on its constraints, it has nothing
to do with the objective function.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 12 / 51

 AX = b
Y
columns numcotms

NJTBY
m

mrows
I B i
matrix
B : basis
N non-basis
: matrix
basic variables
Xi :

Xn : non-basic variables

b #Y Ax =
b
Con equations) BXB + ~X =

To find a BS , I need n equations ,

I already
b) then I still
havem equations (Ax
=
,

need n-m eluations

,
all of these are

from X20 >

-

XI0 .

which n-m X's to be zeo ?

Yn = 0

=>
in equations :

BY +NXr b
Ax b
> =

S
=

= 0
Xv BS
Note : XB = B"b Xn,
=o
may not be feasible !
 make XB B
+
b20 the
We need to sure = ,

this BS becomes BES.

Quiz !

How many BS can you find ?

(m)
How many BES can
you find ?

1 to (mm)
Quiz

How many non-zeros could one have in a basic solution (assuming there
are m constraints)?
No more than m
Could be anything between 0 to m, but typically it is m

How many basic solutions can one have for a linear program with m
constraints and n variables?
n!
At most C (n, m) = m!(n→m)! (Combination number)
Therefore for a finite number of linear constraints, there can only be a
finite number of basic solutions

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 13 / 51

Example

maximize x1 +2x2
subject to x1 → 100
2x2 → 200
x1 +x2 → 150
x1 , x2 ↑0

The standard form:

minimize ↓x1 ↓2x2

-
subject to x1 +s1 = 100
2x2 +s2 = 200
x1 +x2 +s3 = 150
x1 , x2 , s 1 , s 2 , s3 ↑0

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 14 / 51

Example Continued

D
We can write the feasible set by {x : Ax = b, x ↑ 0}. where
   
1 0 1 0 0 100
A =  0 2 0 1 0  b =  200 
1 1 0 0 1 150

Choose three independent columns of A, e.g., the first three, we get the
corresponding basic solution is
 →1    
1 0 1 100 50

feasible !
xB = B →1 b =  0 2 0   200  =  100 
1 1 0 150 50

That is x1 = 50, x2 = 100, s1 = 50. Therefore (50, 100, 50, 0, 0) is a basic

feasible solution. One can find other basic feasible solutions by choosing
other sets of columns.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 15 / 51

 ["
1
A =

Av = b

X, + X2

BYp + NXr =
b
Example Continued

We can list the basic (feasible) solutions

Indices {1, 2, 3} {1, 2, 4} {1, 2, 5} {1, 3, 4}
Solution (50, 100, 50, 0, 0) (100, 50, 0, 100, 0) (100, 100, 0, 0, -50) (150, 0, -50, 200, 0)
Status BFS BFS Basic but not feasible Basic but not feasible
Indices {1, 4, 5} {2, 3, 4} {2, 3, 5} {3, 4, 5}
Solution (100, 0, 0, 200, 50) (0, 150, 100, -100, 0) (0, 100, 100, 0, 50) (0, 0, 100, 200, 150)
Status BFS Basic but not feasible BFS BFS

The other two choices {1, 3, 5} and {2, 4, 5} lead to dependent basic
columns (therefore no basic solutions can be obtained)

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 16 / 51

Verify

They indeed correspond to all the corners of the feasible sets.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 17 / 51

Outline

1 Basic Solution and Basic Feasible Solution

2 Finding a Basic Solution in Standard Form LP

3 LP Duality

4 Table of Possibles and Impossibles

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 18 / 51

Duality Theory
(P) ZP = min x1 + 2x2 + 3x3
s.t. x1 + 5x2 + 4x3 → 6
2x1 + 3x2 ↑ x3 = 3
x1 + x2 ↑ 2x3 ↓ 4
x1 → 0, x2 ↓ 0, x3 free

(D) ZD = max 6y1 + 3y2 + 4y3

s.t. y1 + 2y2 + y3 ↓ 1
5y1 + 3y2 + y3 → 2
4y1 ↑ y2 ↑ 2y3 = 3
y1 → 0, y2 free, y3 ↓ 0
Duality theory is at the heart of optimization.
What motivates us to form the dual?
How do we form the dual problem?
Why do we form the dual this way?
Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 19 / 51
Motivation of Taking Dual

(P) min
s.t.
cT x
Ax ↓ b
B
Any feasible solution of a minimization LP (P) provides an upper
bound. The dual problem (D) of (P) is to find a lower bound (the
best lower bond) to the optimal cost of (P).
This lower bound is useful, because if the lower bound is very close to
an upper bound, we have a good estimate of the true optimal.
However, to get a lower bound, we need to modify the original LP. In
particular, we need to relax the problem.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 20 / 51

Lagrangian Relaxation and Lagrangian Duality

The process of formulating the dual that will give the best lower bound to
the optimal cost of (P) is called relaxation. Relax a minimization problem
(P) involves three principal steps:
Relax the objective function: by constructing a new objective function
that is always smaller or equal to the original objective function of (P)
over the feasible region of (P).
Relax the feasible region of (P): by enlarging the feasible region of the
original problem (P).
Maximize the lower bound over Lagrangian multipliers so that we get
the best lower bound.
This final maximization problem is called the Lagrangian dual problem, or
the dual problem for short.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 21 / 51

Primal LP

n
!
min c j xj
j=1
n
!
s.t. aij xj → bi ↔i = 1, ..., m1
j=1
!n
aij xj = bi ↔i = m1 + 1, ..., m2
j=1
!n
aij xj ↓ bi ↔i = m2 + 1, ..., m
j=1

xj → 0 ↔j = 1, ..., n1
xj free ↔j = n1 + 1, ..., n2
xj ↓ 0 ↔j = n2 + 1, ..., n

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 22 / 51

Example

(P) ZP = min x1 + 2x2 + 3x3

s.t. x1 + 5x2 + 4x3 → 6
2x1 + 3x2 ↑ x3 = 3
x1 + x2 ↑ 2x3 ↓ 4
x1 → 0, x2 ↓ 0, x3 free

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 23 / 51

Step 1: Relax Objective Function
By relaxing the objective function, we mean to formulate a new objective
function that is smaller than or equal to the original primal objective
function.
!n m
! n
!
c j xj + yi · (bi ↑ aij xj )
j=1 i=1 j=1

where yi ’s are Lagrangian multipliers.

" Since we require the new objective
is smaller, we need yi · (bi ↑ nj=1 aij xj ) ↓ 0.

Signated
n
!
aij xj → bi ↗ yi → 0
j=1
n
!
aij xj = bi ↗ yi free
j=1
!n
aij xj ↓ bi ↗ yi ↓ 0
j=1
Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 24 / 51
 New objective >
Longration Multiple
-

= ji-ij
②X;
8 Fix, Ibi the Yi

E If
If ,

bi then 3 : fres
If MijXj =
,

MiXjbi ,
the Like
Example

20
= 0
-
~
The new objective is = O

so treem
x1 + 2x2 + 3x3 + y1 · (6 → x1 → 5x2 → 4x3 ) + y2 · (3 → 2x1 → 3x2 + x3 )
-

·
+y3 · (4 → x1 → x2 + 2x3 )

We need

x1 + 5x2 + 4x3 ↑ 6 ↓ y1 ↑ 0
2x1 + 3x2 → x3 = 3 ↓ y2 free
x1 + x2 → 2x3 ↔ 4 ↓ y3 ↔ 0

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 25 / 51

Step 2: Relax Primal Constraints

We want to enlarge the feasible region of an optimization problem by

removing constraints. The relaxed problem becomes 0
n
! -m
! n
!
(LR) Z (y ) = min
xj
c j xj + 8
yi · (bi → aij xj )
-
j=1 i=1 j=1

s.t. xj ↑ 0 ↗j = 1, ..., n1
xj free ↗j = n1 + 1, ..., n2
xj ↔ 0 ↗j = n2 + 1, ..., n ↑

This problem (LR) is called the Lagrangian relaxation problem of the

original primal problem (P). The objective function of (LR) is called the
-
Lagrangian function. We have Z (y ) ↔ ZP for designated y ’s.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 26 / 51

How to make feasible region larger ?
~ delete constraints

B .
add constraints

X
Lagrangian relaxation problem

n
! m
! n
!
(LR) Z (y ) = min c j xj + yi · (bi → aij xj )
xj
j=1 i=1 j=1

s.t. xj ↑ 0 ↓j = 1, ..., n1
xj free ↓j = n1 + 1, ..., n2
xj ↔ 0 ↓j = n2 + 1, ..., n

m
! n
! m
! n
!
(LR) Z (y ) = yi bi + min c j xj → yi aij xj
xj
i=1 j=1 i=1 j=1

s.t. xj ↑ 0 ↓j = 1, ..., n1
xj free ↓j = n1 + 1, ..., n2
xj ↔ 0 ↓j = n2 + 1, ..., n

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 27 / 51

 &
injXjYibi-iijX;

Fitbiti X
; free ,jEJ

Xio JES

min((-) Xj
Xj

minIdij)X ;
=

=
mindjXj
Edi
We want to solve

me
.

I
Case I:

mdXj
Case I

mida
II
Case

min diXj =
Separable Lagrangian Relaxation Problem

The Lagrangian relaxation problem is separable and it can be divided into

n smaller problems.
m
! n
! m
!
Z (y ) = yi b i + min cj xj → yi aij xj
xj

=
i=1 j=1 i=1

m
" #
! 0 if cj → m

ja
i=1 yi aij ↑ 0 (a)
min (cj → yi aij )xj =
xj →0
i=1
→↓ otherwise
m
" #
! 0 if cj → m i=1 yi aij = 0 (b)
min (cj → yi aij )xj =
xj free
i=1
→↓ otherwise
m
" #
! 0 if cj → mi=1 yi aij ↔ 0 (c)
min (cj → yi aij )xj =
xj ↑0
i=1
→↓ otherwise

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 28 / 51

Lagrangian Relaxation Problem

m
! n
! m
!
Z (y ) = yi b i + min cj xj → yi aij xj
xj
i=1 j=1 i=1
"#
m
i=1 yi bi
if (a), (b), (c) hold for all xj
=
→↓ otherwise
#m
With designated y ’s, Z (y ) is a lower bound on ZP , i.e. i=1 yi bi ↔ ZP .
P ro

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 29 / 51

Example

The Lagrangian relaxation problem is

Z (y ) = min x1 + 2x2 + 3x3 + y1 · (6 → x1 → 5x2 → 4x3 )

x1 ,x2 ,x3 --

+ y2 · (3 → 2x1 → 3x2 + x3 ) + y3 · (4 → x1 → x2 + 2x3 )

- -

s.t. x1 ↑ 0, x2 ↔ 0, x3 free
-

Z (y ) =6y1 + 3y2 + 4y3

imm di
min {(1 → (y1 + 2y2 + y3 ))x1 }
x1 →0
-
+ min {(2 → (5y1 + 3y2 + y3 ))x2 }
x2 ↑0
-3
+ min {(3 → (4y1 → y2 → 2y3 ))x3 }
x3 free
-

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 30 / 51

Example

"
0 if 1 → (y1 + 2y2 + y3 ) ↑ 0 (aa)
min {(1 → (y1 + 2y2 + y3 ))x1 } =
x1 →0 →↓ otherwise
"
0 if 2 → (5y1 + 3y2 + y3 ) ↔ 0 (bb)
min {(2 → (5y1 + 3y2 + y3 ))x2 } =
x2 ↑0 →↓ otherwise
"
0 if 3 → (4y1 → y2 → 2y3 ) = 0 (cc)
min {(3 → (4y1 → y2 → 2y3 ))x3 } =
x3 free →↓ otherwise

"
6y1 + 3y2 + 4y3 if (aa), (bb), (cc) hold
Z (y ) =
→↓ otherwise

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 31 / 51

Step 3: Finding the best lower bound

The best lower bound means the lower bound that is the closest to ZP .
The following LP finds the best lower bound by maximizing Z (y ) over the
constraints (a), (b), (c), and the sign constraints on y’s.

ZD = max Z (y )
Oyi

s.t. (a), (b), (c) ②

V
Jo
yi ↑ 0 ↘i = 1, ..., m1
·

-zl
yi is free ↘i = m1 + 1, ..., m2
-

z(Y)
yi ↔ 0 ↘i = m2 + 1, ..., m
-
z(Yz)
-
z(Y)
Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 32 / 51
Dual problem

m
!
(D) ZD = max b i yi
yi
i=1
!m
s.t. aij yi ↔ cj j = 1, ..., n1
i=1
!m
aij yi = cj j = n1 + 1, ..., n2
i=1
m
!
aij yi ↑ cj j = n2 + 1, ..., n
i=1
yi ↑ 0 ↘i = 1, ..., m1
yi is free ↘i = m1 + 1, ..., m2
yi ↔ 0 ↘i = m2 + 1, ..., m

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 33 / 51

Example

(P) ZP = min x1 + 2x2 + 3x3

x1 ,x2 ,x3

s.t. x1 + 5x2 + 4x3 ↑ 6

2x1 + 3x2 → x3 = 3
x1 + x2 → 2x3 ↔ 4
x1 ↑ 0, x2 ↔ 0, x3 free

(D) ZD = max 6y1 + 3y2 + 4y3

y1 ,y2 ,y3

s.t. y1 + 2y2 + y3 ↔ 1 (aa)

5y1 + 3y2 + y3 ↑ 2 (bb/
4y1 → y2 → 2y3 = 3 (c)
y1 ↑ 0, y2 free, y3 ↔ 0
Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 34 / 51
General LP Dual

Primal Dual
minimize cT x maximize bT y
subject to aiT x ↑ bi , i ≃ M1 , subject to yi ↑ 0, i ≃ M1
aiT x ↔ bi , i ≃ M2 , yi ↔ 0, i ≃ M2
aiT x = bi , i ≃ M3 , yi free, i ≃ M3
xj ↑ 0, j ≃ N1 , ATj y ↔ cj , j ≃ N1
xj ↔ 0, j ≃ N2 , ATj y ↑ cj , j ≃ N2
xj free, j ≃ N3 , ATj y = cj , j ≃ N3

aiT is the ith row of A, Aj is the jth column of A

*
Each primal constraint corresponds to a dual variable
Each primal variable corresponds to a dual constraint
Equality constraints always correspond to free variables

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 35 / 51

Rules to Form Dual Problem

↓ d
Primal minimize maximize Dual

-
↑ bi ↑0
Constraints ↔ bi ↔0 Variables
= bi free
↑0 ↔ cj
Variables ↔0 ↑ cj Constraints
free = cj

Penal left -> right

&
mir

max right -> left

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 36 / 51

Example

max x1 + 2x2 + x3 + x4
s.t. x1 + 2x2 + 3x3 ↔ 2<Y ) .

x2 + x4 ↔ 1 [Yz)
I

x1 + 2x3 ↑ 1 x(ys)
x1 , x3 ↑ 0, x2 , x4 free

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 37 / 51

(P) max
EX +RX2-BYs +RX4
.

StgXv
&2 (9 . /

②I (Y3/

V,, X320 ,
X2 ,
X+ free

(D) min .
2y ,
+ y + y
+
y -1
+
S t
.

ye = 2

+2 % 31
Y2 = 1
,
Y 20, Y220 , 30
Primal and Dual Pair in Standard Form

(P) min c ↭x (D) max b↭ y

s.t. Ax = b s.t. A↭ y ↑ c
x →0 y free

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 38 / 51

Invariance of Transformations

Theorem
If we transform a linear program to an equivalent one (such as by replacing
free variables, adding slack variables, etc), then the dual of the two
problems will be equivalent.

Theorem
If we transform the primal to its dual, then transform the dual to its dual,
then we will obtain a problem equivalent to the primal problem, that is,
the dual of dual is the primal.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 39 / 51

Weak Duality Theorem

Primal Dual
min cT x max b T y
s.t. Ax = b, x → 0 s.t. AT y ↑ c

Theorem (Weak Duality Theorem)

If x is feasible to the primal and y is feasible to the dual, then

bT y ↑ c T x

If the primal is a minimization and dual is a maximization, then

Any dual feasible solution will give a lower bound on the primal
optimal value
Any primal feasible solution will give an upper bound on the dual
optimal value
The optimal value of primal is larger than that of dual
Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 40 / 51
Corollary of Weak Duality

If the optimal objective value of the primal minimization problem is

↓↔ (i.e., the primal problem is unbounded), then the dual
maximization problem must be infeasible.
If the optimal cost of the dual maximization problem is +↔ (i.e., the
dual problem is unbounded), then the primal minimization problem
must be infeasible.
Let x → be feasible to the primal problem and y → be feasible to the
dual problem, and suppose c T x → = b T y → , then x → and y → are optimal
solutions to the primal and dual problems, respectively.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 41 / 51

Strong Duality

Strong Duality Theorem

If a primal linear program (P) has a finite optimal solution x → , then its
dual linear program (D) must also have a finite optimal solution y → , and
the respective optimal objective values are equal, that is c T x → = b T y → .

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 42 / 51

Discussion

Based on the strong duality theorem, we know that (x, y ) is optimal to the
primal and dual respectively if and only if
x is primal feasible
y is dual feasible
They achieve the same objective value

Therefore solving LP is in fact equivalent as solving the following linear

system:
Ax = b, x → 0
AT y ↑ c
bT y = c T x

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 43 / 51

Outline

1 Basic Solution and Basic Feasible Solution

2 Finding a Basic Solution in Standard Form LP

3 LP Duality

4 Table of Possibles and Impossibles

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 44 / 51

Table of Possibles and Impossibles

The primal and dual LPs can be finite optimal, or unbounded, or

infeasible. So, there are in total 9 combinations. Are all these 9
combinations possible?
Finite Optimal Unbounded Infeasible
Finite Optimal Possible Impossible Impossible
Unbounded Impossible Impossible Possible
Infeasible Impossible Possible Possible
Notice this table is exactly symmetric, because the dual of the dual is the
primal.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 45 / 51

Figuring out the possibilities

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 46 / 51

Figuring out the possibilities

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 47 / 51

Figuring out the possibilities

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 48 / 51

Complementarity Conditions
Consider the primal-dual pair:
Primal Dual
minimize cT x maximize bT y
subject to aiT x → bi , i ↗ M1 , subject to yi → 0, i ↗ M1
aiT x ↑ bi , i ↗ M2 , yi ↑ 0, i ↗ M2
aiT x = bi , i ↗ M3 , yi free, i ↗ M3
xj → 0, j ↗ N1 , ATj y ↑ cj , j ↗ N1
xj ↑ 0, j ↗ N2 , ATj y → cj , j ↗ N2
xj free, j ↗ N3 , ATj y = cj , j ↗ N3

Theorem
Let x and y are feasible solutions to the primal and dual problems
respectively. Then x and y are optimal if and only if

yi · (aiT x ↓ bi ) = 0, ↘i; xj · (AT

j y ↓ cj ) = 0, ↘j.

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 49 / 51

Complementary Slackness

Let x and y be feasible solutions to the primal and dual problem,

respectively. Then x and y are optimal solutions for the two respective
problems if and only if they satisfy the following conditions:
Primal Complementary Slackness: yi (ai↭ x ↓ bi ) = 0 for all i. In words,
either the i-th primal constraint is active (binding, tight) so ai↭ x = bi ,
or the corresponding dual variable yi = 0.
Dual Complementary Slackness: xj (AT j y ↓ cj ) = 0 for all j. In words,
either the j-th dual constraint is active (binding, tight) so AT j y = cj ,
or the corresponding primal variable xj = 0.

Proof in homework!

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 50 / 51

Example

min 13x1 + 10x2 + 6x3 max 8y1 + 3y2

s.t. 5x1 + x2 + 3x3 = 8 s.t. 5y1 + 3y2 ↑ 13
3x1 + x2 = 3 y1 + y2 ↑ 10
x1 , x2 , x3 → 0 3y1 ↑ 6
Someone solved the dual problem graphically, and told us the dual
optimal solution y1→ = 2, y2→ = 1. We want to use this information and
Complementary Slackness to get the optimal solution of the primal.
If we are given a primal feasible solution x1→ = 1, x2→ = 0; x3→ = 1, can
we verify this is an optimal solution?

Yuang Chen (SDS/CUHK-SZ) DDA5002/CIE6010 Lecture 11 March 5, 2025 51 / 51