Otimização/Imprimir

Origem: Wikilivros, livros abertos por um mundo aberto.
Saltar para a navegação Saltar para a pesquisa


Capa

Otimização
Conjugate gradient illustration.svg

Introdução


Este material está sendo elaborado com base nas notas de aula da disciplina Otimização II, do curso de Matemática Industrial oferecido pela UFPR, ministrada pelo professor Wilfredo, no segundo semestre letivo do ano de 2008.

O conteúdo do livro não precisa (nem deve) se limitar àquele que consta atualmente no índice. Sendo assim, a qualquer momento o livro pode ser revisto e ampliado.

Sinta-se a vontade para ler este ou quaisquer outros livros do projeto, melhorando-os conforme lhe for possível. Com isso estará ajudando a aumentar a quantidade e a qualidade dos textos didáticos disponíveis em língua portuguesa, ao mesmo tempo em que colaborará com o crescimento projeto Wikilivros como um todo.

Se tiver dúvidas ou sugestões sobre páginas específicas, utilize as páginas de discussão correspondentes para deixar um comentário a respeito.

Ainda há muito por fazer, mas cada um daqueles que contribuem acredita estar fazendo o possível para oferecer o melhor a todos.

Método de gradientes conjugados


Wikipedia
A Wikipédia tem mais sobre este assunto:
Método do gradiente conjugado

Algumas considerações históricas[editar | editar código-fonte]

  • Este método foi originalmente proposto por Hestenes e Stiefel, em 1952.
  • Seu objetivo inicial foi a resolução de problemas quadráticos sem restrições, mas logo o mesmo foi estendido para casos mais gerais.

O método[editar | editar código-fonte]

Este método pode ser considerado sob dois pontos de vista:

  • Como um método de descida, com busca linear exata;
  • Como um método de resolução de sistema linear, baseado em um processo de ortogonalização.
Definição

Um conjunto não vazio é dito convexo quando e vale

Exemplos de conjuntos convexos e côncavos[editar | editar código-fonte]


Definição

Uma função é dita convexa quando é convexo e e vale

Definição

Dado um conjunto convexo , uma função é dita fortemente convexa quando existe uma constante tal que é convexa.

Exercício

Verifique que uma função quadrática é fortemente convexa se existe uma matriz simétrica definida positiva , um vetor e um escalar de modo que .

Resolução
Sendo uma função quadrática, tem-se . A matriz pode ser suposta simétrica, pois caso não seja, toma-se (simétrica), e segue (verifique).

Além disso, se é uma função fortemente convexa, então é estritamente convexa. Como é duas vezes diferenciável (por ser uma função quadrática), a convexidade estrita implica que é definida positiva.


Nota: Uma matriz é definida positiva se, e somente se, todos os seus autovalores são positivos.

Tem-se:

Sendo , segue em particular que e , onde é uma matriz diagonal cujos elementos da diagonal são os autovalores de e é uma matriz onde as colunas são os autovetores correspondentes aos autovalores.

Note que é uma matriz simétrica, pois é a matriz Hessiana de uma função com segundas derivadas parciais contínuas, e consequentemente vale .

Para introduzir o método de direções conjugadas, serão consideradas somente funções quadráticas.

Uma condição necessária de primeira ordem para que seja um ponto de mínimo para a função é que . Para o presente caso, a função é convexa, então, a condição necessária também é suficiente.

Exercício

Prove que se é uma matriz simétrica definida positiva, então dada por possui um único ponto de mínimo.

Resolução
Uma vez que é simétrica definida positiva, a função é fortemente convexa. Mas toda função fortemente convexa, definida em um conjunto fechado não vazio possui um único minimizador, pois:
  • Os conjuntos de nível de uma função fortemente convexa são compactos;
  • Toda função contínua definida em um compacto tem algum minimizador (pelo teorema de Weierstrass);
  • Os minimizadores de uma função convexa são globais;
  • Funções fortemente convexas não podem ter mais de um minimizador.

Em particular, possui um único ponto de mínimo.

No caso de uma função quadrática, tem-se , ou seja, é solução do sistema linear .

A resolução de um sistema linear nem sempre pode ser feita numericamente de forma eficiente. Por exemplo, se a matriz do sistema é:

A solução do sistema linear corresponde à interseção entre duas retas quase paralelas, e os erros de truncamento podem causar imprecisão na solução obtida computacionalmente.

Analiticamente, o sistema tem como solução. Então alguém poderia se perguntar: qual o problema em resolver esse sistema linear, se basta calcular a inversa da matriz e multiplicar pelo vetor ? A resposta é que o calculo da inversa de uma matriz em geral é impraticável computacionalmente, por ter custo muito alto. Por isso, nas situações práticas, onde as matrizes tem ordem bem maior do que 2 (digamos 1000), o cálculo de matrizes inversas não é uma opção.

Assim, com o intuito de desenvolver um método computacional para o cálculo de minimizadores, é preciso utilizar outras técnicas. Considere o seguinte:

Em um método de descida tem-se sempre uma sequencia , com e é um minimizador de

e

Logo, e multiplicando por obtem-se . Consequentemente, o valor de é dado por

Deste modo, o método consistirá de escolher em cada etapa uma direção , e calcular o coeficiente pela fórmula anterior, para gerar o próximo ponto . Mas como escolher a direção ?

Dado e escolhido , defina como , ou seja, é a restrição da função à reta que passa pelo ponto e que tem direção . Logo, derivando a expressão de em relação a , obtem-se

Então, no ponto de mínimo, , tem-se

Ou seja, a direção a ser seguida a partir do ponto é ortogonal ao gradiente da função , no ponto .

Esquema do método de descida[editar | editar código-fonte]

Seja o minimizador da função . Tem-se

Mas implica que , logo

e consequentemente

Donde . Portanto .

Exercício

Provar que se é uma matriz simétrica, definida positiva, então existe uma matriz simétrica , de modo que

Resolução
Sendo uma matriz simétrica, tem-se , com unitária e

Logo

Usando o resultado desse exercício, tem-se ainda que

Fazendo , o método do gradiente conjugado escolhe as direções de descida tais que . Mas quando , tem-se na expressão apresentada anteriormente apenas

Finalmente, tem-se o algoritmo para este método.

Algoritmo de Hestenes-Stiefel[editar | editar código-fonte]

Uma comparação da convergência do método de descida do gradiente com tamanho de passo ótimo (em verde) e o método do gradiente conjugado (em vermelho) para a minimização da forma quadrática com um sistema linear dado. O gradiente conjugado, assumindo aritmética exata, converge em no máximo n passos onde n é o tamanho da matriz do sistema (no exemplo, n=2).
Primeiro passo: Escolha 
  Se , então pare: 
  Senão: 
  Calcular 
  


Passo iterativo : Dado 
  Se , então pare: 
  Senão: 
  
  

Pode-se verificar facilmente que . De fato, como , tem-se . Logo, .

Exercício

Provar que se então .

Resolução
Tem-se

Multiplicando ambos os membros por , e trocando de lugar com resulta:

,

ou seja,

,

somando em ambos os lados, segue que

,

Então

Sendo a última igualdade devida ao fato de para .



Exemplos[editar | editar código-fonte]

Considere definida por . Em outros termos, tomando , tem-se , onde .

Pode-se aplicar o método de direções conjugadas ao seguinte problema

Note, desde já, que o conjunto solução é .

Inicio
  • Toma-se arbitrário, por exemplo, .
  • Avalia-se o gradiente da função neste ponto inicial:
Iteração 1

A seguir, verifica-se se o gradiente se anula no novo ponto :

Como o gradiente já é nulo, não é preciso fazer a segunda iteração, e o ponto é o (único) minimizador global de .


Em um caso mais geral, considerando definida por , tem-se cálculos muito parecidos em cada passo.

O conjunto solução continua sendo .

Inicio
  • Considere como no primeiro exemplo, ou seja, .
  • Avalia-se o gradiente da função neste ponto inicial:
Iteração 1

A seguir, verifica-se se o gradiente se anula no novo ponto :

Novamente, o gradiente se anula já na primeira iteração, de modo que é o minimizador global de .


Exercício

Seja uma matriz simétrica definida positiva, cujos autovalores são todos iguais. Então começando de qualquer ponto , o método fornece como solução.

Um terceiro exemplo pode ser dado tomando e definida por . Observe que tal matriz é simétrica e definida positiva:

Logo, os autovalores de são e . Isso também implica que a função é fortemente convexa.

Aplicando o método:

Início
  • Toma-se um ponto arbitrário no plano, por exemplo ;
  • Verifica-se se tal ponto é o minimizador global, avaliando nele o gradiente da função:
.
  • Já que o gradiente não se anulou no chute inicial, é preciso escolher uma direção e um comprimento de passo para determinar a próxima aproximação:
Iteração 1

Feitos esses cálculos, o próximo ponto é dado por

Para saber se será necessária uma nova iteração, ou se o minimizador foi encontrado, calcula-se o gradiente da função no ponto:

.

Novamente, será preciso calcular uma nova direção e um novo comprimento de passo:

Iteração 2

onde , no algoritmo de Hestenes é dado por:

Portanto

Além disso, o tamanho do passo é dado por

Portanto

Obviamente, este é o minimizador procurado (pois o método tem a propriedade de convergência quadrática, ou seja utiliza no máximo iterações para chegar a solução quando aplicado a funções quadráticas definidas em )

Exercício

Implementar o algoritmo de Hestenes-Stiefel em alguma linguagem de programação, por exemplo em Scilab, ou Matlab.

Exercício

Seja um função quadrática fortemente convexa. Verifique as seguintes igualdades:

Implementação em Scilab[editar | editar código-fonte]

Abaixo é apresentada uma implementação deste algoritmo na linguagem de programação utilizada pelo Scilab.

A = [2 1; 1 2];

function [x] = min_gradiente_conjugado(xk)
  //Entrada: xk em R^n, qualquer "chute inicial"
  //  Saída: x, o ponto em que f assume o valor mínimo
  
  k        = 0        //Indica quantos loops já foram feitos
  epsilon  = 0.01
  n        = size(xk,1)
  g        = df(xk)
  seq      = zeros(n,n+1)
  seq(:,1) = xk
  while (norm(g) > epsilon) & (k <= n)
    if (k == 0)
      d = -g
    else
      d = Hestenes(g,d,A)
    end
    t  = busca_linear(g,d,A)
    xk = xk + t*d
    k  = k+1
    seq(:,k+1) = xk
    g  = df(xk)
  end
  plot(seq(1,:),seq(2,:))
  x = xk  
endfunction


function [fu] = f(u)
  fu=(1/2)*(u'*A*u)
endfunction


function [grf] = df(u)
  grf = A*u
endfunction


function [d] = Hestenes(g,d,A)
  d=-g + ((g'*A*d)/(d'*A*d))*d
endfunction


function [t] = busca_linear(g,d,A)
  t=(g'*g)/(d'*A*d)
endfunction

Para facilitar a compreensão do método, pode ser útil exibir as curvas de nível da função. Uma forma de implementar uma função com esse propósito é a seguinte:

function plotar_curvas
  qtd=101
  tam=max(seq)
  x=linspace(-tam,tam,qtd)
  y=x
  z=zeros(qtd,qtd)
  for i=1:qtd
    for j=1:qtd
      z(i,j)=f([x(i);y(j)])
    end
  end
  contour2d(x,y,z,10)
  a=gca();
  a.x_location = "middle"; 
  a.y_location = "middle"; 
endfunction

Algoritmo de Fletcher-Reeves[editar | editar código-fonte]

Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para ilustrar o método de Fletcher-Reeves.


Esta versão é na verdade uma extensão do algoritmo anterior, permitindo a aplicação no caso de funções que não são quadráticas.

Primeiro passo: Escolha 
 Se , então pare: 
 Senão:  (como em todo método de descida)
 Calcular , através de uma busca linear
 
Passo iterativo:
 Se , então pare: 
 Senão: 
 Calcular , através de uma busca linear
 
 


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.

Algoritmo de Polak-Ribière[editar | editar código-fonte]

Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para ilustrar o método de Fletcher-Reeves.

Uma outra versão é a seguinte:

Primeiro passo: Tomar 
 Se , então pare: 
 Senão:  (como em todo método de descida)
 Calcular , através de uma busca linear
 
 
Passo iterativo:
 Se , então pare: 
 Senão: 
 Calcular , através de uma busca linear
 
 


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.
Exercício

Verificar que, no caso de uma função quadrática e fortemente convexa, os algoritmos de Hestenes-Stiefel, de Fletcher-Reeves e de Polak-Ribière são os mesmos.

Exercício

Seja . Implemente o método de gradientes conjugados, e utilize o algoritmo para determinar o ponto de mínimo da função . Note que o espaço é unidimensional, então o método de gradientes conjugados reduz-se ao método dos gradientes, com primeira direção . Observe ainda que é uma função coerciva fortemente convexa.

Algoritmo auxiliar[editar | editar código-fonte]

Para o caso de funções não quadráticas, é preciso usar algum método de busca linear para a implementação do método dos gradientes conjugados, seja a versão de Fletcher-Reeves ou a de Polak-Ribière. Uma possibilidade é a busca de linear de Armijo (ver Izmailov & Solodov (2007), vol 2, pag. 65), cujo algoritmo é esboçado a seguir:

function busca_linear_Armijo (f, theta, alpha, delta, t0)
  while (alpha * pred > ared)
    t = d * t
  end
endfunction

com:


Crystal Clear app kaddressbook.png Implementar a regra de Armijo e corrigir o esboço acima.

Métodos de penalidades

Wikipedia
A Wikipédia tem mais sobre este assunto:
Métodos de penalidades

Os métodos que recebem este nome fazem parte de uma família de métodos baseados em:

  • Simplicidade conceitual;
  • Eficiência prática;

Algumas das primeiras funções de penalidade foram desenvolvidas por:

  • Courant (1943)
  • Ablate Brighham (1955) (qual o artigo?)
  • AV Fiacco, GP McCormick (1968) (qual o artigo?)

Para compreender este tipo de método, será considerado o seguinte problema:

Adicionalmente, se for considerado o conjunto de pontos , o problema (P) se escreve ainda como

Uma primeira idéia para a resolução desse tipo de problema é fazer uso de funções indicadoras, conforme é definido a seguir:

Definição

Dado um conjunto não vazio , define-se a função indicadora por:

Notas: A função indicadora é às vezes denotada por .

Para transformar um conjunto (P) em um problema sem restrições, pode-se proceder da seguinte maneira: Considerar o problema (PD), dado por:

Considerando definida por:

Tem-se ainda o problema (PP), dado por:

Comentários:

  • A grande vantagem desta idéia é que ela transforma um problema com restrições em um problema irrestrito.
  • A principal desvantagem é que a função definida a seguir é descontínua em cada ponto :

Método de penalidade exterior[editar | editar código-fonte]

Para contornar a desvantagem da descontinuidade da função apresentada anteriormente, surgem outras funções, como por exemplo:

Gráfico de uma função de penalidade
Definição

Dada uma função , definida em um conjunto arbitrário , define-se a parte positiva de , como:


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para comparar uma função e sua correspondente .
Exercício

Verifique que para cada tem-se, para cada , a igualdade , onde é a parte positiva de e é a função definida no exemplo anterior.


Resolução
De fato, dada qualquer função , segue da própria definição de que

Mas

implica que

Portanto, . Como pode ser tomada arbitrariamente, tem-se em particular que .

Exercício

Verifique que para cada tem-se, para cada , a igualdade .


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu conferir o enunciado do exercício anterior. A afirmação parece ser falsa nos casos em que .

A idéia de aplicar penalizações aos pontos que não pertencem ao conjunto viável é formalizada na seguinte definição:

Definição

Seja . A função é chamada de função de penalidade exterior se possui as seguintes propriedades:

  • é contínua

Nota: Lembre-se que é o conjunto viável do problema (P).

Em particular, as funções são funções de penalidade exterior.

Definição

Seja . A função é dita coerciva se


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de exemplos de funções de penalidade, juntamente com algumas imagens ilustrando os seus gráficos.

Nota: Conforme o Wikcionário, o termo coercivo significa: que coage; que reprime; que impõe pena; coercitivo. Nesse sentido, esse é um termo adequado ao tratar do conceito anterior, no contexto dos métodos de penalidade.

Exercício

Verifique que é uma função coerciva se, e somente se, é limitado para todo .

Resolução
Pela definição de limite, a afirmação

é equivalente a dizer que

tal que tem-se .

Esta última implicação, é equivalente à

(sua contrapositiva).

Pela definição de conjunto de nível, isso equivale à . A existência de um número com tal propriedade significa que é um conjunto limitado, donde conclui-se a equivalência entre coercividade e limitação dos conjuntos de níveis


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem que ilustre geometricamente a relação entre coercividade e conjuntos de nível.
Exercício

Verifique que definida por é uma função de penalidade exterior, onde conforme anteriormente, é a parte positiva de .


Resolução
Primeiramente, é uma função não negativa, pois o quadrado de qualquer número real é não negativo, assim como a soma de números reais não negativos.

Em segundo lugar, tem-se se, e somente se, para cada índice e cada índice vale e . Como , tem-se

Finalmente, como a soma e o produto de funções contínuas resulta em uma função contínua, segue que é contínua, pois são contínuas.

Exercício

Verifique que se é uma função contínua coerciva, então existe tal que .


Resolução
Considere um ponto arbitrário . Tome . Nestas condições, é limitado (conforme um dos exercícios anteriores) e fechado (pois é pré-imagem de um conjunto fechado por uma função contínua), portanto compacto. Neste caso, conforme o teorema de Weierstrass, a função possui algum ponto de mínimo no conjunto , ou seja, existe tal que .

Ne verdade, tal ponto é também um minimizador global da função , pois se então (pela definição do conjunto ).


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem ilustrando a existência de minimizadores globais para funções coercivas.

Alguns conceitos da topologia[editar | editar código-fonte]

Em algumas situações, é interessante ter em mente que certos conceitos definidos no contexto da Otimização são, na verdade, instanciações de conceitos mais gerais, muitos deles provenientes da topologia. Alguns exemplos são apresentados a seguir.

Definição

Dado um conjunto , uma coleção de subconjuntos de é chamada de topologia se:

Exemplos
  • Topologia euclidiana:

Em outras palavras, a topologia euclideana é a coleção de todos os conjuntos abertos contidos em . Pode-se verificar com facilidade que de fato são satizfeitas as três propriedades que definem uma topologia.

Outro exemplo muito comum é o seguinte:

  • Topologia euclideana estendida:

Em geral, a noção de limite seria caracterizada topologicamente da seguinte forma:

Definição

De volta ao método[editar | editar código-fonte]

Uma vez apresentados os conceitos iniciais, pode-se provar o seguinte teorema:

Teorema

Considere:

  • uma função de penalidade exterior;
  • uma função contínua;
  • um conjunto fechado;
  • uma sequência de termos positivos tal que .
Suponha que é válida uma das seguintes propriedades:
  1. é coerciva.
  2. é limitado e é coerciva.
Se, para cada , for escolhido ,então:
  1. possui algum ponto de acumulação;
  2. Todo ponto de acumulação de é solução do problema (P);
  3. .


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem que ilustre geometricamente o significado do teorema acima.


Demonstração
Se (1) acontece, então é coerciva, pois

A desigualdade é válida pois é uma função de penalidade, portanto não negativa, e a igualdade se deve à hipotese sobre . Além de coerciva, tal função é contínua (pois é combinação linear de funções contínuas). Logo, a função possui um ponto de mínimo global, ou seja, existe tal que

, para qualquer .

Mas é contínua e coerciva, então também existe tal que

Por outro lado, se vale (2), então é contínua e C compacto. Analogamente, é contínua e compacto, donde tem-se algum tal que

Em ambos os casos, dada uma sequência tal que e , defina-se por . Logo,

Sendo que a primeira desigualdade se deve ao fato de ser um minimizador, por construção, e a segunda segue por que é decrescente. Portanto, .

Além disso, tem-se as seguintes desigualdades:

Logo, somando os membros correspondentes, obtem-se:

ou seja,

Portanto,

Por outro lado, , sendo primeira desigualdade válida por ser não negativa e positivo, e a segunda devida à própria definição de . Logo, .

Se a primeira das hipóteses acontece, segue da coercividade e dessa última desigualdade que . Então é uma sequência limitada.

Se ocorre a segunda, então é coerciva, mas foi mostrado que , consequentemente . Sendo coerciva, conclui-se novamente que é uma sequência limitada.

Portanto, em qualquer caso, possui algum ponto de acumulação.

Seja um ponto de acumulação de . Então existe tal que . Logicamente, . Pela continuidade de e sabendo que , se deduz que . Mas já havia sido verificado que , então segue a igualdade .

A sequência é crescente. Seja (por que razão ele existe?). Como , tem-se . Portanto, . Logo , ou seja, .

Como é contínua, , e este valor é nulo se, e somente se, .

Logo, , donde . Assim, tem-se , ou seja, é solução de (P).

Exercício

Dado o problema (P), considere (isso não quer dizer que o problema tenha solução). suponha-se que e são funções contínuas e que seja não vazio, ou seja, que é factível. Tome como , onde denota a parte positiva de , como de costume. Considere ainda dada por e, para cada , seja Nessas condições, provar que:

  1. é uma função de penalidade exterior
  2. Se então
  3. Se são covexas, então é convexa.
  4. Se são diferenciáveis, então é diferenciável em , e
  5. Se e e se é uma sequência tal que e então é solução de (P).

Algoritmo de penalidade exterior[editar | editar código-fonte]

Primeiro passo: Escolha ,  e 

Passo iterativo : Calcular , solução global de 

Escolha  tal que 

Nota: Neste algoritmo, é uma função de penalidade exterior.

Exercício

Sejam e . Considere o problema: Utilize o método de penalidade exterior para determinar o ponto de mínimo da função sobre o conjunto .

Resolução
Esboço: Pode-se tomar , onde:

Tem-se então o problema irrestrito: , onde pode ser aplicado o método de gradientes conjugados.

Implementação do algoritmo de penalidade exterior em SciLab[editar | editar código-fonte]

Considerando o problema

com uma função quadrática, simétrica positiva definida, lineares, e a função de penalidade, , dada por:

Pode-se usar o método dos gradientes conjugados para resolver o seguinte problema:

onde terá sua matriz Hessiana definida positiva.


Crystal Clear app kaddressbook.png Incluir o código para uma implementação do método em SciLab.

Método de penalidade interior[editar | editar código-fonte]

Este método também é conhecido como método de barreira. Ele consiste em trabalhar com funções de penalidade tais que e qualquer que seja a sequência para a qual , se tem que a função de penalidade tende a .


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para ilustrar uma sequência de pontos que tende a um ponto da fronteira de um conjunto C, de preferência junto com o gráfico de uma função de penalidade deste novo tipo.

Mas como conseguir esse tipo de função?

Exemplos[editar | editar código-fonte]

Considere o caso em que . Lembrando que a função logarítmica tem a propriedade:

pode-se tomar , pois

implica que

Analogamente, tem-se

então, uma outra função com a propriedade desejada é .

O problema a ser resolvido quando se quer aplicar o método de barreira é o seguinte:

onde é tal que

Observação: não é necessariamente igual ao interior do conjunto . Por exemplo:


Crystal Clear app kaddressbook.png Um dos autores deste material sugeriu a adição de uma imagem para ilustrar um conjunto C cujo correspondente C0 seja diferente do interior de C.
Definição

Se diz que uma função é uma função de barreira se ela possui as seguintes propriedades:

  1. é limitada inferiormente em .
  2. Para qualquer sequência tal que vale
  3. é contínua

Algoritmo de barreira[editar | editar código-fonte]

Primeiro passo: Escolha ,  e 

Passo iterativo : Calcular , solução global de 

Escolha  tal que 

Observação: Neste método os termos da sequência estão sempre em .

Implementação do algoritmo de barreira em SciLab[editar | editar código-fonte]

Considerando o problema

pode-se usar o método de barreira no conjunto:

Pode-se usar qualquer das funções de penalidade interior apresentadas, por exemplo:

ou ainda

Como , o problema passa a ser:

Observação: Note que é necessário conhecer um ponto inicial , para servir de primeira aproximação, ou ponto de partida para o algoritmo.

Métodos de região de confiança


Considere o seguinte problema de programação diferenciável não linear sem restrições:

onde é de classe .

Observação: Como não é necessariamente convexa, a matriz pode não ser definida positiva, apesar de ser simétrica. Neste caso, o método de Newton ou suas variantes (direções conjugadas, quase Newton, etc) não servem.

O primeiro método de região de confiança (em inglês, Trust region method), foi introduzido por Powel em 1970 (qual artigo?) mas oficialmente introduzido por Dennis em 1978 (artigo?). Ele consiste no seguinte:

A cada iteração, se constrói um modelo quadrático e uma região de confiança

este princípio pode ser considerado como uma extensão da busca de Armijo unidimensional.

Breve revisão da busca de Armijo[editar | editar código-fonte]

Para entender a geometria do método de região de confiança, é bom lembrar a geometria da busca de Armijo unidimensional.

Seja uma direção de descida de uma função a partir do ponto . Então . Agora, considerando , definida por , tem-se:

. Assim, . Se , então .
Exercício

Mostrar que sempre existe tal que .

Resolução
A resolução deste exercício é deixada a cargo do leitor. Sinta-se livre para melhorar a qualidade deste texto, incluindo-a na versão online deste material.

A busca de Armijo consiste em tomar .

Se

Mas como , então existe algum tal que vale . A tal ponto, chama-se ponto de Armijo.

Busca de Armijo.svg

Introduzindo as seguinte notação

(modelo linear para a função )
(redução predita por este modelo)
(redução real no valor da função)

a pergunta é:

Quando um ponto vai ser ponto de Armijo com essa notação?

Tem-se:

Logo, se segue que é um ponto de Armijo.

Observações: Note que a essência da busca linear de Armijo é construir um modelo linear e um intervalo compacto , sendo e o ponto inicial da busca e logo procurar o ponto de Armijo em .

De volta ao método[editar | editar código-fonte]

O método de região de confiança será uma generalização da busca de Armijo, consistindo da construção de um modelo quadrático e uma região , chamada de região de confiança, e nessa região calcular o novo iterando.

Algoritmo da região de confiança[editar | editar código-fonte]

Primeiro passo: Escolha , , ,  e .

Passo iterativo : Enquanto , construa o modelo quadrático:
 
Calcule , solução de
 
Tome  e 
Se , fazer 
Senão ,  e 

Comentários: No algoritmo anterior, quando se tem um passo falho, a região de confiança sempre diminui. Seria bom incluir casos bons, onde a região deve crescer.

Algoritmo da região de confiança melhorado[editar | editar código-fonte]

Primeiro passo: Escolha , , , , ,  e .

Passo iterativo : Enquanto , construa o modelo quadrático:
 
Continue = 1
Enquanto (Continue = 1)
  Calcule , solução de
   
  Tome  e 
  Se , fazer 
    Se , ; Continue = 0
    k = k+1
  Senão 


O subproblema quadrático[editar | editar código-fonte]

Conforme foi explicado, o método das regiões de confiança constrói um modelo quadrático da forma:

onde, no método, e . Em tal modelo, tem-se

  • um vetor não nulo;
  • uma matriz simétrica (que pode não ser definida positiva)

O problema quadrático é

com .

Este é o problema que será tratado a seguir.

Exercício

Provar que sempre tem solução.

Resolução
Esboço: Como é uma função contínua e o conjunto onde se quer minimizar tal função é uma bola, em dimensão finita, trata-se de minimizar uma função contínua em um compacto. Esse é um problema que tem solução, pelo teorema de Weierstrass.

O exercício anterior garante que o método está bem definido, quer dizer, todas as etapas podem ser realizadas.

O problema de mínimos quadrados


Este tipo de problema é muito frequente em ciências experimentais. Para ter um exemplo em mente durante a discussão que será feita mais adiante, considere as seguintes informações:

Segundo dados disponibilizados pelo IBGE, o Produto Interno Bruto per capita na cidade de São Paulo, no período de 2002 a 2005, foi (em reais): 17734, 19669, 20943 e 24083, respectivamente.

Com base nessas informações, como poderia ser feita uma previsão do valor correspondente ao ano seguinte (2006)?

Uma escolha possível seria supor que a cada ano o PIB aumenta uma aproximadamente constante, ou seja, usar um modelo linear para obter tal estimativa (que possivelmente será bem grosseira). Intuitivamente, bastaria analisar os dados disponíveis e a partir deles deduzir qual é o aumento que ocorre a cada ano. Depois, a previsão para 2006 seria aproximadamente igual à de 2005 somada com aquele aumento anual.

Esta idéia poderia até funcionar para o caso deste exemplo, mas o que fazer se a quantidade de dados disponíveis sobre algum fenômeno (ou alguma situação) for significativamente maior?

A melhor escolha, sem dúvida, é fazer uso de um computador para obter o modelo que melhor descreve o "comportamento" dos dados experimentais.

Em geral, os problemas de mínimos quadrados consistem em identificar os valores de determinados parâmetros, de modo que se satisfaçam certas equações . No contexto do exemplo anterior, se procura um modelo linear para os dados, ou seja, uma função que os descreva da melhor forma possível. Assim, os parâmetros a considerar são e . Os valores ideais para essas variáveis seriam aqueles que verificassem as seguintes equações:

Note que a partir dessas equações poderiam ser definidas as funções como:

É de se esperar que o sistema de equações obtido a pouco não admitirá uma solução exata, pois se tem mais equações do que variáveis.

Isso geralmente acontece, pois é comum haver uma quantidade de equações bem maior que o número de parâmetros a identificar. Em particular, quando todas as equações são lineares em suas variáveis, dificilmente existirá uma solução exata para o sistema linear resultante, pois este terá mais equações do que incógnitas (como no exemplo). Em geral, não é possível encontrar parâmetros que satisfaçam exatamente todas as equações. Por isso, costuma-se tentar identificar os parâmetros que "melhor se aproximam" de uma solução exata, em algum sentido.

Uma forma de obter uma solução aproximada (uma "quase-solução") resulta da seguinte observação: o valor de cada função em uma solução exata deveria ser zero. Se tal exigência é restritiva demais, e com ela não é possível encontrar qualquer solução, uma possibilidade seria exigir um pouco menos. Por exemplo, poderia ser exigido apenas que o valor de , para seja, em geral, pequeno. Uma das formas de capturar essa idéia em termos mais precisos é dizer que se pretende minimizar a soma dos quadrados dos valores de cada . Em símbolos, o problema passaria a ser:

O caso linear[editar | editar código-fonte]

Neste caso, para cada índice , a função é afim linear, ou seja:

onde e para cada . Deste modo, pode-se definir uma função como

de modo que

Motivando a introdução da seguinte notação:

Assim,

Logo, buscar uma solução exata é o mesmo que procurar uma solução para o seguinte sistema linear:

E uma solução aproximada poderia ser buscada a partir do seguinte problema de minimização:

Exercício

Verifique que se houver uma solução exata, ela também será um minimizador de . A recíproca é verdadeira?

Resolução
Primeiramente, observe que para qualquer tem-se

Isso significa que é uma cota inferior para os valores assumidos por esta soma de quadrados. Além disso, se é uma solução exata, então para cada índice tem-se:

e consequentemente

Então, em a soma dos quadrados assume seu valor mínimo.

Não vale a recíproca, pois se para um certo a soma dos quadrados assumir um valor positivo , então

implica que existe algum tal que

Isto significa que não satisfaz a equação de índice , e portanto não pode ser uma solução exata.

Analisando a função objetivo do problema de minimização anterior, tem-se: