程序代写 COMP3530 Discrete Optimization – cscodehelp代写

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···xb·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