Главная » Хабрахабр » [Из песочницы] Немного про коническую двойственность

[Из песочницы] Немного про коническую двойственность

При изучении теоретических курсов по машинному обучению (мат. экономике, оптимизации, финансам и т.д.) часто встречается понятие «двойственной задачи».

Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.

Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием… В этой статье я расскажу про коническую двойственность.

Дальше матан…

Как обычно строят двойственные задачи?

Пусть дана некоторая задача оптимизации:

$$display$$\min_ f(x)\\ f_i(x) \leq 0, \quad 1 \leq i \leq k\\ h_i(x) = 0, 1\leq i \leq m$$display$$

Двойственная задача строится по следующей схеме:

  • Построить Лагранжиан

$$display$$L(x, \lambda, \mu) = f(x)+\sum_{i=1}^k\lambda_i f_i(x)+\sum_{i=1}^m \mu_i h_i(x)$$display$$

  • Построить двойственную функцию

$$display$$g(\lambda, \mu) = \inf_x L(x, \lambda, \mu) $$display$$

  • Получить двойственную задачу

$$display$$\max_{\lambda, \mu}g(\lambda, \mu)\\ \lambda \geq 0 $$display$$

Главная сложность в этой схеме зашита в шаге поиска $inline$\inf_x L(x, \lambda, \mu)$inline$.

Если задача не является выпуклой, то это гроб — в общем случае она не решается за полиномиальное время (если $inline$P\neq NP$inline$) и такие задачи в этой статье мы затрагивать в дальнейшем не будем.

Допустим, что задача выпуклая, что тогда?

Из этого условия, если все Ок, получается вывести или $inline$x(\lambda, \mu) = \arg \min_x L(x, \lambda, \mu)$inline$ и $inline$g(\lambda, \mu) = L(x(\lambda, \mu), \lambda, \mu)$inline$ или напрямую функцию $inline$g(\lambda, \mu)$inline$. Если задача гладкая, то можно воспользоваться условием оптимальности первого порядка $inline$\nabla_x L(x, \lambda, \mu)=0$inline$.

Если задача негладкая, то можно было бы воспользоваться аналогом условия первого порядка $inline$0 \in \partial_x L(x, \lambda, \mu)$inline$ (здесь $inline$\partial_x L(x, \lambda, \mu)$inline$ обозначает субдифференциал функции $inline$L(x, \lambda, \mu)$inline$), однако эта процедура, как правило, намного сложнее.

Но за улучшение структуры (из негладкой в гладкую) как правило всегда приходится платить увеличением размерности. Иногда существует эквивалентная «гладкая» задача оптимизации и можно построить двойственную для нее.

Коническая двойственность

Есть достаточно много задач оптимизации (примеры ниже), допускающих следующее представление:

$$display$$\min_{x\in R^n} c^Tx\\ Ax+b \in K$$display$$

где $inline$A$inline$ — матрица, $inline$b$inline$ — вектор, $inline$K$inline$ — невырожденный выпуклый конус.

В таком случае двойственная задача может быть построена по следующей схеме:

Двойственная задача строится по следующей схеме:

  • Построить Лагранжиан

$$display$$L(x, \lambda) = c^Tx+ \lambda^T (Ax+b)$$display$$

  • Построить двойственную функцию

$$display$$g(\lambda) = \inf_x L(x, \lambda) = \begin{cases} \lambda^T b, \quad c+A^T\lambda = 0\\ -\infty, \quad c+A^T\lambda \neq 0 \end{cases} $$display$$

  • Получить двойственную задачу

$$display$$\max_{\lambda} b^T\lambda\\ c+A^T\lambda=0\\ - \lambda \in K^* $$display$$

где сопряженный конус $inline$K^*$inline$ для конуса $inline$K$inline$ определяется как $inline$K^* = \left \{y \in R^k| z^T y \geq 0, \quad \forall z \in K \right \}$inline$.

Но в том и радость, что есть хороший calculus для построения двойственных конусов и очень часто двойственный конус можно выписать сразу. Как мы видим, вся сложность построения двойственной задачи была перенесена на построение двойственного конуса.

Пример

Допустим, нам нужно построить двойственную задачу оптимизации для задачи:

$$display$$\min_{x \in R^n}\|x\|_2+\|x\|_1\\ Ax \geq b$$display$$

Первое, что можно заметить: целевую функцию всегда можно сделать линейной!

Вернее, всегда есть эквивалентная задача с линейной целевой функцией:

$$display$$\min_{x \in R^n, y \in R, z \in R}y+z\\ \|x\|_2 \leq y\\ \|x\|_1 \leq z\\ Ax \geq b$$display$$

Вот сейчас нужно использовать немного тайного знания: множества

$$display$$K_1 = \{ (x,t) \in R^n\times R| \quad \|x\|_1 \leq t\}$$display$$

и

$$display$$K_2 = \{ (x,t) \in R^n\times R| \quad \|x\|_2 \leq t\}$$display$$

являются выпуклыми конусами.

Таким образом мы приходим к эквивалентной записи задачи:

$$display$$\min_{x\in R^n, y\in R, z\in R} y+z\\ I_{n+1}\begin{pmatrix} x\\ y\end{pmatrix}+0_{n+1}\in K_2\\ I_{n+1}\begin{pmatrix} x\\ z\end{pmatrix}+0_{n+1}\in K_1\\ Ax-b \in R_+^k $$display$$

Теперь мы можем сразу выписать двойственную задачу:

$$display$$\max_{\lambda, \mu, \nu}-b^T\nu\\ \lambda_i+\mu_i+[A^T\nu]_i=0, \quad 1 \leq i \leq n\\ \lambda_{n+1}+1=0\\ \mu_{n+1}+1 = 0\\ -\lambda \in K_2^*(=K_2)\\ -\mu \in K_1^*(=K_{\infty})\\ -\nu \in R^k_+$$display$$

или, если немного упростить,

$$display$$\max_{\lambda, \mu, \nu} -b^T\nu\\ \lambda+\mu+A^T\nu = 0\\ \|\lambda\|_2 \leq 1\\ \|\mu\|_{\infty}\leq 1\\ -\nu \in R^k_+$$display$$

Ссылки для дальнейшего изучения:


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

[Перевод] Интервью с Дэвидом Гобелем

Дэвид любезно согласился дать LEAF очень интересное интервью. Дэвид Гобель – изобретатель, филантроп, футурист и ярый сторонник технологий омоложения; вместе с Обри де Греем он известен как один из основателей Methuselah Foundation и как автор концепции Longevity Escape Velocity (LEV), ...

10 долларов на хостинг: 20 лет назад и сегодня

Всё кругом дорожает, а технологии дешевеют. Когда-то компьютер или мобильный телефон могли позволить себе единицы, сейчас эти устройства есть в каждой российской семье. Цена мегабайта за последние 20 лет упала в несколько тысяч раз. Ещё один пример — хостинг. В ...