Optimalidad - Programación no lineal sin restricciones y con restricciones PDF

Preview

Summary

Programación no lineal sin restricciones y con restricciones...

Description

Investigaci´on de Operaciones

Programaci´on no lineal Ebert Brea* ıa Escuela de Ingenier´ıa Industrial, Facultad de Ingenier´ Universidad Cat´olica Andr´es Bello. Caracas, 10 de octubre de 2019

Resumen Este documento presenta una muy breve introducci´on a la programaci´on no lineal, la cual comprende los distintos tipos de problemas de optimizaci´on, sus condiciones de optimalidad e incluye un simple ejemplo con el prop´osito de ofrecer una interpretaci´ on gr´afica de las condiciones de optimalidad. Adem´as, el lector podr´a encontrar ejercicios propuestos con el objeto de dejarle al lector la soluci´on de los problemas planteados. Palabras claves: optimizaci´on no lineal, condiciones de optimalidad.

Contenido 1. Formulaci´on 1.1. Problema sin restricciones . . . . . . . . . . . . . . . . . . . . . . . 1.2. Problema con restricciones de desigualdad . . . . . . . . . . . . . . . 1.3. Problema con restricciones de desigualdad e igualdad . . . . . . . . .

2 2 2 2

2. Problemas de optimizaci´on

3

3. Condiciones de optimalidad 3.1. Problemas sin restricciones . . . . . . . . . . . . . . . . 3.1.1. Condiciones necesarias de optimalidad . . . . . 3.1.2. Condiciones suficiente de optimalidad . . . . . . 3.2. Problema con restricciones de desigualdades . . . . . . . 3.3. Problema con restricciones de desigualdades e igualdades

*

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

5 5 5 7 8 9

Referencias

13

´Indice Alfab´etico

14

Email: [email protected]

1

Ebert Brea

1.

Formulaci´on

1.1. Problema sin restricciones Problema 1 Sea f (x) : Rn → R, entonces se dice que un problema de minimizaci´on sin restricciones viene expresado por minimice f (x), (1) n x∈R

donde f (x) es la llamada funci´on objetivo. Ejemplo 1 Un ejemplo de un problema de minimizaci´on sin restricciones es minimice n x∈R

4 n  (i) X x −α δ

i=1

2

− x(i) ,

(2)

donde α, δ ∈ R.

1.2. Problema con restricciones de desigualdad Problema 2 Sea f (x) : Rn → R y sean gi (x) : Rn → R la i´ esima funci´on para todo i ∈ {1, 2, . . . , m} de un conjunto de funciones g. Entonces, se dice que un problema de minimizaci´on con restricciones de desigualdad viene expresado por minimice f (x); n x∈R

(3a)

sujeto a: gi (x) ≤ 0,

∀i ∈ {1, 2, . . . , m}.

(3b)

1.3. Problema con restricciones de desigualdad e igualdad Problema 3 Sea f (x) : Rn → R, sean gi (x) : Rn → R la i´ esima funci´on para todo i ∈ n {1, 2, . . . , mg } de un conjunto de funciones g, y sean hj (x) : R → R la jesima ´ funci´on para todo j ∈ {1, 2, . . . , mh } de un conjunto de funciones h, Entonces, se dice que un problema de minimizaci´on con restricciones de desigualdad e idualdad viene expresado por minimice f (x); n x∈R

(4a)

sujeto a: gi (x) ≤ 0,

∀i ∈ {1, 2, . . . , mg }.

(4b)

hj (x) = 0,

∀j ∈ {1, 2, . . . , mh }.

(4c)

2

Ebert Brea

Problemas de optimizaci´on

2.

osito de mostrarle En esta secci´on se introduce algunos problemas de optimizaci´on con el prop´ al lector algunos ejemplos de aplicaci´on dentro de la geometr´ıa anal´ıtica, dejando al lector algunos ejercicios planteado para ser resueltos. Ejemplo 2 Formule un problema de optimizaci´on que permita determinar la m´ınima distancia entre un punto que est´a sobre la superficie definida por la funci´on f (x) : R2 → R y otro punto que on g(x) : R2 → R, donde est´a ubicado sobre la superficie dada por la funci´ 2

