¿Cuál es la diferencia entre optimización lineal y no lineal?

Answer 1

No soy un experto, pero aquí hay información:
En la optimización lineal, la función de costo es un hiperplano con cierta pendiente. Algunas características tienen un peso positivo, y si aumenta esas, siempre aumentará la función objetivo. Por otro lado, algunas características tienen un peso negativo y siempre lo reducirán. Por lo tanto, es bastante fácil de optimizar. La parte interesante es cuando arrojas restricciones. Si tiene restricciones de desigualdad lineal, puede moverse alrededor del borde tratando de encontrar un camino cuesta abajo nuevamente, que es lo que intenta hacer el algoritmo más destacado, el algoritmo simplex. Los problemas lineales son muy típicos de los problemas de planificación y la Investigación de operaciones y, a menudo, implican una enorme cantidad de características, lo que lleva a programas como CPLEX a marcarse para poder resolver ecuaciones con miles de millones de variables.

La optimización no lineal se ocupa, lo adivinaste, de funciones no lineales. Por lo general, distingue entre optimización convexa y no convexa, siendo la primera menos especificada que la segunda, ya que es unimodal. Los métodos típicos para resolver estos problemas son los métodos de primer orden, como el gradiente y el descenso del gradiente conjugado, y los métodos de segundo orden (y sus aproximaciones), como el método de Newton y Levenberg-Marquardt. Uno de los algoritmos más destacados es el algoritmo BFGS.

Hay un montón de variaciones sobre lo anterior, pero estos son algunos de los temas típicos cubiertos en un libro de texto de optimización, en mi experiencia. Consulte la “Optimización numérica” ​​de Nocedal y Wright para obtener un buen libro de texto técnico.

Answer 2

En la optimización lineal, el límite del rango factible es el hiperplano y la función de costo también es lineal. Si alguna de las restricciones o la función obj no es lineal, el problema se convierte en una optimización no lineal.

En la optimización, existe una gran diferencia entre la optimización convexa y la optimización no convexa, sin embargo, no existe una diferencia intrínseca entre la programación lineal y la programación no lineal.
La programación lineal se estudió primero porque es más fácil pensar en la era anterior a la computadora. Simplex fue popular principalmente porque es fácil de escribir en papel (es un método basado en tablas). Tenga en cuenta que la complejidad de Simplex es exponencial.

La mayoría de los algoritmos de tiempo polinómico (como los métodos de punto interior) funcionan tanto para programación lineal como no lineal.