Введение
1 Задача минимизации дискретных энергий 11
1.1 Нотация и постановка задачи 11
1.2 Энергии и марковские случайные поля 13
1.3 Методы минимизации энергии 14
1.3.1 Частные случаи, допускающие точные решения 15
1.3.2 Приближённые алгоритмы 24
2 Субмодулярная релаксация 38
2.1 Парно-сепарабельные ассоциативные энергии 38
2.2 Энергии с потенциалами высоких порядков 40
2.3 Несубмодулярный лагранжиан 43
2.4 Линейные глобальные ограничения 45
3 Точность нижних оценок 47
3.1 Вспомогательные леммы 47
3.2 Парно-сепарабельные ассоциативные энергии 51
3.3 Энергии с потенциалами высоких порядков 54
3.3.1 Перестановочные потенциалы Поттса 55
3.4 Произвольные парно-сепарабельные энергии 57
3.5 Линейные глобальные ограничения 58
4 Максимизация нижних оценок 59
4.1 Теоретические свойства точек максимума 59
4.1.1 Условия сильной и слабой согласованности 59
4.1.2 Зазор между прямой и двойственной задачами 61
4.2 Методы оптимизации для решения двойственной задачи 63
4.3 Максимизация двойственной функции на основе мин-маргиналов 67
4.4 Построение решения прямой задачи 73
4.4.1 Построение целостного дробного решения 74
4.4.2 Частичная оптимальность 77
4.4.3 Построение прямого решения при нулевом зазоре 78
4.4.4 Построение прямого решения в общем случае 81
5 Экспериментальное сравнение 83
5.1 Парно-сепарабельные ассоциативные энергии 83
5.2 Энергии с потенциалами высоких порядков 88
5.3 Произвольные парно-сепарабельные энергии 91
5.4 Глобальные ограничения 94
5.4.1 Сравнение с аналогами 94
5.4.2 Применимость метода на реальных данных 96
Заключение 101
Список рисунков 106
Список таблиц 107
Литература 108
A Потоки и разрезы в сетях 120
