[Из песочницы] Немного про коническую двойственность
При изучении теоретических курсов по машинному обучению (мат. экономике, оптимизации, финансам и т.д.) часто встречается понятие «двойственной задачи».
Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.
В этой статье я расскажу про коническую двойственность. Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием…
Дальше матан…
Как обычно строят двойственные задачи?
Пусть дана некоторая задача оптимизации:
$$display$$\min_{x\in R^n} 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$\nabla_x L (x, \lambda, \mu)=0$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$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$$
Ссылки для дальнейшего изучения:
