Compact course on Discrete Energy Minimization, Kyiv, September 23-27, 2019

Summary

The course presents various existing optimization techniques for energy minimization for discrete graphical models. In particular, it addresses such topics as combinatorial algorithms, integer linear programs, scalable convex and non-convex optimization and convex duality theory. Graphical models play a role of working examples along the course. The goal of the course is to give a background for analysis of existing, and development of new scalable combinatorial optimization.

Schedule and Information

Venue: Kyiv, Peremogy ave. 37, Building 11 of the NTUU “KPI” Campus, Room 214

Time:  23-27.09.2019:

  • 08-30 – 10-05
  • 10-25 – 12-00
  • 13:30 – 15-50

Table of Contents

  • Background: Basics of Linear Programs and Their Geometry
  • Inference in Graphical Models as Integer Linear Program
  • Background: Basics of Convex Analysis and Convex Duality
  • Duality of the LP Relaxation of Inference Problem
  • Background: Basics of Convex Optimization
  • Sub-Gradient and Block-Coordinate Ascent for Inference in Graphical Models
  • Lagrangian  Decomposition Technique
  • Min-Cut/Max-Flow Based Inference
  • LP Relaxation of Inference Problem as st-Min-Cut Problem

Literature

Text-book: B. Savchynskyy. Discrete Graphical Models – An Optimization Perspective 

Video of Lectures: Winter Term 2018/19, Heidelberg University

Thanks to Bálint Csanády, for the video recordings.  Use the username “optml” when prompted.