Pós-graduação
  1. Introdução à análise real  1.1. Teoria dos conjuntos e lógica em análise real  1.1.1. Conjuntos e operações na teoria dos conjuntos e lógica em análise real  1.1.2. Relações e funções  1.1.3. Lógica e quantificadores  1.1.4. Cardinalidade dos conjuntos  1.2. Espaço métrico  1.2.1. Introdução aos conjuntos abertos e fechados em espaços métricos  1.2.2. Convergência de sequências em um espaço métrico  1.2.3. Função contínua em um espaço métrico  1.2.4. Compacidade e completude em espaços métricos na análise real  1.3. Sequências e séries  1.3.1. Convergência de sequências  1.3.2. Séries infinitas  1.3.3. Convergência uniforme  1.3.4. Séries de potências  1.4. Discriminação  1.4.1. Teorema do valor médio  1.4.2. Série de Taylor  1.4.3. Funções de várias variáveis  1.4.4. Derivada parcial  1.5. Integração  1.5.1. Integração de Riemann e Lebesgue  1.5.2. Integrais impróprias  1.5.3. Teoria da Medida: uma ferramenta fundamental na integração  1.5.4. Teorema de Fubini  1.6. Análise funcional  1.6.1. Compreendendo espaços de Banach  1.6.2. Espaços de Hilbert  1.6.3. Operadores em espaços  1.6.4. Teoria Espectral
  2. Álgebra Abstrata  2.1. Compreendendo grupos na álgebra abstrata  2.1.1. Definições e exemplos de grupos na álgebra abstrata  2.1.2. Homomorfismos de grupos  2.1.3. Introdução aos subgrupos normais  2.1.4. Teorema de Sylow  2.2. Anéis e campos  2.2.1. Ideais e anéis quocientes  2.2.2. Extensões de campos  2.2.3. Teoria de Galois  2.2.4. Anéis de polinômios  2.3. Introdução aos módulos em álgebra abstrata  2.3.1. Homomorfismo de Módulos  2.3.2. Módulos livres  2.3.3. Introdução aos produtos tensoriais  2.3.4. Sequência exata em módulos  2.4. Álgebra linear  2.4.1. Espaço vetorial  2.4.2. Autovalores e autovetores  2.4.3. Espaço de produto interno  2.4.4. Diagonalização
  3. Topologia  3.1. Topologia Geral  3.1.1. Conjuntos abertos e fechados  3.1.2. Compacidade e conexidade  3.1.3. Mapas contínuos  3.1.4. Axioma de separação  3.2. Topologia algébrica  3.2.1. Compreendendo grupos fundamentais em topologia algébrica  3.2.2. Homotopia e homologia  3.2.3. Complexo simplicial  3.2.4. Sequências exatas em homologia  3.3. Topologia Diferencial  3.3.1. Compreendendo variedades na topologia diferencial  3.3.2. Funções Suaves  3.3.3. Espaço tangente e cotangente  3.3.4. Feixes vetoriais
  4. Equações diferenciais  4.1. Equação diferencial ordinária  4.1.1. Equações de primeira ordem  4.1.2. Equações lineares de segunda ordem  4.1.3. Sistemas de equações diferenciais  4.1.4. Análise de estabilidade em equações diferenciais ordinárias  4.2. Equações diferenciais parciais  4.2.1. Classificação de PDE  4.2.2. Compreendendo séries de Fourier em equações diferenciais parciais  4.2.3. Introdução às funções de Green  4.2.4. Método de caracterização  4.3. Sistemas dinâmicos em equações diferenciais  4.3.1. Teoria da Sustentabilidade  4.3.2. Ciclos limite em sistemas dinâmicos  4.3.3. Teoria do caos  4.3.4. Teoria da bifurcação
  5. Probabilidade e estatística  5.1. Teoria da probabilidade  5.1.1. Variáveis aleatórias  5.1.2. Distribuições de probabilidade  5.1.3. Lei dos grandes números  5.1.4. Teorema Central do Limite  5.2. Inferência estatística  5.2.1. Teste de hipótese  5.2.2. Intervalo de confiança  5.2.3. Métodos bayesianos  5.2.4. Estimativa de máxima verossimilhança  5.3. Processos estocásticos  5.3.1. Cadeias de Markov  5.3.2. Movimento Browniano  5.3.3. Compreendendo os processos de Poisson  5.3.4. Martingales: Um estudo abrangente em probabilidade e estatística
  6. Análise numérica  6.1. Soluções numéricas de equações  6.1.1. Descoberta original  6.1.2. Métodos iterativos  6.1.3. Análise de convergência  6.1.4. Limites de erro em soluções numéricas de equações  6.2. Álgebra linear numérica  6.2.1. Fatoração de matrizes  6.2.2. Cálculo de autovalores  6.2.3. Matrizes esparsas  6.2.4. Técnicas de pré-condicionamento  6.3. Integração e diferenciação numéricas  6.3.1. Métodos de quadratura  6.3.2. Introdução às diferenças finitas  6.3.3. Análise de erro na integração e diferenciação numérica  6.3.4. Métodos adaptativos em integração e diferenciação numérica
  7. Análise complexa  7.1. Números complexos  7.1.1. Forma polar  7.1.2. Conjugados Complexos  7.1.3. Forma exponencial de números complexos  7.1.4. Raízes da unidade  7.2. Funções analíticas  7.2.1. Equações de Cauchy–Riemann  7.2.2. Séries de potências  7.2.3. Mapeamento conforme  7.2.4. Funções harmônicas  7.3. Integração no plano complexo  7.3.1. Teorema de Cauchy  7.3.2. Teorema do resíduo  7.3.3. Integração de contorno  7.3.4. Transformadas integrais
  8. Lógica Matemática e Fundamentos  8.1. Lógica proposicional  8.1.1. Tabelas de verdade  8.1.2. Equivalência lógica na lógica proposicional  8.1.3. Técnicas de prova em lógica proposicional  8.1.4. Solução na lógica proposicional  8.2. Lógica de predicados  8.2.1. Quantificadores na lógica de predicados  8.2.2. Sistemas formais na lógica de predicados  8.2.3. Completude e correção  8.2.4. Teoria dos modelos  8.3. Teoria dos conjuntos  8.3.1. Cardinalidade e ordinalidade  8.3.2. Sistemas axiomáticos  8.3.3. Compreendendo a teoria dos conjuntos de Zermelo-Fraenkel  8.3.4. Forças na teoria dos conjuntos
  9. Personalização  9.1. Programação linear  9.1.1. Método simplex  9.1.2. Dualidade na programação linear  9.1.3. Análise de sensibilidade em programação linear  9.1.4. Métodos de ponto interior  9.2. Programação não linear  9.2.1. Descida do Gradiente  9.2.2. Múltiplos de Lagrange  9.2.3. Otimização convexa  9.2.4. Programação quadrática  9.3. Otimização Combinatória  9.3.1. Algoritmos de grafos  9.3.2. Programação inteira  9.3.3. Fluxo de Rede  9.3.4. Algoritmos de aproximação
  10. Matemática discreta  10.1. Teoria dos grafos  10.1.1. Representação de grafos  10.1.2. Planicidade e cor  10.1.3. Algoritmo de caminho mais curto  10.1.4. Fluxo de rede  10.2. Companheirismo  10.2.1. Percmutações e combinações  10.2.2. Função geradora  10.2.3. Relação de recorrência  10.2.4. Compreendendo o Princípio da Inclusão-Exclusão  10.3. Criptografia  10.3.1. Aplicações da teoria dos números na criptografia  10.3.2. Criptografia Simétrica e Assimétrica  10.3.3. RSA e criptografia de curva elíptica  10.3.4. Criptografia pós-quântica

Pós-graduação → Personalização → Programação não linear ↓


Programação quadrática


A Programação Quadrática (QP) é um tipo especial de problema de otimização matemática. É um tópico importante no campo da otimização, amplamente utilizado em muitas outras aplicações práticas, como finanças, aprendizado de máquina e sistemas de controle. O objetivo deste guia é explicar os conceitos, a matemática e as aplicações da Programação Quadrática em termos simples.

O que é programação quadrática?

A programação quadrática lida com a otimização (minimização ou maximização) de uma função objetivo quadrática sujeita a restrições lineares. Vamos detalhar:

  • A função objetivo quadrática é uma função matemática onde o termo com a maior potência é o quadrado. Em forma geral, é escrita como:
    f(x) = 0.5 * x t qx + c t x,
    onde Q é uma matriz simétrica nxn, c é um vetor de n números reais, e x é um vetor de variáveis.
  • Restrições lineares são restrições que limitam os valores que uma variável pode assumir. Sua forma geral é:
    a ≤ b,
    onde A é uma matriz, x é um vetor de variáveis, e b é um vetor de restrições. As restrições podem ser igualdades ou desigualdades.

Representação matemática

A forma padrão de um problema de programação quadrática é a seguinte:

Minimizar: f(x) = 0.5 * x T Qx + c T x

sujeito a:
    axis ≤ b
    x = d
    x ≥ 0

