Métodos baseados em interpolação em região de confiança. Fabio Antonio Araujo de Campos 30 de abril de 2010 Tópicos em otimização-MT853 Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Estruturaç~ ao Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Estruturaç~ ao 1- Algumas consideraç~ oes sobre os métodos apresentados. 2- Aproximaç~ ao "DFO". 3- Método de Powell. 4- Método Wedge. 5- Converg^ encia do algoritmo Wedge para pontos estacionários de primeira ordem. 6- Converg^ encia do algoritmo Wedge para pontos estácionários de segunda ordem. 7- Consideraç~ oes finais. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Caracterı́sticas dos métodos Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Caracterı́sticas dos métodos Quantos pontos podem ser incluı́dos na amostra? Um modelo quadrático é desejável, mas a determinação completa de um modelo quadrático baseado em interpolção polinomial pede (n + 1)(n + 2)/2 avaliações de funções. Pode ser muito caro, pedir tal precisão em cada passo; assim pode ser desejável construir modelos baseados em poucos pontos de interpolação(veja cap. 5). O número de pontos na amostra é estático por todo o algoritmo ou pode ser din^ amico? O algoritmo ”DFO”permite um número de pontos dinâmico, já o algoritmo do método de Powell pede uma amostra que tenha exatamente p1 ∈ [n + 2, (n + 1)(n + 2)/2] em todas as iterações. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Caracterı́sticas dos métodos Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Caracterı́sticas dos métodos A amostra precisa ser Λ − posicionado em B(xk ; ∆k ) em cada iteraç~ ao? E sen~ ao, como essa condiç~ ao pode ser relaxada? Para conseguirmos Λ − posicionamento, precisamos desenvolver um critério para aceitar pontos na amostra. Esse critério, em geral, é baseado em um valor limite. Que valor limite podemos escolher e como melhorá-lo se ele for escolhido mal? Se os valores limitantes forem escolhidos muito estritos pode acontecer de não encontrarmos pontos adequados na amostra,e se o limitante é escolhido muito folgado podemos ter um conjunto mal posicionado. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Caracterı́sticas dos métodos Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Caracterı́sticas dos métodos A amostra sempre estará 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 confiança é reduzido. Assim a exig^ encia do conjunto amostral estar dentro da regi~ ao de confiança pode ser relaxado em um algoritmo prá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 decréscimo é alcançado e o modelo é suficientemente bom. Os algoritmos aqui descritos estar~ ao baseados no decréscimo simples. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO A aproximaç~ ao "DFO". Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO A aproximaç~ 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 critério para verificar o Λ − posicionamento. Em outra palavras o número de pontos amostrais é din^ amico. O modelo é o da interpolaç~ ao quadrática da mı́nima norma de Frobenius. O conjunto amostral é 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 prático pois permite que pontos amostrais permaneçam no conjunto amostral atual por poucas Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO iterações subsequentes, sempre que o iterando atual é movido ou o raio da região de confiança é reduzido. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO iterações subsequentes, sempre que o iterando atual é movido ou o raio da região de confiança é reduzido. O algoritmo original usa os NFPs para manter o conjunto amostral Λ − posicionado. Mas o algoritmo para melhoria do modelo usado, é muito semelhante ao algoritmo de pivoteamento. E usaremos este algoritmo, para discutir a convergência global do método. Em cada iteração o algoritmo ”DFO”atualiza o conjunto amostral Yk baseado no algoritmo pivotal. No começo do algoritmo dois valores iniciais são selecionados: 0 < ξacc < 1/4 para aceitação de um ponto no conjunto de interpolação e ξimp > 1 para melhorar o conjunto de interpolação atual. A região em que o polinômio pivô é otimizado é uma bola centrada no iterando atual de raio ∆k . Dado qualquer conjunto de interpolação contendo o iterando atual xk , o algoritmo pode designar o iterando atual como primeiro pivô e selecionar os pontos restantes tal que o Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO conjunto resultante seja Λ − posicionado. Logo o iterando atual sempre estará em um conjunto bem posicionado. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO conjunto resultante seja Λ − posicionado. Logo o iterando atual sempre estará em um conjunto bem posicionado. Considere o ponto amostral xk + sk gerado durante o passo de minimização na região de confiança. Se o ponto gera um decréscimo da função objetivo, então ele será o novo iterando. O centro da região de confiança é movido e o algoritmo 6.5 é aplicado para todos os pontos amostrais que estão na bola de raio r ∆k centrado em xk + sk . Esse procedimento ou selecionará um conjunto bem posicionado, ou irá parar por falta de pontos amostrais adequados. Se o ponto xk + sk não gera um decréscimo na função objetivo, podemos ainda querer adicioná-lo no conjunto amostral, trazendo assim informação nova. Além disso o custo de avaliar a função nesse ponto já foi feito, então adicionamos xk + sk em Yk e aplicamos o algoritmo 6.5. No final, os pontos de Yk que não são usados são descartados. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Quando um passo de melhoria do modelo é desejado, depois que um passo na região de confiança tenha sido calculado, o novo ponto é calculado apenas com a idéia do posicionamento da amostra em mente. Se o conjunto de interpolação Yk não está completo, então aplicamos um passo do algoritmo 6.4 para maximizar o valor absoluto do polinômio pivô e aumentar em um elemento o tamanho do conjunto de interpolação. Caso contrário nós aplicamos um passo do algoritmo 6.6 para trocar um ponto de Yk . A troca é aceitável se o valor do último polinômio pivô é aumentada em pelo menos um fator de ξimp . Caso contrário, consideramos que o passo de melhoria do modelo falhou. O algoritmo pivotal assume que o conjunto de pontos de interpolação é sempre deslocado e escalado para uma bola de raio 1 e centro na origem. Porém na prática basta deslocar e escalar uma única vez. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Agora apresentaremos o algoritmo ”DFO”modificado, para ambas as situações onde gostarı́amos de atingir convergência global para pontos estacionários de primeira ordem ou pontos estacionários de segunda ordem. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Agora apresentaremos o algoritmo ”DFO”modificado, para ambas as situações onde gostarı́amos de atingir convergência global para pontos estacionários de primeira ordem ou pontos estacionários de segunda ordem. Algoritmo 11.1: DFO modificado. Passo 0(inicialização) Escolha um ponto inicial x0 , um raio máximo ∆max > 0 e um raio inicial para a região de confiança ∆0 ∈ (0, ∆max ]. Escolha o conjunto Y0 e calcule o modelo inicial m0 (x). As constantes η1 , γ, γinc , εc , β e µ são escolhidas tal que η1 , γ ∈ (0, 1), γinc > 1, εc > 0 e µ > β > 0. Escolha os limites pivôs positivos ξacc e ξimp e o fator raio da região de confiança r ≥ 1. Ponha k = 0. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO P1(passo crı́tico) Esse passo é 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(Cálculo do passo) Esse passo é como no algoritmo 10.1 ou 10.3. P3(aceitação do ponto) Checar se mk (x) é CFL ou CFQ, que significa garantir que se Yk conté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 é CFL ou CFQ, então xk+1 = xk + sk . Caso contrário o iterando e o modelo nã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 Métodos baseados em interpolaçãoem região de confiança. Algoritmo 10.1,10.2 Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Algoritmo 10.1,10.2 P1(passo crı́tico): Se ||gkicb || > c , então mk = mkicb e ∆k = ∆icb k . Se ||gkicb || ≤ c , então o procedimento segue. Chamamos o algoritmo de melhoramento do modelo para tentar certificar se o modelo mk é FL sobre B(xk ; ∆icb k ). Se pelo menos uma das condições se verificam, O modelo mkicb não é CFL sobre B(xk ; ∆icb k ), icb ∆icb > µ||g ||, k k então aplicamos o algoritmo 10.2(descrito abaixo) para construir o modelo m̃k (xk + sk ), que é 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 contrário, coloque mk = mkicb e ∆k = ∆icb k . Cá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 Métodos baseados em interpolaçãoem região de confiança. Algoritmo 10.1,10.2 Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Algoritmo 10.1,10.2 P5(Atualização do raio da região de confiança): Ponha [∆k , min{γinc ∆k , ∆max }] se ρk ≥ η1 , {γ∆k } se ρk < η1 é FL ∆icb ∈ k+1 {∆k } se ρk < η1 e mk não é CFL Algoritmo 10.2(Passo crı́tico) Esse algoritmo é aplicado somente se ||gkicb || ≤ c e pelo menos um dos seguintes fatos se verificam: o modelo mkicb não é CFL sobre B(xk ; ∆icb k ) icb ou ∆icb > µ||g ||. A constante w ∈ (0, 1) é 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 até 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 ˜ Até ∆k ≤ µ||g ||. k Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO P4(melhoramento do modelo) Se ρk < η1 então tentamos melhorar o modelo. Defina os novos mk e Yk . P5(Atualização o raio) Esse passo é como no algoritmo 10.1 ou 10.3. Faça k ← k + 1 e vá para o passo 1. Notas do algoritmo. Devido aos algoritmos 6.4, 6.5 e 6.6 o conjunto Yk contêm somente pontos gerados por valores pivôs aceitos por estes algoritmos. A cada iteração somente um ou dois novos pontos são gerados. O algoritmo é muito flexı́vel quanto ao número de pontos usados. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. DFO O principal esforço computacional está em calcular os polinômios pivôs. Geralmente são usados pontos da ordem n2 , então o algoritmo pivotal pode pedir operações da ordem de n6 . Para valores pequenos de n este esforço pode ser pequeno, perto do preço para se avaliar uma função. Para valores grandes de n faz sentido nos restringirmos a um número de pontos de ordem n para os modelos. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Método de Powell Aqui vamos desenvolver uma modificação do algoritmo de Powell. Nós vamos combinar as bem sucedidas caracterı́sticas práticas do algoritmo de Powell com a estrutura do cap 10. A maneira com que Powell trabalha na região de confiança não é a mesma desse livro. Para começar o raio da região de confiança e o raio do conjunto de interpolação não são os mesmos. De fato a maneira que Powell trabalha é muito mais complicada que a tratada aqui. O menor dos raios é usado para forçar os pontos de interpolação estejam suficientemente longes para evitar o ruı́do nos valores da função. O passo para atualizar a região de confiança é muito mais complicado. Tudo para melhorar a performance prática do algoritmo. Nosso método de Powell usará mı́nima norma de Frobenius dos Polinômios de Lagrange. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Agora comentaremos algumas caracterı́sticas: Todas as amostras em todas as iterações contém p1 ∈ [n + 2, (n + 1)(n + 2)/2] pontos. o valor p1 = 2n + 1 é uma escolha natural e é valor padrão no NEWUOA. Os modelos são modelos de interpolação quadrática com remanescentes graus de liberdade tomados pela minimização da norma de Frobenius. O conjunto amostral é mantido baseado no algoritmo 6.3 modificado para lidar com o mı́nimo da norma de Frobenius de polinômios de Lagrange. Não é preciso envolver escalamento, pois polinômios de Lagrange são escalados automaticamente. Deslocamentos também não causam efeito. Entretanto, deslocar os pontos com respeito ao centro atual da região de confiança tem um efeito importante sobre a precisão numérica. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell a atualização da amostra no algoritmo de Powell original é realizado da seguinte forma: O conjunto de mı́nima norma de Frobenius de polinômios de Lagrange li (x), i = 0, 1, 2, ..., p,, é mantido em todas as iterações. Se a minimização da região de confiança da k-ésima iteração gera um passo sk , que não é pequeno comparado ao máximo da distância entre os pontos amostrais e o iterando atual, então a função é avaliada em xk + sk e xk+1 = xk + sk . Se a redução em f é suficiente, ou apenas positiva e o modelo é garantido ser FL. A qualidade do modelo é estabelecida no final da iteração anterior. Se o novo ponto xk + sk é aceito como iterando, ele é incluido em Yk e removemos y i tal que a distância ||xk − y i || e o valor |li (xk + sk )| são ambos os maiores possı́veis. O conflito de escolha entre esses dois objetivos é alcançado maximizando o valor absoluto ponderado wi |li (xk + sk )|, onde wi reflete a distância ||xk − y i ||. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Quando o passo sk é 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 )| é maximizado, onde wi reflete a distância ||xk − y i ||, contanto que |li (xk + sk )| > 1 ou ||xk − y i || > r ∆k . Se a melhoria da função objetivo não é suficiente e acredita-se necessária a melhoria do modelo, então o algoritmo escolhe um ponto em Yk o mais distante de xk e tenta trocá-lo por um ponto que maximiza o polinômio de Lagrange correspondente na região de confiança. Para a convergência global precisamos de um passo crı́tico, onde podemos construir um modelo FL. O analogo desse passo para Powell está relacionado em melhorar a geometria, onde o passo sk é muito menor que ∆k , que ocorre quando o gradiente do modelo é pequeno relativo a Hessiana. Agora apresentaremos o algoritmo modificado. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Algoritmo 11.2:Baseado na mı́nima norma de Frobenius de polin^ omios de Lagrange Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Mé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 máximo ∆max > 0 e um raio inicial ∆0 ∈ (0, ∆max ]. Escolha um fator raio para a região de confiança r ≥ 1. Escolha um conjunto bem posicionado Y0 de cardinalidade p1 . Calcule o mı́nimo da norma de Frobenius dos polinômios de Lagrange li (x), i = 0, ..., p,, associado a Y0 e o correspondente modelo quadrático m0 . Escolha um valor limite positivo, Λ > max{|li (x)| : i = 0, ..., p, x ∈ B(x0 ; ∆0 )}. As constantes η1 , γ, γinc , τ , εc , β e µ são escolhidas tal que η1 , γ ∈ (0, 1), γinc > 1, 0 < τ < 1, εc > 0 e µ > β > 0. Ponha k = 0. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell P1(passo crı́tico) Esse passo é como no algoritmo 10.1. Note que mk , Yk e ∆k podem mudar no curso desse passo. P2(cálculo do passo) Esse passo é como no algoritmo 10.1. P3(Aceitação do ponto) Se ||sk || ≥ τ max{||y i − xk ||}, então calcule y i , onde i ∈ arg maxj {wj |li (xk + sk )| : y j ∈ Yk } e wj > 0 é um peso para dar preferência a pontos que estã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 é CFL, então ponha xk+1 = xk + sk . Inclua xk + sk na amostra Yk+1 tracando por y i . Caso contrário, xk+1 = xk . E se ||y i − xk || > r ∆k ou |li (xk + sk )|, então aceitamos xk + sk na amostra Yk+1 tracando por y i . Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell P5(atualização do raio) Esse passo é como no algoritmo 10.1. Atualize o modelo mk para obter mk+1 e recalcule o mı́nimo da norma de Frobenius dos polinômios de Lagrange. Faça k ← k + 1 e vá para o passo 1. Comentários do algoritmo. O passo para atualizar o conjunto de interpolação descrito acima é totalmente suficiente para garantir que modelos FL possam ser construı́dos em um número finito e uniformemente limitado de passos, como pede a analise de convergência do capı́tulo 10. No algoritmo de Powell, não há checagem explı́cita que |li (y∗i )| > Λ > 1; ao invés disso o passo para melhorar o modelo é muito mais complexo; mas ele está destinado a trocar pontos de interpolação velhos por pontos dentro da região de confiança que fornecem valores grandes Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell para os polinômios de Lagrange correspondentes. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell para os polinômios de Lagrange correspondentes. No método original de Powell um passo de decréscimo simples é sempre aceito como novo iterando. Porém nós permitimos isso somente se conseguimos garantir que a amostra Yk sobre qual foi construido o modelo mk é Λ − posicionada em B(xk ; ∆k ). Embora não garantido, é esperado que o conjunto de interpolação permaneça bem posicionado por todo o algoritmo enquanto ele está na bola B(xk ; r ∆k ). Na prática podemos começar com um conjunto de interpolação bem posicionado simples, tal qual o usado por Powell: Y0 = {x0 , x0 + ∆e1 , ..., x0 + ∆en , x0 − ∆e1 , ..., x0 − ∆en } A vantagem deste conjunto é que devido a sua estrutura especial ele Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell toma O(n2 ) operações para construir o conjunto inicial da mı́nima norma de Frobenius dos polinômios de Lagrange. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método de Powell toma O(n2 ) operações para construir o conjunto inicial da mı́nima norma de Frobenius dos polinômios de Lagrange. Método Wedge Os métodos considerados neste capı́tulo estão relacionados com a geração de dois tipos de pontos, aqueles que estão destinados a reduzir o valor da função objetivo e aqueles destinados a melhorar o posicionamento dos pontos. É possı́vel gerar uma única espécie de pontos alcançando ambos os objetivos. Um algoritmo que segue esta idéia foi proposto por Mazzari e Nocedal. Este algoritmo tenta gerar pontos que fornecem simultâneamente decréscimo suficiente para o modelo e satisfaz condições de Λ − posicionamento. Em qualquer iteração, o subproblema de minimização é aumentado por uma restrição adicional que não permite que o novo ponto esteja próximo a uma certa variedade. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Esta variedade é um subconjunto amostral fixado para uma dada iteração e faz com que todos os conjuntos possı́velmente não posicionados contenham o subconjunto amostral fixado. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Esta variedade é um subconjunto amostral fixado para uma dada iteração e faz com que todos os conjuntos possı́velmente não posicionados contenham o subconjunto amostral fixado. Antes que o passo da região de confiança seja feito, nós precisamos identificar quais pontos de Yk serão trocados com novo ponto. Note que os outros dois primeiros métodos fazem o passo na região de confiança e depois decidem quais pontos serão trocados com o novo ponto. Para escolher os pontos de Yk usaremos o seguinte algoritmo. Algoritmo 11.3: Seleção de um ponto para deixar deixar Yk (inicio) Desloque e escale Yk e considere o novo Ŷk = {(y i − xk )/∆k , i = 0, . . . , p}. Ponha ui (x) = φ̄i (x), i = 0, . . . , p. Escolha ξ > 0 e r ≥ 1. Assuma que Ŷk comtêm p1 pontos posicionados. Faça ik = p. Para i = 0, . . . , p − 1 Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge 1. Seleção do ponto: Encontre ji = arg maxj∈{i,...,p}:||ŷ j ||≤r |ui (ŷ j )|. 2. Aceitação do ponto: Se |ui (ŷ j )| < ξ, então ik = i e paramos. Caso contrário, trocamos os pontos ŷ i e ŷ ji no conjunto Ŷk . 3. Eliminação de Gauss: Para j = i + 1, . . . , p uj (x) ← uj (x) − uj (ŷ i ) ui (x). ui (ŷ i ) A proposta desse algoritmo é identificar pontos que possam ser trocados, ou porque estão muito longe do iterando atual ou porque trocando-os podemos melhorar o posicionamento de Ŷk . Assim que tal ponto ŷ ik é identificado e os polinômios pivôs são calculados, o seguinte problema é resolvido para produzir um passo na região de confiança: min s∈Rn mk (x) + gkT s + 12 s T Hk s ||s|| ≤ ∆k , |uik (s/∆k ) | ≥ ξ. Fabio Antonio Araujo de Campos (1) Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge O problema acima é factı́vel para ξ bastante pequeno; assim uma solução ótima existe. Porém estamos interessados nas soluções que satisfaçam a fração do decréscimo de Cauchy. Nós mostraremos que tais soluções também existem para ξ muito pequeno. Além disso a aproximação desta solução pode ser encontrada, talvez com um grande esforço computacional, porém sem qualquer avaliação de função. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Principais caracterı́sticas do método. 1. O algoritmo original usa exatamente n + 1 pontos no caso linear e (n + 1)(n + 2)/2 pontos no caso quadrático. É possı́vel estender isso para usar modelos com a mı́nima norma de Frobenius. 2. Ao contrário dos dois métodos anteriores, o ponto que irá deixar o conjunto Yk será escolhido antes do passo de minimização da região de confiança. 3. O algoritmo apresentado aqui tenta manter um conjunto amostral Λ − posicionado enquanto os pontos estão em B(xk ; r ∆k ), com r ≥ 1. Devido ao uso do algoritmo 11.3, nós assumimos que o subproblema da região de confiança pode ser resolvido depois de um número finito de iterações. O algoritmo Wedge original não emprega o algoritmo 11.3; ele simplesmente seleciona os pontos que estão mais distantes do iterando atual. 4.Fabio Não há Araujo tentativa direta Métodos de melhorar a geometria Antonio de Campos baseados em interpolaçãoem do região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge 4. Não há tentativa direta de melhorar a geometria do conjunto, mas há um caminho heurı́stico para atualização que balança entre pedir posicionamento da amostra e pedir fração de redução suficiente do modelo. 5. Se ik produzido pelo algoritmo é menor que p então, depois do passo na região de confiança o conjunto Yk pode não ser Λ − posicionado em B(xk ; ∆k ). Entretanto se a faixa do subproblema de região de confiança é resolvido com sucesso, então xk e ∆k não mudaram, então na próxima iteração ik é aumentado em uma unidade. Assim, ou o passo na região de confiança é alcançado com sucesso ou ik = p. 6. O passo crı́tico é crucial para convergência do mé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. É possı́vel construir tal conjunto resolvendo repetidamente o problema (1). Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Algoritmo 11.4: Wedge modificado. P0(inı́cio) Escolha um ponto inicial x0 , um raio máximo ∆max > 0 e um raio inicial para a região de confiança ∆0 ∈ (0, ∆max ]. Escolha um conjunto Y0 e calcule um modelo inicial m0 (x). As constantes η1 , γ, γinc , 0 , β e µ são dadas e satisfazem as condições η1 ∈ (0, 1), 0 < γ < 1 < γinc , c > 0 e µ > β > 0. Escolha um limite pivô positivo ξ0 , um coeficiente do decréscimo de Cauchy 0 < κfcd < 1 e um fator raio r ≥ 1 para a região de confiança. Faça k = 0. P1(passo crı́tico) Esse passo é como no algoritmo 10.1(note que mk , Yk e ∆k pode mudar durante o curso desse passo). P2(cálculo do passo) Aplicando o algoritmo 11.3 em Yk para selecionar o polinômio pivô uik (x). Resolva o problema de minimização para obter sk . Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge P3(gestão da faixa) Checar se a nova solução satisfaz a fração de decréscimo de Cauchy: mk (xk ) − mk (xk + sk ) ≥ ||gk || κfcd ||gk || min{ , 1} 2 ||Hk || Se satisfaz, então y ik = xk + sk e vamos para o próximo passo. Caso contrário, a restrição wedge é relaxada fazendo ξk ← ξk /2 e retornamos ao passo 2. P4(Aceitaçã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 ), então xk+1 = xk + sk . Caso contrário xk+1 = xk . Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge P5(Atualização do raio) Esse passo é como no algoritmo 10.1. Atualize o modelo mk baseado no novo conjunto amostral Yk . Faça k ← k + 1 e vá para o passo 1. Notas do algoritmo O esforço computacional por iteração do algoritmo Wedge no passo 2, é de O(p 3 ). Resolver o subproblema Wedge pode ser caro, o que forçou Mazzari e Nocedal a mostrar resultados computacionais comparando a outros métodos. Porém os resultados não são muito vantajosos. Há vários caminhos para se melhorar o algoritmo Wedge. Podemos trocar vários pontos de Yk e resolver várias instâncias do subproblema Wedge de região de confiança para obter um bom equilı́brio entre geometria e decrescimento do modelo. O custo por iteração pode aumentar, porém o número total de iterações poderá diminuir resultando em menos avaliações de função. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Validade do algoritmo Wedge para o caso de primeira ordem. Para mostrarmos convergência a pontos estacionários de primeira ordem, basta mostrarmos que um modelo FL pode ser alcançado em um número finito e uniformemente de iterações mal sucedidas. Lembrando que v , o vetor dos coeficiêntes (com respeito a base natural φ̂) dos polinômios ui (x) que são calculados durante o cálculo do pivô. Sabemos que ||v ||∞ ≤ 1. Em geral sabemos que para qualquer 0 < ξ < 1/4 existe ŝk tal que ||ŝk || ≤ 1 e que |v T sˆk | ≥ ξ(Lemas 3.10 e 3.12). Queremos mostrar que existe ξ > 0 tal que para todas as iterações é possı́vel achar um passo sk que satisfaça simultâneamente as seguintes condições: 1. ||sk || ≤ ∆k , 2. sk gera pelo menos uma fração fixa do decréscimo de Cauchy no modelo. 3. |v T φ̂(sk /∆k )| ≥ ξ. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Disso segue que o modelo pode ser feito FL ou FQ, pelo método Wedge depois de um número finito, uniformemente limitado de iteraçõ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 nós escalarmos a região de confianç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 Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Queremos mostrar que existe uma solução aproximada para o problema min m(s) s∈Rn ||s|| ≤ 1, s.a. |φ(s)T v | ≥ ξ > 0, (2) que produz um decréscimo sobre m(s) tão bom quanto o decréscimo obtido por uma fração fixada no passo de Cauchy. O valor de ξ ainda nã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) Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Se nós mostrarmos que o valor ótimo desse problema está sempre acima de um limitante positivo ξ∗ > 0, para todo v tal que ||v ||∞ ≥ 1, para todo vetor g e matriz simétrica H, então mostramos que existe uma solução aproximada para o problema (2). Para isto precisamos mostrar que o polinômio |φ(s)T v | não se anula em um conjunto factı́vel do problema (3). A dificuldade está onde ||g || ||H|| → 0, o conjunto factı́vel de (3) pode convergir para um ponto singular, sobre qual escolhendo um polinômio adequado pode se anular. Mostraremos que durante o algoritmo Wedge sempre se verifica 0 < gmin < ||g ||/||H||, onde gmin ∈ (0, 1) é uma constante fixa. Como g = gu ∆ e H = Hu ∆2 temos ||g || ||gu || = ||H|| ∆||Hu || Além disso temos que ||H|| ≤ κbhm e ∆ ≤ ∆max . E como o passo de criticalidade será resolvido em alguma hora, do passo 2 temos que ||gu || ≥ min{c , µ−1 ∆}. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Então ||gu || ||g || = ≥ gmin ||H|| ∆||Hu || onde gmin = min{ c 1 , } (4) ∆max κbhm µκbhm Mostraremos agora que é possı́vel uma boa geometria simultâneamente com uma fração do decréscimo de Cauchy. Teorema Seja gmin ∈ (0, 1) uma constante dada. Existe uma constante positiva ξ∗ dependendo de gmin e κfcd tal que o valor ó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 simétrica H ∈ Rn×n tal que Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Mé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 ótimo de (3) é 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 Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Nós provaremos que o seguinte mı́nimo é 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 é 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, é sempre possı́vel para g 0 e H 0 tal que ||g 0 || = 1 e H 0 ≤ 1, encontrar s que satisfaça as duas restriçõ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)| é uma norma em espaço de dimensão finita, temos que existe ξa∗ > 0 tal que min max |v T φ(s)| ≥ ξ∗a isto é, 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 Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Mé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. Entã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 fração do decréscimo de Cauchy. Precisamos pedir uma fração do decréscimo do autopasso. Entã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}, Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Mé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 ó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 siméttrica H ∈ Rn×n tal que σmin ≤ max{ ||g || −λmin (H) , }. ||H|| ||H|| Porém esse resultado não é suficiente, ao contrário do caso de primeira ordem, pois não temos garantia de que σmin exista. No caso de segunda ordem o passo de criticalidade temos Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Método Wedge max{ ||g || 1 −λmin (H) σum c 1 , }= ≥ min{ , }. ||H|| ∆ ||H|| ∆||Hu || ∆max κbhm µκbhm A limitação do lado esquerdo da equação acima envolvendo ∆ não implica a limitação de max{||g ||/||H||, −λmin (H)/||H||}, que é o que nó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 região de confiança onde a fração do autopasso decresce pode encolher para uma região de interior vazio. Isso sigifica que o polinômio se anula em tal região, assim, não há limitante sobre o valor do pivô que possa garantir ser realizável. Portanto nenhum passo é calculado no passo 2 do algoritmo 11.4 para que o decréscimo do autopasso seja atingido. Notas e referências O algoritmo DFO foi implementado por Sceinberg como um pacote de fonte aberta. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Consideraç~ oes finais. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança. Consideraç~ oes finais. Os UOBYQA e NEWUOA são as implementações feitas por Powell e são distribuı́das por ele. O método Wedge foi implementado por Mazari no Matlab, para livre download. Fasano, Morales e Nocedal estudam o comportamento dos algoritmos baseados em interpolação de região de confiança onde a geometria dos pontos é ignorada. Eles possuem bons resultados numericos comparado ao NEWUOA. Esta área hoje ainda está muito ativa. Fabio Antonio Araujo de Campos Métodos baseados em interpolaçãoem região de confiança.