Skip to content
Voltar aos resultados

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

Tamanho da fonte

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

1

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}
2

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}
3

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)
4

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 \delta

Erros 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

  1. Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

    ISBN: 978-0-387-30303-1
    Copiado.