Se você for imprimir esta página, escolha "Visualizar impressão" no seu navegador, ou clique em Versão para impressão, você irá ver esta página sem esse aviso, sem os elementos de navegação a esquerda ou acima, e sem as TOC's de cada página.
Atualize esta página para ter certeza de que está imprimindo a versão mais atual.
Para maiores informações sobre a versão para impressão, incluindo como fazer arquivos PDF realmente adequados para a impressão, veja Wikilivros:Versões para impressã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.
Este é um conjunto convexo, pois todo segmento com extremidades no conjunto está totalmente contido no conjunto.
Este é um conjunto côncavo, pois existe um segmento com extremidades no conjunto que não está totalmente contido no conjunto.
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 .
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:
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:
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
Um dos autores deste material sugeriu a adição de uma implementação do algoritmo acima em SciLab.
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
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.
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:
Para contornar a desvantagem da descontinuidade da função apresentada anteriormente, surgem outras funções, como por exemplo:
Definição
Dada uma função , definida em um conjunto arbitrário , define-se a parte positiva de , como:
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 .
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
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
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 ).
Um dos autores deste material sugeriu a adição de uma imagem ilustrando a existência de minimizadores globais para funções coercivas.
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:
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:
é coerciva.
é limitado e é coerciva.
Se, para cada , for escolhido ,então:
possui algum ponto de acumulação;
Todo ponto de acumulação de é solução do problema (P);
.
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:
é uma função de penalidade exterior
Se então
Se são covexas, então é convexa.
Se são diferenciáveis, então é diferenciável em , e
Se e e se é uma sequência tal que e então é solução de (P).
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 .
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.
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.
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.
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 .
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.
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.
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
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.
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: