Uma introdução à otimização robusta [... e uma pequena lista de compras que eu esqueci ...]

Como determinar quantas pessoas precisam ser contratadas para uma nova realização, com o que exatamente preenchê-la e onde colocar um determinado produto? Quanto maior o negócio, maior a incerteza e mais caro o erro. Derrotar o caos e escolher a melhor solução é uma das tarefas da equipe de ciência de dados. E como a matemática é a base da análise de dados, começaremos com ela.

Neste post, consideraremos problemas de otimização com incerteza nos dados e sua aproximação por problemas convexos determinísticos. Esse é um dos principais truques da otimização robusta - uma técnica que permite lidar com tarefas de otimização sensíveis demais às alterações nos dados de entrada.

A questão da sensibilidade é muito importante. Para tarefas, cuja qualidade depende fracamente de alterações nos dados, é mais fácil usar a otimização estocástica usual. No entanto, em tarefas com alta sensibilidade, essa abordagem gera um resultado ruim. Existem muitas tarefas desse tipo em finanças, gerenciamento da cadeia de suprimentos, design e muitas outras áreas.

E sim, este é um exemplo de postagem em que a complexidade cresce exponencialmente (lixo já) ...

O que significa "resolver" o problema de otimização?

Vamos começar com um breve lembrete.

A tarefa de otimização em geral é assim:

$$

$$\ min_ {x \ in R ^ n} f (x) \\ s.t. \\ x \ in X$$

Aqui $$$f (x)$ chamada função objetivo e $$$X$ - um conjunto válido.

Resolvendo o problema de otimização, entendemos esse ponto $$$x ^ * \ em X$ para o qual é executado:

$$

$$f (x) - f (x ^ *) \ geq 0, \ quad \ forall x \ in X$$

Este é o conceito padrão para resolver o problema de otimização sem incertezas.

O que é um problema de otimização com incerteza?

É hora de pensar sobre a origem da função $$$f (x)$ e limitações $$$X$ .

Muito útil para compartilhar

• lógica estrutural do problema (em outras palavras, quais funções são usadas),
• limitações técnicas (independentes da lógica ou dos dados humanos),
• parâmetros que são avaliados a partir dos dados.

Por exemplo, uma pessoa de negócios veio até nós e mostrou o problema de programação linear:

$$

$$\ min_ {x \ in R ^ 2} 2,16 x_1 + 3,7 x_2 \\ s.t. \\ 0,973 x_1 + 2,619 x_2 \ leq 3,32 \\ x_1 \ geq 0, x_2 \ geq 0$$

Você vê esta tarefa pela primeira vez. Um homem também (talvez não, mas de jaqueta azul tudo é tão abstrato!). Você não sabe o significado das variáveis. Mas mesmo agora, com muita confiança, podemos dizer que:

1. Provavelmente a tarefa é linear, porque alguém decidiu isso. Linearidade é a estrutura que uma pessoa escolheu.
2. Limitações $$$x_1 \ geq 0, x_2 \ geq 0$ são técnicos. Ou seja, eles vieram da "física" e não dos dados (por exemplo, as vendas não podem ser negativas).
3. Coeficientes Específicos $$$\ {0,973, 2,619, 3,32 \}$ na limitação $$$0,973 x_1 + 2,619 x_2 \ leq 3,32$ no nosso exemplo foram avaliados a partir dos dados. Ou seja, no começo alguém disse que a variável $$$x_1$ associado à variável $$$x_2$ , foi dito que a relação é linear e, finalmente, os coeficientes na equação de acoplamento foram estimados a partir dos dados. O mesmo vale para as probabilidades. $$$\ {2,16, 3,7 \}$ na função objetivo.

Quando falamos sobre tarefas com incerteza, direcionamos com precisão a incerteza nos parâmetros estimados a partir dos dados. Não tocamos nas limitações técnicas ou na escolha inicial da estrutura do problema.

De volta à nossa história. Temos um problema linear, alguém estimou os coeficientes nele de alguma forma. Se estivéssemos certos sobre a natureza dos coeficientes na função, na verdade fomos solicitados a resolver o problema em um cenário de desenvolvimento de eventos (uma instância específica do problema).

Às vezes isso é suficiente para nós, e apenas resolvemos.

No entanto, às vezes, resolver um problema para um cenário é uma ideia estúpida (por exemplo, se a solução é muito sensível à variação de dados).

O que fazer neste caso e como modelar a incerteza nos dados?

Primeiro, observe que a incerteza de dados sempre pode ser transferida da função objetivo para restrições ou vice-versa. Como fazer isso, olhe embaixo do corte.

