Quais são os critérios de parada no método dos elipsoides?

Passo 1

O método dos elipsoides é um procedimento iterativo para resolver problemas de factibilidade ou minimização convexa, em que a cada iteração temos um elipsoide
Ek = xmid (x - ck)^TPk^-1(x - ck)<= 1
que contém a região factível Q. Para aplicar o método precisamos de um oráculo que, dado um ponto x, ou confirme que xin Q ou devolva um hiperplano separador (um subgradiente ou corte). Nosso objetivo é decidir quando parar as iterações, garantido que já encontramos ou aproximamos suficientemente a solução ótima.

Passo 2

Critério de parada por corte vazio (factibilidade)
Se ao avaliar o centro ck o oráculo não nos fornece nenhum hiperplano separador, isso significa que
ckin Q
e, no caso de problema de factibilidade, podemos parar imediatamente – encontramos um ponto factível. Em problema de minimização, podemos então avaliar f(ck) como candidata de solução.

Passo 3

Critério de parada por precisão na função
Para minimização de f, supondo que tenhamos um valor de cota inferior Lk (geralmente obtido a partir dos subgradientes) e um valor de função no centro f(ck), podemos parar quando
f(ck) - Lk <= varepsilon,
ou seja, a diferença entre o valor atual e a melhor cota conhecida fica abaixo da tolerância varepsilon>0.

Passo 4

Critério de parada por volume do elipsoide
Como Qsubseteq Ek, garantir que Ek se torne “pequeno” equivale a forçar qualquer ponto em Ek estar a no máximo varepsilon de qualquer outro ponto de Q. Em particular, se o volume de Ek cai abaixo do volume de uma bola de raio varepsilon, então a região factível não pode ser maior que essa bola, o que implica precisão geométrica. Escrevemos
Vol(Ek)<= Voll(B(varepsilon)r) ;;Longrightarrow;; parar

Passo 5

Critério de parada por número máximo de iterações
Usando o fato de que a atualização do volume no método dos elipsoides satisfaz
Vol(Ek+1) <= expl(-tfrac12(n+1)r),Vol(Ek),
pode-se mostrar que basta
k >= llceil tfracn(n+1)2,lnR0varepsilonrrceil
iterações para que Vol(Ek)<= Vol(B(varepsilon)), onde R0 é o raio do elipsoide inicial.

Resposta

Os principais critérios de parada do método dos elipsoides são:
(a) o oráculo não consegue separar o centro ck de Q (achamos ponto factível),
(b) f(ck)-Lk<=varepsilon (atingimos a precisão desejada na função),
(c) Vol(Ek)<=Vol(B(varepsilon)) (volume do elipsoide muito pequeno),
(d) k alcança o número máximo
llceil n(n+1)2lnR0varepsilonrrceil ,.

Exercícios relacionados