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
que contém a região factível
. Para aplicar o método precisamos de um oráculo que, dado um ponto
, ou confirme que
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 o oráculo não nos fornece nenhum hiperplano separador, isso significa que
Se ao avaliar o centro
e, no caso de problema de factibilidade, podemos parar imediatamente – encontramos um ponto factível. Em problema de minimização, podemos então avaliar
como candidata de solução.
Passo 3
Critério de parada por precisão na função
Para minimização de , supondo que tenhamos um valor de cota inferior
(geralmente obtido a partir dos subgradientes) e um valor de função no centro
, podemos parar quando
Para minimização de
ou seja, a diferença entre o valor atual e a melhor cota conhecida fica abaixo da tolerância
.
Passo 4
Critério de parada por volume do elipsoide
Como , garantir que
se torne “pequeno” equivale a forçar qualquer ponto em
estar a no máximo
de qualquer outro ponto de
. Em particular, se o volume de
cai abaixo do volume de uma bola de raio
, então a região factível não pode ser maior que essa bola, o que implica precisão geométrica. Escrevemos
Como
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
Usando o fato de que a atualização do volume no método dos elipsoides satisfaz
pode-se mostrar que basta
iterações para que
, onde
é 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 de
(achamos ponto factível),
(b) (atingimos a precisão desejada na função),
(c) (volume do elipsoide muito pequeno),
(d) alcança o número máximo
(a) o oráculo não consegue separar o centro
(b)
(c)
(d)