При изучении теоретических курсов по машинному обучению (мат. экономике, оптимизации, финансам и т.д.) часто встречается понятие «двойственной задачи».
Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.
В этой статье я расскажу про коническую двойственность. Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием…
Дальше матан…
Пусть дана некоторая задача оптимизации:
Двойственная задача строится по следующей схеме:
Главная сложность в этой схеме зашита в шаге поиска .
Если задача не является выпуклой, то это гроб — в общем случае она не решается за полиномиальное время (если ) и такие задачи в этой статье мы затрагивать в дальнейшем не будем.
Допустим, что задача выпуклая, что тогда?
Если задача гладкая, то можно воспользоваться условием оптимальности первого порядка . Из этого условия, если все Ок, получается вывести или и или напрямую функцию .
Если задача негладкая, то можно было бы воспользоваться аналогом условия первого порядка (здесь обозначает субдифференциал функции ), однако эта процедура, как правило, намного сложнее.
Иногда существует эквивалентная «гладкая» задача оптимизации и можно построить двойственную для нее. Но за улучшение структуры (из негладкой в гладкую) как правило всегда приходится платить увеличением размерности.
Есть достаточно много задач оптимизации (примеры ниже), допускающих следующее представление:
где — матрица, — вектор, — невырожденный выпуклый конус.
В таком случае двойственная задача может быть построена по следующей схеме:
Двойственная задача строится по следующей схеме:
где сопряженный конус для конуса определяется как .
Как мы видим, вся сложность построения двойственной задачи была перенесена на построение двойственного конуса. Но в том и радость, что есть хороший calculus для построения двойственных конусов и очень часто двойственный конус можно выписать сразу.
Допустим, нам нужно построить двойственную задачу оптимизации для задачи:
Здесь ,
Первое, что можно заметить: целевую функцию всегда можно сделать линейной!
Вернее, всегда есть эквивалентная задача с линейной целевой функцией:
Вот сейчас нужно использовать немного тайного знания: множества и являются выпуклыми конусами.
Таким образом мы приходим к эквивалентной записи задачи:
Теперь мы можем сразу выписать двойственную задачу:
или, если немного упростить,
где .
Ссылки для дальнейшего изучения:
Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.
В этой статье я расскажу про коническую двойственность. Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием…
Дальше матан…
Как обычно строят двойственные задачи?
Пусть дана некоторая задача оптимизации:
Двойственная задача строится по следующей схеме:
- Построить Лагранжиан
- Построить двойственную функцию
- Получить двойственную задачу
Главная сложность в этой схеме зашита в шаге поиска .
Если задача не является выпуклой, то это гроб — в общем случае она не решается за полиномиальное время (если ) и такие задачи в этой статье мы затрагивать в дальнейшем не будем.
Допустим, что задача выпуклая, что тогда?
Если задача гладкая, то можно воспользоваться условием оптимальности первого порядка . Из этого условия, если все Ок, получается вывести или и или напрямую функцию .
Если задача негладкая, то можно было бы воспользоваться аналогом условия первого порядка (здесь обозначает субдифференциал функции ), однако эта процедура, как правило, намного сложнее.
Иногда существует эквивалентная «гладкая» задача оптимизации и можно построить двойственную для нее. Но за улучшение структуры (из негладкой в гладкую) как правило всегда приходится платить увеличением размерности.
Коническая двойственность
Есть достаточно много задач оптимизации (примеры ниже), допускающих следующее представление:
где — матрица, — вектор, — невырожденный выпуклый конус.
В таком случае двойственная задача может быть построена по следующей схеме:
Двойственная задача строится по следующей схеме:
- Построить Лагранжиан
- Построить двойственную функцию
- Получить двойственную задачу
где сопряженный конус для конуса определяется как .
Как мы видим, вся сложность построения двойственной задачи была перенесена на построение двойственного конуса. Но в том и радость, что есть хороший calculus для построения двойственных конусов и очень часто двойственный конус можно выписать сразу.
Пример
Допустим, нам нужно построить двойственную задачу оптимизации для задачи:
Здесь ,
Первое, что можно заметить: целевую функцию всегда можно сделать линейной!
Вернее, всегда есть эквивалентная задача с линейной целевой функцией:
Вот сейчас нужно использовать немного тайного знания: множества и являются выпуклыми конусами.
Таким образом мы приходим к эквивалентной записи задачи:
Теперь мы можем сразу выписать двойственную задачу:
или, если немного упростить,
где .
Ссылки для дальнейшего изучения: