YuraDorn Dec 1 2018 at 21:51

Немного про коническую двойственность

2 min

5.5K

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

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

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

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

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

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

$\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$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

$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}$

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

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

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

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

Пример

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

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

Здесь $\|x\|_1 = \sum_{i=1}^n |x_i|$ , $\|x\|_2 = \sqrt{\sum_{i=1}^n x_i^2}$

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

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

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

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

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

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

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

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

$\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$

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

$\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_+$

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

$\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_+$

где $\|\mu\|_{\infty} = \max_{i}|\mu_i|$ .

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

Hubs: