Método do Elipsoide para Problemas Lineares

Como pode resolver um problema de otimização linear pelo método de elipsoides?

Passo 1

Resumindo o enunciado: queremos resolver
maxxinR^n ,c^T x mid A x <= b
onde AinR^mtimes n, binR^m, cinR^n.
O conteúdo é o método do elipsoide, que converte um problema de otimização linear em uma série de problemas de viabilidade em conjuntos convexos, usando um oráculo de separação e atualizando um elipsoide que contém a região viável.

Passo 2

Converter o problema de otimização numa sequência de problemas de viabilidade. Para isso, fixamos um valor candidato mu e definimos o conjunto
S(mu) = ,xinR^n mid A x <= b,;c^T x >= mu
Se soubermos testar em tempo polinomial se S(mu) é vazio ou não, podemos então fazer busca binária sobre mu para aproximar maxc^T x mid A x<= b.

Passo 3

Definir o Oráculo de Separação para S(mu). Dado um ponto teste xk:
  • Se A xk <= b e c^T xk >= mu, o ponto é viável e dizemos “aceito”.
  • Caso contrário, existe alguma restrição violada: ou uma linha ai^T x <= bi ou a desigualdade c^T x >= mu.
    • Se ai^T xk > bi, devolvemos o plano de corte ai^T x <= bi.
    • Se c^T xk < mu, devolvemos o plano de corte c^T x >= mu (ou seja, -c^T x <= -mu).

Passo 4

Escolher um elipsoide inicial E0 = xmid (x - x^0)^T P0^-1(x - x^0) <= 1 que contenha todo o conjunto xmid A x<= b. Em geral basta um cubo ou bola grande centrada na origem, com raio que domine as entradas de A,b,c.

Passo 5

Iterar o método do elipsoide sobre S(mu):
  1. No passo k, testamos o centro xk de Ek no oráculo de separação.
  2. Se for aceito, concluímos que S(mu) não é vazio; paramos e retornamos um ponto viável.
  3. Se houver plano de corte g^T x <= h, atualizamos o elipsoide para Ek+1 de forma que Ek+1 contenha Ekcapg^T x <= h e seu volume diminua em fator fixo.
  4. Repetir até volume do elipsoide ficar muito pequeno (indicando que S(mu) é vazio) ou encontrar ponto viável.

Passo 6

Fazer busca binária sobre mu entre limites mumin e mumax conhecidos (por exemplo, mumin = -M, mumax=M para algum M grande). A cada iteração de bisseção, usamos o método do elipsoide para testar viabilidade de S(mu). Após O(log(tfracMvarepsilon)) cortes, obtemos mu com erro varepsilon.

Passo 7

Convergência e complexidade: cada chamada ao elipsoide leva O(n^2) operações por iteração, e usa O(nlog(R/rho)) iterações para distinguir viabilidade, onde R é o raio do elipsoide inicial e rho o menor raio de inclusão. No total, a combinação com busca binária produz algoritmo polinomial em (n,m,log M,log(1/varepsilon)).

Resposta

Para resolver
maxc^T xmid A x<= b
usa-se o método do elipsoide assim:
  1. Reduzimos ao teste de viabilidade de
    xmid A x<= b,;c^T x>=mu
    via busca binária em mu.
  2. Definimos um oráculo de separação que, dado xk, retorna uma desigualdade violada de A x<= b ou c^T x>=mu.
  3. Iniciamos um elipsoide grande contendo a região viável e, a cada iteração, testamos o centro no oráculo. Se for viável, paramos; senão, cortamos o elipsoide com a hipersuperfície retornada e atualizamos o elipsoide.
  4. Repetimos até declarar vazio (logo diminuir raio) ou encontrar ponto viável.
  5. A cada mu testado, concluímos viabilidade ou não em tempo polinomial e, com busca binária em mu, obtemos a solução aproximada do problema original em tempo polinomial.

Exercícios relacionados