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

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

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

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

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


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

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


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

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

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

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

$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^* $


где сопряженный конус $K^*$ для конуса $K$ определяется как $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|$.

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

Комментарии (6)


  1. kovserg
    02.12.2018 10:46
    #19442256
    +1

    Немогли бы вы уточнить что означают в ||x||1 и ||x||2 индексы 1 и 2, и далее ||?||inf


    1. YuraDorn Автор
      02.12.2018 11:10
      #19442310

      Это индексы нормы. Эта запись используется для сокращения размеров формул.
      Первая норма вектора = сумма модулей компонент вектора
      Вторая норма вектора = обычная евклидова норма = корень из суммы квадратов компонент вектора
      Бесконечная норма вектора = максимум из модулей компонент вектора
      Чуть более подробно можно посмотреть вот тут в разделе «примеры»


  1. S_A
    02.12.2018 11:22
    #19442348

    Пример бы посодержательней… и собственно про содержательную интерпретацию двойственной задачи.


    1. YuraDorn Автор
      02.12.2018 12:49
      #19442572

      Изначально я начал писать пост про робастную оптимизацию, но там получилась большая простыня текста.
      Поэтому я решил вынести технику построения двойственной задачи через конусы в отдельный небольшой пост, на который можно будет сослаться.
      После публикации поста про робастную оптимизацию добавлю соответствующую ссылку в этот текст. Там будут более содержательные примеры.

      С другой стороны содержательная интерпретация двойственной задачи естественным образом зависит от содержательной интерпретации прямой задачи (для которой мы строили двойственную). То есть интерпретация двойственной задачи зависит от контекста.

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

      В детали тут входить тяжело (объемная тема). Самое лучшее изложение, пожалуй, можно найти в первой главе вот этой замечательной книги.


    1. malkovsky
      03.12.2018 13:43
      #19446604
      +1

      Я бы скорее рекомендовал книгу Бойда&Ванденберге (ссылка на нее есть в этой статье), вот например на страницах 230 и 239 есть интерпретация на примере матричных игр: играют двое друг против друга, прямая задача — это задача первого игрока побольше заработать, двойственная — это задача второго игрока поменьше проиграть.

      Или вот есть совсем классический, но частный случай: максимальный поток — минимальный разрез. С одной стороны «какой максимальный объем воды можно пропустить по трубам из S в T», с другой «Какой минимальный набор труб (по суммарной пропускной способности) нужно убрать, чтобы разделить S и T»


      1. YuraDorn Автор
        03.12.2018 15:34
        #19447134

        Именно в качестве источника примеров книга Бойд и Вандерберге действительно очень хороша. Но опять же это примеры и смысл двойственной задачи будет определен контекстом.
        Про какие-то более универсальные вещи лучше смотреть книгу Бен Таля, Гуоуи и Немировского.

        В целом самое общее, что приходит в голову:
        Обычно задача оптимизации выгляди так: мы пытаемся максимизировать некоторый функционал при наличии ограничений. Ограничены обычно ресурсы. То есть какой уровень некоторого функционала качества мы можем достичь, если у нас есть некоторое заданное количество ресурсов. Двойственная задача ставит вопрос по другому: сколько минимально нам нужно ресурсов, чтобы уровень функционала качества из прямой задачи был не меньше, чем некоторая заданная величина.