¿Qué es la programación cuadrática?
La programación cuadrática es un método utilizado para optimizar una función cuadrática multivariable que puede o no estar limitada linealmente. Muchos problemas del mundo real, como optimizar la cartera de una empresa o reducir los costos de un fabricante, se pueden describir utilizando un programa cuadrático. Si la función objetivo es convexa, entonces puede existir una solución factible y puede resolverse mediante algoritmos conocidos como el algoritmo Simplex expandido. Existen métodos para resolver algunas funciones cuadráticas no convexas, pero son complicadas y no están disponibles.
Las técnicas de optimización matemática se utilizan en la programación cuadrática para minimizar una función objetivo. La función objetivo se compone de una serie de variables de decisión que pueden o no estar limitadas. Las variables de decisión tienen poderes 0, 1 o 2. La función objetivo puede estar sujeta a una serie de restricciones de igualdad y desigualdad lineales con respecto a las variables de decisión. Un ejemplo de programación cuadrática es:Minimice f (x, y) = x
A menudo es interesante usar funciones cuadrívicas cuadráticas para describir los problemas del mundo real. Por ejemplo, utilizando la teoría de la cartera moderna, un analista financiero intentará optimizar la cartera de una empresa eligiendo la proporción de activos que minimizan el riesgo asociado con un rendimiento esperado dado. Una ecuación cuadrática compuesta por pesos de activos y la correlación entre los activos describe la varianza de la cartera que se puede minimizar mediante programación cuadrática. Otro ejemplo podría ser un fabricante que utiliza una ecuación cuadrática para describir la relación entre los diferentes componentes de calidad y el costo de un producto. El fabricante puede minimizar los costos mientras mantiene ciertos estándares al agregar restricciones lineales al programa cuadrático.
Uno de los conditios más importantesNS para resolver un programa cuadrático es la convexidad de la ecuación objetiva. La convexidad de una función cuadrática está determinada por la matriz o la matriz de sus segundos derivados. La función se llama convexa si la matriz de Hesse es positiva definida o semi-definida positiva, es decir, si todos los valores propios son positivos o no negativos respectivamente. Si el Hessian es positivo y existe una solución factible, entonces ese mínimo local es único y es un mínimo global. Si el Hessian es semi-positivo, una solución factible puede no ser única. Las funciones cuadráticas no convexas pueden tener mínimos locales o globales, pero son más difíciles de determinar.
Hay muchos enfoques para resolver una función cuadrática convexa utilizando programación cuadrática. El enfoque más común es una expansión del algoritmo simple. Algunos otros métodos incluyen el punto interior o el método de barrera, el método de conjunto activo y el método de gradiente conjugado. Estos métodos están integrados en CERProgramas Tain como Mathematica® y Matlab® y están disponibles en bibliotecas para muchos lenguajes de programación.