21830 articles – 15616 references  [version française]

hal-00527714, version 2

Convex Analysis and Optimization with Submodular Functions: a Tutorial

Francis Bach () 1, 2

Abstract: 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.

  • 1:  WILLOW (INRIA Paris - Rocquencourt)
  • INRIA – Ecole normale supérieure de Paris - ENS Paris – CNRS : UMR8548
  • 2:  Laboratoire d'informatique de l'école normale supérieure (LIENS)
  • CNRS : UMR8548 – Ecole normale supérieure de Paris - ENS Paris
  • Domain : Computer Science/Learning
    Mathematics/Optimization and Control
    Statistics/Machine Learning
  • Keywords : Submodular functions – convex optimization – combinatorial optimization
  • Available versions :  v1 (2010-10-20) v2 (2010-11-14)
 
  • hal-00527714, version 2
  • http://hal.archives-ouvertes.fr/hal-00527714
  • oai:hal.archives-ouvertes.fr:hal-00527714
  • From: Francis Bach <>
  • Submitted on: Sunday, 14 November 2010 14:43:59
  • Updated on: Sunday, 14 November 2010 18:19:44