Programação Não Linear

Programação Não Linear (PNL) é um ramo da programação matemática e da pesquisa operacional que lida com problemas de otimização nos quais a função objetivo e/ou pelo menos uma das restrições são funções não lineares das variáveis de decisão.

A PNL é uma generalização da programação linear e permite modelar uma classe mais ampla de sistemas e processos do mundo real, onde as dependências entre as variáveis não são estritamente proporcionais (ou seja, são descritas por curvas, e não por linhas retas).

Objeto e Aplicações

A programação não linear é utilizada para encontrar soluções ótimas em situações em que:

• A dependência do indicador-alvo (lucro, custos, eficiência, etc.) em relação aos parâmetros controláveis é não linear (por exemplo, retornos decrescentes de escala, custos quadráticos).
• As restrições sobre recursos ou processos tecnológicos são descritas por relações não lineares (por exemplo, reações químicas, leis físicas, dependências econômicas).

Os problemas de PNL surgem em muitas áreas:

• Engenharia de projetos (otimização de estruturas, processos).
• Economia e finanças (otimização de portfólio considerando o risco, modelagem de mercado).
• Tecnologia química (otimização dos regimes de reatores).
• Aprendizado de máquina (treinamento de redes neurais, método das máquinas de vetores de suporte).
• Gerenciamento de processos de produção. Logística (considerando custos não lineares).

Formulação Matemática do Problema de PNL

O problema geral de programação não linear é formulado da seguinte maneira:

É necessário encontrar um conjunto de valores para as variáveis de decisão que maximize ou minimize uma função objetivo não linear. Ao mesmo tempo, os valores das variáveis devem satisfazer um sistema de restrições, que podem ser expressas tanto na forma de desigualdades (por exemplo, "a quantidade A deve ser menor ou igual a B") quanto na forma de igualdades (por exemplo, "a quantidade C deve ser exatamente igual a D"). É importante que pelo menos uma das funções que descrevem o objetivo ou as restrições seja não linear. Frequentemente, são adicionadas condições de não negatividade das variáveis, ou seja, a exigência de que seus valores sejam maiores ou iguais a zero.

O conjunto de todos os conjuntos de valores das variáveis que satisfazem as restrições forma a região de soluções viáveis (RSV).

Diferenças em Relação à Programação Linear

A programação não linear difere significativamente da programação linear (PL):

• Não linearidade: A função objetivo ou as restrições (ou ambas) contêm dependências não lineares.
• Propriedades da RSV: A região de soluções viáveis na PNL pode ser não convexa (ao contrário da PL, onde a RSV é sempre um poliedro convexo).
• Propriedades do ótimo: A solução ótima na PNL não está necessariamente em um vértice da RSV; ela pode estar na fronteira ou no interior da região. Na PNL, podem existir ótimos locais que não são globais.
• Complexidade da solução: Os problemas de PNL são, em geral, significativamente mais complexos de resolver do que os problemas de PL. Não existe um algoritmo universal único, análogo ao método simplex, para todos os problemas de PNL.

Principais Dificuldades e Desafios da PNL

A resolução de problemas de programação não linear está associada a uma série de dificuldades:

• Presença de extremos locais: A maioria dos métodos de PNL garante encontrar apenas um ótimo local (uma solução que é a melhor em alguma vizinhança). A busca por um ótimo global (a melhor solução em toda a RSV) é uma tarefa complexa, especialmente para problemas não convexos.
• Não convexidade: Se o problema não for convexo (a função objetivo ou a RSV não são convexas), pode haver múltiplos ótimos locais, e os métodos de gradiente padrão podem ficar "presos" em um deles.
• Complexidade computacional: Os algoritmos para resolver PNL frequentemente exigem recursos computacionais significativamente maiores em comparação com a PL.

Classes Importantes de Problemas de PNL

Apesar da complexidade geral, existem subclasses importantes de problemas de PNL para as quais foram desenvolvidos métodos de solução eficazes:

• Programação convexa: Um problema de minimização de uma função convexa sobre um conjunto de soluções viáveis convexo (ou maximização de uma função côncava). Propriedade chave: qualquer mínimo local também é um mínimo global. Isso simplifica significativamente a busca pela solução ótima.
• Programação quadrática: A função objetivo é quadrática, e todas as restrições são lineares.
• Programação separável: A função objetivo e as restrições podem ser representadas como somas de funções, cada uma dependendo de apenas uma variável.

Métodos de Solução de Problemas de PNL

Métodos de solução de problemas de programação não linear (PNL)

I. Métodos de otimização irrestrita (otimização sem restrições):

• Métodos de gradiente (método da descida mais íngreme, método dos gradientes conjugados);
• Método de Newton e métodos quasi-Newton (por exemplo, BFGS);
• Métodos que utilizam aproximação da Hessiana.

II. Métodos de otimização restrita (otimização com restrições):

• Métodos de transformação:
  • Método das funções de penalidade (penalty methods);
  • Método das funções de barreira (barrier methods).
• Métodos de busca direta de direções:
  • Método das direções viáveis.
• Métodos baseados em condições de otimalidade:
  • Métodos de Karush-Kuhn-Tucker (condições KKT);
  • Método dos multiplicadores de Lagrange.
• Métodos iterativos:
  • Programação Quadrática Sequencial (SQP);
  • Métodos de pontos interiores.

III. Métodos de otimização global:

• Métodos heurísticos e meta-heurísticos:
  • Algoritmos genéticos;
  • Recozimento simulado;
  • Busca tabu (tabu search).
• Métodos determinísticos:
  • Ramificação e limite (branch and bound);
  • Algoritmos de otimização global para problemas com estrutura especial.

Ver também

• Pesquisa operacional
• Otimização
• Programação linear
• Programação convexa
• Função objetivo
• Restrições
• Região de soluções viáveis

Literatura

• Bazaraa, M.S., Shetty, C.M. Programação Não Linear: Teoria e Algoritmos. — Moscou: Mir, 1982.
• Fiacco, A.V., McCormick, G.P. Programação Não Linear: Métodos de Minimização Irrestrita Sequencial. — Moscou: Mir, 1972.
• Himmelblau, D.M. Programação Não Linear Aplicada. — Moscou: Mir, 1975.
• Nocedal, Jorge; Wright, Stephen J. Numerical Optimization. — Springer, 2006. (2nd ed.)