Métodos baseados em interpolação
em região de confiança.
Fabio Antonio Araujo de Campos
30 de abril de 2010
Tópicos em otimização-MT853
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Estruturaç~
ao
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Estruturaç~
ao
1- Algumas consideraç~
oes sobre os métodos apresentados.
2- Aproximaç~
ao "DFO".
3- Método de Powell.
4- Método Wedge.
5- Converg^
encia do algoritmo Wedge para pontos
estacionários de primeira ordem.
6- Converg^
encia do algoritmo Wedge para pontos
estácionários de segunda ordem.
7- Consideraç~
oes finais.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Caracterı́sticas dos métodos
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Caracterı́sticas dos métodos
Quantos pontos podem ser incluı́dos na amostra?
Um modelo quadrático é desejável, mas a determinação completa
de um modelo quadrático baseado em interpolção polinomial pede
(n + 1)(n + 2)/2 avaliações de funções. Pode ser muito caro, pedir
tal precisão em cada passo; assim pode ser desejável construir
modelos baseados em poucos pontos de interpolação(veja cap. 5).
O número de pontos na amostra é estático por todo o
algoritmo ou pode ser din^
amico?
O algoritmo ”DFO”permite um número de pontos dinâmico, já o
algoritmo do método de Powell pede uma amostra que tenha
exatamente p1 ∈ [n + 2, (n + 1)(n + 2)/2] em todas as iterações.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Caracterı́sticas dos métodos
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Caracterı́sticas dos métodos
A amostra precisa ser Λ − posicionado em B(xk ; ∆k ) em cada
iteraç~
ao? E sen~
ao, como essa condiç~
ao pode ser relaxada?
Para conseguirmos Λ − posicionamento, precisamos desenvolver um
critério para aceitar pontos na amostra. Esse critério, em geral, é
baseado em um valor limite.
Que valor limite podemos escolher e como melhorá-lo se ele
for escolhido mal?
Se os valores limitantes forem escolhidos muito estritos pode
acontecer de não encontrarmos pontos adequados na amostra,e se o
limitante é escolhido muito folgado podemos ter um conjunto mal
posicionado.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Caracterı́sticas dos métodos
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Caracterı́sticas dos métodos
A amostra sempre estará contida em B(xk ; ∆k )?
Podemos querer recalcular muitos dos pontos da amostra
a cada vez que o iterando muda ou o raio da regi~
ao de
confiança é reduzido. Assim a exig^
encia do conjunto
amostral estar dentro da regi~
ao de confiança pode ser
relaxado em um algoritmo prático. Neste caso,
poderı́amos restringir-nos a B(xk ; r ∆k ) para r ≥ 1, ou
n~
ao nos restringirmos, mas trocarmos os pontos que
est~
ao longe de xk por pontos em B(xk ; r ∆k ).
A estrutura do capı́tulo 10 nos permite aceitar novos
iterandos se qualquer decréscimo é alcançado e o
modelo é suficientemente bom. Os algoritmos aqui
descritos estar~
ao baseados no decréscimo simples.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
A aproximaç~
ao "DFO".
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
A aproximaç~
ao "DFO".
Algumas caracterı́sticas principais do algoritmo
desenvolvido por Conn, Scheinberg e Toint.
Faz uso de muitos pontos amostrais(superior a
(n + 1)(n + 2)/2) que s~
ao avaliados no critério para
verificar o Λ − posicionamento. Em outra palavras o
número de pontos amostrais é din^
amico.
O modelo é o da interpolaç~
ao quadrática da mı́nima
norma de Frobenius.
O conjunto amostral é mantido Λ − posicionado em
B(xk ; r ∆k ), com r um fator de escala pequeno, maior ou
igual a 1. Fazendo r ≥ 2 temos um algoritmo mais
prático pois permite que pontos amostrais permaneçam
no conjunto amostral atual por poucas
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
iterações subsequentes, sempre que o iterando atual é movido ou o
raio da região de confiança é reduzido.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
iterações subsequentes, sempre que o iterando atual é movido ou o
raio da região de confiança é reduzido.
O algoritmo original usa os NFPs para manter o conjunto amostral
Λ − posicionado. Mas o algoritmo para melhoria do modelo usado,
é muito semelhante ao algoritmo de pivoteamento. E usaremos este
algoritmo, para discutir a convergência global do método.
Em cada iteração o algoritmo ”DFO”atualiza o conjunto amostral
Yk baseado no algoritmo pivotal.
No começo do algoritmo dois valores iniciais são selecionados:
0 < ξacc < 1/4 para aceitação de um ponto no conjunto de
interpolação e ξimp > 1 para melhorar o conjunto de
interpolação atual. A região em que o polinômio pivô é
otimizado é uma bola centrada no iterando atual de raio ∆k .
Dado qualquer conjunto de interpolação contendo o iterando
atual xk , o algoritmo pode designar o iterando atual como
primeiro pivô e selecionar os pontos restantes tal que o
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
conjunto resultante seja Λ − posicionado. Logo o iterando
atual sempre estará em um conjunto bem posicionado.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
conjunto resultante seja Λ − posicionado. Logo o iterando
atual sempre estará em um conjunto bem posicionado.
Considere o ponto amostral xk + sk gerado durante o passo de
minimização na região de confiança. Se o ponto gera um
decréscimo da função objetivo, então ele será o novo iterando.
O centro da região de confiança é movido e o algoritmo 6.5 é
aplicado para todos os pontos amostrais que estão na bola de
raio r ∆k centrado em xk + sk . Esse procedimento ou
selecionará um conjunto bem posicionado, ou irá parar por
falta de pontos amostrais adequados.
Se o ponto xk + sk não gera um decréscimo na função
objetivo, podemos ainda querer adicioná-lo no conjunto
amostral, trazendo assim informação nova. Além disso o custo
de avaliar a função nesse ponto já foi feito, então adicionamos
xk + sk em Yk e aplicamos o algoritmo 6.5. No final, os pontos
de Yk que não são usados são descartados.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Quando um passo de melhoria do modelo é desejado, depois
que um passo na região de confiança tenha sido calculado, o
novo ponto é calculado apenas com a idéia do posicionamento
da amostra em mente. Se o conjunto de interpolação Yk não
está completo, então aplicamos um passo do algoritmo 6.4
para maximizar o valor absoluto do polinômio pivô e aumentar
em um elemento o tamanho do conjunto de interpolação.
Caso contrário nós aplicamos um passo do algoritmo 6.6 para
trocar um ponto de Yk . A troca é aceitável se o valor do
último polinômio pivô é aumentada em pelo menos um fator
de ξimp . Caso contrário, consideramos que o passo de melhoria
do modelo falhou.
O algoritmo pivotal assume que o conjunto de pontos de
interpolação é sempre deslocado e escalado para uma bola de raio 1
e centro na origem. Porém na prática basta deslocar e escalar uma
única vez.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Agora apresentaremos o algoritmo ”DFO”modificado, para ambas as
situações onde gostarı́amos de atingir convergência global para pontos
estacionários de primeira ordem ou pontos estacionários de segunda
ordem.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Agora apresentaremos o algoritmo ”DFO”modificado, para ambas as
situações onde gostarı́amos de atingir convergência global para pontos
estacionários de primeira ordem ou pontos estacionários de segunda
ordem.
Algoritmo 11.1:
DFO modificado.
Passo 0(inicialização) Escolha um ponto inicial x0 , um raio máximo
∆max > 0 e um raio inicial para a região de confiança
∆0 ∈ (0, ∆max ]. Escolha o conjunto Y0 e calcule o modelo
inicial m0 (x). As constantes η1 , γ, γinc , εc , β e µ são
escolhidas tal que η1 , γ ∈ (0, 1), γinc > 1, εc > 0 e
µ > β > 0. Escolha os limites pivôs positivos ξacc e ξimp e
o fator raio da região de confiança r ≥ 1. Ponha k = 0.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
P1(passo crı́tico) Esse passo é como no algoritmo 10.2 ou 10.4, de
acordo com o resultado desejado. Note que Yk , ∆k e mk
podem mudar durate este passo.
P2(Cálculo do passo) Esse passo é como no algoritmo 10.1 ou 10.3.
P3(aceitação do ponto) Checar se mk (x) é CFL ou CFQ, que significa
garantir que se Yk contém pelo menos n + 1 pontos ou
(n + 1)(n + 2)/2 pontos respect. em B(xk ; ∆k). Calcule
f (xk + sk ) e defina
ρk =
f (xk ) − f (xk + sk )
mk (xk ) − mk (xk + sk )
Se ρk ≥ η1 ou se ρk > 0 e o modelo é CFL ou CFQ, então
xk+1 = xk + sk . Caso contrário o iterando e o modelo não
mudam. Aplicamos o procedimento para incluir o ponto
xk + sk na amostra. Considere novo modelo mk e a nova
amostra Yk .
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Algoritmo 10.1,10.2
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Algoritmo 10.1,10.2
P1(passo crı́tico): Se ||gkicb || > c , então mk = mkicb e ∆k = ∆icb
k . Se
||gkicb || ≤ c , então o procedimento segue. Chamamos o
algoritmo de melhoramento do modelo para tentar
certificar se o modelo mk é FL sobre B(xk ; ∆icb
k ). Se pelo
menos uma das condições se verificam,
O modelo mkicb não é CFL sobre B(xk ; ∆icb
k ),
icb
∆icb
>
µ||g
||,
k
k
então aplicamos o algoritmo 10.2(descrito abaixo) para
construir o modelo m̃k (xk + sk ), que é FL sobre a bola
˜ k ), para algum ∆
˜ k ∈ (0, µ||g̃k ||)] dado pelo
B(xk ; ∆
algoritmo 10.2. Neste caso coloque
mk = m̃k
e
˜ k , β||g̃k ||}, ∆
˜ k }.
∆k = min{max{∆
Caso contrário, coloque mk = mkicb e ∆k = ∆icb
k .
Cálculo do passo: Calcule o passo sk que reduz o modelo mk
suficientemente(relacionado ao passo de Cauchy) e tal que
xk + sk ∈ B(xk ; ∆k ).
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Algoritmo 10.1,10.2
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Algoritmo 10.1,10.2
P5(Atualização do raio da região de confiança): Ponha

 [∆k , min{γinc ∆k , ∆max }] se ρk ≥ η1 ,
{γ∆k }
se ρk < η1 é FL
∆icb
∈
k+1

{∆k }
se ρk < η1 e mk não é CFL
Algoritmo 10.2(Passo crı́tico)
Esse algoritmo é aplicado somente se ||gkicb || ≤ c e pelo menos um dos
seguintes fatos se verificam: o modelo mkicb não é CFL sobre B(xk ; ∆icb
k )
icb
ou ∆icb
>
µ||g
||.
A
constante
w
∈
(0,
1)
é
escolhida
no
Passo
0
do
k
k
algoritmo 10.1.
inı́cio: Ponha i = 0. Seja mk0 = mkicb .
Repita Aumente i por um. Use o algoritmo de melhoramento para
(i−1)
melhorar o modelo anterior mk
até que ele seja FL
i−1 icb
sobre B(xk ; w ∆k ). Denote o novo modelo por mki .
˜ k = w i−1 ∆icb e m̃k = mi .
Ponha ∆
k
k
i
˜
Até ∆k ≤ µ||g ||.
k
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
P4(melhoramento do modelo) Se ρk < η1 então tentamos melhorar o
modelo. Defina os novos mk e Yk .
P5(Atualização o raio) Esse passo é como no algoritmo 10.1 ou 10.3.
Faça k ← k + 1 e vá para o passo 1.
Notas do algoritmo.
Devido aos algoritmos 6.4, 6.5 e 6.6 o conjunto Yk contêm somente
pontos gerados por valores pivôs aceitos por estes algoritmos.
A cada iteração somente um ou dois novos pontos são gerados.
O algoritmo é muito flexı́vel quanto ao número de pontos usados.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
DFO
O principal esforço computacional está em calcular os polinômios
pivôs. Geralmente são usados pontos da ordem n2 , então o
algoritmo pivotal pode pedir operações da ordem de n6 . Para valores
pequenos de n este esforço pode ser pequeno, perto do preço para
se avaliar uma função. Para valores grandes de n faz sentido nos
restringirmos a um número de pontos de ordem n para os modelos.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Método de Powell
Aqui vamos desenvolver uma modificação do algoritmo de Powell.
Nós vamos combinar as bem sucedidas caracterı́sticas práticas do
algoritmo de Powell com a estrutura do cap 10.
A maneira com que Powell trabalha na região de confiança não é a
mesma desse livro. Para começar o raio da região de confiança e o
raio do conjunto de interpolação não são os mesmos.
De fato a maneira que Powell trabalha é muito mais complicada que
a tratada aqui. O menor dos raios é usado para forçar os pontos de
interpolação estejam suficientemente longes para evitar o ruı́do nos
valores da função. O passo para atualizar a região de confiança é
muito mais complicado. Tudo para melhorar a performance prática
do algoritmo. Nosso método de Powell usará mı́nima norma de
Frobenius dos Polinômios de Lagrange.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Agora comentaremos algumas caracterı́sticas:
Todas as amostras em todas as iterações contém
p1 ∈ [n + 2, (n + 1)(n + 2)/2] pontos. o valor p1 = 2n + 1 é uma
escolha natural e é valor padrão no NEWUOA.
Os modelos são modelos de interpolação quadrática com
remanescentes graus de liberdade tomados pela minimização da
norma de Frobenius.
O conjunto amostral é mantido baseado no algoritmo 6.3
modificado para lidar com o mı́nimo da norma de Frobenius de
polinômios de Lagrange.
Não é preciso envolver escalamento, pois polinômios de Lagrange
são escalados automaticamente. Deslocamentos também não
causam efeito. Entretanto, deslocar os pontos com respeito ao
centro atual da região de confiança tem um efeito importante sobre
a precisão numérica.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
a atualização da amostra no algoritmo de Powell original é realizado
da seguinte forma:
O conjunto de mı́nima norma de Frobenius de polinômios de
Lagrange li (x), i = 0, 1, 2, ..., p,, é mantido em todas as
iterações.
Se a minimização da região de confiança da k-ésima iteração
gera um passo sk , que não é pequeno comparado ao máximo
da distância entre os pontos amostrais e o iterando atual,
então a função é avaliada em xk + sk e xk+1 = xk + sk . Se a
redução em f é suficiente, ou apenas positiva e o modelo é
garantido ser FL. A qualidade do modelo é estabelecida no
final da iteração anterior. Se o novo ponto xk + sk é aceito
como iterando, ele é incluido em Yk e removemos y i tal que a
distância ||xk − y i || e o valor |li (xk + sk )| são ambos os
maiores possı́veis. O conflito de escolha entre esses dois
objetivos é alcançado maximizando o valor absoluto ponderado
wi |li (xk + sk )|, onde wi reflete a distância ||xk − y i ||.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Quando o passo sk é rejeitado, o novo ponto xk + sk ainda
pode ser aceito em Yk , removendo o ponto y i tal que o valor
wi |li (xk + sk )| é maximizado, onde wi reflete a distância
||xk − y i ||, contanto que |li (xk + sk )| > 1 ou ||xk − y i || > r ∆k .
Se a melhoria da função objetivo não é suficiente e acredita-se
necessária a melhoria do modelo, então o algoritmo escolhe um
ponto em Yk o mais distante de xk e tenta trocá-lo por um
ponto que maximiza o polinômio de Lagrange correspondente
na região de confiança.
Para a convergência global precisamos de um passo crı́tico, onde
podemos construir um modelo FL. O analogo desse passo para Powell
está relacionado em melhorar a geometria, onde o passo sk é muito
menor que ∆k , que ocorre quando o gradiente do modelo é pequeno
relativo a Hessiana. Agora apresentaremos o algoritmo modificado.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Algoritmo 11.2:Baseado na mı́nima norma de Frobenius de
polin^
omios de Lagrange
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Algoritmo 11.2:Baseado na mı́nima norma de Frobenius de
polin^
omios de Lagrange
P0(inı́cio) Selecione p1 ∈ [n + 2, (n + 1)(n + 2)/2]. Escolha um valor
inicial x0 , um raio máximo ∆max > 0 e um raio inicial
∆0 ∈ (0, ∆max ]. Escolha um fator raio para a região de
confiança r ≥ 1. Escolha um conjunto bem posicionado
Y0 de cardinalidade p1 . Calcule o mı́nimo da norma de
Frobenius dos polinômios de Lagrange li (x), i = 0, ..., p,,
associado a Y0 e o correspondente modelo quadrático m0 .
Escolha um valor limite positivo,
Λ > max{|li (x)| : i = 0, ..., p, x ∈ B(x0 ; ∆0 )}. As
constantes η1 , γ, γinc , τ , εc , β e µ são escolhidas tal que
η1 , γ ∈ (0, 1), γinc > 1, 0 < τ < 1, εc > 0 e µ > β > 0.
Ponha k = 0.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
P1(passo crı́tico) Esse passo é como no algoritmo 10.1. Note que mk ,
Yk e ∆k podem mudar no curso desse passo.
P2(cálculo do passo) Esse passo é como no algoritmo 10.1.
P3(Aceitação do ponto) Se ||sk || ≥ τ max{||y i − xk ||}, então calcule y i ,
onde i ∈ arg maxj {wj |li (xk + sk )| : y j ∈ Yk } e wj > 0 é
um peso para dar preferência a pontos que estão mais
longe de xk . Calcule f (xk + sk ) e defina
ρk =
f (xk ) − f (xk + sk )
mk (xk ) − mk (xk + sk )
Se ρk ≥ η1 ou ρk > 0 e mk é CFL, então ponha
xk+1 = xk + sk . Inclua xk + sk na amostra Yk+1 tracando
por y i . Caso contrário, xk+1 = xk . E se ||y i − xk || > r ∆k
ou |li (xk + sk )|, então aceitamos xk + sk na amostra Yk+1
tracando por y i .
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
P5(atualização do raio) Esse passo é como no algoritmo 10.1. Atualize o
modelo mk para obter mk+1 e recalcule o mı́nimo da
norma de Frobenius dos polinômios de Lagrange. Faça
k ← k + 1 e vá para o passo 1.
Comentários do algoritmo.
O passo para atualizar o conjunto de interpolação descrito acima é
totalmente suficiente para garantir que modelos FL possam ser
construı́dos em um número finito e uniformemente limitado de
passos, como pede a analise de convergência do capı́tulo 10.
No algoritmo de Powell, não há checagem explı́cita que
|li (y∗i )| > Λ > 1; ao invés disso o passo para melhorar o modelo é
muito mais complexo; mas ele está destinado a trocar pontos de
interpolação velhos por pontos dentro da região de confiança que
fornecem valores grandes
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
para os polinômios de Lagrange correspondentes.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
para os polinômios de Lagrange correspondentes.
No método original de Powell um passo de decréscimo simples é
sempre aceito como novo iterando. Porém nós permitimos isso
somente se conseguimos garantir que a amostra Yk sobre qual foi
construido o modelo mk é Λ − posicionada em B(xk ; ∆k ).
Embora não garantido, é esperado que o conjunto de interpolação
permaneça bem posicionado por todo o algoritmo enquanto ele está
na bola B(xk ; r ∆k ). Na prática podemos começar com um conjunto
de interpolação bem posicionado simples, tal qual o usado por
Powell:
Y0 = {x0 , x0 + ∆e1 , ..., x0 + ∆en , x0 − ∆e1 , ..., x0 − ∆en }
A vantagem deste conjunto é que devido a sua estrutura especial ele
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
toma O(n2 ) operações para construir o conjunto inicial da mı́nima
norma de Frobenius dos polinômios de Lagrange.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método de Powell
toma O(n2 ) operações para construir o conjunto inicial da mı́nima
norma de Frobenius dos polinômios de Lagrange.
Método Wedge
Os métodos considerados neste capı́tulo estão relacionados com a
geração de dois tipos de pontos, aqueles que estão destinados a
reduzir o valor da função objetivo e aqueles destinados a melhorar o
posicionamento dos pontos. É possı́vel gerar uma única espécie de
pontos alcançando ambos os objetivos.
Um algoritmo que segue esta idéia foi proposto por Mazzari e
Nocedal. Este algoritmo tenta gerar pontos que fornecem
simultâneamente decréscimo suficiente para o modelo e satisfaz
condições de Λ − posicionamento.
Em qualquer iteração, o subproblema de minimização é aumentado
por uma restrição adicional que não permite que o novo ponto
esteja próximo a uma certa variedade.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Esta variedade é um subconjunto amostral fixado para uma dada
iteração e faz com que todos os conjuntos possı́velmente não
posicionados contenham o subconjunto amostral fixado.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Esta variedade é um subconjunto amostral fixado para uma dada
iteração e faz com que todos os conjuntos possı́velmente não
posicionados contenham o subconjunto amostral fixado.
Antes que o passo da região de confiança seja feito, nós precisamos
identificar quais pontos de Yk serão trocados com novo ponto. Note
que os outros dois primeiros métodos fazem o passo na região de
confiança e depois decidem quais pontos serão trocados com o novo
ponto. Para escolher os pontos de Yk usaremos o seguinte
algoritmo.
Algoritmo 11.3: Seleção de um ponto para deixar deixar Yk
(inicio) Desloque e escale Yk e considere o novo
Ŷk = {(y i − xk )/∆k , i = 0, . . . , p}. Ponha
ui (x) = φ̄i (x), i = 0, . . . , p. Escolha ξ > 0 e r ≥ 1.
Assuma que Ŷk comtêm p1 pontos posicionados.
Faça ik = p. Para i = 0, . . . , p − 1
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
1. Seleção do ponto: Encontre ji = arg maxj∈{i,...,p}:||ŷ j ||≤r |ui (ŷ j )|.
2. Aceitação do ponto: Se |ui (ŷ j )| < ξ, então ik = i e paramos. Caso
contrário, trocamos os pontos ŷ i e ŷ ji no conjunto Ŷk .
3. Eliminação de Gauss: Para j = i + 1, . . . , p
uj (x) ← uj (x) −
uj (ŷ i )
ui (x).
ui (ŷ i )
A proposta desse algoritmo é identificar pontos que possam ser
trocados, ou porque estão muito longe do iterando atual ou porque
trocando-os podemos melhorar o posicionamento de Ŷk . Assim que
tal ponto ŷ ik é identificado e os polinômios pivôs são calculados, o
seguinte problema é resolvido para produzir um passo na região de
confiança:
min
s∈Rn
mk (x) + gkT s + 12 s T Hk s
||s|| ≤ ∆k ,
|uik (s/∆k ) | ≥ ξ.
Fabio Antonio Araujo de Campos
(1)
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
O problema acima é factı́vel para ξ bastante pequeno; assim uma
solução ótima existe. Porém estamos interessados nas soluções que
satisfaçam a fração do decréscimo de Cauchy. Nós mostraremos que
tais soluções também existem para ξ muito pequeno. Além disso a
aproximação desta solução pode ser encontrada, talvez com um
grande esforço computacional, porém sem qualquer avaliação de
função.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Principais caracterı́sticas do método.
1. O algoritmo original usa exatamente n + 1 pontos no caso
linear e (n + 1)(n + 2)/2 pontos no caso quadrático. É
possı́vel estender isso para usar modelos com a mı́nima
norma de Frobenius.
2. Ao contrário dos dois métodos anteriores, o ponto que irá
deixar o conjunto Yk será escolhido antes do passo de
minimização da região de confiança.
3. O algoritmo apresentado aqui tenta manter um conjunto
amostral Λ − posicionado enquanto os pontos estão em
B(xk ; r ∆k ), com r ≥ 1. Devido ao uso do algoritmo 11.3,
nós assumimos que o subproblema da região de confiança
pode ser resolvido depois de um número finito de
iterações. O algoritmo Wedge original não emprega o
algoritmo 11.3; ele simplesmente seleciona os pontos que
estão mais distantes do iterando atual.
4.Fabio
Não
há Araujo
tentativa
direta Métodos
de melhorar
a geometria
Antonio
de Campos
baseados em
interpolaçãoem do
região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
4. Não há tentativa direta de melhorar a geometria do
conjunto, mas há um caminho heurı́stico para atualização
que balança entre pedir posicionamento da amostra e
pedir fração de redução suficiente do modelo.
5. Se ik produzido pelo algoritmo é menor que p então,
depois do passo na região de confiança o conjunto Yk
pode não ser Λ − posicionado em B(xk ; ∆k ). Entretanto
se a faixa do subproblema de região de confiança é
resolvido com sucesso, então xk e ∆k não mudaram,
então na próxima iteração ik é aumentado em uma
unidade. Assim, ou o passo na região de confiança é
alcançado com sucesso ou ik = p.
6. O passo crı́tico é crucial para convergência do método,
assim como foi nos algoritmos anteriores. O passo de
criticalidade precisa gerar modelos FL/FQ em uma bola
suficientemente pequena em torno do iterando atual. É
possı́vel construir tal conjunto resolvendo repetidamente o
problema (1).
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Algoritmo 11.4: Wedge modificado.
P0(inı́cio) Escolha um ponto inicial x0 , um raio máximo ∆max > 0 e
um raio inicial para a região de confiança ∆0 ∈ (0, ∆max ].
Escolha um conjunto Y0 e calcule um modelo inicial
m0 (x). As constantes η1 , γ, γinc , 0 , β e µ são dadas e
satisfazem as condições η1 ∈ (0, 1), 0 < γ < 1 < γinc ,
c > 0 e µ > β > 0. Escolha um limite pivô positivo ξ0 ,
um coeficiente do decréscimo de Cauchy 0 < κfcd < 1 e
um fator raio r ≥ 1 para a região de confiança. Faça
k = 0.
P1(passo crı́tico) Esse passo é como no algoritmo 10.1(note que mk , Yk
e ∆k pode mudar durante o curso desse passo).
P2(cálculo do passo) Aplicando o algoritmo 11.3 em Yk para selecionar
o polinômio pivô uik (x). Resolva o problema de
minimização para obter sk .
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
P3(gestão da faixa) Checar se a nova solução satisfaz a fração de
decréscimo de Cauchy:
mk (xk ) − mk (xk + sk ) ≥
||gk ||
κfcd
||gk || min{
, 1}
2
||Hk ||
Se satisfaz, então y ik = xk + sk e vamos para o próximo
passo. Caso contrário, a restrição wedge é relaxada
fazendo ξk ← ξk /2 e retornamos ao passo 2.
P4(Aceitação do ponto) Calcule f (xk + sk ) e defina
ρk =
f (xk ) − f (xk + sk )
.
mk (xk ) − mk (xk + sk )
Se ρk ≥ η1 ou se ρk > 0 e Y ⊂ B(xk ; r ∆k ), então
xk+1 = xk + sk . Caso contrário xk+1 = xk .
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
P5(Atualização do raio) Esse passo é como no algoritmo 10.1. Atualize
o modelo mk baseado no novo conjunto amostral Yk .
Faça k ← k + 1 e vá para o passo 1.
Notas do algoritmo
O esforço computacional por iteração do algoritmo Wedge no passo
2, é de O(p 3 ). Resolver o subproblema Wedge pode ser caro, o que
forçou Mazzari e Nocedal a mostrar resultados computacionais
comparando a outros métodos. Porém os resultados não são muito
vantajosos.
Há vários caminhos para se melhorar o algoritmo Wedge. Podemos
trocar vários pontos de Yk e resolver várias instâncias do
subproblema Wedge de região de confiança para obter um bom
equilı́brio entre geometria e decrescimento do modelo. O custo por
iteração pode aumentar, porém o número total de iterações poderá
diminuir resultando em menos avaliações de função.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Validade do algoritmo Wedge para o caso de primeira ordem.
Para mostrarmos convergência a pontos estacionários de primeira
ordem, basta mostrarmos que um modelo FL pode ser alcançado em
um número finito e uniformemente de iterações mal sucedidas.
Lembrando que v , o vetor dos coeficiêntes (com respeito a base
natural φ̂) dos polinômios ui (x) que são calculados durante o
cálculo do pivô. Sabemos que ||v ||∞ ≤ 1. Em geral sabemos que
para qualquer 0 < ξ < 1/4 existe ŝk tal que ||ŝk || ≤ 1 e que
|v T sˆk | ≥ ξ(Lemas 3.10 e 3.12).
Queremos mostrar que existe ξ > 0 tal que para todas as iterações é
possı́vel achar um passo sk que satisfaça simultâneamente as
seguintes condições:
1. ||sk || ≤ ∆k ,
2. sk gera pelo menos uma fração fixa do decréscimo de
Cauchy no modelo.
3. |v T φ̂(sk /∆k )| ≥ ξ.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Disso segue que o modelo pode ser feito FL ou FQ, pelo método
Wedge depois de um número finito, uniformemente limitado de
iterações mal sucedidas.
Considere o problema sem escala, indexado por ”u”.
min
c + guT su + 12 suT Hu su = mu (su )
s.a.
||su || ≤ ∆.
su ∈Rn
Se nós escalarmos a região de confiança para raio 1, teremos
s∈Rn
min
c + g T s + 12 s T Hs = m(s)
s.a.
||s|| ≤ 1.
onde s = su /∆, g = ∆gu e H = ∆2 Hu .
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Queremos mostrar que existe uma solução aproximada para o
problema
min
m(s)
s∈Rn
||s|| ≤ 1,
s.a.
|φ(s)T v | ≥ ξ > 0,
(2)
que produz um decréscimo sobre m(s) tão bom quanto o decréscimo
obtido por uma fração fixada no passo de Cauchy. O valor de ξ
ainda não foi determinado, mas precisa ser limitado, distante de
zero, para todo dado considerado no problema(v , g e H).
Mas antes vamos considerar o seguinte problema:
maxn
|φ(s)T v |
s.a.
||s|| ≤ 1,
s∈R
m(0) − m(s) ≥
Fabio Antonio Araujo de Campos
κfcd
2
||g ||
||g || min{ ||H||
, 1}.
(3)
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Se nós mostrarmos que o valor ótimo desse problema está sempre
acima de um limitante positivo ξ∗ > 0, para todo v tal que
||v ||∞ ≥ 1, para todo vetor g e matriz simétrica H, então
mostramos que existe uma solução aproximada para o problema (2).
Para isto precisamos mostrar que o polinômio |φ(s)T v | não se anula
em um conjunto factı́vel do problema (3). A dificuldade está onde
||g ||
||H|| → 0, o conjunto factı́vel de (3) pode convergir para um ponto
singular, sobre qual escolhendo um polinômio adequado pode se
anular. Mostraremos que durante o algoritmo Wedge sempre se
verifica 0 < gmin < ||g ||/||H||, onde gmin ∈ (0, 1) é uma constante
fixa.
Como g = gu ∆ e H = Hu ∆2 temos
||g ||
||gu ||
=
||H||
∆||Hu ||
Além disso temos que ||H|| ≤ κbhm e ∆ ≤ ∆max . E como o passo
de criticalidade será resolvido em alguma hora, do passo 2 temos
que ||gu || ≥ min{c , µ−1 ∆}.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Então
||gu ||
||g ||
=
≥ gmin
||H||
∆||Hu ||
onde
gmin = min{
c
1
,
} (4)
∆max κbhm µκbhm
Mostraremos agora que é possı́vel uma boa geometria
simultâneamente com uma fração do decréscimo de Cauchy.
Teorema
Seja gmin ∈ (0, 1) uma constante dada. Existe uma constante positiva ξ∗
dependendo de gmin e κfcd tal que o valor ótimo de 11.4 satisfaz
ξ(v ; g , H) ≥ ξ∗ > 0
para todo vetor v ∈ Rp tal que ||v ||∞ ≥ 1 e para todo vetor g ∈ Rn e
matriz simétrica H ∈ Rn×n tal que
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
gmin ≤
||g ||
||H||
Dem:
Vamos definir
a(v ; g , H) = max{|φ(s)T v | : ||s|| ≤ 1, m(0) − m(s) ≥
κfcd
||g ||}
2
onde ||g || ≥ ||H|| e
b(v ; g , H) = max{|φ(s)T v | : ||s|| ≤ 1, m(0) − m(s) ≥
κfcd ||g ||2
}
2 ||H||
onde gmin ||H|| ≤ ||g || ≤ ||H||. O valor ótimo de (3) é dado por

a(v ; g , H) onde ||g || ≥ ||H||,

ξ(v ; g , H) =

b(v ; g , H) onde gmin ||H|| ≤ ||g || ≤ ||H||.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Nós provaremos que o seguinte mı́nimo é atingido
min
(v ;g ,,H):||v ||∞ ≥1,||g ||≥||H||
a(v ; g , H) > 0.
Fazendo g 0 = g /||g || e H 0 = H/||g || o problema é equivalente a
minimizar
κfcd
1
}.
a0 (v ; g 0 , H 0 ) = max{|φ(s)T v | : ||s|| ≤ 1, −g 0T s − s T H 0 s ≥
2
2
Desde que −s T H 0 s ≥ −||s||2 onde ||H 0 || ≤ 1 e κfcd < 1, é sempre
possı́vel para g 0 e H 0 tal que ||g 0 || = 1 e H 0 ≤ 1, encontrar s que
satisfaça as duas restrições de a0 (v ; g 0 , H 0 ) estritamente.
Logo existe ra∗ tal que o conjunto factı́vel que define a0 (v ; g 0 , H 0 )
sempre contem B(x; ra∗ ) para x ∈ B(0; 1).
Usando o fato que ψ(s) = maxs∈B(x;ra∗ ) |v T φ(s)| é uma norma em
espaço de dimensão finita, temos que existe ξa∗ > 0 tal que
min
max |v T φ(s)| ≥ ξ∗a isto é, a0 (v ; g 0 , H) ≥ ξ∗a
x∈B(0;1) s∈B(x;ra∗ )
para qualquer v , g 0 e H 0 tal que ||v ||∞ ≥ 1, ||g 0 || e ||H 0 || ≤ 1.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Analogamente mostramos que existe ξ∗b tal que b(v ; g 0 , H 0 ) ≥ ξ∗b
para v , g 0 e H 0 tal que ||v ||∞ ≥ 1, gmin ≤ ||g 0 || ≤ 1 e ||H 0 || = 1.
Então tomamos ξ∗ tal que
ξ∗ = min{ξ∗a , ξ∗b }
Validade do algoritmo Wedge para o caso de segunda ordem.
Para pontos crı́ticos de seguda ordem precisamos pedir mais que uma
fração do decréscimo de Cauchy. Precisamos pedir uma fração do
decréscimo do autopasso. Então nosso problema agora fica
maxn
|φ(s)T v |
s.a.
||s|| ≤ 1,
s∈R
m(0) − m(s) ≥
m(0) − m(s) ≥
Fabio Antonio Araujo de Campos
κfcd
2
κfed
2
||g ||
||g || min{ ||H||
, 1}
max{−λmin (H), 0},
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
com κfcd , κfed ∈ (0, 1).
Teorema
Seja σmin ∈ (0, 1) dado por uma constante. Existe uma constante positiva
ξ∗ dependendo de σmin , κfcd e κfed tal que o valor ótimo de 11.7 satisfaz
ξ(v ; g , H) ≥ ξ∗ > 0
para todo vetor v ∈ Rp tal que ||v ||∞ ≥ 1 e para todo vetor g ∈ Rn e
matriz siméttrica H ∈ Rn×n tal que
σmin ≤ max{
||g || −λmin (H)
,
}.
||H||
||H||
Porém esse resultado não é suficiente, ao contrário do caso de
primeira ordem, pois não temos garantia de que σmin exista.
No caso de segunda ordem o passo de criticalidade temos
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Método Wedge
max{
||g || 1 −λmin (H)
σum
c
1
,
}=
≥ min{
,
}.
||H|| ∆ ||H||
∆||Hu ||
∆max κbhm µκbhm
A limitação do lado esquerdo da equação acima envolvendo ∆ não
implica a limitação de max{||g ||/||H||, −λmin (H)/||H||}, que é o
que nós precisamos.Note que para ∆ pequeno pode acontecer que
||g ||/||H|| e o autovalor mais negativo de H/||H|| aproximem-se de
zero. Assim, pode ser que a parte da região de confiança onde a
fração do autopasso decresce pode encolher para uma região de
interior vazio. Isso sigifica que o polinômio se anula em tal região,
assim, não há limitante sobre o valor do pivô que possa garantir ser
realizável. Portanto nenhum passo é calculado no passo 2 do
algoritmo 11.4 para que o decréscimo do autopasso seja atingido.
Notas e referências
O algoritmo DFO foi implementado por Sceinberg como um pacote
de fonte aberta.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Consideraç~
oes finais.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.
Consideraç~
oes finais.
Os UOBYQA e NEWUOA são as implementações feitas por Powell
e são distribuı́das por ele.
O método Wedge foi implementado por Mazari no Matlab, para
livre download.
Fasano, Morales e Nocedal estudam o comportamento dos
algoritmos baseados em interpolação de região de confiança onde a
geometria dos pontos é ignorada. Eles possuem bons resultados
numericos comparado ao NEWUOA. Esta área hoje ainda está
muito ativa.
Fabio Antonio Araujo de Campos
Métodos baseados em interpolaçãoem região de confiança.