ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal José María Ferrer Caja Universidad Pontificia Comillas

Planteamiento general min f (x ) x

g i (x ) ≤ 0

∀i = 1,..., m

f , gi :
n →



La teoría se desarrolla para problemas de minimización, los problemas de maximización se tratan de forma análoga
En un mismo problema puede haber restricciones de igualdad y de desigualdad
Las funciones f, gi pueden ser diferenciables o no serlo
La resolución es más difícil y costosa que en optimización lineal
Existen algoritmos específicos para ciertos problemas ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 1

Clasificación (1)
Optimización sin restricciones min f (x ) x



Es importante distinguir si f es o no continua y/o diferenciable


Optimización con restricciones lineales min f (x ) x

Ax = b 

Existe una extensión del algoritmo simplex para resolverlo


Programación cuadrática 1 T min c x + x Qx x 2 Ax = b T



(Q ∈
n×n )

Aparece en muchas situaciones. Existen algoritmos eficientes

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 2

Clasificación (2)
Programación convexa f , g i convexas 

Todo mínimo local es global



Si el problema es de maximización, las funciones deben ser cóncavas


Programación separable n

f (x ) = ∑ fj (x j ) j =1 n

gi (x ) = ∑ gi j (x j ) j =1



Cumple la hipótesis de aditividad de la PL

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 3

Clasificación (3)
Programación geométrica n

f (x ), g i (x ) =

∑ c P (x ) j

j

j =1

a

a

a

Pj (x ) = x 1 j 1 x 2 j 2 ...x n jn , j = 1,..., n 

Problemas de diseño en ingeniería


Programación fraccional f (x ) =

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

f1(x ) f2 (x )

Optimización no lineal- 4

Expansión en serie de Taylor
Aproximación del valor de una función por un polinomio 

Se conoce f(x0). Se desea obtener f(x)

f (x ) = f (x 0 + p )  f (x 0 ) + ∇f (x 0 )T p +

1 T 2 p ∇ f (x 0 )p 2

x, x 0 ∈
n p = x − x0

∇f ∇2 f



Gradiente de la función Matriz hessiana de la función

Una función polinómica coincide con su polinomio de Taylor

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 5

Expansión en serie de Taylor. Ejemplo
Obtener el polinomio de Taylor de grado 2 de f (x , y ) = e 2 x −y
Calcular aproximadamente f (0.1, − 0.2)  Usamos el punto (x0,y0) = (0,0) pT = (x,y) - (0,0) = (x,y) f (x , y ) = e 2 x −y ⇒ f (0, 0) = 1  f   2e 2 x −y   2   x ∇ f (x , y ) =   =  2 x −y  ⇒ ∇ f (0, 0) =      fy  −e − 1  f   2 x −y  4 − 2 − 2e 2 x −y   xx fyx   4e  2 2   ∇ f (x , y ) =  ⇒ ∇ f (0, 0) =  =  2 x −y 2 x −y     fxy fyy  − 2e − 2 1  e  1 T 2 p ∇ f (0, 0)p = 2  4 − 2 1 2  x   2 y  = 1 + 2 x − y + 2 x − 2 xy + y    y − 2 1   2  

f (x , y )  f (0, 0) + ∇ f (0, 0)T p + x  1  = 1 + 2 − 1   + x y  2

(

)

(

)

f (0.1, − 0.2)  1 + 0.2 + 0.2 + 0.02 + 0.04 + 0.02 = 1.48 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 6

Matrices simétricas. Menores
Se llaman menores de una matriz a los determinantes de las submatrices cuadradas de la matriz
Menores principales de una matriz (cuadrada): se obtienen cruzando k filas cualesquiera con sus respectivas columnas 

Existen 2n – 1 menores principales en una matriz de orden n


Menores de esquina de una matriz (cuadrada): se obtienen cruzando las k primeras filas con sus respectivas columnas 

Existen n menores de esquina en una matriz de orden n


La matriz cuadrada A (de orden n) es simétrica si At = A ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 7

Matrices definidas y semidefinidas positivas
La matriz simétrica A (de orden n) es semidefinida positiva si x T Ax ≥ 0 ∀x ∈
n o bien

todos sus autovalores son no negativos o bien

todos sus menores principales son no negativos
La matriz simétrica A (de orden n) es definida positiva si x T Ax > 0

∀ x ∈
n − {0}

o bien

todos sus autovalores son positivos o bien

todos sus menores de esquina son positivos ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 8

Matrices definidas y semidefinidas negativas
La matriz simétrica A (de orden n) es semidefinida negativa si x T Ax ≤ 0 ∀x ∈
n o bien

todos sus autovalores son no positivos o bien

-A es semidefinida positiva
La matriz simétrica A (de orden n) es definida negativa si x T Ax < 0

∀ x ∈
n − {0} o bien

todos sus autovalores son negativos o bien

sus menores de esquina son alternativamente 0, etc. o bien ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

-A es definida positiva Optimización no lineal- 9

Funciones convexas y cóncavas
La función f es convexa en un conjunto X si ∀x , y ∈ X , ∀λ ∈ [0,1]

f (λx + (1 − λ)y ) ≤ λ f (x ) + (1 − λ )f (y )


La función f es cóncava si -f es convexa
La función f es convexa (cóncava) en un punto x0 si existe un entorno X de en el que la función es convexa (cóncava)

Convexa

Cóncava Convexa

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Cóncava Optimización no lineal- 10

Funciones convexas y cóncavas. Hessiano
La función f es convexa en el punto x0 si la matriz hessiana es semidefinida positiva en x0
La función f es cóncava en el punto x0 si la matriz hessiana es semidefinida negativa en x0
La región f(x)≤0 es convexa si la matriz hessiana es semidefinida positiva en todos sus puntos
La región f(x)≤0 es cóncava si la matriz hessiana es semidefinida negativa en todos sus puntos f (x , y ) = x 2 − y 2  2 ∇ f (x , y ) =   0

x2 − y ≤ 0 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

0   0 

Semidefinida positiva

Región convexa Optimización no lineal- 11

Optimización sin restricciones y diferenciabilidad
Condición necesaria de optimalidad (para funciones diferenciables) x * es mínimo local de f (x ) ⇒ ∇ f (x *) = 0


Condición necesaria de optimalidad (para funciones dos veces diferenciables)   ∇f (x *) = 0  x * es mínimo local de f (x ) ⇒  2  ∇ f (x *) semidefinida positiva   


Condición suficiente de optimalidad (para funciones dos veces diferenciables)    ⇒ x * es mínimo local estricto de f (x )  ∇2 f (x *) definida positiva     ∇f (x *) = 0

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 12

Optimización sin restricciones y convexidad
Condición necesaria y suficiente de optimalidad (para funciones convexas y dos veces diferenciables) x * es mínimo global de f (x ) ⇔ ∇ f (x *) = 0 

2 2 Ejemplo: min f (x , y ) = x + 3y + 2xy − 4y

 2x + 2y  0  =   ⇒ (x , y ) = (−1,1) ∇f (x , y ) =   6y + 2x − 4 0 2 2  2 ∇ f (x , y ) =   definida positiva ∀(x , y ) 2 6 f es convexa En (-1,1) se alcanza el mínimo global de f: f(-1,1) = - 2 ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 13

Optimización con restricciones. Lagrangiano (1) min f (x ) x


Se tiene el problema

g i (x ) ≤ 0

i = 1,..., m

h j (x ) = 0

j = 1,..., l

x ∈ X ⊆
n


Su función lagrangiana o lagrangiano es: m

l

L(x , λ, µ) = f (x ) + ∑ λi g i (x ) + ∑ µ j h j (x ) i =1

λ ∈
m , µ ∈
l




j =1

Multiplicadores de Lagrange

 L(x , λ, µ) proporciona una cota inferior de f (x ) para λ ≥ 0, µ 

Interesa la cota inferior más ajustada max L(x , λ, µ)


Relajación lagrangiana ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

λ ≥0,µ

{

}

min max L(x , λ, µ) x ∈X

λ ≥0,µ

Optimización no lineal- 14

Optimización con restricciones. Lagrangiano (2)
Si todas las restricciones son de igualdad:   

El mínimo del lagrangiano coincide con el mínimo de la función En el mínimo, el gradiente de la función objetivo es combinación lineal de los gradientes de las restricciones Los coeficientes de la c.l. son los multiplicadores


Para el problema lineal

min cT x x

Ax = b  



T

T

Lagrangiano: L(x , µ) = c x + µ (Ax − b ) Aplicando la condición necesaria ∇L(x * , µ * ) = 0

∇x L(x , µ) = c + AT µ

c + AT µ = 0 ⇒ c = −AT µ

∇µL(x , µ) = Ax − b

Ax − b = 0 ⇒ Ax = b

Los multiplicadores son las variables duales cambiadas de signo

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 15

Condiciones de optimalidad de KKT (1)
Condiciones necesarias de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad 

Sea el problema P

min f (x ) x

gi (x ) ≤ 0

i = 1,..., m

x ∈X n  X ⊆
es abierto y no vacío  Sea x * un punto factible (verifica las restricciones)  Sea I = {i / g i ( x * ) = 0 }  Sean f , {g i , i ∈ I } diferenciables en x *  Sean {g i , i ∉ I } continuas en x *  Sean {∇ g i (x * )} linealmente independientes i ∈I

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 16

Condiciones de optimalidad de KKT (2)
Condiciones necesarias de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad *  x es mínimo local de P ⇒ existen escalares {λi , i ∈ I } tales que

∇ f (x * ) +

∑ λ ∇ g (x i

i

*

)= 0

i ∈I

λi ≥ 0



∀i ∈ I

* Si además {g i , i ∉ I } son diferenciables en x m *

∇ f (x ) +

∑

λ i ∇ g i (x * ) = 0

i =1

*

λi g i (x ) = 0 i = 1, ..., m λi ≥ 0 i = 1, ..., m



Las condiciones necesarias para máximo local son idénticas salvo el signo de los multiplicadores: λi ≤ 0

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 17

Condiciones de KKT. Ejemplo (1) m in f (x , y ) = 9y − (x − 5)2 x ,y

−x 2 + y ≤ 0 −x − y ≤ 0 x −1≤ 0


Condiciones de KKT

  − 2(x − 5) − 2 x λ 1 − λ 2 + λ 3 = 0    9 + λ1 − λ 2 = 0    2  λ ( − x + y) = 0  1   λ 2 (− x − y ) = 0    λ 3 ( x − 1) = 0     λ ,λ ,λ ≥ 0   1 2 3 


Además se deben cumplir las restricciones originales de factibilidad 2   − x +y ≤ 0    −x − y ≤ 0   x −1 ≤ 0    ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 18

Condiciones de KKT. Ejemplo (2)
Se resuelve distinguiendo para cada multiplicador que sea nulo o no  λ 2 = 0 ⇒ λ 1 = − 9 < 0 Imposible. Luego se tiene λ 2 ≠ 0  λ2 ≠ 0 ⇒ y = −x

  − 2x + 10 − 9 + λ3 = 0  • λ 1 = 0 ⇒ λ 2 = 9 . Queda el sistema   λ (x − 1) = 0   3



λ 3 = 0 ⇒ A = (1 2 , − 1 2), λ A = (0, 9, 0 )



λ 3 ≠ 0 ⇒ B = (1, − 1), λ B = (0, 9, 1 )

2 2 • λ 1 ≠ 0 ⇒ y = x ⇒ x = − x ⇒ x (x + 1) = 0

 

x = 0 ⇒ y = 0 ⇒ C = (0, 0), λC = (1, 1 0, 0 ) x = − 1 ⇒ y = 1 ⇒ λ 3 = 0 ⇒ λ 1 = − 3, λ 2 = 6

Imposible


Se han obtenido 3 puntos KKT candidatos a mínimos: A = (1 2 , − 1 2), ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

B = (1, − 1),

C = (0, 0) Optimización no lineal- 19

Condiciones de KKT. Ejemplo (3)
Análisis gráfico: 10 − 2 x   ∇ f (x , y ) =   9    9  ∇ f (A ) = ∇ f (1 / 2, − 1 / 2) =    9   8  ∇ f (B ) = ∇ f (1, − 1) =    9  10  ∇ f (C ) = ∇ f (0, 0) =    9 

C


B y C son mínimos locales estrictos
A no es nada
No existe mínimo global, la función no es acotada ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

A B

Optimización no lineal- 20

Condiciones de optimalidad de KKT (3)
Condiciones suficientes de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad   

Sea x * un punto factible (verifica las restricciones) de P Sea I = {i / g i ( x * ) = 0 } * Sean f , {g i , i ∈ I } convexas y diferenciables en x

Si existen {λi , i ∈ I } tales que

* *   ∇ f ( x ) + λ ∇ g ( x ∑ i i )= 0   i ∈I   λ ≥ 0 ∀i ∈ I    i

* entonces x es mínimo local de P

Si además f , {g i , i ∈ I } son convexas y diferenciables en todo el * conjunto factible, entonces x es el mínimo global de P
Para el caso de maximización, la función objetivo debe ser cóncava y los escalares λi ≤ 0 ∀ i ∈ I ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 21

Condiciones de optimalidad de KKT (4)
Condiciones suficientes de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad 

Como alternativa a la convexidad se puede usar el lagrangiano restringido

L(x ) = f (x ) + ∑ i ∈I λi*g i (x ) 

Si la matriz hessiana en el candidato x * ∇ 2 L ( x * ) = ∇ 2 f (x * ) +



∑

* 2 * λ ∇ g ( x ) i i i ∈I

es semidefinida positiva , entonces x * es un mínimo local de P Si la matriz hessiana anterior es definida positiva, entonces x * es un mínimo local estricto de P

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 22

Condiciones de optimalidad de KKT (5)
Condiciones necesarias de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad e igualdad min f (x )  Sea el problema P’ x

gi (x ) ≤ 0

i = 1,..., m

h j (x ) = 0

j = 1,..., l

x ∈X       

X ⊆
n es abierto y no vacío * Sea x un punto factible (verifica las restricciones) Sea I = {i / g i ( x * ) = 0 } Sean f , {g i , i ∈ I } diferenciables en x * * Sean {g i , i ∉ I } continuas en x * Sean {h j , j = 1, ..., l } continuamente diferenciables en x Sean {∇ g i (x * ), i ∈ I ; ∇ h j (x * ), j = 1, ..., l } l.i.

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 23

Condiciones de optimalidad de KKT (6)
Condiciones necesarias de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad e igualdad *  x es mínimo local de P’ ⇒ existen escalares {λi , i ∈ I ; µ j , j = 1, … , l } tales que l *

∇ f (x ) +

∑ λ ∇ g (x i

*

i

)+



j

* ( x )= 0 j

j =1

i ∈I

λi ≥ 0

∑ µ ∇h

∀i ∈ I

Si además {g i , i ∉ I } son diferenciables en x * m *

∇ f (x ) +

l

∑ λ ∇ g (x i

i

*

)+

i =1

λ i g i (x * ) = 0 λi ≥ 0

∑ µ ∇h j

j

(x * ) = 0

j =1

i = 1, ..., m

i = 1, ..., m

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 24

Condiciones de optimalidad de KKT (7)
Condiciones suficientes de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad e igualdad   

Sea x * un punto factible (verifica las restricciones) de P’ Sea I = {i / g i ( x * ) = 0 } * Sean f , {g i , i ∈ I } convexas y diferenciables en x

Si existen escalares {λi , i ∈ I ; µ j , j = 1, … , l } tales que l

∇f (x ) + ∑ λi ∇ g i (x ) + ∑ µ j ∇h j (x * ) = 0 *

*

i ∈I

λi ≥ 0

j =1

∀i ∈ I

de modo que h j sea convexa en x * si µ j > 0 ó h j sea cóncava en x * si µ j < 0 * entonces x es mínimo local de P’ ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 25

Condiciones de optimalidad de KKT (8)
Condiciones suficientes de Karush-Kuhn-Tucker para problemas con restricciones de desigualdad e igualdad Si además, las condiciones sobre las funciones f , {g i , i ∈ I }, h j se cumplen en todo el conjunto factible, entonces x * es el mínimo global de P’

ESCUELA TÉCNICA SUPERIOR DE INGENIERÍA DEPARTAMENTO DE ORGANIZACIÓN INDUSTRIAL

Optimización no lineal- 26