Descreva em detalhes uma técnica pela qual podemos usar o método elipsoide para resolver um problema de otimização linear.
Passo 1
Resumindo o enunciado: queremos resolver o problema de otimização linear
usando o método elipsoide, que originalmente solve problemas de viabilidade de conjuntos convexos via um oráculo de separação.
Passo 2
Redução da otimização linear a um problema de viabilidade paramétrico. Para cada valor
definimos o conjunto de nível
Se
, existe solução com valor de objetivo
. Assim, basta testar viabilidade de
para aproximar o ótimo em
por busca binária.
Passo 3
Construção do oráculo de separação para
. Dado um ponto candidato
:
. Se existe índice
tal que
, o oráculo retorna o hiperplano de corte
Passo 4
Execução do método elipsoide para decidir viabilidade de
.
. Escolhe-se um elipsoide inicial
por exemplo
e
, onde
é um raio que contém a região viável.
. A cada iteração
toma-se o centro
e consulta-se o oráculo.
. Se o oráculo devolve corte pela direção
, atualiza-se
Passo 5
Inicialização prática e garantia de contenção. Deve-se estimar um
tal que qualquer vértice do politopo
satisfaça
. Com
de raio
o método converge em
iterações para distinguir
de
com precisão
.
Passo 6
Busca binária sobre
. Escolhemos limites iniciais
e
. Enquanto
:
. Define-se
.
. Aplica-se o método elipsoide para viabilidade de
.
. Se viável, atualiza-se
e guarda-se o ponto; senão,
.
No fim, obtemos com
valor ótimo com precisão
.
No fim, obtemos
Passo 7
Complexidade e conclusão. Cada teste de viabilidade é polinomial em
e a busca binária insere fator
. Dessa forma, obtemos uma solução
-aproximada do LP em tempo polinomial.
Resposta
A técnica consiste em reduzir o LP a testes de viabilidade do conjunto paramétrico
, implementar um oráculo de separação simples para
e
, resolver cada teste com o método elipsoide e usar busca binária em
para aproximar o valor ótimo em tempo polinomial.