Optimization Methods Duality Theory I

Optimization Method Duality Theory 1 Outline � � � � � � Slide 1 Motivation of duality General form of the dual Weak and strong duality Relations between primal and dual Economic Interpretation Complementary Slackness 2 Motivation 2.1 An idea from Lagrange Consider the LOP, called the primal with optimal solution x� min c0 x s t Ax = b : : Relax the constraint x�0 c0x + p0(b ; Ax) x�0 (p) � c0x� + p0 (b ; Ax� ) = c0 x� g (p) = min st : : g Get the tightest lower bound, i.e., max ( ) g p g Note that (p) = min h 0 0 x�0 c x + p (b ; Ax) = p0 b + min(c0 ; p0 A)x x�0 i c0 ; p0A � 00, min(c0 ; p0A)x = 0;1 ifotherwise. x�0 Dual max (p) , max p0b s t p0A � c0

g : : 1 Slide 2 3 General form of the dual Primal cx ai x � ai x � ai x = min s:t: Dual 0 0 0 0 j�0 j�0 > xj < 0 i i bi b i b i i x j x j j 2 2 2 2 2 2 max s:t: M1 M2 M3 constraints variables 0 i�0 i�0 > pi < 0 p Aj � cj p Aj � cj p Aj = cj p i p i 0 0 N3 min x1 + 2x2 + 3x3 s:t: ;x1 + 3x2 =5 2x1 ; x2 + 3x3 � 6 x3 � 4 x1 � 0 x2 � 0 x3 free
i j j j 2 2 2 2 2 2 M1 M1 M3 N1 N2 N3 max 5p1 + 6p2 + 4p3 s:t: p1 free p2 � 0 p3 � 0 ;p1 + 2p2 �1 3p1 ; p2 �2 3p2 + p3 = 3: min � � pb 0 N1 N2 3.1 Example Primal Slide 3 max �0 �> 0 <0 i bi = bi b �0 �> 0 � � j j = cj <0 c c Slide 4 Slide 5 dual variables constraints Theorem: The dual of the dual is the primal. 3.2 A matrix view min c0 x s t Ax = b max p0 b s t p0 A � c0 : : Slide 6 : : x�0 min c0 x s t Ax � b max p0 b s t p0 A = c0 : : : : p�0 4 Weak Duality Theorem: If x is primal feasible and p is dual feasible then p0b � c0x Proof p0b = p0Ax � c0x 2 Slide 7 Corollary: If x is primal feasible, p is dual feasible, and p0b = c0 x, then x is optimal in the primal and p is optimal in the dual. 5 Strong Duality Theorem: If the LOP has optimal solution, then so does the dual, and optimal costs are equal. Proof: min c0 x s t Ax = b Slide 8 : : x�0 Apply Simplex optimal solution x, basis B . Optimality conditions: c0 ; c0B B;1A � 00 Slide 9 De ne p0 = c0B B ;1 ) p0 A � c0 ) p dual feasible for max p0 b s t p0 A � c0 : : p0b = cB0 B;1b = cB0 xB = c0 x ) x p are primal and dual optimal
5.1 Intuition Slide 10 a3 c a2 a1 p 1a 1 p 2a 2 . x* 3 6 Relations between primal and dual Finite opt. Unbounded Infeasible Finite opt. Unbounded Infeasible * * * * 7 Economic Interpretation Slide 12 x optimal nondegenerate solution: B;1b 0 � Suppose b changes to b + d for some small d � � � � � � Slide 11 > How is the optimal cost aected? For small d feasibilty unaected Optimality conditions unaected New cost c0B B ;1 (b + d) = p0 (b + d) If resource changes by i, cost changes by i i : \Marginal Price" i d p d 8 Complementary slackness 8.1 Theorem Let x primal feasible and p dual feasible. Then x p optimal if and only if Slide 13 i (a0i x ; bi ) = 0
8i p j (cj ; p0Aj ) = 0
8j x 8.2 Proof � � � � i = pi (a0i x ; bi ) and vj = ( j ; p0Aj ) j If x, p primal and dual feasible, i � 0, j � 0 8 . P P Also c0 x ; p0 b = i i + j j By the strong duality theorem, if x and p are optimal, then c0 x = p0 b ) i = j = 0 for all , . Conversely, if i = j = 0 for all , , then c0 x = p0 b, ) x and p are optimal. u � x u u u � c i v u v v v : j i 4 j i
j Slide 14 8.3 Example min 13 st 5 3 x1 x1 : : x1 x1 + 10 + + x2 x2

x3 x3 x2
Is x = (1 0 1) optimal? � +6 +3 x2
x3 max 8 st 5 p1 =8 =3 � 0 : : 3 p1 0 p2 p2 p2 Slide 15 � � � 13 10 6 Slide 16 5 1 + 3 2 = 13 3 1 = 6 p p ) p1 Objective=19 p1 p1 +3 +3 +
=2
5 p p2 =1