Aqui:

  • x T é a transposta do vetor x.
  • Q é uma matriz positiva semi-definida que garante que o problema seja convexo.
  • A e E são matrizes que representam restrições de desigualdade e igualdade, respectivamente.
  • b e d são vetores que representam constantes para as restrições de desigualdade e igualdade, respectivamente.

Compreensão por meio de exemplos simples

Para melhor compreensão, vejamos um simples problema de programação quadrática.

Exemplo 1: Otimização simples de portfólio

Imagine que você tem duas opções de investimento e precisa decidir quanto investir em cada opção. O objetivo é minimizar o risco (variância) enquanto se alcança um determinado retorno esperado. A função quadrática pode representar a variância (risco) do portfólio.

Suponha que a variância possa ser representada pela seguinte equação quadrática:

Minimizar: f(x) = 0.5 * (x 1 2 + 2x 1 x 2 + x 2 2 )

sujeito a:
    x 1 + x 2 = 1 (a soma das alocações deve ser 1)
    x 1 ≥ 0
    x 2 ≥ 0

O problema nos pede para encontrar os valores de x 1 e x 2 que minimizam o risco, desde que sua soma seja 1 e ambos não sejam negativos.

Visualização da programação quadrática

Olhar para funções quadráticas e restrições pode ajudar a entender o espaço de solução de um problema:


    
    
    
    região viável

Na visualização acima, o círculo azul claro representa a natureza quadrática da função. As linhas vermelhas representam as restrições. A região viável (onde as soluções podem existir) é a intersecção das restrições e dos valores possíveis da função objetivo.

Resolvendo problemas de programação quadrática

Os problemas de programação quadrática podem ser resolvidos usando diferentes métodos, dependendo do tamanho e da complexidade do problema. Alguns dos métodos comuns são os seguintes:

  • Métodos analíticos: Adequados para problemas pequenos, esses métodos envolvem calcular derivadas e igualá-las a zero para encontrar o ponto mínimo.
  • Métodos numéricos: Para problemas maiores, são utilizados métodos numéricos, como o método do conjunto ativo ou o método do ponto interior. Esses métodos começam buscando dentro da região viável para encontrar a solução ótima.
  • Ferramentas de software: Ferramentas como MATLAB, CVX e a biblioteca SciPy do Python permitem a fácil configuração e solução de problemas QP.

Aplicações da programação quadrática

A Programação Quadrática é utilizada em várias indústrias e campos devido à sua capacidade de lidar de forma eficiente com relações quadráticas e restrições.

Finanças

Em finanças, QP é usado para otimização de portfólio, onde a variância (ou risco) dos retornos do portfólio é minimizada, dadas restrições como alcançar um nível desejado de retorno.

Aprendizado de máquina

No aprendizado de máquina, QP é utilizado em máquinas de vetores de suporte para tarefas de classificação, onde ajuda a encontrar o hiperplano de maior margem que separa diferentes classes.

Sistema de controle

A Programação Quadrática também é utilizada no controle preditivo de modelos (MPC), onde otimiza as entradas de controle sujeitas a dinâmicas do sistema e restrições para alcançar o desempenho desejado.

Entendimento matemático profundo

Para obter um entendimento mais formal da Programação Quadrática, vamos examinar alguns aspectos matemáticos:

Convexidade

A matriz Q garante que a função quadrática seja convexa. Funções convexas têm a propriedade especial de que qualquer mínimo local também é um mínimo global, o que simplifica o processo de resolução de problemas.

Para uma matriz ser positiva semi-definida (PSD), todos os seus autovalores devem ser não negativos. Essa propriedade garante a convexidade.

Problema dual

A programação quadrática também tem um problema de dualidade, que é semelhante à programação linear. A resolução do problema de dualidade muitas vezes fornece insights ou soluções numéricas alternativas.

O dual de um programa quadrático conecta-se ao problema original através de variáveis duais e oferece limites na função objetivo do problema original.

Conclusão

A Programação Quadrática é um método versátil e poderoso para otimização onde a função objetivo é quadrática e está sujeita a restrições lineares. Sua capacidade de lidar com problemas grandes e complexos a torna inestimável em muitos campos. Ao entender os conceitos básicos, aplicações e técnicas de solução, pode-se enfrentar efetivamente os desafios da programação quadrática em cenários do mundo real.


Pós-graduação → 9.2.4


U
username
0%
concluído em Pós-graduação

← Anterior (9.2.3)
Otimização convexa
Próximo (9.3) →
Otimização Combinatória

Comentários 



Programação quadrática

https://www.buddymath.com/g/9.2.4?bmal=pt