livro_pnl
203 pág.

livro_pnl


DisciplinaProgramação Não Linear8 materiais114 seguidores
Pré-visualização42 páginas
UM CURSO DE OTIMIZAC¸A\u2dcO
Ademir Alves Ribeiro
Elizabeth Wegner Karas
Curitiba
2011
Suma´rio
Prefa´cio 1
Introduc¸a\u2dco 2
1 Revisa\u2dco de Conceitos 4
1.1 Seque\u2c6ncias . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Definic¸o\u2dces e resultados cla´ssicos . . . . . . . . . . . . . . . . . . . . 4
1.1.2 Ordem de converge\u2c6ncia . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Noc¸o\u2dces de topologia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Resultados de a´lgebra linear . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.4 Fo´rmula de Taylor e teorema da func¸a\u2dco impl´\u131cita . . . . . . . . . . . . . . 16
1.5 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2 Introduc¸a\u2dco a` Otimizac¸a\u2dco 25
2.1 O problema de otimizac¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
2.2 Condic¸o\u2dces de otimalidade . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.3 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3 Convexidade 34
3.1 Conjuntos convexos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2 Func¸o\u2dces convexas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
4 Algoritmos 44
4.1 Algoritmos de descida . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.2 Me´todos de busca unidirecional . . . . . . . . . . . . . . . . . . . . . . . . 47
4.2.1 Busca exata - me´todo da sec¸a\u2dco a´urea . . . . . . . . . . . . . . . . . 47
4.2.2 Busca inexata - condic¸a\u2dco de Armijo . . . . . . . . . . . . . . . . . . 52
4.3 Converge\u2c6ncia global de algoritmos . . . . . . . . . . . . . . . . . . . . . . . 55
4.3.1 Converge\u2c6ncia global de algoritmos de descida . . . . . . . . . . . . 55
4.3.2 Teorema de Polak . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.4 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
ii
5 Me´todos de Otimizac¸a\u2dco Irrestrita 61
5.1 Me´todo do gradiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.1.2 Converge\u2c6ncia global . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.1.3 Velocidade de converge\u2c6ncia . . . . . . . . . . . . . . . . . . . . . . . 63
5.2 Me´todo de Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.2.1 Motivac¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66
5.2.2 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.3 Converge\u2c6ncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68
5.3 Me´todo de direc¸o\u2dces conjugadas . . . . . . . . . . . . . . . . . . . . . . . . 71
5.3.1 Direc¸o\u2dces conjugadas . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3.2 Algoritmo de gradientes conjugados . . . . . . . . . . . . . . . . . . 75
5.3.3 Extensa\u2dco para func¸o\u2dces na\u2dco quadra´ticas . . . . . . . . . . . . . . . . 78
5.3.4 Complexidade algor´\u131tmica . . . . . . . . . . . . . . . . . . . . . . . 78
5.4 Me´todos quase-Newton . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
5.4.1 O algoritmo ba´sico . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
5.4.2 O me´todo DFP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
5.4.3 O me´todo BFGS . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90
5.5 Me´todo de regia\u2dco de confianc¸a . . . . . . . . . . . . . . . . . . . . . . . . . 92
5.5.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93
5.5.2 O passo de Cauchy . . . . . . . . . . . . . . . . . . . . . . . . . . . 94
5.5.3 Converge\u2c6ncia . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96
5.5.4 O me´todo dogleg . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100
5.5.5 O me´todo GC-Steihaug . . . . . . . . . . . . . . . . . . . . . . . . . 103
5.6 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104
6 Implementac¸a\u2dco Computacional 108
6.1 Banco de func¸o\u2dces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108
6.2 Implementac¸a\u2dco dos algoritmos . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.3 Comparac¸a\u2dco de diferentes algoritmos . . . . . . . . . . . . . . . . . . . . . 113
6.4 Outras discusso\u2dces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115
6.5 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116
7 Otimizac¸a\u2dco com Restric¸o\u2dces 118
7.1 Cones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119
7.2 Condic¸o\u2dces de Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . . . . . 125
7.2.1 O cone via´vel linearizado . . . . . . . . . . . . . . . . . . . . . . . . 126
7.2.2 O cone gerado pelos gradientes das restric¸o\u2dces . . . . . . . . . . . . . 127
7.2.3 O cone tangente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128
7.2.4 O teorema de Karush-Kuhn-Tucker . . . . . . . . . . . . . . . . . . 132
iii
7.2.5 A direc¸a\u2dco do gradiente projetado . . . . . . . . . . . . . . . . . . . 134
7.3 Condic¸o\u2dces de qualificac¸a\u2dco . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136
7.3.1 Problemas com restric¸o\u2dces lineares . . . . . . . . . . . . . . . . . . . 137
7.3.2 Condic¸a\u2dco de qualificac¸a\u2dco de Slater . . . . . . . . . . . . . . . . . . . 138
7.3.3 Condic¸a\u2dco de qualificac¸a\u2dco de independe\u2c6ncia linear . . . . . . . . . . 139
7.3.4 Condic¸a\u2dco de qualificac¸a\u2dco de Mangasarian-Fromovitz . . . . . . . . . 140
7.4 Condic¸o\u2dces de otimalidade de segunda ordem . . . . . . . . . . . . . . . . . 143
7.4.1 Problemas com restric¸o\u2dces de igualdade . . . . . . . . . . . . . . . . 144
7.4.2 Problemas com restric¸o\u2dces de igualdade e desigualdade . . . . . . . . 146
7.5 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150
8 Me´todos para Otimizac¸a\u2dco com Restric¸o\u2dces 155
8.1 Programac¸a\u2dco quadra´tica sequencial . . . . . . . . . . . . . . . . . . . . . . 155
8.1.1 Algoritmo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
8.1.2 Converge\u2c6ncia local . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
8.2 Me´todos de filtro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
8.2.1 O algoritmo geral de filtro . . . . . . . . . . . . . . . . . . . . . . . 162
8.2.2 Converge\u2c6ncia global . . . . . . . . . . . . . . . . . . . . . . . . . . . 164
8.3 Exerc´\u131cios do cap´\u131tulo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168
Ape\u2c6ndice: Dicas ou Soluc¸o\u2dces dos Exerc´\u131cios 169
Refere\u2c6ncias Bibliogra´ficas 196
iv
Prefa´cio
O presente texto foi escrito com o propo´sito de servir como material dida´tico
para um curso de otimizac¸a\u2dco. Procuramos abordar aspectos teo´ricos e computacionais.
Interpretac¸o\u2dces geome´tricas sa\u2dco evocadas sempre que poss´\u131vel com o aux´\u131lio de diversas
figuras que aparecem no texto para ilustrar conceitos, exemplos e teoremas. A teoria de
otimizac¸a\u2dco com restric¸o\u2dces e´ apresentada com uma abordagem de cones que, ale´m de ter
um forte apelo geome´trico, consideramos ser mais moderna.
Para um bom aproveitamento do livro, e´ deseja´vel que o estudante tenha co-
nhecimentos de A´lgebra Linear e Ana´lise no IRn. Ale´m disso, e´ importante dar especial
atenc¸a\u2dco aos va´rios exerc´\u131cios que aparecem no final de cada cap´\u131tulo. Muitos exerc´\u131cios
servem para fixar os conceitos, outros para verificar se o leitor consegue identificar e apli-
car certos conceitos para resolver um determinado problema e outros ainda servem para
complementar a teoria.