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