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
max;c^T xsujeito a A x<= b,
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 theta definimos o conjunto de nível
Ktheta = ,xinR^n : A x<= b,;c^T x>=theta
Se Kthetaneqvarnothing, existe solução com valor de objetivo >=theta. Assim, basta testar viabilidade de Ktheta para aproximar o ótimo em theta por busca binária.

Passo 3

Construção do oráculo de separação para Ktheta. Dado um ponto candidato x^k:
1. Se existe índice i tal que ai^T x^k> bi, o oráculo retorna o hiperplano de corte
ai^T x <= bi
2. Senão, se c^T x^k<theta, retorna o corte
-,c^T x <= -,theta
3. Caso contrário, x^kin Ktheta e temos um ponto viável.

Passo 4

Execução do método elipsoide para decidir viabilidade de Ktheta.
1. Escolhe-se um elipsoide inicial
E0 = x : (x-y0)^T P0^-1(x-y0)<=1,
por exemplo y0=0 e P0=R^2In, onde R é um raio que contém a região viável.
2. A cada iteração k toma-se o centro yk e consulta-se o oráculo.
3. Se o oráculo devolve corte pela direção g, atualiza-se
yk+1 = yk - 1n+1,Pk,graizg^T Pk g,
Pk+1 = n^2n^2-1l(Pk - 2n+1,Pk,g,g^T,Pkg^T Pk gr)
4. Repete-se até ou encontrar xin Ktheta (viabilidade) ou concluir que Ktheta é vazio.

Passo 5

Inicialização prática e garantia de contenção. Deve-se estimar um R>0 tal que qualquer vértice do politopo x:Ax<= b satisfaça |x|<= R. Com E0 de raio R o método converge em O(n^2log(R/de<a)) iterações para distinguir Kthetaneqvarnothing de Ktheta=varnothing com precisão de<a.

Passo 6

Busca binária sobre theta. Escolhemos limites iniciais alpha<=minc^T x:Ax<= b e beta>=maxc^T x:Ax<= b. Enquanto beta-alpha>epsilon:
1. Define-se theta=(alpha+beta)/2.
2. Aplica-se o método elipsoide para viabilidade de Ktheta.
3. Se viável, atualiza-se alphatheta e guarda-se o ponto; senão, betatheta.
No fim, obtemos x com c^T x>=alphaapprox valor ótimo com precisão epsilon.

Passo 7

Complexidade e conclusão. Cada teste de viabilidade é polinomial em n,m,log(R/de<a) e a busca binária insere fator O(log((beta-alpha)/epsilon)). Dessa forma, obtemos uma solução epsilon-aproximada do LP em tempo polinomial.

Resposta

A técnica consiste em reduzir o LP a testes de viabilidade do conjunto paramétrico Ktheta, implementar um oráculo de separação simples para Ax<= b e c^T x>=theta, resolver cada teste com o método elipsoide e usar busca binária em theta para aproximar o valor ótimo em tempo polinomial.

Exercícios relacionados