🙏🏼 👏🏻 🛀 Um pouco sobre a dualidade cônica 💪🏾 🤷🏾 ✨

Ao estudar cursos teóricos em aprendizado de máquina (matemática. Economia, otimização, finanças, etc.), o conceito de um "problema duplo" é freqüentemente encontrado.

As tarefas duplas são frequentemente usadas para obter estimativas mais baixas (ou superiores) para o destino funcional em problemas de otimização. Além disso, para quase qualquer declaração significativa do problema de otimização, o problema duplo tem uma interpretação significativa. Ou seja, se você se deparar com um importante problema de otimização, o problema duplo também é provavelmente importante.

Neste artigo, falarei sobre a dualidade cônica. Essa maneira de construir tarefas duplas, na minha opinião, é imerecidamente privada de atenção ...

Próximo matan ...

Como as tarefas duplas geralmente são criadas?

Seja dado algum problema de otimização:

m i n_{x i n R^{n}} f (x) f_{i} (x) l e q 0, q u a d 1 l e q i l e q k h_{i} (x) = 0, 1 l e q i l e q m

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

A tarefa dupla é construída de acordo com o seguinte esquema:

Build Lagrangian

L (x, l a m b d a, m u) = f (x) + s u m_{i = 1}^{k} l a m b d a_{i} f_{i} (x) + s u m_{i = 1}^{m} m u_{i} h_{i} (x)

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

Construa uma função dupla

