Pular para o conteúdo principal

Programação Não-Linear

Introdução​

A Programação Não Linear (PNL) é um processo de otimização em que pelo menos uma das restrições ou a função objetivo é não linear. Esse campo abarca uma vasta gama de problemas que surgem em diversos domínios, desde a engenharia até a economia. Esta dissertação procura elucidar as principais características, métodos de resolução, desafios e aplicações da PNL.

Definição e Características

A PNL lida com funções objetivo e/ou restrições que são não lineares. Em contraste com a Programação Linear, onde a relação entre as variáveis é linear, a PNL permite relações mais complexas e realistas entre as variáveis.

Exemplo de Função Não Linear:

Ótimo Global e Ótimo Local​

Introdução

Quando estamos resolvendo problemas de otimização não linear, uma questão fundamental é entender a diferença entre um ótimo local e um ótimo global. Vamos definir cada um deles e discutir suas características.

Ótimo Local​

Um ótimo local é um ponto onde a função objetivo atinge um valor mínimo ou máximo em relação aos pontos vizinhos. Matematicamente, dado uma função , um ponto é um mínimo local se existe um valor tal que:

Da mesma forma, será um máximo local se:

Ótimo Global​

Um ótimo global é um ponto onde a função objetivo atinge seu valor mínimo ou máximo absoluto em todo o domínio de definição. Para um mínimo global, o ponto satisfaz:

onde é o domínio da função. Para um máximo global, temos:

Comparação entre Ótimo Local e Ótimo Global

  1. Existência: Em muitos casos, existem vários ótimos locais mas apenas um ótimo global.
  2. Dificuldade de encontrar: Encontrar um ótimo global é geralmente mais difícil do que encontrar um ótimo local.
  3. Algoritmos: Alguns algoritmos são capazes de encontrar apenas ótimos locais, enquanto outros (muitas vezes mais computacionalmente intensivos) podem encontrar ótimos globais.

Exemplo: Função de Rosenbrock​

A função de Rosenbrock, muitas vezes usada para testar algoritmos de otimização, é definida como:

Esta função tem um único mínimo global no ponto , onde , mas pode ter vários mínimos locais dependendo dos parâmetros e .

Otimização Convexa​

O que é Otimização Convexa?

A otimização convexa é um subcampo especial da otimização matemática que lida com problemas convexos. Um problema de otimização é dito convexo se o conjunto viável (domínio) é um conjunto convexo e a função objetivo é uma função convexa.

Uma função é convexa se para todos no domínio e para todono intervalo, temos:

Relação com Ótimos Locais e Globais

Otimização Convexa

  1. Unicidade do ótimo: Em problemas de otimização convexa, qualquer mínimo local é também um mínimo global. Isso significa que se você encontrar um mínimo local, você resolveu efetivamente todo o problema.
  2. Eficiência computacional: Algoritmos para otimização convexa, como o método do gradiente, são geralmente mais eficientes em encontrar a solução ótima global.

Otimização Não-Linear (não necessariamente convexa)

  1. Múltiplos ótimos locais: Como discutido anteriormente, problemas não-lineares podem ter múltiplos ótimos locais, tornando mais difícil encontrar o ótimo global.
  2. Dificuldade computacional: Algoritmos para encontrar ótimos globais em problemas não-lineares são frequentemente mais computacionalmente intensivos e complexos.

Exemplos

  • Quadrático convexo: é uma função convexa simples com um único mínimo global.
  • Rosenbrock: Como mencionado antes, a função de Rosenbrock é um exemplo clássico de uma função que não é convexa e que pode ter múltiplos mínimos locais, dependendo dos parâmetros.

Conclusão

A otimização convexa oferece uma série de propriedades e métodos eficientes que tornam mais fácil encontrar soluções ótimas globais. No entanto, muitos problemas do mundo real são não-lineares e não-convexos, exigindo técnicas mais avançadas para encontrar ótimos globais. Entender a diferença entre problemas convexos e não-convexos pode ajudar a escolher o algoritmo de otimização mais adequado para uma dada aplicação.

Ponto Interior​

Método do Ponto Interior​

O Método do Ponto Interior é um algoritmo de otimização que resolve problemas de programação linear e não-linear, abordando-os de "dentro para fora". Em vez de caminhar ao longo das fronteiras da região factível como o método Simplex, ele se move através do interior da região factível.

Conceito Fundamental​

A ideia central é começar de um ponto estritamente interior (um ponto que satisfaça todas as restrições de forma estrita) e seguir uma trajetória que permaneça no interior até chegar a uma solução ótima. Suponhamos que temos um problema de programação linear na forma padrão:

Barreira Logarítmica​

O Método do Ponto Interior frequentemente utiliza uma "função barreira" para garantir que os pontos permaneçam no interior da região factível. A função barreira logarítmica é comumente usada e tem a forma:

A função objetivo modificada torna-se:

onde é um parâmetro de barreira que controla a "força" da barreira. À medida que se aproxima de zero, a solução da função objetivo modificada converge para a solução do problema original.

Etapas do Método​

  1. Escolha do Ponto Inicial: Selecione um ponto estritamente interior, isto é, um ponto que satisfaça e.

  2. Direção de Pesquisa: Utilizando o gradiente e a Hessiana da função objetivo modificada , determine a direção na qual a função diminui mais rapidamente.

  3. Passo ao Longo da Direção: Utilize métodos como backtracking line search para encontrar um tamanho de passo que minimiza .

  4. Iteração: Atualize e repita as etapas 2 e 3 até que os critérios de parada sejam atendidos, como , onde é uma tolerância pequena.

O Método do Ponto Interior é particularmente útil para problemas de grande escala e para problemas onde a região factível é complexa. Ele é flexível e pode ser adaptado para uma ampla variedade de problemas de otimização.

Método do Ponto Interior Primal-Dual​

O Método do Ponto Interior Primal-Dual é uma extensão natural que combina os conceitos de métodos de pontos interiores e dualidade. Este método é altamente eficaz para resolver problemas de programação linear e problemas de otimização convexa mais gerais. Ele busca solucionar simultaneamente tanto o problema primal como o dual, o que frequentemente resulta em melhor eficiência computacional.

Conceito Básico​

Considere o problema de programação linear na forma padrão, o problema primal:

E o problema dual associado:

O Método do Ponto Interior Primal-Dual inicia com pontos interiores factíveis tanto para o problema primal como para o dual e os atualiza simultaneamente.

Função de Barreira Logarítmica e o Primal-Dual​

Assim como no Método do Ponto Interior original, uma função de barreira logarítmica é usada para garantir que as soluções permaneçam no interior da região factível:

Neste caso, o objetivo é minimizar a função objetivo primal mais o termo de barreira, enquanto também se maximiza a função objetivo dual. A função Lagrangiana associada é:

Onde são as variáveis de folga associadas às restrições do problema dual, e é o parâmetro de barreira.

Algoritmo Básico​

  1. Inicialização: Escolha pontos iniciais , , que sejam estritamente interiores.

  2. Resolver o Sistema de Equações Karush-Kuhn-Tucker (KKT): Encontre as direções , , que minimizam a função Lagrangiana.

  3. Atualização dos Pontos: Use um tamanho de passo para atualizar os pontos .

  4. Verificação dos Critérios de Parada: Verifique se os critérios de parada foram atingidos; caso contrário, retorne ao passo 2.

  5. Atualização do Parâmetro de Barreira: Reduza e retorne ao passo 2.

O Método do Ponto Interior Primal-Dual é particularmente eficaz para grandes problemas de programação linear e otimização convexa, fornecendo uma abordagem mais eficiente e robusta em muitos casos.

SQP (Sequential Quadratic Programming)​

O SQP é um método iterativo para resolver problemas de programação não-linear. A ideia básica é resolver uma série de problemas de Programação Quadrática (QP) que aproximam o problema NLP original.

Algoritmo SQP

  1. Inicialização: Comece com um ponto inicial e defina parâmetros como tolerâncias.

  2. Linearização das Restrições e Objetivo: Aproxime as funções objetivo e de restrição usando expansões de Taylor de primeira e segunda ordem para formar um problema QP.

onde é uma aproximação da Hessiana de.

  1. Resolver o QP: Resolva o problema quadrático aproximado para obter uma direção de busca .

  2. Atualização: Atualize o ponto atual , onde é o tamanho do passo obtido por algum critério de busca em linha ou confiança.

  3. Convergência: Verifique a convergência. Se o algoritmo convergir, pare. Caso contrário, retorne ao passo 2.

Vantagens e Desvantagens

  • Vantagens: Eficiente para problemas grandes, aproveita a estrutura esparsa, é adequado para problemas com muitas restrições.

  • Desvantagens: Sensível à escolha do ponto inicial, pode ficar preso em mínimos locais, requer o cálculo de derivadas.