Discrete Optimization in Machine Learning

Submodularity and Discrete Convexity

author: Satoru Fujishige, Research Institute for Mathematical Sciences, Kyoto University
published: Jan. 16, 2013, recorded: December 2012, views: 209

Slides

Slides
0:00	Submodularity and Discrete Convexity
0:11	A submodular function
1:01	A submodular function: Lemma
1:46	A submodular function: Theorem
2:27	Distributive Lattices and Posets: Theorem
6:13	A simple distributive lattice
6:41	Submodular System (D, f) on E - 1
7:11	Submodular System (D, f) on E - 2
8:41	Remark
9:03	Define a supermodular system
9:20	Duality
10:34	(D, f): A submodular system on E - 1
10:58	(D, f): A submodular system on E - 2
11:27	(D, f): A submodular system on E - 3
11:45	(D, f): A submodular system on E - 4
12:03	Polymatroid (Edmonds)
12:47	Matroid (Whitney)
13:22	Generalized polymatroids (Frank, Hassin) and Base Polyhedra
14:19	Theorem (Tomizawa)
14:53	Corollary
16:44	The Intersection Theorem and Its Equivalents - 1
17:43	The Intersection Theorem and Its Equivalents - 2
19:13	The Intersection Theorem and Its Equivalents - 3
20:04	The Intersection Theorem and Its Equivalents - 4
20:46	The Intersection Theorem and Its Equivalents - 5
21:46	The Intersection Theorem and Its Equivalents - 6
22:58	The Intersection Theorem and Its Equivalents - 7
24:08	Minimum-Norm Base and SFM - 1
24:33	Minimum-Norm Base and SFM - 2
26:18	Minimum-Norm Base and SFM - 3
26:39	Minimum-Norm Base and SFM - 4
27:35	Minimum-Norm Base and SFM - 5
28:08	Minimum-Norm Base and SFM - 6
28:19	Minimum-Norm Base and SFM - 7
28:45	Minimum-Norm Base and SFM - 8
29:05	Minimum-Norm Base and SFM - 9
30:01	Minimum-Norm Base and SFM - 10
31:40	Maximum Weight Base Problem - 1
32:16	Maximum Weight Base Problem - 2
33:46	Maximum Weight Base Problem - 3
34:28	Maximum Weight Base Problem - 2
34:59	Maximum Weight Base Problem - 3
35:16	Maximum Weight Base Problem - 4
36:15	Maximum Weight Base Problem - 5
36:32	Maximum Weight Base Problem - 6
36:51	Subgradients and Subdifferentials of Submodular Functions - 1
39:50	Subgradients and Subdifferentials of Submodular Functions - 2
40:27	Subgradients and Subdifferentials of Submodular Functions - 3
40:55	A simplicial division of the plane (triangulation) - 1
41:14	A simplicial division of the plane (triangulation) - 2
42:02	Discrete convex functions - 1
42:36	Discrete convex functions - 2
45:17	Discrete convex functions - 3
47:10	Discrete convex functions - 4
48:22	Discrete convex functions - 5
48:40	Discrete convex functions - 6
50:36	Discrete convex functions - 7
50:45	Discrete convex functions - 8
51:14	M♮-concave function g
51:35	Simultaneous Exchange Axiom for M♮-convex functions
52:06	Discrete Separation Theorem (L♮) - 1
52:32	Discrete Separation Theorem (L♮) - 2
52:53	Discrete Separation Theorem (L♮) - 3
53:21	Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 1
53:52	Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 2
54:14	Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 3
54:38	Intersections of subdifferentials and superdifferentials (integral generalized polymatroids) - 4
55:07	Discrete Fenchel Duality Theorem (Murota) - 1
55:51	Discrete Fenchel Duality Theorem (Murota) - 2
57:12	For more information see the following monographs

Report a problem or upload files

If you have found a problem with this lecture or would like to send us extra material, articles, exercises, etc., please use our ticket system to describe your request and upload the data.
Enter your e-mail into the 'Cc' field, and we will keep you updated with your request's status.

Lecture popularity: You need to login to cast your vote.

Description

The present talk is a tutorial one and gives some essence of submodular functions and discrete convexity.

The contents of my talk will be the following:

Submodular and Supermodular Functions
1. Submodularity
2. Distributive Lattices and Posets (Birkhoff-Iri)
Submodular Systems and Supermodular Systems
1. Submodular polyhedron and Base Polyhedron
2. Duality
3. Polymatroids and Matroids
4. Generalized Polymatroids
5. Characterization by Edge-vectors
6. Crossing- and Intersecting-submodular Functions
Intersection Theorem and Its Equivalents
1. Intersection Theorem
2. Discrete Separation Theorem
3. Fenchel Duality Theorem
4. Minkowski Sum Theorem
Minimum-Norm Base and Submodular Function Minimization
1. Lexicographically Optimal Base
2. Minimum-Norm Base
3. Submodular Function Minimization
Maximum Weight Base Problem
1. Greedy Algorithm
2. Lovasz extension
3. Subgradients and Subdifferentials of Submodular Functions
Discrete Convex Analysis
1. L♮-convex Functions
2. M♮-convex Functions
3. Discrete Separation Theorem
4. Fenchel Duality Theorem