Descreva como funciona o método dos elipsoides para determinar uma solução do sistema
.
Passo 1
Estamos diante do problema de encontrar um vetor
tal que
onde
é uma matriz
e
. 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
, diga se ele satisfaz
ou retorne uma desigualdade violada.
Passo 2
Definimos um elipsoide inicial
onde normalmente
e
, com
grande o suficiente para conter a bola de raio
que engloba toda solução possível (por hipótese supomos conhecer tal
).
Passo 3
Em cada iteração
, tomamos o centro
de
e consultamos o oráculo de separação:
- Se
, então já é uma solução factível e o algoritmo termina. - Caso contrário, existe um índice
tal que A desigualdade define um semiespaço que contém toda a região factível e separa dela.
Passo 4
Construímos o próximo elipsoide
que contém a interseção
. As fórmulas de atualização são
Essas expressões garantem que
,
ou seja, diminuição exponencial do volume a cada corte.
ou seja, diminuição exponencial do volume a cada corte.
Passo 5
Continuamos as iterações até encontrarmos
factível ou até que o volume de
caia abaixo de
, onde
é 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 é
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
com
ou provar que não há solução, tudo em tempo polinomial
.