Atualização do Elipsoide
Seja a restrição violada na iteração
, dada por
, com o elipsoide atual
:
- Definir:
- Novo centro:
- Nova matriz:
- Obs: Alguns textos não consideram
ao calcular o novo centro.
Passo 1
O enunciado trata da atualização do elipsoide na iteração
do método do elipsoide para resolver um sistema de restrições lineares. Temos um elipsoide atual
e uma restrição violada
O objetivo é construir um novo elipsoide menor que contenha a parte viável (a interseção do elipsoide antigo com o meio-espaço
), reduzindo o volume a cada passo.
Passo 2
Primeiro normalizamos o “vetor de corte” e medimos o deslocamento da restrição em relação ao centro atual. Definimos
Aqui
é um vetor de norma unitária no espaço métrico induzido por
, e
mede quantos “raios normalizados” o plano
está afastado do centro
.
Passo 3
Para garantir que o novo elipsoide contenha a parte viável, movemos o centro ao longo de
. A fórmula geral do novo centro é
Intuição: se
, o plano corta exatamente pelo centro e deslocamos em
do “raio”; se
, o corte está fora do elipsoide e deslocamos um pouco mais.
Passo 4
A nova matriz de forma do elipsoide deve encolher na direção de
e expandir ligeiramente nas demais para manter a volumetria mínima que ainda contemple o corte. O fator de escala e a projeção usam o resultado padrão
Isso garante que
e que o elipsoide resultante engloba o conjunto viável remanescente.
Passo 5
Em muitas referências a atualização do centro ignora o deslocamento
, usando
o que corresponde ao caso especial
(o plano sempre passa pelo centro).