2

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

∀x ∈ R2 .

g(x) = −(x(1) − 5)2 − (x(2) − 5)2 ,

∀x ∈ R2 .

(5a) (5b)

Soluci´on: a sobre la Denote un punto sobre la superficie de la curva f (x) como x1 , y a un punto que est´ superficie g(x) como x2 . Definido estos puntos entonces se puede decir que:   (1) (2) (6) x1 = x1 , x1 , f (x) .   (2) (1) x2 = x2 , x2 , g(x) .

(7)

||x2 − x1 ||2 = (x2 − x1 )t (x2 − x1 ).

(8)

Ahora, el valor al cuadrado de la distancia entre x1 y x2 , viene dado por

Aplicando la Ec. (8), se obtiene 2

||x2 −x1 || =



(1) x2

−

(1) x1

2 2  2 2  2   (2)2 (1)2 (2) (2) (2) (1) . + x2 − x1 + − x2 − 5 − x2 − 5 − x1 − x1 (9)

Quedando entonces el problema como Entonces, el problema queda formulado como minimice ||x2 − x1 ||2 , x∈R4

(10)

donde ||x2 − x1 ||2 viene dado por la Ec. (9). Ejercicio 1 Formule un problema de optimizaci´on que permita determinar la m´ınima distancia t t entre un punto (x1t , f (x1 )) del lugar geom´etrico definido por f (x); y un punto (x2t , g(x2 )) del lugar geom´etrico g(x), de acuerdo con los siguientes casos: I)

a) f (x) : R → R, donde f (x) = (x − 2)2 , ∀ x ∈ R; b) g(x) : R → R, donde g(x) = 1 − x, ∀ x ∈ R. 3

Ebert Brea

II)

a) f (x) : R3 → R, donde f (x) = b) g(x) : R3 → R, donde g(x) =

III)

P3

(k)2 , ∀ x ∈ R3 ; k=1 x P3 − k=1 x(k) − 30, ∀ x

∈ R3 ;

a) f (x) : R → R, donde f (x) = x2 x, ∀ x ∈ R;

b) g(x) : R → R, donde g(x) = −(x − 1)2 , ∀ x ∈ R. Ejercicio 2 Sean dos c´ırculos, no solapados entre s´ı, c1 y c2 con radios r1 y r2 , respectivamente.

C

R

C1 r1

C2

r2

Figura 1: Representaci´ on gr´afica del Problema 2 Si ambos c´ırculos est´an inscritos en una circunferencia C de radio R, y sus centros est´ an alineados con el centro de la circunferencia C, tal como son mostrados en la Fig. 1. Entonces: a) formule un problema de optimizaci´on, tal que permita minimizar el a´ rea no cubierta por los c´ırculos c1 y c2 dentro de la circunferencia C ; b) identifique a trav´es de m´etodos matem´aticos de optimizaci´on, las soluciones optimas ´ del problema formulado en la parte a). Ejercicio 3 Sean un cuadrado y una circunferencia con centro en el centro del cuadrado, tal como es mostrado en la Fig. 2 de la p´agina 5. Si la longitud de los per´ımetros del cuadrado y la circunferencia ambos suman L. Entonces: a) formule un problema de optimizaci´on, tal que permita dibujar la circunferencia de m´axima a´ rea que est´e inscrita en el cuadrado; b) identifique a trav´es de m´etodos matem´aticos de optimizaci´on, las soluciones optimas ´ del problema formulado en la parte a).

4

Ebert Brea

Figura 2: Representaci´ on gr´afica del Problema 3 c) formule un problema de optimizaci´on, tal que permita dibujar el cuadrado de m´axima a´ rea tal est´e inscrito en la circunferencia; d) identifique a trav´es de m´etodos matem´aticos de optimizaci´on, las soluciones optimas ´ del problema formulado en la parte c).

3.

Condiciones de optimalidad

Definici´on 1 (M´ınimo local) Sea el Problema 1 de minimizaci´on. Entonces se dice que x ˆ soluciona localmente el problema, si f (ˆ x) ≤ f (x) para todo x ∈ Rn x ∈ Nε (ˆ x). Definici´on 2 (M´ınimo global) Sea el Problema 1 de minimizaci´on. Entonces se dice que x ˆ solun ciona globalmente el problema, si f (ˆ x) ≤ f (x) para todo x ∈ R

3.1. Problemas sin restricciones Sea el Problema 1 de la p´ agina 2. Entonces se dice que si x ˆ soluciona localmente, este ´ tiene las propiedades siguientes: 3.1.1.

Condiciones necesarias de optimalidad

Teorema 1 (Direcci´on descendente) Sea f (x) : Rn → R una funci´on diferenciable en x0 . Si existe un vector d ∈ Rn tal que ∇f (x0 )t d < 0, entonces existe un δ > 0 tal que f (x0 +λd) < f (x0 ) para todo 0 < λ < δ, por tanto d es una direcci´on de descenso de f (x) en x0 5

Ebert Brea Demostraci´on. Partiendo del hecho que f (x) es diferenciable, se tiene que f (x0 + λd) = f (x0 ) + λ∇f (x0 )t d + λ||d||α(x0 ; λd)

(11)

donde α(x0 ; λd) → 0 cuando λ → 0, lo que arroja f (x0 + λd) − f (x0 ) = ∇f (x0 )t d + ||d||α(x0 ; λd). λ

(12)

Debido al hecho de que ∇f (x0 )t d < 0 y α(x0 ; λd) → 0 cuando λ → 0, entonces existe un δ > 0 tal que ∇f (x0 )t d + ||d||α(x0 ; λd) < 0, 0 < λ < δ. (13) Por tanto, como λ > 0, entonces de Ec. (12) f (x0 + λd) < f (x0 ).

(14)

