Submodularity Reading Group and Linear Programming Overview

Slide Note

In this detailed reading group session led by Pawan Kumar, explore topics like Matroid Polytopes, Polymatroid, linear programming, and more. Understand concepts like Polyhedron, Vertex, and examples in the context of submodularity. Dive into how constraints, objectives, and feasible regions play a crucial role in maximizing linear functions. Get insights into specific examples and proofs related to polyhedral feasible regions.

adis407 Follow

Uploaded on Feb 20, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

Submodularity Reading Group Matroid Polytopes, Polymatroid M. Pawan Kumar http://www.robots.ox.ac.uk/~oval/

Outline Linear Programming Matroid Polytopes Polymatroid

Polyhedron Ax b A : m x n matrix b: m x 1 vector

Bounded Polyhedron = Polytope Ax b A : m x n matrix b: m x 1 vector

Vertex z is a vertex of P = {x, Ax b} z is not a convex combination of two points in P There does not exist x, y P and 0 < < 1 x z and y z such that z = x + (1- ) y

Vertex z is a vertex of P = {x, Ax b} Recall A is an m x n matrix Azis a submatrix of A Contains all rows of A such that aiTz = bi

Vertex z is a vertex of P Proof? Rank of Az = n See hidden slides

Linear Program Maximize a linear function Objective function maxxcTx s.t. A x b Constraints Over a polyhedral feasible region A: m x n matrix x: n x 1 vector b: m x 1 vector c: n x 1 vector

Example maxx x1 + x2 x1 0 x2 0 s.t. 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 What is c? A? b?

Example x1 0 x2 0

Example x1 0 x2 0 4x1 x2 = 8

Example x1 0 x2 0 4x1 x2 8

Example x1 0 x2 0 4x1 x2 8 2x1 + x2 10

Example x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2

Example x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 x1 + x2 = 0 maxx x1 + x2

Example Optimal solution x1 + x2 = 8 x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 maxx x1 + x2

Outline Linear Programming Duality LP Solutions Matroid Polytopes Polymatroid

Example maxx 3x1 + x2 + 2x3 7 x 2 x -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. 3 x 2x1 + 2x2 + 5x3 24 4x1 + x2 + 2x3 36 Scale the constraints, add them up Upper bound on solution 3x1 + x2 + 2x3 90

Example maxx 3x1 + x2 + 2x3 1 x -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. 2x1 + 2x2 + 5x3 24 1 x 4x1 + x2 + 2x3 36 Scale the constraints, add them up Upper bound on solution 3x1 + x2 + 2x3 36

Example maxx 3x1 + x2 + 2x3 1 x -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. 2x1 + 2x2 + 5x3 24 1 x 4x1 + x2 + 2x3 36 Scale the constraints, add them up Tightest upper bound? 3x1 + x2 + 2x3 36

Example maxx 3x1 + x2 + 2x3 y1 y2 y3 -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. y4 y5 y6 2x1 + 2x2 + 5x3 24 4x1 + x2 + 2x3 36 We should be able to add up the inequalities y1, y2, y3, y4, y5, y6 0

Example maxx 3x1 + x2 + 2x3 y1 y2 y3 -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. y4 y5 y6 2x1 + 2x2 + 5x3 24 4x1 + x2 + 2x3 36 Coefficient of x1 should be 3 -y1 + y4 + 2y5 + 4y6 = 3

Example maxx 3x1 + x2 + 2x3 y1 y2 y3 -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. y4 y5 y6 2x1 + 2x2 + 5x3 24 4x1 + x2 + 2x3 36 Coefficient of x2 should be 1 -y2 + y4 + 2y5 + y6 = 1

Example maxx 3x1 + x2 + 2x3 y1 y2 y3 -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. y4 y5 y6 2x1 + 2x2 + 5x3 24 4x1 + x2 + 2x3 36 Coefficient of x3 should be 2 -y3 + 3y4 + 5y5 + 2y6 = 2

Example maxx 3x1 + x2 + 2x3 y1 y2 y3 -x1 0, -x2 0, -x3 0 x1 + x2 + 3x3 30 s.t. y4 y5 y6 2x1 + 2x2 + 5x3 24 4x1 + x2 + 2x3 36 Upper bound should be tightest miny 30y4 + 24y5 + 36y6

Dual miny 30y4 + 24y5 + 36y6 s.t. y1, y2, y3, y4, y5, y6 0 -y1 + y4 + 2y5 + 4y6 = 3 -y2 + y4 + 2y5 + y6 = 1 -y3 + 3y4 + 5y5 + 2y6 = 2 Original problem is called primal Dual of dual is primal

Dual maxxcTx s.t. A x b

Dual maxxcTx - yT(A x b) miny 0 KKT Condition? ATy = c miny 0 bTy s.t. ATy = c

maxxcTx Primal s.t. A x b miny 0 bTy Dual s.t. ATy = c

Strong Duality maxxcTx p = Primal s.t. A x b If p or d , then p = d. Think back to the intuition of dual miny 0 bTy d = Dual s.t. ATy = c Skipping the proof

Question maxxcTx s.t. A1x b1 A2x b2 A3x = b3 Dual?

Outline Linear Programming Duality LP Solutions Matroid Polytopes Polymatroid

Graphical Solution x1 + x2 = 8 x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 maxx x1 + x2 Optimal solution at a vertex

Graphical Solution x1 = 3 x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 maxx x1 Optimal solution at a vertex

Graphical Solution x2 = 6 x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 maxx x2 Optimal solution at a vertex

Graphical Solution x1 0 x2 0 4x1 x2 8 2x1 + x2 10 5x1 - 2x2 -2 An optimal solution always at a vertex maxxcTx Proof?

Solving the LP Dantzig (1951): Simplex Method Search over vertices of the polyhedra Worst-case complexity is exponential Smoothed complexity is polynomial Khachiyan (1979, 1980): Ellipsoid Method Polynomial time complexity LP is a P optimization problem Karmarkar (1984): Interior-point Method Polynomial time complexity Competitive with Simplex Method

Solving the LP Plenty of standard software available Mosek (http://www.mosek.com) C++ API Matlab API Python API Free academic license

Outline Linear Programming Matroid Polytopes Polymatroid

Incidence Vector of Set Matroid M = (S, I) Set X S Incidence vector vX {0,1}|S| 1, if s X vX(s) = 0, if s X

Example (Uniform Matroid) s 1 2 3 4 5 6 7 8 9 w(s) 10 5 2 1 3 6 12 2 1 S = {1,2, ,9} 1 0 1 0 1 0 0 0 0 k = 4 X = {1, 3, 5} vX?

Example (Graphic Matroid) S = E v0 e1 e2 v1 v4 e4 e5 e3 e6 X S v2 v5 e7 e9 v3 v6 e8

Example (Graphic Matroid) S = E v0 e1 e2 1 0 0 1 0 0 0 1 1 v1 v4 e4 e5 e3 e6 X S v2 v5 e7 e9 vX? v3 v6 e8

Incidence Vectors of Independent Sets Matroid M = (S, I) vX {0,1}|S|, X I Convex Hull Ax b A? b?

Outline Linear Programming Matroid Polytopes Independent Set Polytope Base Polytope Polymatroid

Independent Set Polytope Matroid M = (S, I) vX {0,1}|S|, X I Convex Hull Ax b x Real|S|

Independent Set Polytope Matroid M = (S, I) vX {0,1}|S|, X I x Real|S| Necessary conditions Sufficient for integral x Proof? xs 0, for all s S Why? s U xs rM(U), for all U S Why?

Independent Set Polytope Matroid M = (S, I) vX {0,1}|S|, X I x Real|S| Necessary conditions Sufficient for all x Lectures slides for proof xs 0, for all s S Why? s U xs rM(U), for all U S Why?