Estocástica, on-line, otimização robusta e lista de produtos

Podemos ter muitos cenários de incerteza, bem como opções para o que fazer com isso. Ilustramos várias abordagens padrão com um exemplo simples.

Não sei como está a situação de um leitor respeitado, mas aqui sou casado (com sucesso) e periodicamente vou ao supermercado. Com uma folha, é claro (dá invulnerabilidade de compras impulsivas). Às vezes, não apenas para a loja, mas para o Auchan condicional, onde é mais barato, mas para onde ir longe.

Modelaremos esta situação: chegamos a Auchan com uma folha nas mãos para fazer compras.

Atenção, a primeira pergunta: como modelar?

Entrada: informações sobre os produtos a serem comprados e a quantidade necessária.

Por conveniência, podemos pensar no folheto como um vetor inteiro não negativo $$$y \ em Z _ + ^ n$ .

Como variáveis, tomamos, respectivamente, um vetor inteiro não negativo $$$x \ em Z _ + ^ n$ - quantos e quais produtos finalmente compraremos (nossa solução).

O ponto é pequeno - faça algum tipo de função objetiva $$$f (x, y)$ , que indica o quanto cometemos um erro na escolha dos produtos.

Dependendo do contexto, o tipo de função pode mudar, mas existem alguns requisitos básicos para isso:

• Função $$$f (x, y)$ deve ter um mínimo $$$x ^ * = \ arg \ min_ {x \ in R ^ n} f (x, y) = y$ (ou seja, na melhor das hipóteses, compraremos exatamente o que está escrito no folheto)
• Função $$$f (x, y)$ deve ser convexo em $$$x$ (e de preferência suave) - para poder calcular efetivamente $$$min$ .

Assim, obtemos o problema:

$$

$$min_ {x \ in R ^ n} f (x, y)$$

Agora imagine que a folha permaneceu em casa ...

Então, com uma observação, entramos no mundo das tarefas com incerteza.

Então, o que fazer se na tarefa $$$min_ {x \ in R ^ n} f (x, y)$ desconhecido para nós $$$y$ ?

A resposta, novamente, depende do contexto.

Otimização estocástica

A otimização estocástica (geralmente) envolve

• A incerteza nos dados é de natureza estocástica. Conhecimento completo da distribuição probabilística de valores de parâmetros não determinísticos
• Limitações, incluindo incerteza, são suaves

No nosso exemplo, se o modelássemos usando otimização estocástica, diríamos

• Ok, eu não sei o que estava escrito no folheto, mas ando com folhetos há 8 anos e tenho conhecimento suficiente sobre a distribuição do vetor $$$y$
• Mesmo se eu cometer um erro com a escolha (ou seja, com $$$x$ ), voltando para casa, descubro o verdadeiro $$$y$ e, se eu estiver completamente seguro, irei até Pyaterochka e comprarei lá, embora mais caro.
• Agora vou escolher uma $$$x$ , que minimizará algum tipo de agregação da função objetivo original e possíveis "multas" pelo erro.

Isso nos levará a esta tarefa:

$$

$$\ min_ {x \ in R ^ n} E_y [f (x, y) + \ psi (y, z)] \\ s.t. \\ x + z \ geq y$$

Observe que nesta tarefa, de fato, tomamos decisões duas vezes: primeiro, a principal decisão de compra na Auchan, pela qual somos responsáveis $$$x$ , então "correção de erros" com $$$z$ .

Os principais problemas com essa abordagem são:

• Geralmente, não há informações sobre a distribuição dos parâmetros.
• As limitações podem ser severas (para tarefas com alto risco - morte, ruína, apocalipse nuclear ou zumbi, etc.)
• Nem sempre é possível “corrigir erros” (uma decisão é tomada uma vez) ou vice-versa, muitas vezes são tomadas decisões (nesse caso, muitas integrais aninhadas aparecerão e será muito difícil contar).

Otimização online

A otimização online é uma estrutura que explora tomadas de decisão consistentes. Uma das abordagens padrão para modelagem nessa estrutura são os bandidos com várias armas, que já foram escritos sobre Habré muitas vezes.

No contexto do nosso exemplo de brinquedo, deveríamos:

• não tinha (e nunca usou antes) folheto
  
• e em casa seríamos elogiados / repreendidos pelos produtos que compramos (ao mesmo tempo, só podíamos adivinhar o conjunto desejado)
• a tarefa seria aprender o mais rápido possível a comprar comida, bem como seu antigo príncipe imaginário ou o melhor amigo dos filhos de sua mãe.

