mslivro
262 pág.

mslivro


DisciplinaProgramação Não Linear8 materiais114 seguidores
Pré-visualização50 páginas
ME´TODOS COMPUTACIONAIS
DE OTIMIZAC¸A\u2dcO
Jose´ Mario Mart´\u131nez
Sandra Augusta Santos
Departamento de Matema´tica Aplicada
IMECC-UNICAMP
1995
Atualizado em dezembro de 1998
I´NDICE
1. INTRODUC¸A\u2dcO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1 UMA CLASSIFICAC¸A\u2dcO INFORMAL . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.2 UM PROBLEMA DE ESTIMAC¸A\u2dcO DE PARA\u2c6METROS . . . . . . 3
1.3 DEFININDO MINIMIZADORES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2. CONDIC¸O\u2dcES DE OTIMALIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
2.1 RESTRIC¸O\u2dcES EM FORMATO GERAL . . . . . . . . . . . . . . . . . . . . . . 12
2.2 RESTRIC¸O\u2dcES DE IGUALDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3 RESTRIC¸O\u2dcES DE DESIGUALDADE . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.4 RESTRIC¸O\u2dcES DE IGUALDADE E DESIGUALDADE . . . . . . . 22
3. CONVEXIDADE E DUALIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1 CONVEXIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
3.2 DUALIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
4. MINIMIZAC¸A\u2dcO DE QUADRA´TICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1 QUADRA´TICAS SEM RESTRIC¸O\u2dcES . . . . . . . . . . . . . . . . . . . . . . . . 37
4.1.1 USANDO FATORAC¸O\u2dcES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
4.1.2 O CASO ESPARSO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
4.1.3 ME´TODOS ITERATIVOS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
4.2 QUADRA´TICAS EM BOLAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
4.3 QUADRA´TICAS EM CAIXAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
5. SISTEMAS DE EQUAC¸O\u2dcES NA\u2dcO-LINEARES . . . . . . . . . . . . . . . . . . . . 73
5.1 O ME´TODO DE NEWTON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74
5.2 ME´TODOS QUASE-NEWTON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76
5.3 ME´TODOS DE NEWTON INEXATOS . . . . . . . . . . . . . . . . . . . . . . . 79
5.4 CONVERGE\u2c6NCIA LOCAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
5.4.1 O TEOREMA DAS DUAS VIZINHANC¸AS . . . . . . . . . . . . . 85
5.4.2 CONVERGE\u2c6NCIA QUADRA´TICA DE NEWTON . . . . . . 87
5.4.3 CONVERGE\u2c6NCIA DOS QUASE-NEWTON . . . . . . . . . . . . 89
5.4.4 CONVERGE\u2c6NCIA DOS NEWTON INEXATOS . . . . . . . . 95
6. MINIMIZAC¸A\u2dcO IRRESTRITA E BUSCA LINEAR . . . . . . . . . . . . . . . 99
i
6.1 ALGORITMOS GERAIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99
6.2 O ME´TODO DE NEWTON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107
6.3 ME´TODOS QUASE-NEWTON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112
6.4 ME´TODOS DE NEWTON TRUNCADOS . . . . . . . . . . . . . . . . . . . 122
7. REGIO\u2dcES DE CONFIANC¸A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
7.1 ALGORITMO GERAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126
7.2 ME´TODO DE NEWTON . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127
7.3 MINIMIZAC¸A\u2dcO EM CAIXAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
8. MINIMIZAC¸A\u2dcO UNIDIMENSIONAL . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145
8.1 ME´TODOS DIRETOS PARA REDUC¸A\u2dcO DE INCERTEZA . 145
8.2 APROXIMAC¸O\u2dcES POLINOMIAIS . . . . . . . . . . . . . . . . . . . . . . . . . . 148
8.3 TE´CNICAS DE MINIMIZAC¸A\u2dcO GLOBAL . . . . . . . . . . . . . . . . . . 152
9. RESTRIC¸O\u2dcES LINEARES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155
9.1 IGUALDADES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 156
9.2 ESTRATE´GIA DE RESTRIC¸O\u2dcES ATIVAS . . . . . . . . . . . . . . . . . . 158
9.3 SAINDO DA FACE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161
9.4 REDUC¸A\u2dcO A CAIXAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 163
9.5 PONTOS INTERIORES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166
10. PENALIDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171
10.1 ME´TODOS DE BARREIRAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172
10.2 PENALIDADE EXTERNA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179
10.3 LAGRANGIANO AUMENTADO . . . . . . . . . . . . . . . . . . . . . . . . . . . 188
11. GRADIENTE REDUZIDO GENERALIZADO . . . . . . . . . . . . . . . . . . . 195
11.1 RESTRIC¸O\u2dcES DE IGUALDADE . . . . . . . . . . . . . . . . . . . . . . . . . . . 196
11.2 GRG COM DESIGUALDADES . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200
11.3 IMPLEMENTAC¸A\u2dcO COMPUTACIONAL . . . . . . . . . . . . . . . . . . 202
12. PROGRAMAC¸A\u2dcO QUADRA´TICA SEQUENCIAL . . . . . . . . . . . . . . 205
12.1 PROGRAMAC¸A\u2dcO QUADRA´TICA SEQUENCIAL \u201cPURA\u201d 206
12.2 FORC¸ANDO SOLUBILIDADE DO SUBPROBLEMA . . . . . . 208
12.3 A FUNC¸A\u2dcO DE ME´RITO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210
12.4 DECRE´SCIMO SUFICIENTE . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213
12.5 O PARA\u2c6METRO DE PENALIDADE . . . . . . . . . . . . . . . . . . . . . . . 216
12.6 O ALGORITMO ESTA´ BEM DEFINIDO . . . . . . . . . . . . . . . . . . 219
12.7 A PROVA DE CONVERGE\u2c6NCIA GLOBAL . . . . . . . . . . . . . . . . 223
ii
12.8 A HESSIANA DA QUADRA´TICA . . . . . . . . . . . . . . . . . . . . . . . . . 226
12.9 OUTRAS FUNC¸O\u2dcES DE ME´RITO . . . . . . . . . . . . . . . . . . . . . . . . . 229
12.10 NOTAS HISTO´RICAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 233
BIBLIOGRAFIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 237
iii
Chapter 1
Introduc¸a\u2dco
Otimizac¸a\u2dco e´ um problema matema´tico com muitas aplicac¸o\u2dces no \u201cmundo
real\u201d. Consiste em encontrar os m\u131´nimos ou ma´ximos de uma func¸a\u2dco de
va´rias varia´veis, com valores dentro de uma determinada regia\u2dco do espac¸o
multi-dimensional. Os responsa´veis pela tomada de deciso\u2dces nos mais vari-
ados campos da atividade humana defrontam-se, cotidianamente, com esse
tipo de necessidade. A`s vezes, a \u131´ndole do problema, a demanda de re-
sultados precisos, ou a pro´pria curiosidade, leva a formalizar varia´veis, re-
stric¸o\u2dces e objetivos, de maneira que a natureza matema´tica do problema
emerge. Esse e´ o processo de modelagem, que descobre isomorfismos entre
a realidade emp´\u131rica e o idealismo dos objetos matema´ticos. No entanto,
a corresponde\u2c6ncia entre experie\u2c6ncia e modelo formal esta´ longe de ser per-
feita: a traduc¸a\u2dco esta´ sujeita a erros, simplificac¸o\u2dces e falhas de comunicac¸a\u2dco.
Notavelmente, a problema´tica de adequar um modelo matema´tico a uma
situac¸a\u2dco real tambe´m pode ser formulada como um problema matema´tico,
quase sempre de otimizac¸a\u2dco.
1.1 Uma classificac¸a\u2dco informal
O problema a ser considerado neste livro e´ o seguinte:
Minimizar f(x) sujeita a x \u2208 \u2126 \u2282 IRn. (1.1.1)
A func¸a\u2dco f e´ chamada func¸a\u2dco objetivo e o conjunto \u2126, frequ¨entemente
definido por um conjunto de igualdades e desigualdades, e´ o conjunto fact´\u131vel.
Os pontos de \u2126 sera\u2dco os pontos fact´\u131veis de (1.1.1).
1
2 CHAPTER 1. INTRODUC¸A\u2dcO
De fato, estamos ta\u2dco interessados emminimizar como emmaximizar func¸o\u2dces,
mas falaremos apenas de minimizar dado que, claramente, maximizar f(x)
em uma regia\u2dco qualquer do espac¸o IRn e´ equivalente a minimizar \u2212f(x) na
mesma regia\u2dco. As soluc¸o\u2dces x\u2217 \u2208 \u2126 do problema (1.1.1)