PROGRAMACIÓN CUADRATICA
La programación cuadrática (QP) es el nombre que se le da a un
procedimiento que minimiza una función cuadrática de n variables sujeta a m
restricciones lineales de igualdad o desigualdad. Un programa cuadrático es la
forma más simple de problema no lineal con restricciones de desigualdad. La
importancia de la programación cuadrática es debida a que un gran número de
problemas aparecen de forma natural como cuadráticos (optimización por mínimos
cuadrados, con restricciones lineales), pero además es importante porque aparece
como un subproblema frecuentemente para resolver problemas no lineales más
complicados. Las técnicas propuestas para solucionar los problemas cuadráticos
tienen mucha similitud con la programación lineal.
La programación cuadrática
es un método utilizado para
optimizar una función
cuadrática multivariable que
puede estar o no
restringida linealmente.
Muchos
problemas del mundo real,
como optimizar la cartera de
una empresa o reducir los
costos de un fabricante, se
pueden describir mediante un
programa cuadrático.
La programación cuadrática
(QP) es un tipo especial
en la matemática de
optimización de problemas.
Es el problema de optimizar
(reduciendo al mínimo o
maximizando) una función
cuadrática de varias
variables conforme a
apremios
lineales en estas variables.
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.
La programación cuadrática
es un método utilizado para
optimizar una función
cuadrática multivariable que
puede estar o no
restringida linealmente.
Muchos
problemas del mundo real,
como optimizar la cartera de
una empresa o reducir los
costos de un fabricante, se
pueden describir mediante un
programa cuadrático.
La programación cuadrática
(QP) es un tipo especial
en la matemática de
optimización de problemas.
Es el problema de optimizar
(reduciendo al mínimo o
maximizando) una función
cuadrática de varias
variables conforme a
apremios
lineales en estas variables.
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.
La programación cuadrática
es un método utilizado para
optimizar una función
cuadrática multivariable que
puede estar o no
restringida linealmente.
Muchos
problemas del mundo real,
como optimizar la cartera de
una empresa o reducir los
costos de un fabricante, se
pueden describir mediante un
programa cuadrático.
La programación cuadrática
(QP) es un tipo especial
en la matemática de
optimización de problemas.
Es el problema de optimizar
(reduciendo al mínimo o
maximizando) una función
cuadrática de varias
variables conforme a
apremios
lineales en estas variables.
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.
La programación cuadrática
es un método utilizado para
optimizar una función
cuadrática multivariable que
puede estar o no
restringida linealmente.
Muchos
problemas del mundo real,
como optimizar la cartera de
una empresa o reducir los
costos de un fabricante, se
pueden describir mediante un
programa cuadrático.
La programación cuadrática
(QP) es un tipo especial
en la matemática de
optimización de problemas.
Es el problema de optimizar
(reduciendo al mínimo o
maximizando) una función
cuadrática de varias
variables conforme a
apremios
lineales en estas variables.
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.
La programación cuadrática
es un método utilizado para
optimizar una función
cuadrática multivariable que
puede estar o no
restringida linealmente.
Muchos
problemas del mundo real,
como optimizar la cartera de
una empresa o reducir los
costos de un fabricante, se
pueden describir mediante un
programa cuadrático.
La programación cuadrática
(QP) es un tipo especial
en la matemática de
optimización de problemas.
Es el problema de optimizar
(reduciendo al mínimo o
maximizando) una función
cuadrática de varias
variables conforme a
apremios
lineales en estas variables.
Si la función objetivo es
convexa, entonces puede
existir una solución factible y
puede resolverse mediante
algoritmos conocidos como
el algoritmo simplex
expandid
En otras palabras, la programación cuadrática es un método utilizado para
optimizar una función cuadrática multivariable que puede estar o no restringida
linealmente. Muchos problemas del mundo real, como optimizar la cartera de una
empresa o reducir los costos de un fabricante, se pueden describir mediante un
programa cuadrático. La programación cuadrática es un caso particular de la programación no
lineal, al que se le pueden aplicar técnicas de programación no lineal, como pueden ser: de
restricciones activas, gradientes conjugados, estimación de los multiplicadores de Lagrange, etc. La
programación cuadrática forma parte esencial de la programación no lineal debido a la gran
cantidad de áreas en donde se aplica.
La importancia de este método recae en que, como es un caso especial de la
programación no lineal, se utiliza como una función modelo para aproximar funciones no lineales
a través de modelos locales. La programación cuadrática trabaja con una clase especial de
problemas en el que una función cuadrática de variables de decisión sujeta a restricciones lineales
de desigualdad requiere ser optimizada, en nuestro caso, requiere ser minimizada.
Una función cuadrática, en notación matricial, es una función de la forma:
1 T T
f ( x )= x Qx+ c x
2
Existen diferentes tipos de problemas de programación cuadrática, los cuales se pueden clasificar
en:
Problemas cuadráticos de minimización sin restricciones: requieren minimizar la función
cuadrática f(x) sobre el espacio completo.
Problemas cuadráticos de minimización sujetos a restricciones de igualdad: requieren minimizar
la función objetivo f(x) sujeta a restricciones lineales de igualdad Ax = b.
Problemas cuadráticos de minimización sujetos a restricciones lineales de desigualdad:
Requieren minimizar la función objetivo f(x) sujeta a restricciones lineales de desigualdad Ax ≥ b,
también puede contener restricciones de igualdad.
Problemas de optimización de redes cuadráticas: Son problemas cuadráticos en los que las
restricciones son restricciones de baja conservación sobre una red pura o generalizada.
Problemas cuadráticos convexos: Son cualesquiera de los mencionados arriba, en el cual la
función objetivo a ser minimizada, f(x) es convexa.
Problemas cuadráticos no convexos: Son cualesquiera de los mencionados arriba, en el cual la
función objetivo a ser minimizada, f(x) es no convexa.
Problemas de complementariedad lineal: Son problemas especiales con un sistema de ecuaciones
en variables no negativas, en el cual las variables están formadas en varios pares llamados pares
complementarios.
La programación cuadrática tiene aplicaciones muy importantes, por ejemplo, en el área
financiera, se pueden realizar análisis, usando modelos de programación cuadrática para
determinar la selección de estrategias óptimas de inversión. En los impuestos, la programación
cuadrática juega un papel muy importante en el análisis de políticas de impuestos. Otra aplicación
importante, es en la que los economistas utilizan modelos de equilibrio para analizar expectativas
de cambio en condiciones económicas, predicción de precios, incremento de la inflación, etc. Estos
modelos involucran el uso de programación cuadrática.
PROGRAMACION SEPARABLE
El objetivo principal de este método es reemplazar cada función no lineal por una aproximación
lineal a trozos. La programación separable es muy importante ya que permite aproximar un
problema no lineal convexo con un modelo de programación lineal que da una precisión arbitraria.
Para problemas no convexos la aproximación mediante este método también es válida, pero se
requiere de un esfuerzo mayor.
n
Definición 1. Una función f : X → R , X ⊂ Rn se dice que es separable si f (x)=∑ f ( x) ,es decir,
j =1
si f (x 1 , ... , xn) puede ser expresada como la suma de n funciones de una sola variable
f 1(x 1), ... , fn(xn).
Algunas funciones no lineales no son separables, pero pueden hacerse separables llevando a cabo
las sustituciones apropiadas. Por ejemplo, considere el problema
x1 +x 2
min : F ( x )=e
Entonces, sea f =e x 1+ x 2, luego ln (f )=x 1+ x 2 y el problema se convierte en
min F=f
Sujeto a ln (f )=x 1+ x 2
Siendo así, este problema es separable.
Para poder aplicar el método a un problema de programación no lineal, este debe cumplir con que
la función objetivo y todas las restricciones son separables. En un principio se considera una
función continua de una sola variable f(x). El intervalo [a, b] para x es particionado en intervalos
más pequeños a través de puntos de cuadrícula a = x0 < x1 < x2 < ... < xk = b. La funcion no lineal
f(x) es aproximada en el intervalo [xl , xl+1] de la siguiente forma. Sea x una combinación convexa
de x 1 y x 1+1, es decir, x=λ x 1 + ( 1−λ )x +1 , para algún λ ∈ [0, 1]. Luego ^f ( x )= λ f ( x ) + ( 1−λ )x +1
1 1
La distancia entre cada intervalo puede ser igual o no. Mas generalmente, la funcion f puede ser
aproximada en el intervalo [a, b] a través de los puntos x0, x1, ..., xk por una funcion lineal a trozos
^f así:
donde maximo dos ´ λl son positivos y deben ser adyacentes. En algunos casos λl es llamado peso
asociado al punto xl .
La programación separable es un caso especial de programación convexa, en donde la suposición
adicional es: Todas las funciones f(x) y g(x) son funciones separables. Una función separable es una
función en la que cada término incluye una sola variable, por lo que la función se puede separar en
una suma de funciones de variables individuales. Por ejemplo, si f(x) es una función separable, se
puede expresar como
Programación separable La programación separable es un caso especial de programación convexa,
en donde la suposición adicional es Todas las funciones / ( x ) y g¡(x) son funciones separables. Una
función separable es una función en la que cada término incluye una sola variable, por lo que la
función se puede separar en una suma de funciones de variables individuales. Por ejemplo, si f(x)
es una función separable, se puede expresar como en donde cada fj (Xj) incluye sólo los términos
con Xj en donde cada fi (Xj) incluye sólo los términos con Xj. En la terminología de programación
lineal , los problemas de programación separable satisfacen las suposiciones de aditividad pero no
las de proporcionalidad (para funciones no lineales).
GEOMETRICA
Los metodos de soluci ´ on de programaci ´ on geom ´ etrica no han cambiado mucho, debido a la
transfor- ´ macion fundamental que los hace importantes para empezar. ´ La solucion de
problemas de programaci ´ on geom ´ etrica se centra alrededor del hecho de que es posible ´
convertir todos los problemas de programacion geom ´ etrica a problemas no lineares pero
convexos con el ´ siguiente procedimiento[1]: Cada variable de decision´ xi se transforma a una yi =
logxi , de forma que xi = e yi . La funcion objetivo se convierte en minimizar ´ log f0. Las
inecuaciones fi ≤ 1 se convierten en log fi ≤ 0 Las ecuaciones gi = 1 se convierten en log gi = 0 De
esta forma las igualdades g adquieren la forma: log g(e y ) = log c + a1 log x1 + ... + an log xn = log c
+ a1y1 + ... + anyn (10) Que son afines, y se pueden transformar a: a1y1 + ...anyn = − log c (11) Que
es lineal. Similarmente, es posible demostrar que log f(e y ) sera una funci ´ on convexa cuando ´ f
es una funcion´ posinomial. De esta forma el problema se convierte en no-lineal pero convexo, y
puede ser resuelto por cualquier metodo de soluci ´ on de problemas convexos. Por este motivo
no ha habido mucho desarrollo en cuanto ´ a los metodos de soluci ´ on de problemas de
programaci ´ on geom ´ etrica, sino que el desarrollo es m ´ as´ centrado a encontrar mejores
formas de resolver problemas de optimizacion convexos, y a encontrar ´ formas de convertir
problemas de programacion geom ´ etrica particulares a unos que tengan restricciones ´ incluso
mas sencillas de resolver
El método de programación geométrica se usa cuando la función objetivo es una función
posinomial, las restricciones de desigualdad son posinomiales, y las de igualdad son monomiales.
Este tipo de problemas son comunes en lo relacionado a volúmenes, áreas, ubicaciones, entre
otros. El objetivo es realizar una transformación mediante cambios de variables para convertir el
problema a un problema de optimización convexo.
