Optimizacion 645zv

Cap´ıtulo 2 Optimizaci´ on cl´ asica: Programas sin restricciones. Un problema de optimizaci´on sin restricciones tiene el aspecto Max. (o Min.) f (X) s. a X ∈ IRn El conjunto factible es todo IRn . La condici´on X ∈ IRn no supone ninguna restricci´on y habitualmente la omitiremos, escribiendo simplemente Max. (o Min.) f (X) Este tipo de problemas ya han sido estudiados parcialmente por el alumno en las Matem´aticas II, en donde se estudia c´omo hallar los m´aximos o m´ınimos locales de una tal funci´on. (Aunque en un problema de optimizaci´on lo que realmente buscamos son los m´aximos y m´ınimos globales). La forma de buscar los m´aximos y m´ınimos globales es comprobar previamente si nuestra funci´on cumple alg´ un requisito que garantice la existencia de m´ınimo global o m´aximo global. En este sentido, el hecho de que la funci´on sea coerciva, anticoerciva, c´oncava o convexa puede ser de gran ayuda. En todo lo que sigue supondremos que las funciones que manejamos son continuas y que tienen derivadas parciales continuas, al menos hasta el segundo orden, es decir, que son de clase C 2 en IRn . Empezamos haciendo un breve repaso de lo que se vio en Matem´aticas II.

´ CLASICA: ´ 2CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES.

2.1.

B´ usqueda de m´ aximos y m´ınimos locales. (Repaso)

2.1.1.

Puntos cr´ıticos. Condici´ on necesaria de m´ aximo o m´ınimo local.

Sea una funci´on f : S → IR, siendo S ⊆ IRn un conjunto abierto1 , f ∈ C 1 (S). Si f tiene un m´aximo local o un m´ınimo local en el punto Po ∈ S, entonces: ∇f (Po ) = O es decir

∂f (Po ) = 0, ∂x1

∂f ∂f (Po ) = 0, · · · · · · , (Po ) = 0 ∂x2 ∂xn

Los puntos Po para los cuales ∇f (Po ) = O se llaman puntos cr´ıticos de la funci´on f . Son los u ´nicos puntos donde puede haber m´aximos o m´ınimos locales de la funci´on.

2.1.2.

Condici´ on suficiente de m´ aximo o m´ınimo local.

En la misma situaci´on, y suponiendo que f ∈ C 2 (S), sea Po un punto cr´ıtico de f . Sea Hess(f ) (Po ) la matriz hessiana de f en dicho punto. Entonces: 1. Si Hess(f ) (Po ) es Definida Positiva, entonces f tiene un m´ınimo local en el punto Po . 2. Si Hess(f ) (Po ) es Definida Negativa, entonces f tiene un m´aximo local en el punto Po . 3. Si Hess(f )(Po ) es Indefinida, entonces f tiene un punto de silla2 en el punto Po . 4. Si Hess(f ) (Po ) es Semidefinida Positiva o Semidefinida Negativa, entonces el criterio no decide. Ejemplo.- Para la funci´on definida en IR2 : f (x, y) = 2x3 + xy 2 + 5x2 + y 2 Un conjunto S ⊂ IRn es abierto cuando no contiene a ninguno de sus puntos frontera, es decir, cuando F r(S) ∩ S = φ. En particular, IRn es abierto. 2 Se llama “punto de silla” a cualquier punto cr´ıtico que no sea ni m´aximo local ni m´ınimo local. 1

´ ´ 2.1. BUSQUEDA DE MAXIMOS Y M´INIMOS LOCALES. (REPASO)

3

vamos a hallar sus puntos cr´ıticos. Calcularemos tambi´en la matriz hessiana y la evaluaremos en cada punto cr´ıtico para dilucidar si se trata de un m´aximo local, un m´ınimo local o un punto de silla. Calculamos las derivadas parciales de primer orden: ³ ´ ¡ ¢ ∂f ∂f ∇f (x, y) = ∂x , ∂y = 6x2 + y 2 + 10x , 2xy + 2y Resolvemos el sistema

½

6x2 + y 2 + 10x = 0 2xy + 2y = 0

La segunda ecuaci´on, 2xy +2y = 2y(x+1) = 0 nos dice que debe ser y = 0 ´o x = −1 . Entramos en la primera ecuaci´on con cada una de estas posibilidades. Caso 1: Si y = 0, entonces 6x2 + 10x = 0, es decir, x(6x + 10) = 0, de donde debe ser x = 0 ´o x = −10/6 = −5/3. Tenemos as´ı los puntos cr´ıticos y = 0, x = 0, es decir, P1 = (0, 0) e y = 0, x = −5/3, es decir, P2 = (−5/3, 0) . Caso 2: Si x = −1, entonces 6 + y 2 − 10 = 0, es decir, y 2 = 4, o sea y = ±2. Tenemos as´ı dos nuevos puntos cr´ıticos: P3 = (−1, 2) y P4 = (−1, −2) . En definitiva, los puntos cr´ıticos son: P1 = (0, 0),

P2 = (−5/3, 0),

P3 = (−1, 2),

P4 = (−1, −2)

Para clasificar cada uno de estos puntos cr´ıticos como un m´aximo local, un m´ınimo local o un punto de silla debemos calcular la matriz hessiana, formada por las derivadas parciales de segundo orden: ∂ 2f = 12x + 10, ∂x2

∂ 2f ∂ 2f = = 2y, ∂x∂y ∂y∂x

∂ 2f = 2x + 2 ∂y 2

Por tanto, la matriz hessiana en un punto gen´erico (x, y) es: µ ¶ 12x + 10 2y Hess(f ) (x, y) = 2y 2x + 2 Ahora pasamos a evaluar esta matriz hessiana en cada punto cr´ıtico y a clasificarla. En el punto cr´ıtico P1 = (0, 0), la matriz hessiana queda: µ ¶ 10 0 Hess(f ) (0, 0) = 0 2

´ CLASICA: ´ 4CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. Vemos que D1 = 10 > 0 y D2 = 20 > 0. Por tanto, esta matriz es definida positiva, y entonces nuestro punto cr´ıtico P1 = (0, 0) es un m´ınimo local. En el punto cr´ıtico P2 = (−5/3, 0), la matriz hessiana es: µ ¶ −10 0 Hess(f ) (−5/3, 0) = 0 −4/3 Vemos que esta matriz es definida negativa (porque D1 = −10 < 0 y D2 = 40/3 > 0), y entonces el punto cr´ıtico P2 = (−5/3, 0) es un m´ aximo local. En P3 = (−1, 2), la matriz hessiana es: µ Hess(f ) (−1, 2) =

−2 4 4 0

¶

Vemos que D2 = −16 < 0, por lo que esta matriz es indefinida. El punto cr´ıtico P3 = (−1, 2) es un punto de silla (es decir, ni m´aximo ni m´ınimo local). En P4 = (−1, −2), la matriz hessiana es: µ Hess(f ) (−1, −2) =

−2 −4 −4 0

¶

que tambi´en es indefinida, y entonces el punto cr´ıtico P4 = (−1, −2) es un punto de silla. A continuaci´on, vamos a conocer un tipo de funciones para las cuales est´a garantizada la existencia de m´ınimo global. Se trata de las

2.2.

Funciones coercivas.

Definici´ on.- Sea f : IRn → IR una funci´on. Diremos que es una funci´ on coerciva si, para todo k ∈ IR el conjunto de subnivel k Ωk = {X ∈ IRn / f (X) ≤ k} es compacto. NOTA: El conjunto vac´ıo, φ, es compacto. Ejemplo.- Veamos que la funci´on f (x, y) = x2 + y 2 es coerciva. El conjunto de subnivel k es: Ωk = {(x, y) ∈ IR2 / x2 + y 2 ≤ k}

2.2. FUNCIONES COERCIVAS.

5

Para k < 0, Ωk = φ, que es compacto. Para k = 0, Ωk = {(0, 0)}, que tambi´en es compacto. Para k > 0, Ωk = {(x, y) ∈ IR2 / x2 + y 2 ≤ k} es la bola cerrada de centro (0, 0) y radio √ k, que es un conjunto compacto. Por tanto, esta funci´on es coerciva. Ejemplo.- La funci´on f (x, y) = x + 2y ¿es coerciva? El conjunto de subnivel k es Ωk = {(x, y) ∈ IR2 / x + 2y ≤ k} Este conjunto es un semiplano no acotado. Por tanto, no es un conjunto compacto nunca, da igual qui´en sea k. As´ı que la funci´on dada no es coerciva3 .

2.2.1.

Funciones coercivas: casos particulares.

A. Caso de funciones de una variable. Se puede probar que para cualquier funci´on continua f : IR → IR: ( l´ım f (x) = +∞ x−>+∞ f es coerciva ⇐⇒ l´ım f (x) = +∞ x−>−∞

En consecuencia, ejemplos concretos de funciones coercivas (de una variable) son: f (x) = x2 −5x+6,

2

f (x) = ex ,

f (x) =

x4 − 5x , x2 + 6

f (x) = |x|,

f (x) = 5x4 −4x3 +2x+5

(En general, toda funci´on de una variable que sea polin´omica de grado par y cuyo coeficiente de mayor grado sea positivo, es coerciva.) Y ejemplos concretos de funciones no coercivas son: f (x) = ex ,

f (x) = x3 + 3x2 ,

f (x) = 2x + 3,

f (x) = −3x2 + 5,

f (x) = cos x

3 En realidad, para que una funci´on no sea coerciva, bastar´ıa con que alguno de los Ωk no sea compacto.

´ CLASICA: ´ 6CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. B. Caso de funciones de variables separadas. Supongamos una funci´on de dos variables que sea de variables separadas, es decir, del tipo f (x, y) = ϕ(x) + ψ(y) Entonces f es coerciva

⇐⇒

ϕ y ψ son coercivas

Por ejemplo, son coercivas: 2

f (x, y) = ex + y 2 ,

f (x, y) = x2 − 5x + y 4 − 7y 3 + 12

Y no son coercivas: f (x, y) = x3 + y 2 ,

f (x, y) = x4 + ey

De manera an´aloga, si tenemos una funci´on de tres variables del tipo f (x, y, z) = ϕ(x) + ψ(y) + η(z) Entonces f es coerciva

⇐⇒

ϕ, ψ y η son coercivas

¿Qu´e importancia tienen las funciones coercivas desde el punto de vista de la optimizaci´on? Nos lo dice el siguiente teorema. TEOREMA.- Si f : IRn → IR es una funci´on continua y coerciva, entonces existe P1 ∈ IRn tal que f (P1 ) ≤ f (X), (∀X ∈ IRn ). Demostraci´ on: Tomo un punto cualquiera, Po de IRn y tomo M = f (Po ). Minimizar f (X) Consideramos el problema s. a X ∈ ΩM Este problema verifica las hip´otesis del Teorema de Weierstrass (ya que f es continua, ΩM es compacto-por ser f coerciva- y ΩM 6= φ, ya que Po ∈ ΩM ). Por tanto, podemos asegurar que existe P1 ∈ ΩM tal que f (P1 ) ≤ f (X) (∀X ∈ ΩM ). Si X es cualquier punto de IRn entonces caben dos posibilidades: Si X ∈ / ΩM , entonces f (X) > M = f (Po ) ≥ f (P1 ). Si X ∈ ΩM , entonces f (X) ≥ f (P1 ) Por tanto, en cualquier caso, f (X) ≥ f (P1 ), como quer´ıamos demostrar. Este teorema nos dice que toda funci´ on coerciva f : IRn → IR tiene m´ınimo global n sobre IR .

2.3. PROPIEDADES DE LAS FUNCIONES COERCIVAS.

2.3.

7

Propiedades de las funciones coercivas.

1) Coercividad y composici´ on. n Sean f : IR → IR y F : IR → IR funciones continuas tales que f es coerciva y F verifica que l´ım F (z) = +∞. z→+∞

Entonces la funci´on compuesta g(X) = F (f (X)) es tambi´en coerciva. Ejemplos.2

2

La funci´on g(x, y) = e3x +2y −10y−3 es coerciva, ya que la funci´on f (x, y) = 3x2 + 2y 2 − 10y − 3 es coerciva y la funci´on F (z) = ez cumple la condici´on de que su l´ımite en +∞ es +∞. p La funci´on g(x, y) = x4 + y 2 + 5 es coerciva, ya que la funci´on f (x, y) = x4 + √ y 2 + 5 es coerciva y la funci´on F (z) = z cumple la condici´on4 de que su l´ımite en +∞ es +∞. El conjunto S = {(x, y) /(x2 + 3y 4 )7 ≤ 40} ¿podemos asegurar que es compacto? S´ı, ya que la funci´on g(x, y) = (x2 +3y 4 )7 es coerciva5 . Por tanto, nuestro conjunto S es en realidad el conjunto de subnivel Ω40 para esta funci´on coerciva y, en consecuencia, es un conjunto compacto. 2) Coercividad y orden. Sean f y g dos funciones definidas en IRn y continuas. Supongamos que f (X) ≤ g(X) (∀X ∈ IRn ). Se tiene que: Si f es coerciva, entonces tambi´en g es coerciva. Demostraci´ on: Partimos de la base de que f es coerciva. Queremos demostrar que g es coerciva. Pensamos en los conjuntos de subnivel k de ambas funciones: Ωk (f ) = {X ∈ IRn / f (X) ≤ k},

Ωk (g) = {X ∈ IRn / g(X) ≤ k}

El hecho de que f (X) ≤ g(X) para todo X ∈ IRn nos dice que Ωk (g) ⊂ Ωk (f ). (Ya que X ∈ Ωk (g) ⇒ g(X) ≤ k ⇒ f (X) ≤ g(X) ≤ k ⇒ f (X) ≤ k ⇒ X ∈ Ωk (f )) 4 La propiedad enunciada es v´alida tambi´en aunque la funci´on F no est´e definida en√todo IR, sino en un intervalo como [0, +∞[ ´o ]0, +∞[, como es el caso de nuestra funci´on F (z) = z, siempre y cuando el dominio de esta funci´on F contenga al rango de f . 5 g(x, y) es coerciva, ya que f (x, y) = x2 +3y 4 es coerciva y se cumple adem´as que F (z) = z 7 → +∞ cuando z → +∞.

´ CLASICA: ´ 8CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. El hecho de que Ωk (f ) sea compacto -sabemos que lo es por ser f coerciva- obliga a que tambi´en Ωk (g) sea compacto, ya que Ωk (g) es cerrado -por ser un conjunto de subnively acotado -por estar incluido en Ωk (f ), que est´a acotado-. Ejemplo.- La funci´on g(x, y) = x2 + y 4 + 20 sen (x + y), ¿podemos asegurar que es coerciva? Observamos que siempre se verifica que −1 ≤ sen (x + y) ≤ 1. Con lo cual, g(x, y) = x2 + y 4 + 20 sen (x + y) ≥ x2 + y 4 − 20 = f (x, y) Sabemos que f (x, y) es coerciva6 . Por tanto, g(x, y) tambi´en es coerciva. Como caso particular de esta propiedad tenemos el Caso de funciones polin´ omicas de segundo grado. Una funci´on de dos variables, polin´omica de grado dos, tiene el aspecto f (x, y) = a x2 + 2b x y + c y 2 + d x + k y + n (donde a, b, c, d, k y n son constantes). Los t´erminos de grado dos, a x2 + 2b x y + c y 2

µ

definen una forma cuadr´atica cuya matriz asociada es A =

a b b c

¶ .

Se puede demostrar que f es una funci´on coerciva ⇐⇒ A es definida positiva

Ejemplo.- La funci´on polin´omica de grado dos f (x, y) = x2 + 4 x y + y 2 + 7 x + 5 y + 8 µ 2

2

¿es coerciva? La matriz asociada a la forma cuadr´atica x + 4 x y + y es A =

1 2 2 1

Esta matriz no es definida positiva. Es indefinida, ya que D2 = −3 < 0. Por tanto, la funci´on no es coerciva. Ejemplo.- La funci´on f (x, y) = 3 x2 + 4 x y + 2 y 2 − 5 x + 6 y − 10 6

Por ser f (x, y) = ϕ(x) + ψ(y), siendo ϕ(x) = x2 coerciva y ψ(y) = y 4 − 20 tambi´en coerciva.

¶

´ ´ 2.4. EL METODO DE PRIMER ORDEN. (PARA MINIMIZACION) µ

3 2 ¿es coerciva? La matriz asociada a la forma cuadr´atica es A = 2 2 Esta matriz es definida positiva (porque D1 = 3 > 0, D2 = 2 > 0). Por tanto, esta funci´on s´ı es coerciva.

9 ¶ .

Podemos dar una peque˜ na justificaci´on de porqu´e el hecho de que una funci´on polin´omica de grado dos sea o no coerciva depende del signo de la forma cuadr´ asociada. µ atica ¶ a b Hay una propiedad, llamada de Rayleigh, que dice que si A = es la matriz asociada b c a la forma cuadr´atica en dos variables, QA (x, y) = a x2 + 2b xy + c y 2 y llamo λ1 al menor de los valores propios de A, entonces QA (x, y) ≥ λ1 (x2 + y 2 ) A consecuencia de esto, si tengo una funci´on polin´omica de grado dos en dos variables, f (x, y) = a x2 + 2b x y + c y 2 + d x + k y + n ocurre que f (x, y) = a x2 +2b x y+c y 2 + d x+k y+n ≥ λ1 (x2 +y 2 )+ d x+k y+n = λ1 x2 + d x+ λ1 y 2 + k y+n La funci´on λ1 x2 + d x + λ1 y 2 + k y + n es una funci´on de variables separadas. En el caso de que fuera λ1 > 0 (o, lo que es lo mismo, en el caso de que la forma cuadr´atica fuera definida positiva), esta u ´ltima funci´on es coerciva. Y, por la propiedad 2, nuestra f tambi´en es coerciva.

3) Coercividad y m´aximos globales. Si f : IRn → IR es una funci´on coerciva, entonces no tiene m´aximo global. Demostraci´ on: Si tuviera m´aximo global, es decir, existiera un punto P2 tal que f (P2 ) ≥ f (X), (∀X ∈ IRn ), entonces, llamando M = f (P2 ) el conjunto de subnivel ΩM ser´ıa todo IRn , que no es compacto y contradice la suposici´on de que la funci´on era coerciva.

2.4.

El m´ etodo de primer orden. (Para minimizaci´ on)

Tratamos de resolver un problema de minimizaci´on sin restricciones, es decir, un problema del tipo Min. f (X) . Supongamos que tenemos garantizado que el problema tiene soluci´on, es decir, que tiene m´ınimo global. (Esta garant´ıa se tiene si, por ejemplo, la funci´on f es coerciva, aunque tambi´en puede garantiz´arsenos la existencia de soluci´on de otras maneras diferentes). Pues bien en esta situaci´on, podemos resolver el problema de la siguiente manera (M´etodo de primer orden).

´ CLASICA: ´ 10CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. 1. Calculamos los puntos cr´ıticos de f (“candidatos”). 2. Evaluamos f en los puntos cr´ıticos. 3. El menor valor de los obtenidos corresponde al m´ınimo global. ¿Por qu´e se llama M´etodo de primer orden? Porque s´olo se usan las derivadas de primer orden para hallar los puntos cr´ıticos, y luego basta con evaluar la funci´on en ellos. Ejemplo.- Vamos a resolver el problema Min. f (x, y) = x4 − 2x2 + y 2 + 5 . En primer lugar, tratamos de garantizar la existencia de soluci´on, comprobando si la funci´on es coerciva. Se trata de una funci´on de variables separadas. La funci´on en x, ϕ(x) = x4 − 2x2 es coerciva, (ya que es polin´omica de grado par y con coeficiente de mayor grado positivo). Y la funci´on en y, ψ(y) = y 2 + 5 es tambi´en coerciva, por la misma raz´on. Por tanto, nuestra funci´on f (x, y) es coerciva. Aplicamos el m´etodo de primer orden para hallar la soluci´on. Las derivadas parciales son: ∂f = 4x3 − 4x, ∂x

∂f = 2y ∂y

½

4x3 − 4x = 0 2y = 0 obtenemos como puntos cr´ıticos: (0, 0), (1, 0), y (−1, 0). Es decir, el conjunto de “candidatos” es: C = { (0, 0), (1, 0), (−1, 0) } Al resolver el sistema

Ahora evaluamos la funci´on, f (x, y) = x4 − 2x2 + y 2 + 5, en ellos y obtenemos: f (0, 0) = 5 f (1, 0) = 4 f (−1, 0) = 4 Por tanto, el valor m´ınimo es 4 y los puntos m´ınimos globales son (1, 0) y (−1, 0). Ejemplo.- Queremos resolver el problema Min. f (x, y) = 2x2 + 2xy + y 2 + 2x − 3 . Se trataµde una ¶ funci´on polin´omica de grado 2. La matriz asociada a la forma cuadr´atica 2 1 es A = . Esta matriz es definida positiva. Por tanto, nuestra funci´on es coer1 1 civa.

2.5. FUNCIONES ANTICOERCIVAS.

11

Hallamos los puntos cr´ıticos y obtenemos que el u ´nico punto cr´ıtico es el punto (−1, 1). Puesto que sabemos que el problema tiene soluci´on (=m´ınimo global) y s´olo tenemos un candidato, ´este es el m´ınimo global. En definitiva, la soluci´on de este problema es que el m´ınimo global es el punto (−1, 1) y el valor m´ınimo es f (−1, 1) = −4.

2.5.

Funciones anticoercivas.

Diremos que una funci´on f : IRn → IR es anticoerciva cuando su opuesta, −f sea coerciva. Es decir, f es anticoerciva ⇐⇒ −f es coerciva Equivalentemente, f es anticoerciva si y s´olo si el conjunto de supernivel k, Λk = {X ∈ IRn / f (X) ≥ k} es compacto, para todo k ∈ IR. Al igual que pasaba con las funciones coercivas, es posible reconocer a simple vista que una determinada funci´on es anticoerciva en ciertos casos particulares.

2.5.1.

Funciones anticoercivas: casos particulares.

Caso de funciones de una variable f : IR → IR. ( f es anticoerciva

⇐⇒

l´ım f (x) = −∞

x−>+∞

l´ım f (x) = −∞

x−>−∞

(Por ejemplo, f (x) = −x2 + 5x es anticoerciva y tambi´en f (x) = −5x4 + 4x3 es anticoerciva. En general, toda funci´on de una variable que sea polin´omica de grado par y cuyo coeficiente de mayor grado sea negativo, es anticoerciva.) Caso de funciones de variables separadas: f (x, y) = ϕ(x) + ψ(y) es anticoerciva

⇐⇒

ϕ y ψ son anticoercivas

Caso de funciones polin´omicas de grado dos, en dos variables. f es una funci´on anticoerciva ⇐⇒ A es definida negativa (siendo A la matriz asociada a la forma cuadr´atica correspondiente)

´ CLASICA: ´ 12CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. La importancia de las funciones anticoercivas desde el punto de vista de la optimizaci´on nos la da el siguiente resultado: TEOREMA.- Si f : IRn → IR es una funci´on continua y anticoerciva, entonces dicha funci´on tiene m´ aximo global. (Y no tiene m´ınimo global). Para resolver problemas de maximizaci´on podemos establecer un m´etodo de primer orden an´alogo al que vimos para minimizaci´on.

2.6.

M´ etodo de primer orden. (Para maximizaci´ on)

Dado un problema de maximizaci´on sin restricciones, es decir, del tipo Max. f (X) , supongamos que estamos seguros de que tiene soluci´on (por ejemplo, si f es anticoerciva). Entonces 1. Calculamos los puntos cr´ıticos de f . 2. Evaluamos f en los puntos cr´ıticos. 3. El mayor valor de los obtenidos corresponde al m´aximo global.

Ejemplo.- Vamos a resolver el problema Max.

f (x, y) = −4x2 + 4xy − 3y 2 + 20x + 26y .

Se trata µ de una funci´ ¶on polin´omica de grado 2. La matriz asociada a la forma cuadr´atica −4 2 es A = . Esta matriz es definida negativa. Por tanto, nuestra funci´on es 2 −3 anticoerciva. Sabemos que el problema tiene soluci´on. Hallamos los puntos cr´ıticos. Obtenemos que el u ´nico punto cr´ıtico es el punto (7, 9). Por tanto, la soluci´on de este problema es que el punto (7, 9) es m´aximo global y el valor m´aximo es f (7, 9) = 187. NOTA: Alternativamente, el problema podr´ıa haber sido resuelto traduciendo al problema equivalente de minimizar la funci´on opuesta. A continuaci´on pasamos a estudiar otros tipos de funciones, las funciones convexas y las funciones c´oncavas. Antes debemos ver el concepto de conjunto convexo.

2.7. CONJUNTOS CONVEXOS.

2.7.

13

Conjuntos convexos.

Def.- Segmento cerrado determinado por dos puntos. Sean P, Q dos puntos de IRn . El segmento [P, Q] que forman se define como el conjunto: [P, Q] = {tQ + (1 − t)P / 0 ≤ t ≤ 1} Al darle a t los diferentes valores reales entre 0 y 1 obtenemos los diferentes puntos del segmento [P, Q]. Ejemplo:.- P = (5, 1), Q = (4, −1). Un punto gen´erico del segmento [P, Q] es de la forma X = t(4, −1) + (1 − t)(5, 1) = (4t + 5 − 5t, −t + 1 − t) = (5 − t, 1 − 2t) Para t = 0: (5, 1) = P Para t = 1: (4, −1) = Q Para t = 1/2: ( 92 , 0) que es el punto medio del segmento.

Def.- Conjunto convexo. Un conjunto U ⊂ IRn se dice convexo si, siempre que tomemos dos puntos P y Q que pertenezcan a U , el segmento que determinan, [P, Q] est´a ´ıntegramente incluido en el conjunto U . Ejemplos.-

3) {(x, y) : x2 + y 2 = 1}

5) {(x, y) : y ≥ x2 }

4) {(x, y) : x2 + y 2 < 1}

6) {(x, y) : y ≤ x2 }

´ CLASICA: ´ 14CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES.

Propiedad.- La intersecci´on de conjuntos convexos es tambi´en un conjunto convexo. Por tanto, tambi´en es convexo el conjunto {(x, y) : x2 + y 2 ≤ 1, y ≥ x2 } Def.- Punto extremo de un conjunto convexo. Dado un conjunto convexo U , diremos que un punto P ∈ U es un punto extremo o v´ertice de U cuando P no es punto medio de ning´ un segmento contenido en U . Ejemplo.- En el conjunto convexo U = {(x, y) / x2 + y 2 ≤ 4}, que es la bola cerrada de centro (0, 0) y radio 2, los puntos extremos son los de la circunferencia de igual centro y radio. Ejemplo.- En el conjunto convexo U = {(x, y) / 1 ≤ x ≤ 2, 2 ≤ y ≤ 4}, que es un rect´angulo, los puntos extremos son los cuatro v´ertices del rect´angulo, es decir, los puntos (1, 2), (1, 4), (2, 2) y (2, 4).

2.8.

Funciones convexas

Def.- Sea S un conjunto convexo y sea f : S → IR una funci´on. Diremos que f es convexa en S si ocurre que f (tQ + (1 − t)P ) ≤ tf (Q) + (1 − t)f (P )

(∀t ∈ [0, 1],

∀ P, Q ∈ S)

Esta definici´on significa que, para cualesquiera dos puntos de la gr´afica de la funci´on, el segmento que los une est´a o por encima de la gr´afica o en la misma gr´afica.

Ejemplos.1) f (x) = x2

2) f (x) = ex

2.9. PROPIEDADES DE LAS FUNCIONES CONVEXAS 3) f (x) = 2x − 1

15

4) f (x, y) = x2 + y 2

Def.- En la misma situaci´on de la definici´on anterior, diremos que f es estrictamente convexa si ocurre que f (tQ + (1 − t)P ) < tf (Q) + (1 − t)f (P )

(∀t ∈]0, 1[ ,

∀ P, Q ∈ S, P 6= Q)

Lo que significa esta definici´on es que para cualesquiera dos puntos de la gr´afica de la funci´on, el segmento que los une est´a estrictamente por encima de la gr´afica. Ejemplo.Las funciones 1), 2) y 4) del ejemplo anterior son estrictamente convexas. En cambio, la funci´on f (x) = 2x − 1 es convexa, pero no es estrictamente convexa. Observe el alumno que si una funci´on es estrictamente convexa, en particular es convexa. Al rev´es no.

2.9.

Propiedades de las funciones convexas

1. Sea f : IRn → IR una funci´on continua y convexa en IRn . Entonces: Los conjuntos de subnivel de f son convexos. (Es decir, para todo k ∈ IR el conjunto Ωk = {X ∈ IRn / f (X) ≤ k} es convexo.) Adem´as, como la intersecci´on de conjuntos convexos es convexo, si tenemos dos (o m´as) funciones convexas, f1 , f2 , · · ·, el conjunto Ω = {X ∈ IRn / f1 (X) ≤ k1 , f2 (X) ≤ k2 , · · ·} es convexo. Ejemplo.Ω = {(x, y) / x2 + y 2 ≤ 5, 2x − y ≤ 2}

´ CLASICA: ´ 16CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. es un conjunto convexo7 . En las siguientes propiedades S representa un subconjunto convexo de IRn y f : S → IR una funci´on convexa y de clase C 1 en S. 2. Si Po ∈ S es un punto cr´ıtico de f (es decir, ∇f (Po ) = O), entonces Po es un m´ınimo global de f en S. Ejemplo.- Para la funci´on f (x, y) = x2 + 2y 2 , que es convexa en IR2 , el u ´nico punto cr´ıtico es Po = (0, 0). Por tanto, este punto es m´ınimo global de f en IR2 . 3. Si f es estrictamente convexa es imposible que tenga m´as de un punto m´ınimo global. Es decir, tiene un m´ınimo global o ninguno. Demostraci´ on: Si hubiera dos puntos m´ınimos globales distintos, P y Q y llamando m = f (P ) = f (Q) al valor m´ınimo, tenemos que µ ¶ 1 1 1 1 1 1 f Q + P < f (Q) + f (P ) = m + m = m 2 2 2 2 2 2 Esto nos dir´ıa que en el punto H = 12 Q + 12 P la funci´on f toma un valor f (H) < m, lo que es absurdo porque m era el valor m´ınimo. Ejemplos.La funci´on f (x) = x2 es estrictamente convexa en IR y tiene un solo m´ınimo global, x = 0. La funci´on f (x) = ex es estrictamente convexa en IR y no tiene m´ınimo global. 4. Si S es compacto, adem´as de convexo, entonces el m´ aximo valor de f se alcanza en alg´ un punto extremo de S. En otras palabras, si E(S) es el conjunto de puntos extremos de S: M´aximo valor de f sobre S = M´aximo valor de f sobre E(S). Ejemplo.- Dado el problema Max s. a

x2 + 2y 2 x+y ≤2 x ≥ 0, y ≥ 0

7 Hemos tenido en cuenta que la funci´on f1 (x, y) = x2 + y 2 es convexa y que tambi´en lo es la funci´on f2 (x, y) = 2x − y.

´ 2.10. FUNCIONES CONCAVAS

17

vemos que el conjunto factible S = {(x, y) / x + y ≤ 2, x ≥ 0, y ≥ 0} es compacto y convexo. Por tanto, existe m´aximo global, y adem´as se alcanza en alg´ un punto extremo. Los puntos extremos de S son E(S) = { (0, 0), (2, 0) (0, 2)} Evaluando f (x, y) = x2 + 2y 2 en estos puntos extremos, tenemos que f (0, 0) = 0, f (2, 0) = 4, f (0, 2) = 8. Por tanto, el valor m´aximo es M = 8 y se alcanza en el punto (0, 2).

2.10.

Funciones c´ oncavas

Def.- Sea S ⊂ IRn un conjunto convexo y sea f : S → IR una funci´on. Diremos que f es c´oncava en S si su opuesta, −f es una funci´on convexa en S. Ejemplos.1) f (x) = −x2 ,

2) f (x) = 2x − 1,

3) f (x, y) = −x2 − y 2

NOTA 1: Una funci´on f es estrictamente c´oncava si y s´olo si su opuesta −f es estrictamente convexa. NOTA 2: Una funci´on puede no ser ni c´oncava ni convexa. Por ejemplo, la funci´on f (x) = x3 definida en IR no es ni c´oncava ni convexa. Pero si la restringimos a S = [0, +∞[, entonces s´ı es una funci´on convexa sobre S = [0, +∞[.

La funci´on f (x, y) = y 2 − x2 definida en IR2 cuya gr´afica aparece a continuaci´on es un ejemplo de una funci´on que no es ni c´oncava ni convexa.

NOTA 3: Existen funciones que son convexas y c´oncavas a la vez. Las funciones polin´omicas de grado uno, como f (x) = ax + b, f (x, y) = ax + by + c.

´ CLASICA: ´ 18CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. Son las u ´nicas funciones simult´aneamente c´oncavas y convexas.

2.10.1.

Propiedades de las funciones c´ oncavas

Sea S un subconjunto convexo de IRn y sea f : S → IR una funci´on de clase C 1 y c´ oncava en S. Entonces se verifican las siguientes propiedades: 1. Si Po ∈ S es un punto cr´ıtico de f (es decir, ∇f (Po ) = O), entonces Po es un m´ aximo global de f en S. 2. Si f es estrictamente c´ oncava es imposible que tenga m´as de un punto m´aximo global. Es decir, tiene un m´ aximo global o ninguno. 3. Si S es compacto, adem´as de convexo, entonces el m´ınimo valor de la funci´ on c´ oncava f se alcanza en alg´ un punto extremo de S.

2.11.

Caracterizaci´ on de las funciones convexas y c´ oncavas

El alumno ya sabe que el signo de la segunda derivada caracteriza la convexidad o concavidad de las funciones de una variable. En concreto, Sea f : I → IR una funci´on, siendo I un intervalo real, f ∈ C 2 (I). Entonces 1. f 00 (x) ≥ 0 para todo punto x de I ⇔ f es convexa en I. 2. f 00 (x) ≤ 0 para todo punto x de I ⇔ f es c´oncava en I. Para la convexidad o concavidad estricta, el resultado es: 1. f 00 (x) > 0 para todo punto x de I ⇒ f es estrictamente convexa en I. 2. f 00 (x) < 0 para todo punto x de I ⇒ f es estrictamente c´oncava en I. OJO: En los dos u ´ltimos apartados, no es cierta la implicaci´on ⇐. Por ejemplo, la 4 funci´on f (x) = x es estrictamente convexa en I = IR, pero su segunda derivada, f 00 (x) = 12x2 no es estrictamente positiva para todo x ∈ IR, ya que se anula para x = 0. Pues bien existe una caracterizaci´on an´aloga para funciones de varias variables.

´ DE LAS FUNCIONES CONVEXAS Y CONCAVAS ´ 2.11. CARACTERIZACION 19

Caracterizaci´ on de la convexidad o concavidad de una funci´ on mediante la matriz hessiana. Sea una funci´on f : S → IR, siendo S ⊂ IRn un conjunto convexo. Suponemos que f es de clase C 2 en S. Consideramos la matriz hessiana, Hess f (X) en un punto gen´erico X ∈ S. Entonces 1. f es convexa en S ⇔ Hess f (X) es Definida o Semidefinida Positiva en todo punto X de S. 2. f es c´oncava en S ⇔ Hess f (X) es Definida o Semidefinida Negativa en todo punto X de S. Para la convexidad o concavidad estricta tenemos el siguiente resultado: 1. Hess f (X) es Def. Pos. (∀ X ∈ S) ⇒ f es estrictamente convexa en S. 2. Hess f (X) es Def. Neg. (∀ X ∈ S) ⇒ f es estrictamente c´oncava en S. Ejemplo.- La funci´on f (x, y) = x3 + 3y 2 , ¿es convexa en IR2 ? La matriz hessiana es ¶ µ 6x 0 Hess f (x, y) = 0 6 Antes de nada, observemos que el hecho de ser definida o semidefinida positiva, indistintamente, en cualquier punto (x, y) ∈ IR2 , se traduce8 en que sean: a = 6x ≥ 0,

c = 6 ≥ 0,

D2 = 36x ≥ 0

Pues bien, est´a claro que el signo de a = 6x no es siempre ≥ 0, ya que este signo es negativo, cuando x es negativo. Por tanto, no se verifica que nuestra matriz hessiana sea siempre definida o semidefinida positiva. En consecuencia, nuestra funci´on no es convexa. Ejemplo.- ¿Es c´oncava en IR2 la funci´oµ n f (x, y) ¶ = x3 + 3y 2 del ejemplo anterior? 6x 0 La matriz hessiana era: Hess f (x, y) = 0 6 Observemos que el hecho de que esta matriz sea definida o semidefinida negativa en cualquier punto (x, y) ∈ IR2 , se traduce en que sean: a = 6x ≤ 0, 8

c = 6 ≤ 0,

D2 = 36x ≥ 0

Estamos usando el criterio de los menores principales generalizados.

´ CLASICA: ´ 20CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. Y bien, esto no ocurre nunca, ya que c = 6 > 0. Por tanto, nuestra funci´on no es c´oncava. En definitiva, la funci´on dada no es ni c´oncava ni convexa en IR2 . Ejemplo.- La funci´on de antes, f (x, y) = x3 + 3y 2 , ¿es convexa en el conjunto convexo siguiente? S = {(x, y) ∈ IR2 /x > 0, y > 0 } µ ¶ 6x 0 La matriz hessiana es Hess f (x, y) = 0 6 Vemos que, cuando (x, y) ∈ S, es decir, cuando x > 0, y > 0, se tiene que: a = 6x > 0,

c = 6 > 0,

D2 = 36x > 0

Por tanto, esta matriz hessiana es definida positiva, en todo punto (x, y) ∈ S. Por tanto nuestra funci´on s´ı es convexa en el conjunto S. Es m´as, es estrictamente convexa en dicho conjunto S. Ejemplo.- (Funci´on polin´omica de segundo grado.) Dada una funci´on polin´omica general de segundo grado en dos variables, f (x, y) = a x2 + 2b x y + c y 2 + d x + k y + n (donde a, b, c, d, k y n son constantes arbitrarias). Los t´erminos de segundo grado, a x2 + 2b x y + c y 2 representan una forma cuadr´atica cuya matriz asociada es µ ¶ a b A= b c Podemos comprobar muy f´acilmente que f es convexa ⇐⇒ A es definida o semidefinida positiva . f es c´oncava ⇐⇒ A es definida o semidefinida negativa . (Vamos a comprobarlo. Para nuestra funci´on f (x, y), la matriz hessiana es µ ¶ µ ¶ 2a 2b a b Hess f (x, y) = =2 = 2A 2b 2c b c Esta matriz no depende del punto (x, y) ∈ IR2 (ya que, al derivar dos veces polinomios de grado dos se obtienen constantes). Observamos que la matriz hessiana (2A) tiene exactamente la misma clasificaci´on como forma cuadr´atica que la matriz A. Por tanto, f es convexa ⇔ Hessf (x, y) = 2A es D.P. o S.D.P. ⇔ A es D.P. o S.D.P.

´ Y CONVEXIDAD. 2.12. OPTIMIZACION

21

De manera an´aloga, f es c´oncava si y s´olo si A es definida o semidefinida negativa.)

Ejemplo.La funci´on polin´omica de grado dos f (x, y) = 3 x2 + 5 x y + 4 y 2 + 28 x + 45 y + 321 ¿es c´oncava o convexa? La matriz asociada a la forma cuadr´atica es µ 3 A= 5 2

5 2

¶

4

Esta matriz se clasifica como definida positiva (ya que a = 3 > 0, c = 4 > 0 y D2 = 12 − 25 = 23 > 0). 4 4 Por tanto, nuestra funci´on es convexa. De hecho, es estrictamente convexa. Ejemplo.- La funci´on polin´omica de grado dos g(x, y) = 4 x2 + 10 x y + 2 y 2 + 42 x + 65 y + 12 ¿es c´oncava o convexa? La matriz asociada a la forma cuadr´atica es µ ¶ 4 5 A= 5 2 Esta matriz es indefinida, porque D2 < 0. En consecuencia, esta funci´on g no es ni c´oncava ni convexa.

2.12.

Optimizaci´ on y convexidad.

Hemos visto antes que si S ⊂ IRn es un conjunto convexo y f : S → IR es una funci´on, entonces: Si la funci´on f es convexa y tiene alg´ un punto cr´ıtico, dicho punto cr´ıtico es un m´ınimo global. Si la funci´on f es c´oncava y tiene alg´ un punto cr´ıtico, ´este es un m´aximo global. NOTA: El resultado anterior no dice que una funci´on convexa tenga siempre m´ınimo global. S´olo dice que, en caso de que la funci´on convexa tenga alg´ un punto cr´ıtico, ´este es un m´ınimo global. Pero es perfectamente posible que una funci´on convexa no tenga puntos cr´ıticos, como por ejemplo, la funci´on exponencial en una variable, f (x) = ex .

´ CLASICA: ´ 22CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES.

Ejemplo.Tratamos de minimizar la funci´on f (x, y) = x2 + 5 y 2 − 4 x y − 8x + 10y + 9, definida en IR2 . Empezamos por comprobar si es convexa. Como es polin´omica de grado dos, miramos la matriz asociada a la forma cuadr´atica, µ ¶ 1 −2 A= −2 5 Vemos que es definida positiva. Por tanto, nuestra funci´on es convexa. Por tanto, en caso de que tenga alg´ un punto cr´ıtico, ´este es un m´ınimo global. Hallamos los puntos cr´ıticos: ¾ ∂f = 2x − 4y − 8 = 0 ∂x =⇒ x = 10, y = 3 ∂f = 10y − 4x + 10 = 0 ∂y Por tanto, el punto cr´ıtico (10, 3) es el m´ınimo global.

2.13.

Test de existencia de ´ optimo global.

Para un problema de minimizaci´ on. Si tenemos que resolver un problema de minimizaci´on sin restricciones, es decir, del tipo Min. f (X) , en primer lugar debemos ver si podemos garantizar la existencia de ´optimo(=m´ınimo) global. Para ello, nos planteamos las siguientes preguntas. 1. ¿La funci´on f es coerciva? 2. ¿La funci´on f es convexa y tiene al menos un punto cr´ıtico? Si al menos una de las dos preguntas anteriores tiene respuesta afirmativa, podemos asegurar que existe m´ınimo global. Para hallar el m´ınimo global podemos seguir el m´etodo de primer orden. Para un problema de maximizaci´ on. Si tenemos que resolver un problema del tipo siguientes preguntas.

Max.

f (X) , nos planteamos las

1. ¿La funci´on f es anticoerciva? 2. ¿La funci´on f es c´oncava y tiene al menos un punto cr´ıtico? Si al menos una de las dos preguntas anteriores tiene respuesta afirmativa, podemos asegurar que existe m´aximo global. Para hallarlo, seguiremos el m´etodo de primer orden.

´ ENTRE CONVEXIDAD Y COERCIVIDAD. 2.14. RELACION

2.14.

23

Relaci´ on entre convexidad y coercividad.

Al aplicarle el test de existencia de ´optimo global a un problema de, digamos, minimizaci´on, si la primera de las dos preguntas tiene respuesta afirmativa, ya no necesitamos responder a la segunda. Pero es bastante posible que las dos respuestas sean afirmativas. Por ejemplo, la funci´on f (x, y) = x2 + y 2 es una funci´on coerciva y tambi´en es una funci´on convexa. Eso nos lleva a pensar que tal vez que exista alguna relaci´on entre que una funci´on sea coerciva y que sea convexa. En concreto, nos podemos preguntar: ¿Toda funci´on coerciva es convexa? La respuesta es: no necesariamente. Por ejemplo, la funci´on de una variable f (x) = x4 − 4x2 , de la que damos su gr´afica a continuaci´on, es coerciva y no convexa.

Tambi´en podemos preguntarnos: ¿Toda funci´on convexa es coerciva? La respuesta es otra vez: no necesariamente. Por ejemplo, la funci´on exponencial f (x) = ex es convexa y no es coerciva. En definitiva, aunque puede darse el caso de que una funci´on sea convexa y tambi´en coerciva, el hecho de ser convexa no implica que sea coerciva ni al contrario. De manera an´aloga, el hecho de que una funci´on sea c´oncava no implica que sea anticoerciva ni al rev´es.

´ CLASICA: ´ 24CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES.

2.15.

´ ´ APENDICE. FORMAS CUADRATICAS.

1.- Formas cuadr´ aticas en dos variables. Una forma cuadr´atica en dos variables es una funci´on f (x, y) = a x2 + 2 b xy + c y 2 donde a, b y c son constantes reales. La expresi´on anterior se puede escribir usando matrices de la siguiente manera: µ ¶µ ¶ ¡ ¢ a b x f (x, y) = x y b c y µ

¶ a b La matriz A = recibe el nombre de matriz asociada a la forma cuadr´atica. b c Esta matriz es siempre una matriz sim´etrica. 1.1 Definici´ on: Clasificaci´ on de las formas cuadr´ aticas. Una forma cuadr´atica, f (x, y) = a x2 + 2 b xy + c y 2 se clasifica atendiendo al signo que tenga f (x, y). En concreto, la definici´on es la siguiente. 1. Se dice que la forma cuadr´atica es definida positiva si f (x, y) > 0 para todo (x, y) 6= (0, 0). 2. Se dice que es definida negativa si f (x, y) < 0 para todo (x, y) 6= (0, 0). 3. Se dice que es semidefinida positiva si f (x, y) ≥ 0 para todo (x, y) (y adem´as, existe (xo , yo ) 6= (0, 0) tal que f (xo , yo ) = 0). 4. Se dice que es semidefinida negativa si f (x, y) ≤ 0 para todo (x, y) (y adem´as, existe (xo , yo ) 6= (0, 0) tal que f (xo , yo ) = 0). 5. Se dice que es indefinida si existen dos puntos distintos, (x1 , y1 ) y (x2 , y2 ) tales que f (x1 , y1 ) > 0 y f (x2 , y2 ) < 0. Ejemplos.La forma cuadr´atica f (x, y) = 2x2 + y 2 es definida positiva, ya que f (x, y) > 0 para todo (x, y) 6= (0, 0).

´ ´ 2.15. APENDICE. FORMAS CUADRATICAS.

25

f (x, y) = 2x2 − y 2 es indefinida, ya que los valores de f (x, y) pueden ser tanto positivos como negativos. Por ejemplo, para (x, y) = (1, 0), vemos que f (1, 0) = 2 > 0. Y para (x, y) = (0, 1), se tiene que f (0, 1) = −1 < 0. La forma cuadr´atica f (x, y) = x2 − 2xy + y 2 = (x − y)2 es semidefinida positiva, ya que f (x, y) ≥ 0 para todo (x, y). Adem´as, toma el valor cero sobre alg´ un punto no nulo. Por ejemplo, f (1, 1) = 0. Algunas observaciones: Cualquiera que sea la forma cuadr´atica f (x, y), se tiene que f (0, 0) = 0. Toda forma cuadr´atica en dos variables cae en uno y s´olo uno de los tipos de la clasificaci´on, con excepci´on de la forma cuadr´atica trivial, (f (x, y) = 0, para todo (x, y) ∈ IR2 ), que es simult´aneamente semidefinida positiva y semidefinida negativa. Los ejemplos anteriores eran especialmente sencillos, por lo que hemos podido clasificar la forma cuadr´atica usando solamente la definici´on. Pero no siempre ocurre as´ı, lo que nos lleva a recordar criterios m´as u ´tiles para clasificar formas cuadr´aticas. 1.2 Criterio de los valores propios. Tenemos una forma cuadr´atica f (x, y) = a x2 + 2 b xy + c y 2 . La matriz asociada es ¶ µ a b A= b c Entonces: 1. A es definida positiva9 ⇔ Todos los valores propios de A son > 0. 2. A es definida negativa ⇔ Todos los valores propios de A son < 0. 3. A es indefinida ⇔ Existe alg´ un valor propio > 0 y alg´ un otro < 0. 4. A es semidefinida positiva ⇔ Todos los valores propios de A son ≥ 0 (y alguno de ellos es exactamente 0). 5. A es semidefinida negativa ⇔ Todos los valores propios de A son ≤ 0 (y alguno de ellos es exactamente 0) 9 Por comodidad, usaremos la expresi´on la matriz A es definida ... en lugar de la forma cuadr´ atica f es definida ...

´ CLASICA: ´ 26CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES.

Ejemplos.µ 1. Vamos a clasificar la forma cuadr´atica cuya matriz asociada es A =

−3 0 0 2

¶ .

Los valores propios son las ra´ıces de su polinomio caracter´ıstico, ¯ ¯ ¯ −3 − λ 0 ¯¯ ¯ = (−3 − λ)(2 − λ) = 0 pA (λ) = ¯ 0 2−λ ¯ Por tanto, los valores propios son: λ1 = −3 y λ2 = 2. Como son uno positivo y el otro negativo, esta forma cuadr´atica (´o esta matriz) se clasifica como indefinida. µ ¶ 1 2 2. Sea la forma cuadr´atica cuya matriz asociada es A = 2 5 Calculamos los valores propios: ¯ ¯ 1−λ 2 pA (λ) = ¯¯ 2 5−λ

¯ ¯ ¯ = (1 − λ)(5 − λ) − 4 = λ2 − 6λ + 1 ¯

2 Resolviendo √ la ecuaci´on λ − 6λ +√1 = 0 obtenemos los valores propios, que son 6 + 32 ∼ 6 − 32 ∼ λ1 = = 5,83 y λ1 = = 0,17. Puesto que ambos valores propios 2 2 son estrictamente positivos, nuestra matriz es definida positiva.

El ejemplo anterior muestra que el c´alculo de los valores propios puede ser tedioso. Existe otro criterio de clasificaci´on de formas cuadr´aticas, el de los menores principales, en el cual las operaciones son mucho m´as sencillas. 1.3 Criterio de los menores principales. Ses una forma cuadr´atica f (x, y) = a x2 + 2 b xy + c y 2 , cuya matriz asociada es µ ¶ a b A= b c Los menores principales de esta matriz son: De orden uno: D1 = a, De orden dos: D2 = ac − b2 (=el determinante de A). La clasificaci´on depende de los signos de estos menores principales. Se tiene que 1. D1 > 0, D2 > 0 ⇔ A es definida positiva. 2. D1 < 0, D2 > 0 ⇔ A es definida negativa.

´ ´ 2.15. APENDICE. FORMAS CUADRATICAS.

27

3. D1 > 0, D2 = 0 ⇒ A es semidefinida positiva. 4. D1 < 0, D2 = 0 ⇒ A es semidefinida negativa. 5. D2 < 0 ⇔ A es indefinida. Ejemplos.µ

1.

2.

3.

4.

¶ 1 2 Vamos a clasificar la forma cuadr´atica cuya matriz asociada es A = 2 5 Vemos que D1 = 1 > 0 y D2 = 5 − 4 = 1 > 0. Por tanto, esta matriz es definida positiva. µ ¶ −3 0 Para la matriz A = vemos que D2 = −3 < 0 y D2 = 3 > 0. Por 0 −1 tanto, esta matriz es definida negativa. ¶ µ 1 3 vemos que D2 = −7 < 0. Por tanto, esta matriz es Para la matriz A = 3 2 indefinida. µ ¶ 0 0 Para la matriz A = vemos que D1 = 0 y D2 = 0. Este caso no aparece 0 −1 contemplado en este criterio de los menores principales. En este caso, el criterio no decide. As´ı que no podemos clasificar esta forma cuadr´atica, salvo que recurramos al criterio de los valores propios o al criterio que vemos a continuaci´on.

Existe otro criterio, que tambi´en utiliza el signo de ciertos menores de la matriz, que presenta la ventaja de que siempre decide. Es el 1.4 Criterio de los menores principales generalizados. Ses una forma cuadr´atica f (x, y) = a x2 + 2 b xy + c y 2 , cuya matriz asociada es µ ¶ a b A= b c Los menores principales generalizados de esta matriz son: De orden uno: D1 = a, D10 = c (los elementos de la diagonal). De orden dos: D2 = ac − b2 (el determinante de la matriz) Se tiene que 1. A es definida positiva ⇔ a > 0, c > 0 y D2 > 0.

´ CLASICA: ´ 28CAP´ITULO 2. OPTIMIZACION PROGRAMAS SIN RESTRICCIONES. 2. A es definida negativa ⇔ a < 0, c < 0 y D2 > 0. 3. A es semidefinida positiva ⇔ a ≥ 0, c ≥ 0 y D2 ≥ 0 (siendo al menos uno de estos valores exactamente igual a 0). 4. A es semidefinida negativa ⇔ a ≤ 0, c ≤ 0 y D2 ≥ 0 (siendo al menos uno de estos valores exactamente igual a 0). 5. A es indefinida ⇔ D2 < 0. Ejemplos.µ

¶ 0 0 1. Vamos a clasificar la forma cuadr´atica cuya matriz asociada es A = 0 −1 Vemos que a = 0, c = −1 < 0, y D2 = 0. Por tanto, esta matriz es semidefinida negativa. ¶ µ 0 0 vemos que a = 0, c = 3 > 0, y D2 = 0. Por tanto, 2. Para la matriz A = 0 3 esta matriz es semidefinida positiva.

2.- Formas cuadr´ aticas en tres variables. Una forma cuadr´atica en tres variables es una funci´on f  a11 a12 ¡ ¢ f (x1 , x2 , x3 ) = x1 x2 x3 ·  a12 a22 a13 a23

: IR3 → IR del tipo    a13 x1 a23  ·  x2  a33 x3

o, lo que es lo mismo, f (x1 , x2 , x3 ) = a11 x21 + a22 x22 + a33 x23 + 2a12 x1 x2 + 2a13 x1 x3 + 2a23 x2 x3 La matriz sim´etrica

 a11 a12 a13 A =  a12 a22 a23  a13 a23 a33 

es la matriz asociada a la forma cuadr´atica. La definici´on de cu´ando una forma cuadr´atica en tres variables es definida positiva, definida negativa, etc. es totalmente an´aloga al caso de dos variables, as´ı que no la daremos. Para clasificar una forma cuadr´atica en tres variables se puede utilizar el criterio de los valores propios, que se expresa de la misma forma que para dos variables, pero que

´ ´ 2.15. APENDICE. FORMAS CUADRATICAS.

29

puede ser inc´omodo de utilizar debido a que hace falta calcular los valores propios de una matriz de orden tres y eso, en algunos casos, puede ser muy complicado. El otro criterio, el de los menores principales, se establece para el caso de tres variables de la siguiente manera. Tenemos la matriz sim´etrica de orden tres   a11 a12 a13 A =  a12 a22 a23  a13 a23 a33 Los menores principales son: De orden uno: D1 = ¯a11 . ¯ a a De orden dos: D2 = ¯¯ 11 12 a12 a22 De orden tres: D3 = |A|. Entonces,

¯ ¯ ¯. ¯

1. D1 > 0, D2 > 0, D3 > 0 ⇔ A es definida positiva. 2. D1 < 0, D2 > 0, D3 < 0 ⇔ A es definida negativa. 3. D1 > 0, D2 > 0, D3 = 0 ⇒ A es semidefinida positiva. 4. D1 < 0, D2 > 0, D3 = 0 ⇒ A es semidefinida negativa. 5. D3 6= 0 (y no se da el caso de Def. Pos. ´o Def. Neg.) ⇒ A es indefinida. Ejemplo.Consideramos la forma cuadr´atica cuya matriz asociada es   1 2 3 A =  2 −1 0  3 0 5 Vemos que D1 = 1, D2 = −5, y D3 = −16. Por tanto, esta forma cuadr´atica es indefinida.