Otimização robusta

A otimização robusta é uma extensão lógica da ideia de uma solução minimax.

Idealmente, devemos agora tomar uma decisão que sempre será aceitável, independentemente das circunstâncias. As pessoas que projetaram panelas, ferros e geladeiras na URSS fizeram isso no contexto de otimização robusta: o produto deve funcionar mesmo que tenha sido usado por 20 anos como a principal ferramenta para o extermínio de mutantes que surgiram após a guerra nuclear (também precisa ser sobrevivido).

Além disso, quero que a tarefa seja inserida em um solucionador comum - e eles não entendem as restrições "para qualquer implementação de uma variável aleatória" (se não houver um número finito dessas implementações).

No problema de um folheto, a decisão deve ser tomada aqui e agora e permanecer válida em qualquer circunstância:

$$

$$\ min_ {x \ in R ^ n, t \ in R} t \\ s.t. \\ f (x, y) \ leq t \ quad \ forall y \\ x \ geq y \ quad \ forall y$$

É claro que, mesmo neste exemplo de brinquedo, se você não precisar de nada $$$y$ , nenhuma solução significativa funcionará.

Então, como você lida com essas tarefas?

Construindo uma versão robusta de uma tarefa usando o exemplo de tarefa LP

Considere um problema de otimização linear com incerteza:

$$

$$\ min_ {x \ in R ^ n} c ^ Tx + d \\ s.t. \\ Ax \ leq b$$

Parâmetros $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ foram derivados de dados e incluem incerteza.

Suposição 1: Muitos valores (implementações) $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ pode ser parametrizado, ou seja, existem tais $$$\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix}, \ begin {pmatrix} c_1 ^ T, d_1 \\ A_1, b_1 \ end {pmatrix}, \ dots, \ begin {pmatrix } c_k ^ T, d_k \\ A_k, b_k \ end {pmatrix}$ que qualquer implementação de dados $$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix}$ encontra-se no conjunto:

$$

$$\ begin {pmatrix} c ^ T, d \\ A, b \ end {pmatrix} \ in U = \ left \ {\ begin {pmatrix} c_0 ^ T, d_0 \\ A_0, b_0 \ end {pmatrix} + \ sum_ {i = 1} ^ k \ zeta_i \ begin {pmatrix} c_i ^ T, d_i \\ A_i, b_i \ end {pmatrix} | \ quad \ zeta \ no Q \ subconjunto R ^ k \ right \}$$

Aqui $$$\ begin {pmatrix} c ^ T_0, d_0 \\ A_0, b_0 \ end {pmatrix}$ são chamados dados "nominais" e $$$\ begin {pmatrix} c ^ T_i, d_i \\ A_i, b_i \ end {pmatrix} \ quad (1 \ leq i \ leq k)$ - "turnos".



Já sabemos que toda a incerteza no problema pode ser removida nas limitações. Vamos fazer isso.

Temos o problema

$$

$$\ min_ {x \ in R ^ n, t \ in R} t \\ st \\ c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ em U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ em U \\ $$

Versão robusta da tarefa

Agora é a hora de um dos truques mais legais da otimização robusta - como passar de um número infinito de restrições para um conjunto finito de boas restrições.

Para começar, considere um exemplo simples quando

$$

$$Q = \ {\ zeta \ em R ^ k | \ | \ zeta \ | _2 \ leq 1 \}$$

Todas as restrições no sistema

$$

$$c ^ Tx + d \ leq t, \ quad \ forall \ begin {pmatrix} c ^ T, d \ end {pmatrix} \ em U \\ Ax \ leq b, \ quad \ forall \ begin {pmatrix} A, b \ end {pmatrix} \ em U \\ $$

o mesmo tipo - são apenas desigualdades lineares. Aprenda a trabalhar com um - aprenda a trabalhar com todos.

Portanto, consideramos uma restrição do tipo de desigualdade:

$$

$$a ^ Tx \ leq b \ quad \ forall (a, b) \ em U = \ {(a_0, b_0) + \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i, b_i) | \ quad \ zeta \ em Q \} \\ (a_0 + \ sum_ {i = 1} ^ k \ zeta_i a_i) ^ Tx \ leq b_0 + \ sum_ {i = 1} ^ k \ zeta_i b_i \ quad \ forall \ zeta \ in Q \\ \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx \ quad \ forall \ zeta \ em Q \\ \ max _ {\ zeta \ em Q} \ sum_ {i = 1} ^ k \ zeta_i \ cdot (a_i ^ T x - b_i) \ leq b_0 - a_0 ^ Tx$$

Deixe-me explicar o que aconteceu.

Primeiro, transferimos todas as partes com incerteza para o lado esquerdo da desigualdade; $$$\ zeta$ .
Depois disso, analisamos o pior caso (para cada $$$x$ ele é dele).
Como resultado, obtivemos o seguinte registro:

$$

$$g (x) = max _ {\ zeta \ in Q} f (x, \ zeta) \ leq b_0 - a_0 ^ Tx$$

.

O próximo passo é escrever uma função explícita $$$g (x)$ . Para fazer isso, basta resolver o problema de otimização $$$\ zeta$ e substituir o ideal $$$\ zeta *$ :

$$

$$\ max _ {\ | \ zeta \ | _2 \ leq 1} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) = \ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx - b_i) ^ 2}$$

o que leva à desigualdade:

$$

$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$$

Observe que a desigualdade resultante é convexa e qualquer $$$x$ satisfazê-lo satisfaz o original $$$a ^ Tx \ leq b$ para qualquer implementação $$$(a, b) \ em U$ ...

Limitação $$$\ sqrt {\ sum_ {i = 1} ^ k (a_i ^ Tx-b_i) ^ 2} + a_0 ^ Tx \ leq b_0$ chamada a versão robusta da restrição $$$a ^ Tx \ leq b \ quad \ forall (a, b) \ em U$ .

Este é um dos principais pilares da otimização robusta - a aproximação das restrições de probabilidade por um conjunto finito de restrições convexas.

O que fazer com restrições mais complexas (não lineares)?

Construindo versões robustas de restrições usando dualidade cônica

Muitas restrições não lineares padrão podem ser representadas em uma forma cônica (ou seja, na forma $$$Axe + b \ em K$ onde $$$K$ algum cone convexo fechado):

• Não negatividade $$$X \ geq 0 \ quad \ leftrightarrow \ quad x \ em R ^ n _ +$
• Restrições de norma $$$\ | x \ | _p \ leq p \ quad \ leftrightarrow \ quad \ begin {pmatrix} x \\ p \ end {pmatrix} \ em K_p ^ n = \ left \ {(x, t) \ em R ^ n \ times R_ + | \ quad \ | x \ | _p \ leq t \ right \}$
• Restrições à definição positiva da matriz $$$x_1F_1 + \ pontos x_nF_n + G \ successq 0$

Voltar para restrições robustas.

Suponha que o problema de otimização com relação a $$$\ zeta$ conseguiu ser reduzido a uma forma cônica

$$

$$\ max _ {\ zeta} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx - b_i) \\ s.t \\ C \ zeta + d \ em K$$

Construímos um dual para esse problema.

Há algum tempo, publiquei um post sobre a dualidade cônica exatamente para dedicar um pouco menos de atenção à técnica deste post.

$$

$$\ min _ {\ lambda} \ lambda ^ Td \\ st \\ C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k \\ \ lambda \ em K ^ *$$

Agora cabe à pequena coisa - o teorema da dualidade fraca:

$$

$$\ max _ {[\ zeta: \ quad C \ zeta + d \ em K]} \ sum_ {i = 1} ^ k \ zeta_i (a_i ^ Tx-b_i) \ leq \ min _ {\ lambda \ em G} \ lambda ^ Td \\ onde \\ G = \ esquerda \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ em K ^ * \ right \}$$

Portanto, como uma aproximação robusta da restrição inicial $$$a ^ Tx \ leq b, \ quad (a, b) \ em U$ restrição pode ser usada

$$

$$\ lambda ^ Td \ leq b_0 - a_0 ^ Tx \\ G = \ esquerda \ {\ lambda | \ quad C ^ T \ lambda + \ begin {pmatrix} a_1 ^ Tx - b_1 \\ \ dots \\ a_k ^ Tx - b_k \ end {pmatrix} = 0_k; \ quad \ lambda \ em K ^ * \ right \}$$

onde $$$\ lambda$ mesma variável que $$$x$ .

Então, construímos uma restrição robusta para a desigualdade original.

Conclusão

Examinamos a técnica de aproximação de restrições ruins (estocásticas) por um conjunto de boas restrições convexas. Isso pode ser útil, por exemplo, se:

• Você não deseja escrever algoritmos, mas o solucionador que você está usando não sabe como trabalhar com restrições de probabilidade.
• Há um problema com os parâmetros estocásticos, enquanto o ideal é muito sensível às flutuações nos dados.
• E, é claro, tarefas com incerteza, onde todas as restrições são rígidas (o preço do erro é muito alto)