Um problema de otimização min-max (OMM) é um problema de otimização matemática da seguinte forma:

,

no qual f é uma função limitada e g é uma função convexa . Os problemas MMO desempenham um papel central na teoria dos jogos, na otimização convexa e na aprendizagem de máquina online . A solução de um problema MMO envolve encontrar um par viável de vetores ( x*, y* ) que seja um ponto de sela, ou seja, que satisfaça simultaneamente as duas condições seguintes:

f(x*,y*) ≤ f(x,y*) para todo x com g( x, y* ) ≤ 0; f(x*,y*) ≥ f(x*,y) para todo y com g( x*, y ) ≤ 0.

Note que a otimização não é feita sequencialmente (maximizar f(x,y) em relação a y para cada x fixo e, em seguida, maximizar a função resultante em relação a x, ou vice versa). Isso é feito simultaneamente: a solução deve ser mínima em relação a x para o y* dado e máxima em relação a y para o x* dado.

A solução para um problema OMM é um equilíbrio de Nash em um jogo de soma zero de dois jogadores, onde o retorno do jogador y é f( x, y ) (e o retorno do jogador x é -f( x, y )). Assim, resolver um problema OMM é um caso especial de computação de equilíbrio de Nash. Jogadores consideram o pior retorno possível para cada estratégia, e escolhem pela estratégia que possui o maior menor retorno.

Função objetivo convexa-côncava A função f é chamada convexa-côncava se for uma função convexa de x para qualquer y fixo e uma função côncava de y para qualquer x fixo. Quando f é contínua e convexa-côncava, e o conjunto de restrições é um espaço compacto convexo, o OMM sempre possui uma solução, que pode ser computada eficientemente usando programação convexa. Isto foi provado por Rosen em 1965 e foi usado para provar a existência de equilíbrios de Nash em jogos côncavos.

O teorema minimax de Sion (1958) prova uma forma ainda mais geral: se f é uma função quase-convexa de x para qualquer y fixo, e uma função quase-côncava de y para qualquer x fixo, e o conjunto de restrições é um espaço compacto convexo, o OMM sempre tem uma solução, que pode ser calculada calculando sequencialmente o máximo e depois o mínimo, ou o mínimo e depois o máximo (os dois cálculos sequenciais levam a resultados idênticos neste caso).

Se f for L-suave, o problema pode ser resolvido usando métodos de primeira ordem, obtendo um erro polinomial de aproximação em L e 1/T em T iterações.

Se f também for fortemente convexa-côncava, a taxa de convergência linear é possível.

Função objetivo não convexa-côncava Em aprendizado profundo, é muitas vezes necessário resolver problemas OMM com funções objetivo que não são convexas-côncavas. Isso é particularmente usado para testar a robustez de sistemas de aprendizado profundo contra oponentes, pois se quer calcular o retorno mínimo (considerando todas as estratégias de ataque) do máximo (considerando todas as estratégias de defesa).

Em OMM com funções objetivo não convexa-côncava, uma solução pode não existir mesmo quando o conjunto viável é compacto (isso difere dosdifere do problemas de minimização ou maximização padrão, onde sempre existe uma solução mesmo quando a função objetivo não é convexa nem côncava). Um exemplo é o caso de f (x, y) = (x - y)2 como a função objetivo e o cubo unitário [0,1]x[0,1] como o conjunto viável. Aqui, para cada x fixo, o máximo em relação a y é atingido em y = 0 (se x > 0,5) ou y = 1 (se x < 0,5). No entanto, para qualquer y fixo, o mínimo em relação a x é atingido em x = y . Portanto, nenhum ponto é simultaneamente máximo em relação a y e mínimo em relação a x .

O processo de verificação de se um determinado problema OMM tem solução é NP-difícil . Permanecerá NP-difícil mesmo no caso especial em que a região viável é uma caixa [0,1] d, a função f é G-Lipschitz e L-suave, e apenas uma solução epsilon-aproximada é permitida (onde 1/epsilon, G e L são polinômios na dimensão d). Os métodos de primeira ordem não funcionam bem para esses problemas.

Daskalakis, Skoutakis e Zampetakis estudam OMMs com restrições lineares (o conjunto viável é um politopo ). Eles analisam a complexidade de tempo de execução do cálculo de equilíbrios locais aproximados de mínimo-máximo em função dos parâmetros de aproximação, da suavidade e da constante de Lipschitz da função objetivo.

Ver também

Otimização lexicográfica max-min - um tipo diferente de problema de otimização (multiobjetivo em vez de objetivo único). Teorema popular (teoria dos jogos) - um teorema no qual os pagamentos minmax são importantes. São conhecidos como "pontos de punição" ou "pontos de ameaça", já que um jogador não pode ser punido além desse limite. Negociação cooperativa - outra área em que os pagamentos minmax são importantes. Aqui, são mais conhecidos como "pontos de desacordo" ou "pontos de status quo". Teorema do minimax - estabelece condições para jogos, garantindo que o valor minimax seja igual ao valor maximin.

Referências

Categoria:Otimização matemática Categoria:Otimização