3 TEOREMA 1. CONDICION NECESARIA DE OPTIMO

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

...