g (l a m b d a, m u) = i n f_{x} L (x, l a m b d a, m u

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

Obter uma tarefa dupla

m a x_{l a m b d a, m u} g (l a m b d a, m u) l a m b d a g e q 0

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

A principal dificuldade desse esquema está ligada na etapa de pesquisa

i n f_{x} L (x, l a m b d a, m u)

$\ inf_x L (x, \ lambda, \ mu)$ .

Se o problema não for convexo, é um caixão - no caso geral, não pode ser resolvido em tempo polinomial (se

P n e q N P

$P \ neq NP$ ) e esses problemas neste artigo não entraremos em contato no futuro.

Suponha que o problema é convexo, e daí?

Se o problema for suave, podemos usar a condição de otimização de primeira ordem

n a b l a_{x} L (x, l a m b d a, m u) = 0

$\ nabla_x L (x, \ lambda, \ mu) = 0$ . A partir dessa condição, se tudo estiver OK, deduzirá ou

x (l a m b d a, m u) = a r g m i n_{x} L (x, l a m b d a, m u)

$x (\ lambda, \ mu) = \ arg \ min_x L (x, \ lambda, \ mu)$ e

g (l a m b d a, m u) = L (x (l a m b d a, m u), l a m b d a, m u

$g (\ lambda, \ mu) = L (x (\ lambda, \ mu), \ lambda, \ mu$ ou diretamente função

g (l a m b d a, m u)

$g (\ lambda, \ mu)$ .

Se o problema não for bom, poderíamos usar um análogo da condição de primeira ordem

0 i n p a r c i a l_{x} L (x, l a m b d a, m u)

$0 \ in \ parcial_x L (x, \ lambda, \ mu)$ (aqui

p a r c i a l_{x} L (x, l a m b d a, m u)

$\ parcial_x L (x, \ lambda, \ mu)$ denota um subdiferencial de uma função

L (x, l a m b d a, m u)

$L (x, \ lambda, \ mu)$ ), no entanto, esse procedimento geralmente é muito mais complicado.

Às vezes, existe um problema de otimização “suave” equivalente e pode-se construir um duplo para ele. Mas, para a melhoria da estrutura (de não suave para suave), como regra, você sempre deve pagar um aumento de dimensão.

Dualidade cônica

Existem algumas tarefas de otimização (exemplos abaixo) que admitem a seguinte representação:

m i n_{x i n R^{n}} c^{T} x A x + b e m K

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

onde

A

$A$ - matriz

b

$b$ - vetor

K

$K$ - cone convexo não degenerado.

Nesse caso, a tarefa dupla pode ser construída de acordo com o seguinte esquema:

A tarefa dupla é construída de acordo com o seguinte esquema:

Build Lagrangian

L (x, l a m b d a) = c^{T} x + l a m b d a^{T} (A x + b)

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

Construa uma função dupla

g (l a m b d a) = i n f_{x} L (x, l a m b d a) = b e g i n c a s e s l a m b d a^{T} b, q u a d c + A^{T} l a m b d a = 0 - i n f t y, q u a d c + A^{T} l a m b d a n e q 0 e n d c a s e s

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

Obter uma tarefa dupla

m a x_{l a m b d a} b^{T} l a m b d a c + A^{T} l a m b d a = 0 - l a m b d a e m K^{*}

$\ max _ {\ lambda} b ^ T \ lambda \\ c + A ^ T \ lambda = 0 \\ - \ lambda \ em K ^ *$

onde está o cone conjugado

K^{*}

$K ^ *$ para cone

K

$K$ definido como

K ^ * = \ left \ {y \ em R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ in K \ right \}

$K ^ * = \ left \ {y \ em R ^ k | z ^ T y \ geq 0, \ quad \ forall z \ in K \ right \}$ .

Como vemos, toda a complexidade da construção do problema duplo foi transferida para a construção do cone duplo. Mas a alegria é que existe um bom cálculo para a construção de cones duplos e, muitas vezes, um cone duplo pode ser escrito imediatamente.

Exemplo

Suponha que precisamos construir um problema de otimização dupla para o problema:

m i n_{x i n R^{n}} | x |_{2} + | x |_{1} A x g e q b

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

Aqui

| x |_{1} = s u m_{i = 1}^{n} | x_{i} |

$\ | x \ | _1 = \ sum_ {i = 1} ^ n | x_i |$ ,

| x |_{2} = s q r t s u m_{i = 1}^{n} x_{i}^{2}

$\ | x \ | _2 = \ sqrt {\ sum_ {i = 1} ^ n x_i ^ 2}$

A primeira coisa que você pode notar: a função objetivo sempre pode ser linear!

Em vez disso, sempre há um problema equivalente com uma função objetivo linear:

m i n_{x e m R^{n}, y e m R, z e m R} y + z | x |_{2} l e q y | x |_{1} l e q z A x g e q b

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

Agora você precisa usar um pouco de conhecimento secreto: muitos

K_1 = \ {(x, t) \ em R ^ n \ vezes R | \ quad \ | x \ | _1 \ leq t \}

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

K_2 = \ {(x, t) \ em R ^ n \ vezes R | \ quad \ | x \ | _2 \ leq t \}

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

são cones convexos.

Assim, chegamos à notação equivalente do problema:

m i n_{x e m R^{n}, y e m R, z e m R} y + z I_{n + 1} b e g i n p m a t r i x x y e n d p m a t r i x + 0_{n + 1} e m K_{2} I_{n + 1} b e g i n p m a t r i x x z e n d p m a t r i x + 0_{n + 1} e m K_{1} A x - b e m R_{+}^{k}

$\ min_ {x \ em R ^ n, y \ em R, z \ em R} y + z \\ I_ {n + 1} \ begin {pmatrix} x \\ y \ end {pmatrix} + 0_ {n +1} \ em K_2 \\ I_ {n + 1} \ begin {pmatrix} x \\ z \ end {pmatrix} + 0_ {n + 1} \ em K_1 \\ Ax-b \ em R _ + ^ k$

Agora podemos escrever imediatamente um problema duplo:

m a x_{l a m b d a, m u, n u} - b^{T} n u l a m b d a_{i} + m u_{i} + [A^{T} n u]_{i} = 0, q u a d 1 l e q i l e q n l a m b d a_{n + 1} + 1 = 0 m u_{n + 1} + 1 = 0 - l a m b d a e m K_{2}^{*} (= K_{2}) - m u e m K_{1}^{*} (= K_{i n f t y}) - n u e m 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 \ em K_2 ^ * (= K_2) \\ - \ mu \ em K_1 ^ * (= K _ {\ infty}) \\ - \ nu \ em R ^ k _ +$

ou, para simplificar um pouco,

m a x_{l a m b d a, m u, n u} - b^{T} n u l a m b d a + m u + A^{T} n u = 0 | l a m b d a |_{2} l e q 1 | m u |_{i n f t y} l e q 1 - n u e m R_{+}^{k}

$\ max _ {\ lambda, \ mu, \ nu} -b ^ T \ nu \\ \ lambda + \ mu + A ^ T \ nu = 0 \\ \ | \ lambda \ | _2 \ leq 1 \\ \ | \ mu \ | _ {\ infty} \ leq 1 \\ - \ nu \ em R ^ k _ +$

onde

| m u |_{i n f t y} = m a x_{i} | m u_{i} |

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

Links para mais estudos:

Um pouco sobre a dualidade cônica

Como as tarefas duplas geralmente são criadas?

Dualidade cônica

Exemplo

More articles: