Atualização do Elipsoide

Seja a restrição violada na iteração k, dada por a^top x <= b, com o elipsoide atual E(M^k, X^k) :
  • Definir:
u=M^k araiza^top M^k a, beta=b-a^top X^kraiza^top M^k a
  • Novo centro:
X^k+1=X^k-1+betan+1 u
  • Nova matriz:
M^k+1=n^2n^2-1(M^k-2n+1 u u^top)
  • Obs: Alguns textos não consideram beta ao calcular o novo centro.

Passo 1

O enunciado trata da atualização do elipsoide na iteração k do método do elipsoide para resolver um sistema de restrições lineares. Temos um elipsoide atual
E(M^k,X^k)=,xmid (x-X^k)^!top(M^k)^-1(x-X^k)<=1
e uma restrição violada
a^topx<= b
O objetivo é construir um novo elipsoide menor que contenha a parte viável (a interseção do elipsoide antigo com o meio-espaço a^topx<= b), 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
u = M^k,araiza^topM^k a, beta = b - a^topX^kraiza^topM^k a
Aqui ,u é um vetor de norma unitária no espaço métrico induzido por (M^k)^-1, e beta mede quantos “raios normalizados” o plano a^topx=b está afastado do centro X^k.

Passo 3

Para garantir que o novo elipsoide contenha a parte viável, movemos o centro ao longo de -u. A fórmula geral do novo centro é
X^k+1 = X^k - 1+betan+1;u
Intuição: se beta=0, o plano corta exatamente pelo centro e deslocamos em 1/(n+1) do “raio”; se beta>0, 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 u 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
M^k+1 = n^2n^2-1l(M^k - 2n+1,u,u^topr)
Isso garante que det(M^k+1)<det(M^k) 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 beta, usando
X^k+1=X^k-1n+1,u,
o que corresponde ao caso especial beta=0 (o plano sempre passa pelo centro).

Resposta

u=M^karaiza^topM^ka, beta=b - a^topX^kraiza^topM^ka,
X^k+1=X^k-1+betan+1,u,
M^k+1=n^2n^2-1l(M^k-2n+1,u,u^topr)

Exercícios relacionados