Programação não linear

Em matemática , a programação não linear ( PNL ) é o processo de resolução de um problema de otimização onde algumas das restrições ou a função objetivo são não lineares . Um problema de otimização é o de cálculo dos extremos (máximos, mínimos ou pontos estacionários) de uma função objetivo sobre um conjunto de variáveis ​​reais desconhecidas e condicionais à satisfação de um sistema de igualdades e desigualdades , denominadas coletivamente de restrições . É o subcampo da otimização matemática que trata de problemas que não são lineares.

Definição e discussão

Sejam n , m e p números inteiros positivos. Seja X um subconjunto de R n (geralmente restrito por caixa), sejam f , g i e h j funções com valor real em X para cada i em { 1 , ..., m } e cada j em { 1 , ..., p }, com pelo menos um de f , g i e h j sendo não linear.

Um problema de programação não linear é um problema de otimização da forma

Dependendo do conjunto de restrições, existem várias possibilidades:

  • problema viável é aquele para o qual existe pelo menos um conjunto de valores para as variáveis ​​de escolha que satisfazem todas as restrições.
  • um problema inviável é aquele para o qual nenhum conjunto de valores para as variáveis ​​de escolha satisfaz todas as restrições. Isto é, as restrições são mutuamente contraditórias e não existe solução; o conjunto viável é o conjunto vazio .
  • problema ilimitado é um problema viável para o qual a função objetivo pode ser melhor do que qualquer valor finito dado. Assim, não existe uma solução óptima, porque existe sempre uma solução viável que fornece um melhor valor da função objectivo do que qualquer solução proposta.

A maioria das aplicações realistas apresenta problemas viáveis, com problemas inviáveis ​​ou ilimitados vistos como uma falha de um modelo subjacente. Em alguns casos, problemas inviáveis ​​são resolvidos minimizando uma soma de violações de viabilidade.

Alguns casos especiais de programação não linear possuem métodos de solução especializados:

  • Se a função objetivo for côncava (problema de maximização) ou convexa (problema de minimização) e o conjunto de restrições for convexo , então o programa é chamado de convexo e métodos gerais de otimização convexa podem ser usados ​​na maioria dos casos.
  • Se a função objetivo for quadrática e as restrições forem lineares, serão utilizadas técnicas de programação quadrática .
  • Se a função objetivo for uma razão entre uma função côncava e uma função convexa (no caso de maximização) e as restrições forem convexas, então o problema pode ser transformado em um problema de otimização convexo usando técnicas de programação fracionária .

Aplicabilidade

Um problema não convexo típico é o de optimização dos custos de transporte através da selecção de um conjunto de métodos de transporte, um ou mais dos quais apresentam economias de escala , com várias conectividades e restrições de capacidade. Um exemplo seria o transporte de produtos petrolíferos, dada uma seleção ou combinação de oleoduto, navio-tanque ferroviário, navio-tanque rodoviário, barcaça fluvial ou navio-tanque costeiro. Devido ao tamanho econômico do lote, as funções de custo podem apresentar descontinuidades, além de mudanças suaves.

Na ciência experimental, algumas análises simples de dados (como ajustar um espectro com uma soma de picos de localização e forma conhecidas, mas de magnitude desconhecida) podem ser feitas com métodos lineares, mas em geral esses problemas também são não lineares. Normalmente, tem-se um modelo teórico do sistema em estudo com parâmetros variáveis ​​e um modelo do experimento ou experimentos, que também podem ter parâmetros desconhecidos. Tenta-se encontrar o melhor ajuste numericamente. Neste caso, muitas vezes deseja-se uma medida da precisão do resultado, bem como o melhor ajuste em si.

Métodos para resolver um programa não linear geral

Métodos analíticos

Sob diferenciabilidade e qualificações de restrição , as condições de Karush – Kuhn – Tucker (KKT) fornecem as condições necessárias para que uma solução seja ótima. Se algumas das funções não forem diferenciáveis, versões subdiferenciais das condições de Karush – Kuhn – Tucker (KKT) estarão disponíveis. [1]

Sob convexidade, as condições KKT são suficientes para um ótimo global . Sem convexidade, estas condições são suficientes apenas para um ótimo local . Em alguns casos, o número de ótimos locais é pequeno, e pode-se encontrar todos eles analiticamente e encontrar aquele para o qual o valor objetivo é menor. [2] : Seção 5 

Métodos numéricos

Na maioria dos casos realistas, é muito difícil resolver analiticamente as condições KKT e, portanto, os problemas são resolvidos usando métodos numéricos . Esses métodos são iterativos: eles começam com um ponto inicial e depois prosseguem para pontos que deveriam estar mais próximos do ponto ótimo, usando alguma regra de atualização. Existem três tipos de regras de atualização: [2] : 5.1.2 

  • Rotinas de ordem zero - utilizam apenas os valores da função objetivo e das funções de restrição no ponto atual;
  • Rotinas de primeira ordem - utilizam também os valores dos gradientes destas funções;
  • Rotinas de segunda ordem - utilizam também os valores dos Hessianos destas funções.

Rotinas de terceira ordem (e superiores) são teoricamente possíveis, mas não utilizadas na prática, devido à maior carga computacional e ao pequeno benefício teórico.

Filial e limite

Outro método envolve o uso de técnicas de ramificação e limite , onde o programa é dividido em subclasses a serem resolvidas com aproximações convexas (problema de minimização) ou lineares que formam um limite inferior para o custo geral dentro da subdivisão. Com as divisões subsequentes, em algum momento será obtida uma solução real cujo custo é igual ao melhor limite inferior obtido para qualquer uma das soluções aproximadas. Esta solução é ótima, embora possivelmente não seja a única. O algoritmo também pode ser interrompido antecipadamente, com a garantia de que a melhor solução possível está dentro de uma tolerância do melhor ponto encontrado; tais pontos são chamados de ε-ótimo. A terminação em pontos ε-ótimos é normalmente necessária para garantir a terminação finita. Isto é especialmente útil para problemas grandes e difíceis e problemas com custos ou valores incertos, onde a incerteza pode ser estimada com uma estimativa de confiabilidade apropriada.

Implementações

Existem vários solucionadores de programação não linear, incluindo código aberto:

  • ALGLIB (API C++, C#, Java, Python) implementa vários solucionadores de programação não linear de primeira ordem e sem derivadas
  • NLopt (implementação C/C++, com inúmeras interfaces, incluindo Julia, Python, R, MATLAB/Octave), inclui vários solucionadores de programação não linear
  • SciPy (padrão de fato para Python científico) possui o solucionador scipy.optimize, que inclui vários algoritmos de programação não linear (ordem zero, primeira ordem e segunda ordem).

Exemplos Numéricos

Exemplo bidimensional

A região azul é a região viável . A tangência da reta com a região viável representa a solução. A linha é a melhor linha de contorno alcançável (locus com um determinado valor da função objetivo).

Um problema simples (mostrado no diagrama) pode ser definido pelas restrições

com uma função objetivo a ser maximizada
onde x = ( x 1 , x 2 ) .

Exemplo tridimensional

A tangência da superfície superior com o espaço restrito no centro representa a solução.

Outro problema simples (ver diagrama) pode ser definido pelas restrições

com uma função objetivo a ser maximizada
onde x = ( x 1 , x 2 , x 3 ) .

Veja também

Referências

  1. ^ Ruszczyński, Andrzej (2006). Otimização Não Linear . Princeton, NJ: Princeton University Press . pág. xii+454. ISBN  978-0691119151. MR  2199043.
  2. ^ ab Nemirovsky e Ben-Tal (2023). "Otimização III: Otimização Convexa" (PDF) .

Leitura adicional

  • Avriel, Mordecai (2003). Programação Não Linear: Análise e Métodos. Publicação Dover. ISBN 0-486-43227-0 . 
  • Bazaraa, Mokhtar S. e Shetty, CM (1979). Programação não linear. Teoria e algoritmos. John Wiley e Filhos. ISBN 0-471-78610-1 . 
  • Bonnans, J. Frédéric; Gilberto, J. Charles; Lemaréchal, Claude ; Sagastizábal, Claudia A. (2006). Otimização numérica: Aspectos teóricos e práticos. Universitext (segunda edição revisada da tradução da edição francesa de 1997). Berlim: Springer-Verlag. pág. xiv+490. doi :10.1007/978-3-540-35447-5. ISBN 3-540-35445-X. SENHOR  2265882.
  • Luenberger, David G .; Sim, Yinyu (2008). Programação linear e não linear . Série Internacional em Pesquisa Operacional e Ciência de Gestão. Vol. 116 (Terceira edição). Nova York: Springer. pág. xiv+546. ISBN 978-0-387-74502-2. SENHOR  2423726.
  • Nocedal, Jorge e Wright, Stephen J. (1999). Otimização Numérica. Springer. ISBN 0-387-98793-2 . 
  • Jan Brinkhuis e Vladimir Tikhomirov, Otimização: Insights e Aplicações , 2005, Princeton University Press

links externos

  • Glossário de Programação Matemática
Obtido em "https://en.wikipedia.org/w/index.php?title=Nonlinear_programming&oldid=1206689135"