COMP3530 Discrete Optimization
Week 4: Duality
Julian of Computer Science University of and Refresher
Goal for Today
Introduce Linear Programming duality and show how to certify optimality.
“”” t
LP
tI
”
DUAL
1
Recall
A Linear Program is optimization problem of the form minimize c · x
A-✗= 6 ✗70
rows of A
subject to Ax b x 2 Rn
+→ program in standard form.
whereA2Rm⇥n,b2Rm,andc2Rn.
Any general Linear Program can be reduced to an equivalent
I
are
L
.
.
Simplex algorithm solves Linear Programs in standard form.
2
Duality
Bounding the Value of an LP?
1 24+3×2
2/4+3×2
✗• +5×254
z⇤ = maximize 2×1 + 3×2 subject to 6×1 + 4×2 10
x1 + 5×2 4 x1,x2 0
f
2-* soo
-2*58
z-E-5.ci
it
6/1,1-4×2510
=D
2
3
f- ✗
524,1-5×2/52.4=8
⇒
[6%+4×2500]
2 ✗ r t ¥ É É ( + ; 4×2 ) 54+1,1=5.0 3
Finding the
z⇤ = maximize 2×1 + 3×2
subject to 6×1 + 4×2 10 ( %)
(
(4%+542)×2
T
need this = min 10Yo+*YL
x1 + 5×2 4 x1,x2 0
t✗
§toy, +442 |z*§
72
yy, +542
Yr , Yz ZO
5. 1- GY
,
+42
FÉ=¥¥¥
Y, = Yz=’%o E- 4 7126 5%
73
Primal-Dual programs
A 2 Rm⇥n: matrix with columns A1,…,An and rows a1T,…,amT. m
i-n ls.t.
[ bi Yi fi
min ¥ cjxj ,
m a x
) a:X > bi
Hiett ( Xj
)
ytn-jfcj-Vjc.nu
(Xj) yTAj > Cj jerk (Yi) atix-biv-ic-Mzcjlytn-j-cj-vjc-Nztxiej7d.co
( %)
atixfbi
Kiene
tjtN, Yi > 0 , (1) XJEO Kjell Y i£ ° ltiemz
I. free then, (D) Yi free
ltiemz
5
✗
Weak Duality
Thm.: Let x and y be feasible primal-dual solutions then it must bethatc···xb·y. c. ✗ b-Y
Proof
EMER 3 I
É
7,2
YTAJ
Xj
c.✗=
j-. r j=
m
im
bi
ai [ [
i
(D)
( P)
Corollary :
If (P) is
unbounded
unbounded
= D = D
infeasible
infeasible
=
YTA✗ =
e-= )
✗
Yi
=\ =b•Y
☐
If
(D) is
6
Weak Duality
Thm.: Let x and y be feasible primal-dual solutions then it must
b e t h a t c M· · · x b r · y .
c. ✗ 7 boy
Max 2% Yi =
YSO ✗,,
m in
(Y) ×, £2 ((Xo)
✗ ,
unbounded
infeasible
free
i
6
Strong Duality
Thm.: If the primal (dual) problem is feasible and has bounded LPs objective then so that the dual (primal). Furthermore, both
s_olut_ions have the same value.
(D)
/
b. y Atysc
✗ free
fioofp ) 0¥
min c.✗ St Aeb
M a x
/ m p le x
✗z,
P) =D returns B
/ standard form
1 =D
E- YTAZO
* Asci ⇒
y is
feasible
dual
/2;¥F?¥;a÷
Define E- EBA”B
(
inducing ✗ B=A 6
s✗ .
b-f. ✗j=oj¢B
EigXp
=C.
=✗
7
/
Strong Duality
Thm.: If the primal (dual) problem is feasible and has bounded
objective then so that the dual (primal). Furthermore, both
LPs s=olutionshavethesamevalue. (D)
920
m i-c.im # (p)A-✗ AT=L I
–
I✗ mine I
76 y
free
( P ‘ )
.
“” ÑY ñ x s i
I free
(D)
A- E – I ← , ✗ y ,
7
Certifying Properties
Certifying Optimality
Obs.: To certify that a given feasible primal solution x is optimal, we need to produce a feasible dual solution y with the same cost.
8
Complementary Slackness
“”
2. yi =0oraiTx=bi foralli.
n I[in
bi .: Let x and y be optimal primal and dual solutions, then: 1. xj =0oryTAj =cj forallj,
g. × ; > [ yTAj✗j=yTA✗ .- Zyiatix >
i= ‘
j=,
5=1
i= , f aÉx3b;
atixsbi
Ñi✗=b;
p
Cj > YTA; cjfyt =yTAj
for f- 30 for XJEO for g- tree
Ipo
Tito
Yitree
9
Certifying Infeasibility
Thm.: Let A 2 Rm⇥n, b 2 Rm then exactly one of these holds: 1. 9x 2Rn :Ax =b,x 0,
¥2. 9y 2 Rm : AT y 0, b · y < 0. suHoosebothareT
AJ Z o YTA 70T
YTA ✗ 30T✗
ytb
Suppose both are false maxo•x⇐minb
7,0
S.t. Ax :b ✗ 30
is infeasible
Aiyzo
y free feasible
unbounded
objective
f . y 7,0 CONTRADICTION !
CONTRADICTION !
boy co
10
Administratrivia
Announcements
• Install Gurobi on your computer, apply for an academic license, and run the Jupyter notebook from the demo.
• How are the tutorials going? To make the most of your tutorial, please attempt the problems ahead of time.
• due on September 10 (11:59pm)
• submission is via Gradescope (up and running)
82
• Assignment 1:
• available in Ed (resource tab)
11
12