Unformatted text preview:

LogisticsReviewMore PolytopesPolymatroidMost Violated InequalityScratchSummaryLogistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryEE595A – Submodular functions, their optimizationand applications – Spring 2011Prof. Jeff BilmesUniversity of Washington, SeattleDepartment of Electrical EngineeringWinter Quarter, 2011http://ee.washington.edu/class/235/2011wtr/index.htmlLecture 7 - April 20th, 2011Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 1Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryAnnouncementsReminder, HW1 is on the web page now, at http://ssli.ee.washington.edu/~bilmes/ee595a_spring_2011/hw1.pdfIt is due, Tuesday, April 26th, 11:45pmAll submissions must be done electronically, via our drop box. Seethe linkhttps://catalyst.uw.edu/collectit/dropbox/bilmes/14888,or look at the homework on the web page.Please write down your email on paper for me.Engineering Discovery Dayshttp://www.engr.washington.edu/alumcomm/openhouse.html,so no class on Friday.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 2Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryConvex Polytope - key representation theoremA polytope can be defined in a number of ways, two of which includeTheorem 2.1A subset P ⊆ REis a polytope iff it can be described in either of thefollowing (equivalent) ways:P is the convex hull of a finite set of points.If it is a bounded intersection of halfspaces, that is there exits matrix Aand vector b such thatP = {x : Ax ≤ b} (1)This result follows directly from results proven by Fourier, Motzkin,Farkas, and Car´atheodory.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 3Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryConvex Polytope - key representation theoremA polytope can be defined in a number of ways, two of which includeTheorem 2.1A subset P ⊆ REis a polytope iff it can be described in either of thefollowing (equivalent) ways:P is the convex hull of a finite set of points.If it is a bounded intersection of halfspaces, that is there exits matrix Aand vector b such thatP = {x : Ax ≤ b} (1)This result follows directly from results proven by Fourier, Motzkin,Farkas, and Car´atheodory.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 3Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryIndependence PolyhedraFor each I ∈ I of a matroid M = (E, I), we can form the incidencevector 1I.Taking the convex hull, we get the independent set polytope, that isPind. set= conv {∪I ∈I1I} (2)Now take the rank function r of M, and define the followingpolyhedron:Pr=nx ∈ RE: x ≥ 0, x(A) ≤ r(A), ∀A ⊆ Eo(3)Theorem 2.2Pr= Pind. set(4)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 4Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryIndependence PolyhedraFor each I ∈ I of a matroid M = (E, I), we can form the incidencevector 1I.Taking the convex hull, we get the independent set polytope, that isPind. set= conv {∪I ∈I1I} (2)Now take the rank function r of M, and define the followingpolyhedron:Pr=nx ∈ RE: x ≥ 0, x(A) ≤ r(A), ∀A ⊆ Eo(3)Theorem 2.2Pr= Pind. set(4)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 4Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryIndependence PolyhedraFor each I ∈ I of a matroid M = (E, I), we can form the incidencevector 1I.Taking the convex hull, we get the independent set polytope, that isPind. set= conv {∪I ∈I1I} (2)Now take the rank function r of M, and define the followingpolyhedron:Pr=nx ∈ RE: x ≥ 0, x(A) ≤ r(A), ∀A ⊆ Eo(3)Theorem 2.2Pr= Pind. set(4)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 4Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryIndependence PolyhedraFor each I ∈ I of a matroid M = (E, I), we can form the incidencevector 1I.Taking the convex hull, we get the independent set polytope, that isPind. set= conv {∪I ∈I1I} (2)Now take the rank function r of M, and define the followingpolyhedron:Pr=nx ∈ RE: x ≥ 0, x(A) ≤ r(A), ∀A ⊆ Eo(3)Theorem 2.2Pr= Pind. set(4)Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 4Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryMatroid Polyhedron in 2DPr=nx ∈ RE: x ≥ 0, x(A) ≤ r(A), ∀A ⊆ Vo(5)Consider this in two dimensions. We have equations of the form:x1≥ 0 and x2≥ 0 (6)x1≤ r({v1}) (7)x2≤ r({v2}) (8)x1+ x2≤ r({v1, v2}) (9)Because r is submodular, we haver({v1}) + r({v2}) ≥ r({v1, v2}) + r(∅) (10)so since r({v1, v2}) ≤ r({v1}) + r({v2}), the last inequality is eithertouching or active.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 5Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryMatroid Polyhedron in 2DPr=nx ∈ RE: x ≥ 0, x(A) ≤ r(A), ∀A ⊆ Vo(5)Consider this in two dimensions. We have equations of the form:x1≥ 0 and x2≥ 0 (6)x1≤ r({v1}) (7)x2≤ r({v2}) (8)x1+ x2≤ r({v1, v2}) (9)Because r is submodular, we haver({v1}) + r({v2}) ≥ r({v1, v2}) + r(∅) (10)so since r({v1, v2}) ≤ r({v1}) + r({v2}), the last inequality is eithertouching or active.Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 5Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryMatroid Polyhedron in 2Dx1x2x1x2r(v1)=1r(v1)=1r(v2)=1r(v2)=0x1+ = 2x2= r({v1, v2})x1+ = 1x2= r({v1, v2})= 1r({v1, v2})= 0r({v1, v2})x1x2x1x2r(v1)=1r(v2)=1x1≥ 0x2≥ 0x1≤ r({v1})x2≤ r({v2})x1+ x2≤ r({v1, v2})And, if v2 is a loop ...Prof. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 6Logistics Review More Polytopes Polymatroid Most Violated Inequality Scratch SummaryMatroid Polyhedron in 2Dx1≥ 0x2≥ 0x1≤ r({v1})x2≤ r({v2})x1+ x2≤ r({v1, v2})PossibleNotPossibleNotPossibleProf. Jeff Bilmes EE595A/Spr 2011/Submodular Functions – Lecture 7 - April 20th, 2011 page 7Logistics Review More Polytopes


View Full Document

UW EE 595A - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?