.

ET589 - Optimização

Versão do curso: 2010.2
Duração: [12/8/2010]-[30/12/2010]
Horário: Terça-feira, 8-10h; Quinta-feira, 10-12h
Horário de consulta: Terça-feira, 14-16h
Estagiário: Sr. Abraão D. C. Nascimento, M.Sc.

Assuntos Ministrados

Aula Assunto
1 - 12/8 Apresentação do Curso e Metodologia
2 - 17/8 Conceitos de Programação Matemática; Tipos de Programação [C07, Cap. 1]; Desenvolvimento de Modelos [PP87, pp. 46-49]; Exercícios [S96, p. 18]
3 - 19/8 Exemplo de Modelagem: Problema da Dieta com Comentários Históricos [PP87, pp. 50-54; I02, pp. 103-105]; Método Gráfico de Solução [PP87, pp. 58; C07, Cap.3]
4 - 24/8 Transformação para a Forma Padrão [PP87, pp. 65-70; C07, Cap. 4]; Convexidade [PP87, pp. 38-42; C07, Cap. 2]; Teoremas Fundamentais de Programação Linear [PP87, pp. 70-76; C07, Cap. 5]
5 - 26/8 Simplex: Método Algébrico [PP87, pp. 77-82], [C07 ,Cap. 6]
6 - 31/8 Simplex: Solução via Quadros (Tableaux) [PP87, pp. 82-87], [C07, Cap. 7]
Aulas suspensas: Instrutor nos EUA como Professor Visitante. Aulas retornam em 1 de outubro.
7 - 5/10 Estudo de uma implementação em MATLAB para Simplex via Quadros [C07, Apen. C]
8 - 7/10 Simplex: Implementação Matricial [C07, Cap. 8]
9 - 14/10 Estudo de uma implementação em MATLAB para Simplex (Matricial) [C07, Apen. D]
10 - 19/10 Dualidade: Primal e Dual; Propriedades; Exercícios [PP87, pp. 146-157]
11 - 21/10 Teorema da Dualidade Fraca, Teorema da Dualidade Forte [PP87, pp. 157-162]
12 - 26/10 Teorema da Folga Complementar [PP87, pp. 163-171]
13 - 28/10 Método Dual-Simplex [P87, pp. 171-177]
14 - 4/11 Leitura
15 - 9/11 1o. Exercício Escolar (Versa sobre Aulas 2-14)
16 - 11/11 Correcção do 1o. EE
17 - 16/11 O Problema de Otimização Não-linear; Expansão em Série de Taylor [Vide qualquer livro de Cálculo]
18 - 18/11 Otimização Irrestrita de Funções de uma Variável: Estudo das Derivadas [C07, Cap. 13]; Otimização de Funções Unimodais [C07, Cap. 13]; Busca Sequencial: Busca trisseccional [C07, Cap. 13]
19 - 22/11 Busca Áurea [C07, Cap. 13], [MF, url]; Busca de Fibonacci [C07, Cap. 13], [MF, url]
20 - 25/11 Méthodos de Ponto Fixo; Méthodo de Newton-Raphson para Optimização; Aproximação Quadrática [C07, Cap. 13]
21 - 30/11 Condições de Convergência para o Méthodo de Newton-Raphson; Estudo de uma Implementação Computacional no N-R; Método da Secante para Optimização [C07, Cap. 13]
22 - 30/11 Otimização Irrestrita de Funções de Várias Variáveis; Gradiente; Pontos Críticos; Classificação dos Pontos Críticos; Matriz Hessiana [C07, Cap. 14]
23 - 2/12 Definidade; Caso Bidimensional [C07, Cap. 14]
24 - 7/12 Aplicação: Méthodo dos Mínimos Quadrados [C07, Cap. 14]
25 - 9/12 Método do Gradiente [MF]
26 - 14/12 Método dos Multiplicadores de Lagrange: Demonstração, Interpretação; Uso do Hessiano para Classificação dos Pontos Críticos Obtidos
27 - 16/12 Generalização do Método dos Multiplicadores de Lagrange: Condições de Karush-Kuhn-Tucker
28 - 21/12 2o. Exercício Escolar (Versa sobre Aulas 17-27)
29 - 23/12 Correcção do 2o. EE
30 - 28/12 2a. Chamada (Versa sobre Aulas 2-27)
31 - 30/12 Exame Final (Versa sobre Aulas 2-27)

Tarefa de Casa

Aula Tarefa
1 (i) Leia sobre a carreira profissional.
(ii) Leia sobre Política e Etiqueta em sala de aula.
2 (i) Faça uma revisão de Álgebra Linear [PP87, Cap. 1].
(ii) Modele os problemas propostos em [S96, pp. 18-21].
(iii) Compareça ao Teatro da UFPE durante esta semana (19-20 de agosto às 6:30pm ou 21-22 de agosto às 5pm) para audição de Chopin e Schumann.
3 (i) Resolva [PP87, pp. 61-64].
(ii) Resolva os problemas propostos em [S96, pp. 18-21].
4 (i) Estude [PP87, pp. 40-41].
(ii) Ler [C07]; Estude a Notação para as Dimensões dos vetores e Matrizes.
5 (i) Estude o método algébrico como descrito em [C07].
(ii) Resolva problemas de PL pelo método algébrico.
6 Resolva todos os exercícios propostos em [K96, pp. 329-330].
7 (i) Implemente em R o algoritmo Simplex via quadros.
(ii) Leia este tutorial sobre o MATLAB.
(iii) Instale o Octave em sua máquina e rode/teste/examine/expanda/depure o código examinado em aula. Binários do Octave para Windows aqui; interface QtOctave (recomendável) disponível aqui. Se em Linux, tanto o Octave quando a interface QtOctave estão disponíveis via gerenciador de pacotes (e.g., Synaptic).
8 (i) Estude em detalhes [C07, Cap.8], inclusive o Exemplo Numérico.
(ii) Consulte a referência "Introduction to Algorithms (Cormen, Leiserson, and Rivest) 2001", disponível na Bib. Setorial do CCEN.
9 (i) Implemente em R o algoritmo Simplex (matricial).
(ii) Simulação computational: Para diversos valores de n e m, gere aleatoriamente 20 problemas de programação linear, resolva-os usando o Simplex e calcule o número médio de iterações necessárias. Faça um gráfico em três dimensões.
10 Leia [PP87, cap.6]; Resolva exercícios relacionados com a aula em [PP87, pp. 182-185].
11 Em [PP87, p. 159], lê-se "Analogamente, pode-se demonstrar que y_i* (i=1,2,...m) é uma solução ótima do dual". Demonstre essa assertiva.
12 (i) Estude o Corolário (e sua demonstração!) dado em [PP87, p. 167].
(ii) Examine em detalhe o exemplo em [PP87, pp. 168-171].
(iii) Resolva o máximo de exercícios em [PP87, pp. 182-185] e [K96, pp. 335-337].
15 Resolva em extremo detalhe o 1o. Exercício Escolar.
17 (i) Estude o conceito de expansão em série de Taylor.
(ii) Estude sobre o erro de truncamento.
(iii) Use seu livro de Cálculo favorito para resolver exercícios sobre os assuntos supra-citados.
(iv) Encontre a expansão em série de Taylor da função exp(-1/x^2) em torno de x = 0. O que está acontecendo?
(v) Usando o programa Winplot, no modo 2-Dim (pressione F2), use o menu 'Equa >> Explicit' para realizar o gráfico de alguma função. Depois vá no menu 'One >> Slider'. Use a barra de rolagem da janela slider. Faça a aproximação em série de Taylor para várias ordens (degree), usando o botão 'Taylor approx'.
(vi) Familiarize-se com o Winplot de modo geral; baixe um tutorial do Winplot no sítio do item anterior.
18 (i) Implemente em R e em Octave o algoritmo da Busca Trissectional [C07, Cap.13].
(ii) Adapte seu código para implementar a busca "quadrissectional", i.e., considerando-se pontos c, d e e no intervalo original [a, b]. Consulte [C07, Sec. 13.3] para detalhes e notação.
19 (i) Leia [C07, Cap.13].
(ii) Implemente em R o algoritmo da Busca Áurea e da Busca de Fibonacci [C07, Cap.13].
(iii) Consulte as seguintes sítios sobre os números de Fibonacci: (a) Mathworld e (b) Wikipedia.
20 (i) Estude a nota de aula sobre o método de Newton-Raphson.
(i) Resolva a lista de exercícios sobre o método de Newton-Raphson.
21 (i) Resolva a lista de exercícios proposta sobre métodos de ponto fixo e o método de Newton-Raphson.
(ii) Resolva/estude os exercícios resolvidos sobre (a) a Busca Áurea, (b) a Busca de Fibonacci e (c) o Método de Newton-Raphson na referência [MF] (Acesse os nexos anteriores).
25 (i) Leia sobre o Método do Gradiente em [MF]
(ii) Resolva a seguinte
lista sobre o Método do Gradiente.
(iii) Resolva esta outra lista sobre o Método do Gradiente.
(iv) Examine, execute, teste e comente o seguinte código em R.
(v) Converta o código acima para linguagem MATLAB/Octave.

Referências

  1. [PP87] Puccini, A. L.; Pizolato, N. D., "Programação Linear", Livros Técnicos e Científicos Editora S.A., 1987. [Disponível nas Bibliotecas do CTG e do CCSA.]
  2. [C07] Cintra, R. J., "Notas de Aula de Optimização", UFPE, 2006-2008. [Notas de Aula em processo de escrita.]
  3. [K96] Kolman, B., "Introdução à Álgebra Linear com Aplicações", Prentice-Hall do Brasil, 1996. [Texto elementar e introdutório, porém muito bem escrito e preciso; leitura recomendada.]
  4. [MF] Mathews, John H.; Fink, Kurtis D., Modules for Numerical Methods & Numerical Analysis, sítio da interrede em California State Univ. Fullerton. [Versão impressa em capa-dura disponível em Amazon.com, p.ex.]
  5. [I02] Intriligator, M. D., "Mathematical Optimization and Economic Theory", SIAM, 2002. [Livro clássico. Deve ser consultado pelos seriamente interessados.]
  6. [BV04] Boyd, S.; Vandenberghe, L., "Convex Optimization", Cambridge University Press, 2004. [Livro inteiro em formato PDF disponível gratuita e legalmente na interrede no seguinte sítio: "Convex Optimization - Boyd and Vandenberghe".]
  7. [S96] da Silva, E. M.; da Silva, E. M.; Gonçalves, V.; Murolo, A. C., "Pesquisa Operacional: Programação Linear, Simulação", Editora Atlas, 1996. [Este livro deve ser utilizado apenas pelos seus exercícios.]
  8. [MS] Material Suplementar.

Política do Curso

A prova de 2a. chamada é destinada apenas àqueles que não compareceram a um dos dois exercícios escolares.

Não serão realizados listas, provas extras, testes ou qualquer outro meio destinado a "melhorar" a nota. O conceito final no curso será obtido exclusivamente dos resultados apresentados nos Exercícios Escolares, na 2a. Chamada e no Exame Final.