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

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

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

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

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

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

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

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

$$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 Интересное!

[Перевод] Вы знаете кило, мега и гига. Как насчёт ронна и куэкка?

Как раз переопределив килограмм и иные базовые меры, хранители метрической системы выбрали новую цель: новые префиксы для безумно больших и малых чисел. К ним присоединятся их микроскопические коллеги, ронто – 10-27, и куэкто – 10-30. Предложение, поданное в Международное Бюро ...

Лунный орбитальный зонд NASA сделал новые снимки Китайской станции «Чанъэ-4» — ближе и яснее

15 февраля 2019 года NASA показало новые фотографии с орбиты Луны, сделанные зондом LRO спускаемого аппарата «Чанъэ-4» и ровера «Юйту-2». Первая попытка сфотографировать модули «Чанъэ-4» на обратной стороне Луны с расстояния 330 км описана тут. Первое фото зонда LRO от ...