Programación no lineal

La programación no lineal ( PNL , N on Linear P rogramming ) es un caso de programación matemática que no se reduce a plantear un problema de programación lineal (por ejemplo, en el que la función objetivo o restricción es una función no lineal ) [1] .

El problema de la programación no lineal se plantea como el problema de encontrar el óptimo de una determinada función objetivo bajo las condiciones $F(x_{1},\ldots x_{n})$

g_{j}(x_{1},\ldots x_{n})\geq 0

donde - parámetros, - restricciones, - número de parámetros, - número de restricciones. $x_{i},i=1,\ldots,n$ $g_{j},j=1,\ldots,s$ $norte$ $s$

A diferencia de un problema de programación lineal, en un problema de programación no lineal, el óptimo no se encuentra necesariamente en el límite de la región definida por las restricciones.

Métodos para resolver el problema

Uno de los métodos que nos permite reducir el problema de la programación no lineal a la resolución de un sistema de ecuaciones es el método de los multiplicadores de Lagrange indefinidos .

Si la función objetivo es lineal y el espacio acotado es un politopo , entonces el problema es un problema de programación lineal que se puede resolver utilizando soluciones de programación lineal bien conocidas . $F$

Si la función objetivo es cóncava (problema de maximización) o convexa (problema de minimización) y el conjunto de restricciones es convexo, entonces el problema se llama convexo y, en la mayoría de los casos , se pueden usar métodos de optimización convexos generales .

Si la función objetivo es la relación de funciones cóncavas y convexas (en la maximización) y las restricciones son convexas, entonces el problema puede transformarse en un problema de optimización convexa utilizando técnicas de programación fraccionaria.

Existen varios métodos para resolver problemas no convexos. Un enfoque consiste en utilizar formulaciones especiales de problemas de programación lineal. Otro método implica el uso de métodos de ramificación y límite , donde el problema se subdivide para resolverlo con aproximaciones convexas (problema de minimización) o lineales que forman un límite inferior en el costo total dentro de la partición. En los siguientes apartados, en algún momento, se obtendrá una solución real cuyo coste es igual a la mejor cota inferior obtenida para cualquiera de las soluciones aproximadas. Esta solución es óptima, aunque quizás no la única. El algoritmo se puede terminar en una etapa temprana, con la confianza de que la solución óptima está dentro de la desviación aceptable del mejor punto encontrado; tales puntos se denominan ε-óptimo. La terminación de puntos ε-óptimos, como regla, es necesaria para asegurar la finitud de la terminación. Esto es especialmente útil para problemas grandes y complejos y problemas con costos o valores inciertos, donde la incertidumbre se puede determinar a partir de una estimación de confiabilidad adecuada.

Condiciones de diferenciación y regularidad , las condiciones de Karush-Kuhn-Tucker (KKT) proporcionan las condiciones necesarias para la optimización de la solución. Para la convexidad, estas condiciones también son suficientes.

Otro método para resolver problemas de programación no lineal es la programación dinámica [2] .

Véase también

Programación lineal

Enlaces

Encontrar el óptimo online por el método de los complejos

Notas

↑ Hadley, 1967 , pág. 11, 12
↑ Hadley, 1967 , pág. quince.

Literatura

Headley J. Programación dinámica y no lineal. - M. : Mir, 1967. - 506 p.

diccionarios y enciclopedias	gran ruso Britannica (en línea)
En catálogos bibliográficos	BNF : 122677537 J9U : 987007533977205171 LCCN : sh85092331 NKC : ph293203

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial