Disciplina Curricular
Optimização e Algoritmos OA
Mestrado Integrado em Engenharia Electrotécnica e de Computadores - MEEC 2006
Contextos
Grupo: MEEC 2006 > 2º Ciclo > Área de Especialização > Área de Especialização Secundária > Sistemas, Decisão e Controlo
Período:
Grupo: MEEC 2006 > 2º Ciclo > Área de Especialização > Área de Especialização Principal > Computadores > Formação Complementar a Computadores
Período:
Grupo: MEEC 2006 > 2º Ciclo > Área de Especialização > Área de Especialização Principal > Telecomunicações > Formação Complementar a Telecomunicações
Período:
Grupo: MEEC 2006 > 2º Ciclo > Área de Especialização > Área de Especialização Principal > Sistemas, Decisão e Controlo > Decisão e Controlo & Robótica
Período:
Grupo: MEEC 2006 > 2º Ciclo > Área de Especialização > Área de Especialização Principal > Electrónica > Formação Complementar a Electrónica
Período:
Peso
6.0 (para cálculo da média)
Objectivos
Conhecer os fundamentos da teoria e algoritmos para problemas de optimização linear e não linear, com ou sem restrições. Reconhecer propriedades dos problemas de optimização e desenvolver algoritmos eficientes para os resolver. Interpretar geometricamente os resultados teóricos. Aplicar a teoria em problemas práticos de engenharia. Aprender técnicas de transformação, reformulação e simplificação de problemas de optimização
Programa
Parte I: teoria e algoritmos para optimização sem restrições. Exemplos em engenharia. Conceitos gerais: minimizantes locais/globais, funções convexas. Condições necessárias e suficientes para optimalidade (1ª/2ª ordem). Algoritmos iterativos por pesquisa em linhas: as direcções de gradiente, quasi-Newton BFGS e Newton (puro e modificado) e a regra de Wolfe. Velocidade de convergência. Algoritmo de gradientes conjugados. Parte II: teoria e algoritmos para optimização com restrições. Exemplos em engenharia. Conceitos gerais: minimizantes locais e globais, programas convexos. Condições necessárias e suficientes de Karush-Kuhn-Tucker (KKT) para optimalidade (1ª/2ª ordem). Interpretação geométrica. Geometria dos programas lineares (poliedros, vértices,vértices adjacentes,etc). Teorema fundamental da programação linear. Algoritmo simplex. Dualidade para programas lineares. Métodos de ponto interior para programas convexos. Algoritmos para programas gerais (não-convexos): métodos de penalização e barreira. Parte III: Optimização em redes/grafos: algoritmos de caminho mínimo, problemas de fluxo máximo e fluxo de custo mínimo. Programação dinâmica. Teoria de Jogos: jogos estáticos e dinâmicos. Eficiência de algoritmos.
Metodologia de avaliação
A nota final (NF) é a média aritmética das notas dos 3 testes: NF = (NT1+NT2+NT3)/3 (NTm=nota do teste m). Para aprovação na disciplina é necessário que NF >= 9.5