By Wu Zhenan (bonhomme@nus.edu.sg).

This folder contains 3 explanatory notes. File Min_Norm_Point Algorithm explains basic matters including introduction to submodular function and lovasz extension. File Associating Minimal Norm with Lovasz Extension proves that finding the point of minimal norm inside base polyhedron provides a solution to the minimization of a submodular function. File Explaining Min-Norm-Point Algorithm explains the validity of minimum-norm point algorithm. Definitions and letter symbols are passed bettween documents.

There seems to be slight differences between mechanisms of minimum-norm point algorithm stated in Explaining Min-Norm-Point Algorithm and in matlab code https://www.mathworks.com/matlabcentral/fileexchange/20504-submodular-function-optimization?s_tid=srchtitle_submodular%20function%20optimization_1 (stated in the document), but it can be shown that both mechanisms work.

References to these documents are:

"Stefanie Jegelka: An introduction to Submodularity, Part 1", in https://www.youtube.com/watch?v=Y3u_hvxayDY

"Lexicographically Optimal Base of a Polymatroid with Respect to a Weight Vector” by Satoru Fujishige, published as Vol. 5, No. 2 of the May, 1980 release of “Mathematics of Operations Research”

“The Minimum-Norm-Point Algorithm Submodular Function Minimization and Linear Programming” by Satoru Fujishige, Takumi Hayashi and Shigueo Isotani, published in September 2006

Submodular Function Minimization codes, by Andrea Krause, in https://www.mathworks.com/matlabcentral/fileexchange/20504-submodular-function-optimization?s_tid=srchtitle_submodular%20function%20optimization_1