OPTIMIZAÇÃO E ALGORITMOS

Professor Responsável: João Sentieiro (Mailto:jjss@isr.ist.utl.pt)

PAUTA COM A REVISAO DE PROVAS DO EXAME DE 2 EPOCA (REVISTO 22 FEV)

PAUTA COM A REVISAO DE PROVAS DO EXAME DE 1 EPOCA

PROGRAMA:

I — Introdução

Optimização, tipos de problemas, dimensão de problemas, algoritmos iterativos e convergência

II – Revisão matemática (a fazer pelos alunos com base nos elementos de estudo fornecidos)

Notação; Subespaços e independência linear; Normas; Sequências; Limites e Continuidade; Matrizes quadradas e valores próprios; Matrizes simétricas e positivas definidas; Derivadas; Contracções; Conjuntos e funções convexas.

III — Programação Linear

Propriedades fundamentais: exemplos de problemas de programação linear, soluções básicas, teorema fundamental da programação linear, convexidade. O Método Simplex: Pivots, pontos extremos adjacentes, determinação de soluções factíveis. Variáveis artificiais, forma matricial do método Simplex.

IV —Optimização em R^N

Problemas sem restrições: Condições de optimalidade; Métodos guiados pelo gradiente, convergência e taxa de convergência. Procura de Fibonacci e Golden Section. Métodos de procura em linha: Regra de Armijo. Métodos de Steepest Descent e de Newton. Métodos Quasi-Newton; Métodos de direcções conjugadas. Métodos de gradiente condicionado e projectado. Maximização e minimização de funções convexas.

V — Problemas com restrições

Teoria dos Multiplicadores de Lagrange.Condições Necessárias para restrições do tipo igualdade; condições suficientes e análise de sensibilidade. Restrições do tipo desigualdade: Restrições lineares e dualidade. Métodos de Barreira e de Ponto Interior; Métodos de penalização e de Lagrangeana Aumentada: Introdução à Teoria da Dualidade.