Programação Não Linear
- Proposto por
- Jorge Nocedal & Stephen Wright
- Ano
- 2006
- Tipo
- Continuous mathematical optimization
- Família
- Mathematical programming
Este texto é uma tradução automática e ainda não foi revisado. Ler o original em inglês
O que ele faz?
Programação não linear (PNL) é um ramo da otimização matemática que lida com problemas nos quais a função objetivo ou pelo menos uma restrição é não linear.
Formalizada de forma abrangente por Jorge Nocedal e Stephen Wright em seu texto seminal de 2006, a PNL engloba algoritmos baseados em gradiente — incluindo programação quadrática sequencial (PQS), métodos de pontos interiores e abordagens quase-Newton — para encontrar soluções ótimas local ou globalmente para problemas de decisão contínuos que surgem em engenharia, economia e ciências físicas.
A intuição por trás do método
Imagine descer uma paisagem montanhosa e encoberta por neblina, permanecendo dentro de uma região cercada. Você não consegue ver todo o terreno, então sente a inclinação sob seus pés (gradiente), ajusta a direção do seu passo para descer a colina e verifica a cada movimento se não cruzou a cerca (restrições). Se a cerca se curva ou as colinas se sobrepõem, caminhos retos simples não funcionarão — você deve curvar seu caminho. A programação não linear formaliza exatamente esse processo, substituindo a caminhada intuitiva por regras de tamanho de passo e direção matematicamente rigorosas.
História
Os fundamentos teóricos da programação não linear remontam às condições KKT derivadas por Karush (1939) e Kuhn e Tucker (1951). Algoritmos práticos aceleraram durante as décadas de 1960-1980 com o desenvolvimento de métodos PQS, abordagens de Lagrangiano aumentado e atualizações quase-Newton, incluindo BFGS (1970). A segunda edição de 2006 de Numerical Optimization de Nocedal e Wright tornou-se uma referência definitiva, sintetizando a teoria de convergência, os frameworks de busca linear e região de confiança, e os métodos de pontos interiores em um tratamento moderno coerente.
Quando usar
Use programação não linear quando o objetivo ou as restrições não podem ser linearizados sem perda material de precisão e as variáveis de decisão são contínuas. Configurações típicas incluem projeto de engenharia com restrições de leis físicas, otimização de portfólio com medidas de risco não lineares e regressão com formas de modelo não lineares. As principais suposições são que f e c são pelo menos duas vezes continuamente diferenciáveis (para resolvedores baseados em gradiente) e que as qualificações de restrição são válidas. Quando as variáveis são inteiras, aplicam-se extensões de programação não linear inteira mista (PNLIM). Para problemas convexos, os métodos de pontos interiores garantem a otimalidade global; para problemas não convexos, existem apenas garantias locais.
Limitações e considerações
- Problemas não convexos oferecem apenas garantias de otimalidade local; soluções globais exigem estratégias adicionais de busca global.
- Exige que o objetivo e as restrições sejam suaves (pelo menos diferenciáveis); problemas não suaves precisam de métodos subdiferenciais especializados.
- O custo computacional cresce substancialmente com o tamanho do problema quando a avaliação exata do Hessiano é necessária.
- As qualificações de restrição podem falhar (por exemplo, em pontos viáveis degenerados), fazendo com que as condições KKT percam seu fundamento teórico.
As condições da fonte não substituem a revisão científica independente nem a validação por um motor de análise.
Pontos fortes
- Lida com uma ampla classe de problemas do mundo real onde aproximações lineares ou quadráticas são insuficientes.
- Teoria algorítmica madura com garantias de convergência bem estudadas para instâncias convexas.
- Resolvedores eficientes baseados em gradiente (PQS, ponto interior) escalam para milhares de variáveis na prática.
- A estrutura unificada do Lagrangiano acomoda naturalmente restrições mistas de igualdade e desigualdade.
Aplicações
- Engenharia estrutural e aeroespacial: minimização de peso sujeita a restrições de tensão e deflexão.
- Gestão de portfólio: maximização do retorno esperado sujeita a um orçamento de variância (risco) não linear.
- Projeto de processo químico: otimização do rendimento do reator sujeita a restrições termodinâmicas e de segurança.
- Aprendizado de máquina: treinamento de redes neurais e modelos de kernel via resolvedores de PNL irrestritos ou restritos.
- Sistemas de energia: problemas de fluxo de potência ótimo no despacho da rede elétrica com restrições físicas não lineares.
Como funciona
Como funciona
O analista define um objetivo escalar f(x) a ser minimizado ou maximizado sobre as variáveis de decisão x em R^n, juntamente com restrições de igualdade c_i(x) = 0 e restrições de desigualdade c_j(x) >= 0. Identificar quais restrições estão ativas em uma solução candidata e se as condições de regularidade (qualificações de restrição) são válidas é crítico nesta fase e determina qual teoria de otimalidade se aplica.
Fórmula
\min_{x \in \mathbb{R}^n} f(x) \quad \text{s.t.} \quad c_i(x) = 0,\; i \in \mathcal{E};\quad c_j(x) \ge 0,\; j \in \mathcal{I}As condições de Karush-Kuhn-Tucker (KKT) fornecem condições necessárias de primeira ordem para um ótimo local. Elas exigem estacionaridade do Lagrangiano, folga complementar para multiplicadores de desigualdade (lambda_j c_j = 0), viabilidade dual (lambda_j >= 0) e viabilidade primal. Algoritmos constroem iterativamente iterados que satisfazem essas condições de forma progressivamente mais rigorosa, com condições de suficiência de segunda ordem confirmando que um ponto estacionário é de fato um mínimo local.
Fórmula
\nabla f(x^*) - \sum_{i \in \mathcal{E} \cup \mathcal{I}} \lambda_i \nabla c_i(x^*) = 0, \quad \lambda_j c_j(x^*) = 0, \quad \lambda_j \ge 0 \; \forall j \in \mathcal{I}A cada iteração k, um algoritmo calcula uma direção de busca p_k — tipicamente via uma aproximação quase-Newton B_k do Hessiano (por exemplo, BFGS) ou um sistema exato de segunda derivada — e um comprimento de passo alpha_k que satisfaz as condições de Wolfe ou Armijo. Os métodos PQS resolvem um subproblema quadrático para p_k, enquanto os métodos de pontos interiores adicionam termos de barreira para lidar com restrições de desigualdade e conduzir os iterados para o interior viável.
Fórmula
x_{k+1} = x_k + \alpha_k p_k, \quad p_k = -B_k^{-1} \nabla f(x_k)A terminação ocorre quando tanto a norma do gradiente do Lagrangiano quanto a violação máxima da restrição caem abaixo das tolerâncias prescritas (epsilon e delta). Como a PNL é geralmente não convexa, os algoritmos podem convergir para ótimos locais; múltiplos reinícios a partir de diferentes pontos de partida ou estratégias de busca global (branch-and-bound, multistart) são recomendados quando a otimalidade global é exigida.
Fórmula
\|\nabla f(x_k)\| \le \epsilon \quad \text{and} \quad \max_{i} |c_i(x_k)| \le \deltaErros comuns
- Ignorar as qualificações de restrição e aplicar cegamente as condições KKT em pontos degenerados ou inviáveis leva a soluções espúrias.
- Usar variáveis mal escalonadas causa aproximações hessianas mal condicionadas e convergência lenta ou falha.
- Aceitar o primeiro mínimo local encontrado sem múltiplos reinícios em configurações não convexas pode perder significativamente o ótimo global.
- As aproximações de gradiente por diferenças finitas introduzem erro numérico; a diferenciação analítica ou automática é fortemente preferida.
Perguntas frequentes
Todo programa linear é também um programa não linear?
Sim. A programação linear é um caso especial de PNL onde tanto o objetivo quanto todas as restrições são afins. No entanto, a PL admite os algoritmos simplex e de pontos interiores que exploram a linearidade e são muito mais eficientes do que os resolvedores de PNL gerais; usar um resolvedor de PNL geral para uma PL é um desperdício, mas matematicamente válido.
Quando posso confiar que um ponto KKT é um mínimo global?
Quando a PNL é convexa — significando que f é convexa e o conjunto viável é um conjunto convexo — qualquer ponto KKT é um mínimo global. Para problemas não convexos, essa garantia não se mantém, e um ponto KKT é apenas um mínimo local (sob condições de suficiência de segunda ordem). Métodos de otimização global, como branch-and-bound ou relaxações convexas, são necessários caso contrário.
Qual a diferença entre os métodos PQS e de pontos interiores?
PQS resolve iterativamente subproblemas de programação quadrática que aproximam a PNL localmente e é frequentemente preferido para problemas de pequeno a médio porte com muitas restrições ativas. Os métodos de pontos interiores (barreira) permanecem estritamente dentro da região viável e tendem a escalar melhor para problemas esparsos grandes. Ambos convergem superlinearmente sob condições de regularidade apropriadas.
Métodos relacionados
Fontes
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
ISBN: 978-0-387-30303-1Copiado.