Programação não linear

Em matemática, programação não linear é o processo de resolução de um problema de otimização definido por um sistema de equações e desigualdades, coletivamente denominadas restrições, através de um conjunto de desconhecido variáveis reais, juntamente com uma função objetivo a ser maximizada ou minimizada, onde algumas das restrições ou a função objetivo são não lineares. É um sub-campo da otimização matemática que lida com problemas que não são lineares.

Definição

Seja n, m e p números inteiros positivos. Seja X um subconjunto de Rⁿ e f, g_i e h_j funções reais em X para cada i em {1, ..., m} e cada j em {1, ..., p}, com pelo menos uma dessas funções, f, g_i e h_j sendo não linear.

Um problema de minimização não linear é um problema de otimização da forma:[http://www.ime.unicamp.br/~friedlan/livro.pdf]

${\displaystyle }$

Um problema não linear de maximização é definido de forma análoga.

Possíveis tipos de conjunto de restrições

Existem várias possibilidades para a natureza do conjunto de restrições, também conhecido como conjunto viável região viável.

Um problema inviável é aquele para qual nenhum conjunto de valores para a escolha das variáveis satisfaz todas as restrições. Isto é, as restrições são mutuamente contraditórias, e não existe uma solução; o conjunto viável é o conjunto vazio.

Um problema viável é aquele para o qual existe pelo menos um conjunto de valores para a escolha das variáveis que satisfaz todas as restrições.

Um problema unbounded é viável para o qual a função objetivo pode ser feita para ser melhor do que qualquer valor finito. Assim, não há nenhuma solução ótima, porque há sempre uma solução viável que dá um melhor valor da função objetivo que qualquer solução proposta.

Métodos para resolver o problema

Se a função objetivo f é linear e o espaço de restrições é um polítopo, o problema é de programação linear, que pode ser resolvido utilizando-se conhecidas técnicas de programação linear, tais como o método simplex.

Se a função objetivo é côncava (problema de maximização), ou convexa (problema de minimização) e o conjunto de restrições é convexo, então o problema é chamado convexo e métodos gerais de otimização convexa podem ser usados na maioria dos casos.

Se a função objetivo é quadrática e as restrições são do tipo linear, técnicas de programação quadrática são utilizadas.[http://www.ime.unicamp.br/~friedlan/livro.pdf 34]

Se a função objetivo é a razão de uma função côncava e uma função convexa (no caso de maximização) e as restrições são convexas, então o problema pode ser transformado em um problema de otimização convexa usando técnicas de programação fracional.

Vários métodos estão disponíveis para a resolução de problemas não convexos. Uma abordagem é a utilização de formulações especiais de problemas de programação linear. Outro método envolve o uso de técnicas branch and bound, onde o programa é dividido em subclasses para ser resolvido com aproximações convexas (problema de minimização) ou lineares que formam um limite inferior sobre o custo global dentro da subdivisão. Com as divisões posteriores, em algum ponto uma solução real será obtida e terá o custo igual ao melhor limite inferior obtido para qualquer uma das soluções aproximadas. Esta solução é ótima, embora possivelmente não seja única. O algoritmo também pode ser interrompido precocemente, com a certeza de que a melhor solução possível está dentro de uma tolerância a partir do melhor ponto encontrado; tais pontos são chamados de ε-ótimos. Encerrando em pontos ε-ótimos é usualmente necessário para garantir encerramento em tempo finito. Isto é especialmente útil para problemas grandes e difíceis e problemas com custos incertos ou valores onde a incerteza pode ser estimada com uma estimação ideal de pontos é normalmente necessário para garantir finito de terminação. Isto é especialmente útil para grandes problemas difíceis e problemas com o incerto custos ou valores, em que a incerteza pode ser estimada com uma fiabilidade apropriada.

Em diferenciabilidade e qualificação de restrições, as condições Karush-Kuhn-Tucker fornecem condições necessárias para que uma solução seja ótima. Sob convexidade, estas condições também são suficientes. Se algumas das funções são não diferenciáveis, versões subdiferenciais das condições Krush-Kuhn-Tucker estão disponíveis.

Exemplos

Exemplo bidimensional

A tangência da linha com espaço de restrições representa a solução. A linha é a melhor linha de contorno realizável (locus com um determinado valor da função objetivo).

Um problema simples pode ser definido pelas restrições

x₁ ≥ 0

x₂ ≥ 0

x₁² + x₂² ≥ 1

x₁² + x₂² ≤ 2

com uma função objetivo a ser maximizada

f(x) = x₁ + x₂

onde x = (x₁, x₂).

Exemplo tridimensional

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

Outro problema simples pode ser definido pelas restrições

x₁² − x₂² + x₃² ≤ 2

x₁² + x₂² + x₃² ≤ 10

com uma função objetivo a ser maximizada

f(x) = x₁x₂ + x₂x₃

onde x = (x₁, x₂, x₃).

Veja também

• Ajuste de curvas
• Método dos mínimos quadrados
• Programação Linear
• Werner Fenchel, que criou a fundação para a programação não-linear

Leitura complementar

• Avriel, Mardoqueu (2003). Programação não-linear: Análise e Métodos. Dover Publicação. ISBN 0-486-43227-0.
• Bazaraa, Mokhtar S. e Shetty, C. M. (1979). Programação não-linear. Teoria e algoritmos. John Wiley & Sons. ISBN 0-471-78610-1.
• Bertsekas, Dimitri P. (1999). Programação não-linear: 2ª Edição. Athena Científica. ISBN 1-886529-00-0.
• Bonnans, J. Frédéric; Gilbert, J. Charles; Lemaréchal, Claude; Sagastizábal, Claudia A. Numerical optimization: Theoretical and practical aspects. Col: Universitext. [S.l.: s.n.] ISBN 3-540-35445-X. MR 2265882. doi:10.1007/978-3-540-35447-5 
• Luenberger, David G.; Ye, Yinyu. Linear and nonlinear programming. Col: International Series in Operations Research & Management Science. 116. [S.l.: s.n.] ISBN 978-0-387-74502-2. MR 2423726 
• Nocedal, Jorge e Wright, Stephen J. (1999). Otimização Numérica. Springer. ISBN 0-387-98793-2.
• Jan Brinkhuis e Vladimir Tikhomirov, Optimização: perspectivas e Aplicações, 2005, Princeton University Press

Ligações externas

• Mathematical Programming Glossary (em inglês)
• Nonlinear Programming Survey OR/MS Today (em inglês)
• Overview of Optimization in Industry (em inglês)