При изучении теоретических курсов по машинному обучению (мат. экономике, оптимизации, финансам и т.д.) часто встречается понятие «двойственной задачи».
Двойственные задачи часто используются для получения нижних (или верхних) оценок на целевой функционал в задачах оптимизации. Кроме этого, почти для любой осмысленной постановки задачи оптимизации двойственная задача имеет содержательную интерпретацию. То есть если Вы столкнулись с важной задачей оптимизации, то и ее двойственная тоже, скорее всего, важна.
В этой статье я расскажу про коническую двойственность. Этот способ построения двойственных задач, на мой взгляд, незаслуженно обделен вниманием…
Дальше матан…
Как обычно строят двойственные задачи?
Пусть дана некоторая задача оптимизации:
$$display$$min_{xin R^n} f(x)\ f_i(x) leq 0, quad 1 leq i leq k\ h_i(x) = 0, 1leq i leq m$$display$$
Двойственная задача строится по следующей схеме:
- Построить Лагранжиан
$$display$$L(x, lambda, mu) = f(x)+sum_{i=1}^klambda_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$Pneq 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_{xin 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^Tlambda = 0\ -infty, quad c+A^Tlambda neq 0 end{cases} $$display$$
- Получить двойственную задачу
$$display$$max_{lambda} b^Tlambda\ c+A^Tlambda=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^ntimes R| quad |x|_1 leq t}$$display$$
и
$$display$$K_2 = { (x,t) in R^ntimes R| quad |x|_2 leq t}$$display$$
являются выпуклыми конусами.
Таким образом мы приходим к эквивалентной записи задачи:
$$display$$min_{xin R^n, yin R, zin R} y+z\ I_{n+1}begin{pmatrix} x\ yend{pmatrix}+0_{n+1}in K_2\ I_{n+1}begin{pmatrix} x\ zend{pmatrix}+0_{n+1}in K_1\ Ax-b in R_+^k $$display$$
Теперь мы можем сразу выписать двойственную задачу:
$$display$$max_{lambda, mu, nu}-b^Tnu\ lambda_i+mu_i+[A^Tnu]_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^Tnu\ lambda+mu+A^Tnu = 0\ |lambda|_2 leq 1\ |mu|_{infty}leq 1\ -nu in R^k_+$$display$$
Ссылки для дальнейшего изучения:
- S.Boyd & L. Vanderberghe, «Convex Optimization», 2.6 (p.51)
- A. Ben-Tall & L. El Ghaoui& A. Nemirovski, «Robust Optimization», App. A
Автор: YuraDorn
