Otimização Convexa

📚 Resumo do Conteúdo

Um curso e livro-texto abrangente de nível de pós-graduação que cobre a teoria, aplicações e algoritmos numéricos da otimização convexa. O foco está em reconhecer e formular problemas convexos em engenharia e ciências.

Domine a base matemática e os algoritmos práticos da otimização convexa para engenharia e ciência de dados.

Autor: Stephen Boyd, Lieven Vandenberghe

Agradecimentos: Apoiado parcialmente pela NSF, e por contribuições de alunos e colegas da Stanford e UCLA, incluindo menções especiais a Arkadi Nemirovski e Kishan Baheti.

🎯 Objetivos de Aprendizagem

1. Definir os componentes de um problema matemático de otimização, incluindo a função objetivo, restrições e variáveis.
2. Distinguir entre problemas de mínimos quadrados, programação linear e otimização convexa com base em suas propriedades matemáticas.
3. Comparar estratégias de otimização local e global e avaliar a complexidade computacional associada a cada uma.
4. Definir e distinguir conjuntos afins, conjuntos convexos e cones usando notação formal de combinação.
5. Identificar e representar conjuntos convexos padrão, incluindo bolas euclidianas, elipsoides, poliedros e o cone semi-definido positivo.
6. Aplicar operações que preservam a convexidade, como interseção, transformações afins e funções perspectivas, para verificar propriedades de conjuntos.
7. Identificar e aplicar operações que preservam a convexidade, incluindo o supremo pontual de funções afins e regras de composição vetorial.
8. Derivar o conjugado de Lagrange de várias funções e aplicar a desigualdade de Young.
9. Caracterizar a quasiconvexidade usando conjuntos subníveis e condições diferenciais de primeira e segunda ordem.
10. Formular e Transformar: Converter problemas de otimização brutos em formas convexas padrão usando variáveis de folga e eliminação de restrições.

🔹 Aula 1: Introdução à Otimização Matemática

Visão Geral: Esta aula apresenta os conceitos fundamentais da otimização matemática, passando da formulação geral do problema até classes específicas e solucionáveis, como mínimos quadrados e programação linear. Destaca-se a distinção crítica entre otimização convexa e não convexa, detalhando como métodos convexos servem como um "ponto de inflexão" confiável para eficiência e fornecem ferramentas essenciais para resolver problemas não lineares mais difíceis.

Resultados de Aprendizagem:

• Definir os componentes de um problema matemático de otimização, incluindo a função objetivo, restrições e variáveis.
• Distinguir entre problemas de mínimos quadrados, programação linear e otimização convexa com base em suas propriedades matemáticas.
• Comparar estratégias de otimização local e global e avaliar a complexidade computacional associada a cada uma.

🔹 Aula 2: Teoria dos Conjuntos Convexos

Visão Geral: Esta aula explora a geometria fundamental da otimização, passando de estruturas lineares básicas para as propriedades complexas de conjuntos convexos e cones. Aborda as definições matemáticas de conjuntos afins e convexos, examina geometrias específicas como poliedros e cones semi-definidos positivos, e detalha as operações e teoremas que permitem aos pesquisadores caracterizar e manipular conjuntos convexos em espaços de alta dimensão.

Resultados de Aprendizagem:

• Definir e distinguir entre conjuntos afins, conjuntos convexos e cones usando notação formal de combinação.
• Identificar e representar conjuntos convexos padrão, incluindo bolas euclidianas, elipsoides, poliedros e o cone semi-definido positivo.
• Aplicar operações que preservam a convexidade, como interseção, transformações afins e funções perspectivas, para verificar propriedades de conjuntos.

🔹 Aula 3: Funções Convexas e Propriedades

Visão Geral: Esta aula explora operações avançadas que preservam a convexidade, como supremos pontuais e regras específicas de composição, e introduz a função conjugada de Lagrange. Estende o conceito de convexidade para funções quasiconvexas e log-concavas, além de examinar a convexidade com respeito a desigualdades generalizadas e propriedades matriciais específicas como o complemento de Schur. Esses conceitos formam a base matemática para identificar e formular problemas de otimização complexos.

Resultados de Aprendizagem:

• Identificar e aplicar operações que preservam a convexidade, incluindo o supremo pontual de funções afins e regras de composição vetorial.
• Derivar o conjugado de Lagrange de várias funções e aplicar a desigualdade de Young.
• Caracterizar a quasiconvexidade usando conjuntos subníveis e condições diferenciais de primeira e segunda ordem.

🔹 Aula 4: Formulação de Problemas de Otimização Convexa

Visão Geral: Esta aula aborda a estrutura formal e a transformação de problemas de otimização convexa, desde formas padrão e condições de otimalidade até classes específicas de problemas como Programação Linear (PL), Quadrática (PQ) e Programação Semidefinida (PSD). Os alunos aprenderão a identificar otimalidade global, usar o método da bissetriz para problemas quasiconvexos e aplicar a scalarização à otimização vetorial multicritério.

Resultados de Aprendizagem:

• Formular e Transformar: Converter problemas de otimização brutos em formas convexas padrão usando variáveis de folga e eliminação de restrições.
• Analisar a Otimalidade: Aplicar o critério de otimalidade baseado no gradiente para determinar se um ponto é globalmente ótimo.
• Classificar e Resolver: Distinguir entre PL, PQ, SOCP, GP e PSD, e aplicar métodos especializados como o Método da Bisseção para funções quasiconvexas.

🔹 Aula 5: Dualidade de Lagrange e Condições KKT

Visão Geral: Esta aula explora a teoria fundamental da dualidade de Lagrange, passando da definição da função dual de Lagrange à formulação do problema dual. Aborda a lacuna crítica entre valores ótimos primal e dual, as interpretações geométricas e jogísticas dessas relações, e as condições de Karush-Kuhn-Tucker (KKT) que caracterizam soluções ótimas. Finalmente, a aula estende esses conceitos à análise de sensibilidade e preços sombra.

Resultados de Aprendizagem:

• Derivar a função dual de Lagrange e formular o problema dual para diversos problemas de otimização.
• Avaliar a relação entre problemas primal e dual usando dualidade fraca e forte, bem como a condição de qualificação de Slater.
• Aplicar as condições de otimalidade KKT para resolver e verificar soluções ótimas em problemas convexos e não convexos.

🔹 Aula 6: Aproximação, Ajuste e Regularização

Visão Geral: Esta aula explora as bases matemáticas e aplicações práticas da aproximação de soluções para sistemas de equações lineares e ajuste de funções a dados. Cobrem-se aproximações baseadas em normas, incluindo funções de penalidade e regularização para lidar com outliers e esparsidade, e técnicas de otimização robusta para tratar incertezas nos dados. Além disso, detalha-se o ajuste de funções sob restrições específicas, como convexidade e monotonicidade.

Resultados de Aprendizagem:

• Formular e resolver problemas de aproximação por norma e interpretar as diferenças geométricas e estatísticas entre os métodos de mínimos quadrados, Chebyshev e L1.
• Projetar e implementar modelos de aproximação regularizada para alcançar trade-offs entre erro residual, magnitude da solução e esparsidade.
• Construir frameworks de aproximação robusta para considerar incertezas na matriz de dados.

🔹 Aula 7: Estimação e Inferência Estatística

Visão Geral: Esta aula explora a intersecção entre inferência estatística e otimização convexa. Foca-se na formulação de problemas de estimação — incluindo máxima verossimilhança, estimação não paramétrica de distribuições e projeto ótimo de detectores — como programas convexos. Os alunos aprenderão a usar otimização para encontrar parâmetros e projetar experimentos informativos.

Resultados de Aprendizagem:

• Formular e resolver problemas de Estimação da Máxima Verossimilhança (EMV) e Regressão Logística como tarefas de otimização convexa.
• Projetar detectores ótimos usando Programação Linear (PL) e interpretar Características Operacionais do Receptor (ROC).
• Aplicar técnicas de estimação não paramétrica, incluindo Entropia Máxima e minimização da divergência de Kullback-Leibler.

🔹 Aula 8: Problemas Geométricos e Classificação

Visão Geral: Esta aula explora a aplicação da otimização convexa a problemas geométricos, incluindo a projeção de pontos sobre conjuntos, cálculo de distâncias entre conjuntos e caracterização de centros de conjuntos. Aprofunda ainda esses princípios geométricos em tarefas do mundo real, como classificação linear e não linear, posicionamento ótimo de instalações e planejamento de layout usando programação geométrica.

Resultados de Aprendizagem:

• Formular e resolver problemas de projeção e distância entre conjuntos convexos usando as condições KKT e representações duais.
• Aproximar conjuntos convexos complexos usando elipsoides de volume extremal e identificar seus fatores de eficiência.
• Calcular diversos centros de conjuntos e aplicá-los à discriminação e classificação robustas.

🔹 Aula 9: Algoritmos de Minimização Sem Restrições

Visão Geral: Esta aula cobre os fundamentos teóricos e implementações algorítmicas da minimização sem restrições para funções convexas. Detalha métodos de descida que vão do Gradiente de Primeira Ordem ao Método de Newton de Segunda Ordem. Uma parte significativa é dedicada à análise de convergência, focando em convexidade forte e a teoria invariante afim da auto-concordância.

Resultados de Aprendizagem:

• Definir convexidade forte e utilizar suas implicações para fornecer limites superiores sobre subotimalidade e distância até o otimizador.
• Comparar e contrastar o Gradiente Descendente com o Descenso Mais Acentuado sob as normas Euclidiana, Quadrática e L1.
• Calcular o passo de Newton e a diminuição de Newton, explicando por que o método de Newton é invariante afim.

🔹 Aula 10: Minimização com Restrições de Igualdade

Visão Geral: Esta aula explora métodos para resolver problemas de otimização convexa com restrições lineares de igualdade. Foca-se na derivação e implementação do passo de Newton, comparando métodos de início viável e inviável, e interpretando esses passos dentro de um framework primal-dual. Ênfase especial é dada à implementação numérica eficiente via eliminação bloco do sistema KKT.

Resultados de Aprendizagem:

• Calcular e interpretar o passo de Newton e a diminuição para problemas com restrições de igualdade.
• Demonstrar a equivalência entre o método de Newton com restrições de igualdade e a eliminação dessas restrições.
• Implementar o método de Newton com início inviável e explicar sua propriedade de redução dos resíduos primal-dual.

🔹 Aula 11: Métodos de Ponto Interior

Visão Geral: Esta aula aborda os métodos de ponto interior, que resolvem problemas de otimização convexa com restrições de desigualdade aplicando o método de Newton a uma sequência de problemas com restrições de igualdade. O núcleo envolve funções-barreira logarítmicas, rastreando uma trajetória central rumo à solução ótima, e utilizando frameworks primal-dual para aumentar eficiência e robustez.

Resultados de Aprendizagem:

• Definir e construir funções-barreira logarítmicas e caracterizar a trajetória central e seus pontos duais associados.
• Implementar o método barreira, incluindo o trade-off entre passos de centrificação e iterações externas.
• Formular e resolver problemas de fase I de viabilidade para encontrar pontos de partida estritamente viáveis.