ˆ. Si xˆ soluciona localmente el Corolario 1 Sea f (x) : Rn → R una funci´on diferenciable en x Problema 1 de la p´agina 2, entonces ∇f (ˆ x) = 0n Demostraci´on. Suponga que x ˆ es un m´ınimo local del Problema 1 de la p´agina 2, y que existe una x) justo en x ˆ, y por tanto ∇f (ˆ x)t d = −||∇f (ˆ x)||2 < 0. direcci´on de descenso d = −∇f (ˆ agina 5 se tiene entonces que debe existir un punto xˆ + λd, Por otra parte, del Teorema 1 de la p´ tal que f (ˆ x − λ||∇f (ˆ x)||2 ) < f(ˆ x), ∀0 < λ < δ, (15) agina 5. lo que absolutamente contradice el Teorema 1 de la p´ ˆ es un Teorema 2 Sea f (x) : Rn → R una funci´on doblemente diferenciable justo en xˆ. Si x m´ınimo local del Problema 1 de la p´agina 2. Entonces x ˆ es un punto estacionario, lo que permite x) es semidefinida asegurar que ∇f (ˆ x) = 0n , y adem´as f (x) es convexa justo en xˆ. A saber, H(ˆ positiva justo en xˆ, y se denota como H(ˆ x)  0. Demostraci´on. Debido a que se parte del hecho que f (x) justo en xˆ es doblemente diferenciable, se tiene entonces 1 f (ˆ x + λd) = f (ˆ x) + λ∇f (ˆ x)t d + λ2 dt H(ˆ x)d + λ2 ||d||2 α(ˆ x; λd), 2

(16)

donde α(ˆ x; λd) → 0 cuando λ → 0. Debido al hecho de que se ha afirmado que xˆ es al menos un m´ınimo local, entonces del Corolario 1 se puede asegurar que ∇f (ˆ x) = 0n , lo que arroja f (ˆ x + λd) − f (ˆ x) 1 t x)d + ||d||2 α(ˆ x; λd), = d H(ˆ 2 2 λ

(17)

6

Ebert Brea Como xˆ es un m´ınimo local, entonces f (ˆ x + λd) − f (ˆ x) > 0, en consecuencia 1 t d H(ˆ x)d + ||d||2 α(ˆ x; λd) ≥ 0 2

(18)

Al hacer λ → 0, claramente de Ec. (18) se tiene que dt H(ˆ x)d ≥ 0, y por tanto H(ˆ x)  0, dado que d 6= 0n . 3.1.2.

Condiciones suficiente de optimalidad

La condici´on suficiente se refiere aquellas condiciones de optimalidad que al ser satisfechas en xˆ, permite asegurar que xˆ es un m´ınimo local. Teorema 3 Sea f (x) : Rn → R una funci´on doblemente diferenciable justo en el punto xˆ. Si ∇f (ˆ x) = 0n y H(ˆ x)  0, entonces x ˆ es estrictamente un m´ınimo local. Demostraci´on. V´ease (Bazaraa et al., 2006, Cap. 4) ˆ. Entonces se Teorema 4 (m´ınimo global) Sea f (x) : Rn → R una funci´on pseudoconvexa en x dice que xˆ soluciona globalmente el Problema 1 de la p´agina 2 si y s´olo si (ssi) ∇f (ˆ x) = 0n . Demostraci´on. Debido al Corolario 1 de la p´agina 6, se tiene que si x ˆ soluciona globalmente x) = 0n . Ahora, debido a que f (x) es pseudoconvexa en Problema 1 de la p´agina 2, entonces ∇f (ˆ xˆ se tiene que para cualquier x ∈ R, f (x) ≥ f (ˆ x). Ejercicio 4 Empleando las condiciones de optimalidad, identifique las soluciones o´ ptimas del problema:  2  2  minimice a − x(1) + 2a − x(1) x(2) , (19) x∈R2

 t donde: a > 0 es un escalar real; y adem´as x = x(1), x(2) ∈ R2 denota el vector de decisi´on.

Ejercicio 5 Empleando las condiciones de optimalidad, identifique las soluciones m´ınimas factibles del problema: !  (k) 4 2 X  (k) 2 x minimice − x −2 , (20) x∈R2 5 k=1  t donde x = x(1), x(2) ∈ R2 denota el vector de decisi´on.

Ejercicio 6 Empleando las condiciones de optimalidad, identifique las soluciones m´ınimas factibles del problema: !  (k) 4 3 X  (k) 2 x minimice − x −2 , (21) x∈R3 5 k=1  t donde x = x(1), x(2) , x(3) ∈ R3 denota el vector de decisi´on. 7

Ebert Brea

3.2. Problema con restricciones de desigualdades Definici´on 3 (Cono de direcciones factibles) Sea S un conjunto no vac´ıo en Rn , y sea xc ∈ cl (S). El cono de direcciones factibles de S en xc, el cual es denotado por D, est´a dado por D = {d ∈ Rn : d 6= 0n , {xc + λd} ∈ S},

∀0 < λ < δ,

(22)

donde δ > 0. Teorema 5 Sea f (x) : Rn → R y considere el problema a minimizar f (x) sujeto a x ∈ S, donde S= 6 ∅. Suponga adem´as que f (x) es diferenciable en un punto x ˆ ∈ S. Si x ˆ soluciona localmente el problema, entonces Fo ∩ D = ∅, donde Fo = {d ∈ Rn : ∇f (ˆ x)t d < 0},

(23)

D es el cono de direcciones factibles. Demostraci´on. V´ease (Bazaraa et al., 2006, Cap. 4) Teorema 6 Sea el Problema 2 de la p´agina 2. Sea x ˆ un punto factible, y sea I = {i : gi (ˆ x) = 0}, es decir, las restricciones activadas o saturadas. M´as a´un, suponga que tanto f (x) como gi (x) son diferenciables en el punto x ˆ para todo i ∈ I y que gi (x) para todo i ∈ / I son continuas en el punto xˆ. Si x ˆ es un m´ınimo local del problema, entonces Fo ∩ Go = ∅, donde Fo = {d ∈ Rn : ∇f (ˆ x)t d < 0}, Go = {d ∈ Rn : ∇gi (ˆ x)t d < 0},

∀i ∈ I.

(24) (25)

Demostraci´on. V´ease (Bazaraa et al., 2006, Cap. 4) Teorema 7 (Fritz John) Sea X un conjunto abierto y no vac´ıo en Rn , y sean f (x) : Rn → R y gi (x) : Rn → R para todo i ∈ {1, 2, . . . , mg }. Considere el Problema P f (x); minimice n

(26a)

x ∈ X;

(26b)

∀i ∈ {1, 2, . . . , m}.

(26c)

x∈R

sujeto a: gi (x) ≤ 0,

x) = 0}, es decir, las restricciones Sea x una soluci´on factible del problema y sea I = {i : gi (ˆ activadas o saturadas. ˆ para todo i ∈ I Adem´as, suponga que tanto f (x) como gi (x) son diferenciables en el punto x y que gi (x) para todo i ∈ / I son continuas en el punto x ˆ. Si x ˆ soluciona localmente el Problema P , entonces existen escalares µ0 y µi para todo i ∈ I, tal que X µi ∇gi (ˆ x) = 0n , (27) µ0 ∇f (ˆ x) + i∈I

8

Ebert Brea

donde µ0 > 0, µi > 0 ∀i ∈ I.

3.3. Problema con restricciones de desigualdades e igualdades on necesaria de optimalidad local. El siguiente teorema constituye lo que se llama una condici´ Teorema 8 (Fritz John) Sea X un conjunto abierto y no vac´ıo en Rn , y sean f (x) : Rn → R y gi (x) : Rn → R para todo i ∈ {1, 2, . . . , mg }. Considere el Problema P minimice f (x); n

(28a)

x ∈ X;

(28b)

gi (x) ≤ 0,

∀i ∈ {1, 2, . . . , m}.

(28c)

hi (x) = 0,

∀i ∈ {1, 2, . . . , mh }.

(28d)

x∈R

sujeto a:

Sea x una soluci´on factible del problema y sea I = {i : gi (ˆ x) = 0}, es decir, las restricciones activadas o saturadas. Adem´as, suponga que tanto f (x) como gi (x) son diferenciables en el punto x ˆ para todo i ∈ I y que gi (x) para todo i ∈ / I son continuas en el punto x ˆ. Si x ˆ soluciona localmente el Problema P , entonces existen escalares µ0 y µi para todo i ∈ I, tal que µ0 ∇f (ˆ x) +

X

µi ∇gi (ˆ x) = 0n +

mh X

νi ∇hi (ˆ x) = 0n ,

(29)

i=1

i∈I

donde µ0 > 0, µi > 0,

∀i ∈ I.

∀i ∈ {1, 2, . . . , mh }.

νi > 0,

Demostraci´on. V´ease (Bazaraa et al., 2006, Cap. 4) Teorema 9 (Karush-Kuhn-Tucker(KKT)-Necesarias) Sea X un conjunto abierto y no vac´ıo en Rn , y sean f (x) : Rn → R; gi (x) : Rn → R para todo i ∈ {1, 2, . . . , mg }; y hi (x) : Rn → R para todo i ∈ {1, 2, . . . , mh }. Considere el Problema P f (x); minimice n

(30a)

x ∈ X;

(30b)

gi (x) ≤ 0,

∀i ∈ {1, 2, . . . , mg }.

(30c)

hi (x) = 0,

∀i ∈ {1, 2, . . . , mh }.

(30d)

x∈R

sujeto a:

9

Ebert Brea Sea xˆ una soluci´on factible del problema y sea I = {i : gi (ˆ x) = 0}, es decir, las restricciones activadas o saturadas. Adem´as, suponga que tanto f (x) como gi (x) son diferenciables en el punto xˆ para todo i ∈ I y que las gi (x) para todo i ∈ / I son continuas en el punto x ˆ, y las hi (x) son continuamente diferenciables en el punto xˆ. M´as a´un, suponga que tanto los ∇gi (x) para todo i ∈ I como los ∇hi (x) son linealmente independientes en el punto xˆ. Si xˆ soluciona localmente el Problema P, entonces existen escalares µi para todo i ∈ I y νi para todo i ∈ {1, 2, . . . , mh }, tal que ∇f (ˆ x) +

X

µi ∇gi (ˆ x) +

mh X

νi ∇hi (ˆ x) = 0n ,

(31)

i=1

i∈I

donde µi > 0 ∀i ∈ I. Demostraci´on. Del Teorema 7 de la p´agina 8, se tiene que de la Ec. (27) de la p´ agina 8 µ0 > 0, dado que si µ0 = 0, entonces los ∇gi (x) para todo i ∈ I como los ∇hi (x) no son linealmente independientes en el punto xˆ. Es decir, µ0 ∇f (ˆ x) +

X

µi ∇gi (ˆ x) +

νi ∇hi (ˆ x) = 0n ,

(32)

i=1

i∈I

X

mh X

µi ∇gi (ˆ x) +

mh X

νi ∇hi (ˆ x) = 0n ,

(33)

i=1

i∈I

Ejemplo 3 Identifique y represente gr´ aficamente la soluci´on del problema: 2

2

minimice x(1) + x(2) ; 2

(34)

2x(1) + 4x(2) ≥ 16

(35a)

x∈R

sujeto a: (1)

4x

(2)

+ 2x

≥ 16

(35b)

Soluci´on Con el prop´osito de encontrar una soluci´on al problema, se debe reexpresar el problema en su forma can´onica, lo que implica que el problema queda 2

2

minimice x(1) + x(2) ; 2

(36)

x∈R

10

Ebert Brea

sujeto a: g1 (x) = 16 − 2x(1) − 4x(2) ≤ 0

(37a)

g2 (x) = 16 − 4x(1) − 2x(2) ≤ 0

(37b)

Bajo el supuesto de que ambas restricciones se activan, se tiene que I = {1, 2}, y al aplicar la condici´on necesaria de KKT se tiene         −4 0 2 xˆ(1) −2 + µ2 = (38a) + µ1 (2) −4 −2 0 2 xˆ g1 (ˆ x) = 16 − 2ˆ x(1) − 4ˆ x(2) = 0

(38b)

g2 (ˆ x) = 16 − 4ˆ x(1) − 2ˆ x(2) = 0

(38c)

De las Ecs. (38b) y (38c), se obtiene que x ˆ = (8/3, 8/3)t , y sustituyendo este resultado en la 8 Ec. (38a), se tiene que µ1 = µ2 = 9 ≥ 0. Por tanto, el punto xˆ = (8/3, 8/3)t es un punto que satisface la condici´on necesario de KKT, y en consecuencia es denominado punto KKT. x(2) 12 10 8

g1 (x) = 0

f (x) ˆ 6 4

µ2 g2 (x) ˆ −6

−4

−2

2 µi i=1

gi (x) ˆ

2

0

xˆ

2 µ1 g1 (x) ˆ

4

6

8

10

12 x(1)

−2 −4 g2 (x) = 0 −6

x), µ1 ∇g1 (ˆ x) y µ2 ∇g2 (ˆ x) Figura 3: Representaci´ on gr´afica de un punto KKT, ∇f (ˆ La Fig. 3 muestra una explicaci´on de como es anulado el vector ∇f (ˆ x) por los vectores ∇g1 (ˆ x) son ajustado por sus respectivos y ∇g2 (ˆ x), cuando estos ultimos ´ P2 multiplicadores µ1 y µ1 . Note que la figura muestra los vectores ∇f (ˆ x) y la suma ponderada i=1 µi ∇gi (ˆ x) por los multiplicadores 11

Ebert Brea µi para i ∈ {1, 2}, anclados sobre el punto x ˆ = (8/3, 8/3)t . La figura tambi´ en representa en color crema la regi´on de factibilidad del problema, as´ı como las curvas de nivel de la funci´on objetivo, mostrando las cotas de mayor nivel de la curvas de nivel mediante la representaci´on de mayor intensidad de color azul. aficamente la soluci´on del problema: Ejercicio 7 Identifique y represente gr´  2 2 minimice x(1) − 4 + x(2) ; 2

(39)

2x(1) + 4x(2) ≥ 16;

(...