Convex Analysis and Optimization with Submodular Functions: a Tutorial

Understand

Set-functions appear in many areas of computer science and applied mathematics, such as machine learning, computer vision, operations research or electrical networks.

• Among these set-functions, submodular functions play an important role, similar to convex functions on vector spaces.
• In this tutorial, the theory of submodular functions is presented, in a self-contained way, with all results shown from first principles.
• A good knowledge of convex analysis is assumed.