New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Gregg Ziemann


Gregg Ziemann
GPA 3.77


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Military Science

This 8 page Class Notes was uploaded by Gregg Ziemann on Sunday September 6, 2015. The Class Notes belongs to M S 0 at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 10 views. For similar materials see /class/181775/m-s-0-university-of-texas-at-austin in Military Science at University of Texas at Austin.




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 09/06/15
EE 381V Convex Optimization 7 Theory and Applications Fall 2007 Lecture 10 7 October 8 Lecturer Constantine Caramanis Scribe H Ku B Rengarajan S Yun 101 Topics covered 1 Geometric multipliers 2 Duality and the dual problem 3 Sufficient conditions for strong duality 4 Min common max crossing problem 102 The optimality condition for constrained convex set In the last class we discussed local optimality conditions for constrained convex optimization and began considering duality and the dual function as well as geometric multipliers and graphical interpretations of complementary slackness and the primal dual relationship In this lecture we continue along these themes We provide the picture of complementary slackness and present some results concerning the primal and dual problems and their relationship Next we give two sets of sufficient conditions that guarantee that there is no duality gap between the primal and dual problems We also show the road map of proving one of condition and give part of the proof which is then completed in the next lecture Recall that in the last two lectures we saw the optimality condition 0 E a f Tcz 101 Now consider the optimization problem min x 7 st hz0 f 7 900 0 m EX From this we considered the Lagrangian function Lm u x hm ugz where we took M Z 0 The restriction of nonnegativity of u can be seen as related to the optimality condition given above 0 E a m Tcz To see this consider a simpler case where L is differentiable We want to nd 3 M so that F giro WM M9xl 102 10 1 EE 381V Lecture 10 7 October 8 Fall 2007 Suppose Hf such that the in mization on the right hand side of the above equation is attained Then since L is continuous and convex VmLm 0 Thus Vm AVmM uVmgm 0 Note that this is essentially the optimality condition 0 E me Tcz0 103 Recall from a past lecture that the tangent cone Tcz is the closure of all feasible directions of motion Thus in our setting we have Tcz lehzTd 0VgmTd 0 104 Now from Farkas s lemma which you prove on a homework the polar cone Tcz0 can be rep resented as Tcm0 c0neVhm7VhmVgm A1Vhm 27Vhz qux 1 A2 2 0 WWW MWWL M Z 0 ln Lecture 8Section 84 and Figure 86 we saw an example where we have failure of existence of Lagrange multipliers due to a local reason This is different from a failure of strong duality ie a non zero duality gap We explore this latter topic in this lecture De nition The YUM pair is called a geometric multipliersource Bertsekas Ozdaglar Nedic if m 2 0 and r infmgx maxim Proposition 101 If 1 is a Geometric multiplier then f is a global minimum iff a f is feasible f E X hz 0gz 0 b Lm u minmgx Lm u 0 WWW 04 Proof The sufficiency is clear and follow is the proof of necessity lf is the global min then a is true naturally because that is the constraints of the problem For a global minimum by de nition we have F g 2 fhm 9f LVJif Z infmexLWJif 10 so that b is true For 0 because hm 0 gt pgm 0 hence c is proved 10 2 EE 381V Lecture 10 7 October 8 Fall 2007 For the Geometric multiplier and Lagrange multiplier we can make some comments as follows a Assume the problem is convex and f is a global minimum then set of both Geometric multiplier and Larange multiplier are the same b For convex problems the set of Geometric multiplier does not depend on the optimal solution f it is the same for all f and may be nonempty even if the problem has no optimal solution c For nonconvex problems the Geometric multiplier may not exist at all 103 Picture of Complementary Slackness We can give a pictorial representation of the meaning of the constraint pgm 0 given in the proposition above Consider again the Min Common PointMax Crossing problem without loss of generality we consider only inequality constraints min x st gz 0 Fig 103 is a case where u 0 and gz lt 0 while Fig 103 shows a case where u 7 O and 9M 0 0 S 9z fzlz E 7W g lt0 M0 Figure 101 Complementary slackness in the min common pointmax crossing problem EE 381V Lecture 10 7 October 8 Fall 2007 104 Dual Function and Duality As we did in the previous lecture let us consider again the following optimization problem which we call the primal optimization problem min fz st him0i1r gjz 0j1m mEX The dual objective function is de ned as q u infmeXLm u For a graphical interpretation of this function see the previous lecture The dual optimization problem is ql ma q7 M st 1 2 0 Proposition 102 q is closed upper semi continuous and concave Proof This follows from the de nition of q as an in mum over linear functions D Proposition 103 For any primal feasible point z and dual feasible u we have qu fm and in particular q F This is called Weak Duality Proof For any xed Ana we have q M infzeX LZ M 1an feasible HZ O M9Z 1an feasible f 2 10 D Proposition 104 The vectors f x if form an optimal solution geometric multiplier pair iff 1 Primal Feasibility f E X hz O gz 0 2 Dual Feasibility if 2 0 3 Lm A infieldm A 4 Complementary Slackness pgm 0 Proof gt It is clear that the conditions above hold if z x if form an optimal solution geometric multiplier pair from the de nition of a geometric multiplier pair 10 4 EE 381V Lecture 10 7 October 8 Fall 2007 F fz by de nition Lm if by conditions 1 and 4 min metMm xiii by condition 3 q7 If at q Also F 2 q by Prop 103 Thus F q E Proposition 105 Saddle point The vectors mu form an optimal solution geometric multiplier pair iff z E X A 2 0 f x if is a saddle point for Lm Ana ie Lxu Lxu Lmu V m E X u 2 0 Proof gt If f x M form an optimal solution geometric multiplier pair MKJM l A b R Also Lm x M infmeXLm x M by Prop 104 Thus Lzu Lm u LWiAMSLWi mU f0 MW 11993 Hf WW W90 5 MW WW S WW 1390 VM 2 0 105 Setting 1 1 in Eq 105 we get hm hz VA This can only be true if hz 0 Thus we now have WW S W903 VP 2 0 106 This implies gz 0 Setting 1 0 in Eq 106 we get pgz 2 0 But gz 0 and pgm 2 0 implies pgm 0 Also Lzu Lmu Vz E X implies Lm x M infmeXLm x M Thus all the conditions in Prop 104 are satis ed and f u form an optimal solution geometric multiplier pair D 105 Suf cient conditions for strong duality 1051 Two sets of su icient condition to guarantee no duality gap 0 A1 For C a convex set and P a polyhedral set 10 5 EE 381V Lecture 10 7 October 8 Fall 2007 7 F is nite 7 X P O C 7 f is convex on C 7 3 a feasible solution in the relative interior of C 0 A2 slater s condition 7 F is nite 7 X is convex 7 feasible set is X g 0 and g are all convex 7 There exists i E X st gJi lt 0 for Vj Theorem 106 Under either A1 or A2 there is no duality gap and the set of Geometric Multiplier is not empty 1052 Road map to proof of Thm 106 under condition A1 a Go back to Min commonMax crossing and give suf cient conditions for 10 q b Prove nonlinear version of Farkas s lemma c Use Farkas s lemma to prove the strong duality theorem 1053 Su icient conditions for strong duality in the Min commonMax crossing problem Let us recall the general setting ofthe Min common Max crossing problem Given a set M Q Rn we de ne the Min common problem as min w Ow6M We de ne the max crossing problem as 516 N where the function qu is de ned by 610 w Wu Theorem 107 If following three conditions are true 0 10 is nite o M 7110le w With mu 6 M o 0 E intD7 D Ule with U710 E M 10 6 EE 381V Lecture 10 October 8 Fall 2007 H l Figure 102 q 212 then 1 w and C5 MWi 10 0 Given a set M the set M is the extension upward of M This is illustrated in Figure 102 Proof First we note that by our construction of M and by the assumed optimality of w the point 0 w cannot be contained in the relative interior of M This follows because the direction of optimization down the vertical axis is in a M In particular 0 w must be on the relative boundary of M Now since M is convex and 0 w is on the relative boundary of M there exists a supporting hyperplane H through 0 w which does not contain all of M Call this hyperplane H HWSOLT Then we have 7 lt8730707wgt 80w su sow 2 7 sowquot Vuw EM 107 sups u sowuw E M gt sow 108 Inequality 107 expresses the fact that H is a supporting hyperplane and then the strict inequal ity of 108 expresses the fact that H does not contain all of M Suppose so lt 0 Then we can let w enough large so that 107 does not hold Suppose so 0 Then from 107 su Z 0 Vu E D But since 0 6 1 this implies that we must have s 0 But this is a contradiction to 108 Thus so gt 0 and thus by a positive 10 7 EE 381V Lecture 10 7 October 8 Fall 2007 normalization we can take so 1 Therefore from 107 w lt3ugtw Vuw EM lt inf w uw6lts ugt w lt f 7 136me w 618 E f But by weak duality 10 2 q Thus 10 q thus concluding the proof D 1054 Farkas7s Lemma We state the nonlinear version of Farkas s lemma here deferring the proof to the next lecture Lemma 108 Consider the optimization problem F min x st 990 S 0 m E C where C is a convex set and f and g are convex functions as in this and previous lectures 9 could represent a vector valued function in which case we understand each statement about 9 to be interpreted in a component wise fashion Now de ne the set Q My 2 0 x 1 uTgm 2 O Vz E C Then 3 E Cstgi lt 0 ltgt C is non empty and compact


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Steve Martinelli UC Los Angeles

"There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

Janice Dongeun University of Washington

"I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.