Optimizacion No Lineal

República Bolivariana de Venezuela

Ministerio del Poder Popular para la Defensa

Universidad Nacional Experimental Politécnica de la Fuerza Armada

UNEFA Núcleo Mérida

Programación Cuadrática

Método de los multiplicadores de Lagrange

Mérida, Enero de 2014

Programación Cuadrática

Un problema de Programación Cuadrática es aquél que contiene una función objetivo cuadrático y restricciones lineales.

min f(x)= ∑_(j=1 )^n▒c_(j ) x_j  ∑_(i=1 )^n▒∑_(j=1 )^n▒〖q_ij x_j 〗 x_i

s.a. ∑_(j=1)^n▒a_ij x_j  b_i i=1,…,m

x_j  0

En notación matricial:

min 〖f(x)=cx+x〗^(T ) Qx

s.a g_(1 ) (x)=x≥0

g_(2 ) (x)=Ax -b≥0

Condiciones de Kuhn-Tucker

min 〖f(x)=cx+x〗^(T ) Qx

s.a g_(1 ) (x)=x≥0

g_(2 ) (x)=Ax -b≥0

Condiciones de KT

〖∇f(x)=c +x〗^T (Q+Q^T)

∇g_1 (x)=1¦(1 )

∇g_2 (x) 〖=A〗^T

Si la función objetivo es convexa, es decir la matriz Q es una matriz cuadrada, y definida positiva, y las restricciones son lineales, las condiciones de Kunh-Tucker son necesarias y suficientes para encontrar el óptimo de la función.

Método de Wolfe sólo hay que resolver las condiciones de KT para encontrar el óptimo, como un problema de programación lineal.

Otro método más eficiente y simple para resolver las CKT es el método pivote complementario. Para el cual hacemos el siguiente cambio de variable:

w=Mz  q

w,z  0 w^T z=0

Una solución (w,z) no negativa al sistema de ecuaciones w=Mz+q se le llama una solución factible al problema complementario.

Una solución (w,z) factible al problema complementario que también satisface la condición complementaria w^Tz=0 se le llama solución complementaria.

La condición w^Tz=0 es equivalente a w_i z_i=0 para todas las i. Las variables w_i y z_i para cada i, son llamadas un par complementario de variables.

Método de Pivote Complementario 2

Supongamos que tenemos que encontrar una solución no negativa a un sistema de ecuaciones de la siguiente forma:

Encontrar los vectores w y z tales que:

w = Mz  q

w  0 z  0

w^(T )z = 0

Sistema de ecuaciones lineales: Requiere que la solución al sistema sea no negativa.

No hay Función Objetivo, solo una restricción no lineal.

Programación Cuadrática Secuencial (SQP)

〖q(x;x〗^0)=f(x^0)+∇f〖(x〗^0)(x-x^0)+1/2(x-x^0) ∇^(2 ) f(x^0)(x-x^0)

Paso 1: Formular el problema de Programación Cuadrática (QP)

Paso 2: Resolver el problema QP. Poner x^((t+1)) = x^t + d

Paso 3: Verificar la convergencia. Si no converge repetir el paso 1.

Aproximación Cuadrática de la Función de Lagrange

Supongamos la función de Lagrange:

L(x,μ,δ)=f(x)-∑▒〖δ_k h_k (x)-∑▒〖μ_j g_(j ) 〗〗(x)

En algún punto ( x , μ , λ ) el subproblema se convierte en:

min q(d;x ̅)≡∇f(x ̅ )^T d+1/2 d^(T ) ∇^2 xL(x ̅,μ ̅,δ ̅)d

Problema de convergencia: la matriz H=∇^2L tiene que ser definida positiva.

Método de los multiplicadores de Lagrange

Los problemas estudiados hasta ahora son de extremos libres (o sin restricciones), en ellos se pretende obtener los extremos de una función sin añadir condición alguna.

Sin embargo, se pueden plantear problemas de obtención de extremos de una función, de manera que estos cumplan determinadas condiciones (restricciones o ligaduras).

Gran cantidad de problemas que se presentan en la realidad son de extremos con ligaduras. Por ejemplo, una empresa tratará de maximizar las ganancias, pero estará condicionada por la cantidad de mano de obra necesaria, la materia prima disponible, etc.

Ejemplo de esto, puede ser el siguiente problema: determinar los extremos de la función f(x, y, z) = x2+y2+z2, verificando la ligadura x+y-2z = 1; la función dada, en principio, es de tres variables, pero se reduce a una función de dos variables despejando una cualquiera de las variables de la ligadura y sustituyéndola en la en la función, con lo cual se ha reducido el problema con ligadura a otro sin ligadura.

Lo realizado anteriormente, en general puede no ser fácil, y en algunos casos puede ser imposible.

Estudiamos ahora un método alternativo: el de los multiplicadores de

...