При изучении теоретических курсов по машинному обучению (мат. экономике, оптимизации, финансам и т.д.) часто встречается понятие «двойственной задачи».
Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.
В этой статье я расскажу про коническую двойственность. Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием…
Дальше матан…
Пусть дана некоторая задача оптимизации:
Двойственная задача строится по следующей схеме:
Главная сложность в этой схеме зашита в шаге поиска
.
Если задача не является выпуклой, то это гроб — в общем случае она не решается за полиномиальное время (если
) и такие задачи в этой статье мы затрагивать в дальнейшем не будем.
Допустим, что задача выпуклая, что тогда?
Если задача гладкая, то можно воспользоваться условием оптимальности первого порядка
. Из этого условия, если все Ок, получается вывести или
и
или напрямую функцию
.
Если задача негладкая, то можно было бы воспользоваться аналогом условия первого порядка
(здесь
обозначает субдифференциал функции
), однако эта процедура, как правило, намного сложнее.
Иногда существует эквивалентная «гладкая» задача оптимизации и можно построить двойственную для нее. Но за улучшение структуры (из негладкой в гладкую) как правило всегда приходится платить увеличением размерности.
Есть достаточно много задач оптимизации (примеры ниже), допускающих следующее представление:
где
— матрица,
— вектор,
— невырожденный выпуклый конус.
В таком случае двойственная задача может быть построена по следующей схеме:
Двойственная задача строится по следующей схеме:
где сопряженный конус
для конуса
определяется как
.
Как мы видим, вся сложность построения двойственной задачи была перенесена на построение двойственного конуса. Но в том и радость, что есть хороший calculus для построения двойственных конусов и очень часто двойственный конус можно выписать сразу.
Допустим, нам нужно построить двойственную задачу оптимизации для задачи:
Здесь
, ![$\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2}$](https://habrastorage.org/getpro/habr/formulas/50b/ced/4ee/50bced4eea2a9d10ae203baad764bbff.svg)
Первое, что можно заметить: целевую функцию всегда можно сделать линейной!
Вернее, всегда есть эквивалентная задача с линейной целевой функцией:
Вот сейчас нужно использовать немного тайного знания: множества
Таким образом мы приходим к эквивалентной записи задачи:
Теперь мы можем сразу выписать двойственную задачу:
или, если немного упростить,
где
.
Ссылки для дальнейшего изучения:
Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.
В этой статье я расскажу про коническую двойственность. Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием…
Дальше матан…
Как обычно строят двойственные задачи?
Пусть дана некоторая задача оптимизации:
Двойственная задача строится по следующей схеме:
- Построить Лагранжиан
- Построить двойственную функцию
- Получить двойственную задачу
Главная сложность в этой схеме зашита в шаге поиска
Если задача не является выпуклой, то это гроб — в общем случае она не решается за полиномиальное время (если
Допустим, что задача выпуклая, что тогда?
Если задача гладкая, то можно воспользоваться условием оптимальности первого порядка
Если задача негладкая, то можно было бы воспользоваться аналогом условия первого порядка
Иногда существует эквивалентная «гладкая» задача оптимизации и можно построить двойственную для нее. Но за улучшение структуры (из негладкой в гладкую) как правило всегда приходится платить увеличением размерности.
Коническая двойственность
Есть достаточно много задач оптимизации (примеры ниже), допускающих следующее представление:
где
В таком случае двойственная задача может быть построена по следующей схеме:
Двойственная задача строится по следующей схеме:
- Построить Лагранжиан
- Построить двойственную функцию
- Получить двойственную задачу
где сопряженный конус
Как мы видим, вся сложность построения двойственной задачи была перенесена на построение двойственного конуса. Но в том и радость, что есть хороший calculus для построения двойственных конусов и очень часто двойственный конус можно выписать сразу.
Пример
Допустим, нам нужно построить двойственную задачу оптимизации для задачи:
Здесь
Первое, что можно заметить: целевую функцию всегда можно сделать линейной!
Вернее, всегда есть эквивалентная задача с линейной целевой функцией:
Вот сейчас нужно использовать немного тайного знания: множества
Таким образом мы приходим к эквивалентной записи задачи:
Теперь мы можем сразу выписать двойственную задачу:
или, если немного упростить,
где
Ссылки для дальнейшего изучения: