Descreva como funciona o método dos elipsoides para determinar uma solução do sistema A x <= b.

Passo 1

Estamos diante do problema de encontrar um vetor xinR^n tal que
A x <= b,
onde A é uma matriz mtimes n e binR^m. O método dos elipsoides é um algoritmo de programação convexa que decide, em tempo polinomial, se esse sistema é factível e, em caso afirmativo, produz uma solução aproximada. Para aplicá-lo precisamos de um elipsoide inicial que contenha a região factível (ou um hiper-retângulo que a contenha) e de um “oráculo de separação” que, dado um ponto xk, diga se ele satisfaz Axk<= b ou retorne uma desigualdade violada.

Passo 2

Definimos um elipsoide inicial
E0 = ,xmid (x - x0)^top H0^-1(x - x0) <= 1,
onde normalmente x0=0 e H0 = R^2 In, com R grande o suficiente para conter a bola de raio R que engloba toda solução possível (por hipótese supomos conhecer tal R).

Passo 3

Em cada iteração k, tomamos o centro xk de Ek e consultamos o oráculo de separação:
  • Se A xk <= b, então xk já é uma solução factível e o algoritmo termina.
  • Caso contrário, existe um índice i tal que ai^top xk > bi A desigualdade ai^top x <= bi define um semiespaço que contém toda a região factível e separa xk dela.

Passo 4

Construímos o próximo elipsoide Ek+1 que contém a interseção Ekcapai^top x<= bi. As fórmulas de atualização são
xk+1 = xk - 1n+1,Hk,airaizai^top Hk,ai,
Hk+1 = n^2n^2-1l(Hk - 2n+1,Hk,ai,ai^top Hkai^top Hk,air)
Essas expressões garantem que
vol(Ek+1) < exp(-1/(2n)),vol(Ek),
ou seja, diminuição exponencial do volume a cada corte.

Passo 5

Continuamos as iterações até encontrarmos xk factível ou até que o volume de Ek caia abaixo de voll(B(r)r), onde r é um limite inferior não nulo do raio da maior bola inscrita na região factível (se existir). O número de passos necessários é
Ol(n^2logRrr),
o que faz do método dos elipsoides um algoritmo de tempo polinomial para decisão de factibilidade.

Resposta

O método dos elipsoides começa com um elipsoide grande que contém a região factível. A cada iteração testa o centro; se não for factível, usa uma desigualdade violada como plano de corte e atualiza o elipsoide pela fórmula de Khachiyan, reduzindo seu volume de forma controlada. Repete até encontrar x com Ax<= b ou provar que não há solução, tudo em tempo polinomial O(n^2log(R/r)).

Exercícios relacionados