En matemáticas, programación non linear (PNL) é o proceso de resolución dun sistema de igualdades e desigualdades suxeitas a un conxunto de restricións sobre un conxunto de variables reais descoñecidas, cunha función obxectivo para maximizar (ou minimizar), cando algunha das restricións ou a función obxectivo non son lineares.
O problema de programación non linear pode enunciarse dun xeito moi simple:
o
onde
Se a función obxectivo f é linear e o espazo restrinxido é un politopo, o problema é de programación linear e pode resolverse utilizando algún dos algoritmos coñecidos de programación linear.
Se a función obxectivo é cóncava (problema de maximización), ou convexa (problema de minimización) e o conxunto de restricións é convexo, entón pode empregarse o método xeral de optimización convexa
Existen diversos métodos para resolver problemas non convexos. Un deles consiste en empregar formulacións especiais de problemas de programación linear. Outro método implica o uso de técnicas de ramificación e poda, cando o problema se divide en subdivisións para resolver mediante aproximacións que forman un límite inferior do custo total en cada subdivisión.
Mediante subdivisións sucesivas, obterase unha solución cun custo igual ou inferior que o mellor límite inferior obtido por algunha das solucións aproximadas. Esta solución é óptima, aínda que posiblemente non sexa única.
O algoritmo pode ser parado antes, coa garantía de que a mellor solución será mellor que a solución atopada nunha porcentaxe limitada. Iso emprégase en concreto en problemas importantes e especialmente difíciles e cando o problema conta con custos incertos ou valores onde a incerteza pode ser estimada nun grao de fiabilidade apropiado.
As condicións de Karush-Kuhn-Tucker proporcionan as condicións necesarias para que unha solución sexa óptima.
Un problema sinxelo pode definirse polas restricións:
cunha función obxectivo que se quere maximizar
onde x = (x1, x2)
Outro problema simple defínese pola restricións:x12 − x22 + x32 ≤ 2
onde x = (x1, x2, x3)