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
onde
,
,
.
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.
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
e definimos o conjunto
Se soubermos testar em tempo polinomial se
é vazio ou não, podemos então fazer busca binária sobre
para aproximar
.
Passo 3
Definir o Oráculo de Separação para
. Dado um ponto teste
:
- Se
e , o ponto é viável e dizemos “aceito”. - Caso contrário, existe alguma restrição violada: ou uma linha
ou a desigualdade . - Se
, devolvemos o plano de corte . - Se
, devolvemos o plano de corte (ou seja, ).
- Se
Passo 4
Escolher um elipsoide inicial
que contenha todo o conjunto
. Em geral basta um cubo ou bola grande centrada na origem, com raio que domine as entradas de
.
Passo 5
Iterar o método do elipsoide sobre
:
- No passo
, testamos o centro de no oráculo de separação. - Se for aceito, concluímos que
não é vazio; paramos e retornamos um ponto viável. - Se houver plano de corte
, atualizamos o elipsoide para de forma que contenha e seu volume diminua em fator fixo. - Repetir até volume do elipsoide ficar muito pequeno (indicando que
é vazio) ou encontrar ponto viável.
Passo 6
Fazer busca binária sobre
entre limites
e
conhecidos (por exemplo,
,
para algum
grande). A cada iteração de bisseção, usamos o método do elipsoide para testar viabilidade de
. Após
cortes, obtemos
com erro
.
Passo 7
Convergência e complexidade: cada chamada ao elipsoide leva
operações por iteração, e usa
iterações para distinguir viabilidade, onde
é o raio do elipsoide inicial e
o menor raio de inclusão. No total, a combinação com busca binária produz algoritmo polinomial em
.
Resposta
Para resolver
usa-se o método do elipsoide assim:
- Reduzimos ao teste de viabilidade de
via busca binária em. - Definimos um oráculo de separação que, dado
, retorna uma desigualdade violada de ou . - 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.
- Repetimos até declarar vazio (logo diminuir raio) ou encontrar ponto viável.
- A cada
testado, concluímos viabilidade ou não em tempo polinomial e, com busca binária em , obtemos a solução aproximada do problema original em tempo polinomial.