Optimización sin restricciones: Condiciones de óptimo, signo de formas cuadráticas y métodos de determinación

1.- Optimización sin restricciones

Planteamiento del problema:

Opt. f(x)

f: D  Rn  R

CONDICIÓN NECESARIA DE ÓPTIMO

*f(x*)=*

CONDICIÓN SUFICIENTE (2º orden) DE MÁXIMO LOCAL ESTRICTO

Hf(x*) DEFINIDA NEGATIVA

CONDICIÓN SUFICIENTE (2º orden) DE MÍNIMO LOCAL ESTRICTO

Hf(x*) DEFINIDA POSITIVA

MÉTODOS PARA LA DETERMINACIÓN DEL SIGNO DE UNA FORMA CUADRÁTICA NO RESTRINGIDA:

AUTOVALORES DE UNA MATRIZ A

(matrices simétricas)

Se trata de obtener las raíces de la ecuación característica: *A- * I*= 0

donde A es la matriz cuadrada de orden n, I es la matriz identidad de orden n.

DEFINIDAS

CONDICIÓN NECESARIA Y SUFICIENTE

DEFINIDA POSITIVA *i > 0, *i=1,...,n

DEFINIDA NEGATIVA *i < 0, *i=1,...,n

SEMIDEFINIDAS

CONDICIÓN NECESARIA Y SUFICIENTE

SEMIDEFINIDA POSITIVA *i*0, *i=1,...,n

con al menos un *j =0 y un *k>0 , 1*k,j*n

SEMIDEFINIDA NEGATIVA *i*0, *i=1,...,n

con al menos un *j =0 y un *k<0 , 1*k,j*n

INDEFINIDAS

CONDICIÓN NECESARIA Y SUFICIENTE

INDEFINIDA  *i > 0

 *j < 0

NULA

CONDICIÓN NECESARIA Y SUFICIENTE

NULA *i = 0, *i=1,...,n

MENORES PRINCIPALES CONDUCENTES DE A

(matrices simétricas)

Determinante de Orden 1: 1ªfila-1ªcolumna; A1=*a11*

Determinante de Orden 2: 2 primeras filas-2 primeras columnas

A2=

Determinante de Orden 3: 3 primeras filas-3 primeras columnas

A3=

...

DEFINIDAS

CONDICIÓN NECESARIA Y SUFICIENTE

DEFINIDA POSITIVA A1>0,A2>0,A3>0,...An>0

DEFINIDA NEGATIVA A1<0,A2>0,A3<0,A4>0,...

An>0 si n es par

An<0 si n es impar

SEMIDEFINIDAS

CONDICIÓN NECESARIA

*A*= 0

CONDICIÓN SUFICIENTE

SEMIDEFINIDA POSITIVA A1>0,A2>0,A3>0,...Ar>0

Ar+1= 0, ..., An=0

con r = rango(A)

SEMIDEFINIDA NEGATIVA

A1<0,A2>0,A3<0,A4>0,...

Ar>0 si n es par

Ar<0 si n es impar

Ar+1=0, ..., An=0

con r = rango(A)

NULA

A=  (matriz nula)

INDEFINIDAS

CONDICIONES SUFICIENTES

1.- Menor principal de orden par negativo. Otra C.S. :

2.- Determinante no nulo y no se verifica la CN y S de definida (ni DP ni DN)

2.- Optimización con restricciones

Planteamiento:

Opt. F(x)

s. a: hi(x)=bi , con i= 1, ..., m.

Las ecuaciones son funcionalmente independientes:

rg(Jh(x))=m para al menos un punto x  Dh,

siendo n>m , n= nº de variables, y m=nº de restricciones.

Para una función lagrangiana como ésta:

,

las condiciones de primer orden (necesarias) y las de segundo orden(suficientes), es decir, tras haber cumplido las de primer orden, son las siguientes, siempre que L(x,)C2 en (x*,*).

RESUMEN:

CONDICIÓN NECESARIA DE ÓPTIMO (primer orden)

*L(x*,**)=*

CONDICIÓN SUFICIENTE DE MÁXIMO LOCAL (2º orden)

HL(x*,**) DEFINIDA NEGATIVA

CONDICIÓN SUFICIENTE DE MÍNIMO LOCAL (2º orden)

HL(x*,**) DEFINIDA POSITIVA

C.S. DE EXTREMO LOCAL

(segundo orden)

METODOS PARA DETERMINAR EL SIGNO DE HL(x*, *)

METODO 1.- Menores orlados

La matriz hessiana de la función lagrangiana es:

Si las m primeras columnas de la matriz jacobiana de las restricciones en el punto crítico, Jh(x*), son L.I.(linealmente independientes: determinante distinto de cero) las condiciones planteadas actuarán como condición necesaria y suficiente.

Si las m primeras columnas de la matriz jacobiana de las restricciones en el punto crítico, Jh(x*), son L.D.(linealmente dependientes, determinante formado por esas m columnas es nulo) las condiciones planteadas actuarán sólo como condición suficiente.

Ejemplo de construcción de los menores orlados:

Opt. F(x1, x2, x3, x4, x5)

sujeto a:

h1(x1, x2, x3, x4, x5)=b1

h2(x1, x2, x3, x4, x5)=b2

Se trata de un problema de 5 variables y 2 restricciones.(n=5, m=2). La matriz hessiana es una matriz de 7 por 7 (5+2).

Los menores orlados a calcular son los de orden r = m+1, ..., n = 3, 4, 5. Hay que calcular tres menores orlados, los de orden 3, 4 y 5 (serán determinantes de orden 5, 6 y 7 respectivamente): H3* , H4* , H5* .

La función lagrangiana es:

L((x1, x2, x3, x4, x5)=

= F(x1, x2, x3, x4, x5)+ 1  b1 - h1(x1, x2, x3, x4, x5)+ 2  b2 - h2(x1, x2, x3, x4, x5)

Suponiendo que en el punto crítico (x*, *), la matriz hessiana de la función lagrangiana es la siguiente:

1 2 0 5 4 -1 2

2 3 -1 0 0 0 3

0 -1 4 1 3 0 1

5 0 1 7 9 2 11

4 0 3 9 8 4 3

-1 0 0 2 4 0 0

2 3 1 11 3 0 0

Para formar el H3* se toman las tres primeras filas y tres primeras columnas de la matriz hessiana de la función lagrangiana en el punto crítico, y se orlan con las tres primeras columnas de la matriz jacobiana de las restricciones con signo cambiado, y las tres primeras filas de la matriz jacobiana de las restricciones traspuesta con signo cambiado ("con signo cambiado" dado como está construida la función lagrangiana del problema. Para los menores orlados de orden 4 y 5 se hará lo mismo, pero en vez de tomar 3 filas y 3 columnas, se tomarán 4 y 5, respectivamente. Nótese que el menor orlado de orden 5 es el determinante de la matriz hessiana de la función lagrangiana.

Para H3*

1 2 0 5 4 -1 2

2 3 -1 0 0 0 3

0 -1 4 1 3 0 1

5 0 1 7 9 2 11

4 0 3 9 8 4 3

-1 0 0 2 4 0 0

2 3 1 11 3 0 0

1 2 0 -1 2

2 3 -1 0 3

0 -1 4 0 1

-1 0 0 0 0

2 3 1 0 0

Para H4*

1 2 0 5 4 -1 2

2 3 -1 0 0 0 3

0 -1 4 1 3 0 1

5 0 1 7 9 2 11

4 0 3 9 8 4 3

-1 0 0 2 4 0 0

2 3 1 11 3 0 0

1 2 0 5 -1 2

2 3 -1 0 0 3

0 -1 4 1 0 1

5 0 1 7 2 11

-1 0 0 2 0 0

2 3 1 11 0 0

H5* = │HL│

NOTA: Como las m, 2, primeras columnas de Jh(x) son L.I., las condiciones enunciadas anteriormente actúan como CN y S.

METODO 2.- Resolución de ecuación y estudio del signo de sus soluciones

1º.- Planteamiento de la siguiente ecuación:

2º.- Obtención de la solución de la ecuación para los distintos valores de .

3º.- Estudio del signo de las (n-m) soluciones de la ecuación, los i.

C.N. y S.

METODO 3.- Sustitución de variables, obtención de un nuevo polinomio característico con (n-m) variables, determinación de la matriz que represente a la forma cuadrática restringida y estudio de su signo como forma cuadrática sin restringir.

La matriz hessiana de la función lagrangiana representa a una forma cuadrática restringida a un subespacio. La forma cuadrática viene representada por la submatriz HLxx y el subespacio viene caracterizado por el producto de la matriz jacobiana de las restricciones en x* por el vector de incrementos infinitesimales de las variables igualado a un vector nulo de Rm (m= nº de restricciones), es decir, por la expresión, Jh(x*) dx = 0. Este sistema de ecuaciones lineales que caracterizan a un subespacio vectorial permite despejar m dxj en función del resto. Se sustituyen estos dxj en el polinomio cuadrático de la forma cuadrática q(dx)= dxt HLxx dx. Después se considera que la forma cuadrática ya no está definida en Rn , pues sólo dependerá de (n-m) dxi , por lo que se determina una matriz simétrica de orden (n-m) que representa a la forma cuadrática restringida. Se estudia el signo de dicha matriz considerándola como la de una forma cuadrática no restringida. Por tanto, los pasos a seguir son:

1º.- Planteamiento del sistema de m ecuaciones Jh(x*) dx = 0.

2º.- “Resolución” del sistema compatible indeterminado (Cramer) despejando m variables, dxj , en función de las (n-m) restantes.

3º.- Sustitución de esas variables en el polinomio cuadrático dxt HLxx dx .

4º.- Obtención de la matriz simétrica de orden (n-m) que represente a la forma cuadrática restringida.

5º.- Estudio del signo de la matriz obtenida en el paso anterior mediante alguno de los métodos ya explicados para formas cuadráticas no restringidas (autovalores, menores principales conducentes,...).

3.- Interpretación del multiplicador de Lagrange

Para una función lagrangiana como ésta:

L(x,*)= F(x)+ *i (b i - h i(x))

...