Tema 3 - Programación no lineal: Sin restricciones

Introducción y repaso

ℹ️

Estos problemas son problemas clásicos de optimización de funciones de grado 2 o superior.

💡

Cuando la función de optimización tiene una sola variable, se dice que es unidimensional

Si el problema tiene dos variables, intentaremos poner una en función de la otra

🔀

Podemos convertir un problema de máximización a minimización y viceversa aplicando la siguiente expresión

min(f) = -max(-f)

🔖

Notación y expresiones

Punto estacionario → Punto de pendiente $0$ (el valor de la primero derivada en ese punto es cero)

$f^*$ → Vector de los puntos estacionarios de la función $f$

Maximizador/minimizador → Valor de $x$ para el cual la primera derivada es cero

Min / Max local o global → Valor de $f(x)$ para el cual la primera derivada es cero

Local → Es un punto de pendiente cero, pero no es el más alto/bajo de los puntos estacionarios de la función
Global → Es un punto de pendiente cero, y es el más alto/bajo de los puntos estacionarios de la función

🧮

Conceptos de matemáticas

$f'(x)$ → Valor de la pendiente de la función en el punto $x$

$f''(x)$ → Valor de la curvatura de la función en el punto $x$ , se usa también para saber si un punto estacionario es un máximo o mínimo

Métodos de optimización no lineal

🧮

Ejemplos de simplificación a una variable

📝

Ejemplo 12 - Cercado de un recinto

Método analítico

ℹ️

Este método es el método básico que consiste en analizar la pendiente de la función con la derivada

1️⃣

Hacer la derivada de la función

f'(x)

2️⃣

Igualar la derivada a

0

para hallar los puntos candidatos a máximos o mínimos

f'(x) = 0\\ x_1 = m, x_2 = n, x_3= t

3️⃣

Analizar si el punto candidato es un máximo o un mínimo

Opción 1: Observar la pendiente de los puntos a la izq y dch del punto candidato para determinar si el un máximo o mínimo. Si la pendiente del punto a la izq y el de a la dch es + y - respectivamente, es un maximo, si es al reves, es un mínimo. Si la pendiente es del mismo signo, no es ni un máximo ni un mínimo

f'(m-0.00001) = +k_1,\ f'(m+0.00001) = -k_2

Hacer lo mismo para los puntos $n$ y $t$

💡

Si el resto de puntos candidatos están separados, podemos cojer un número próximo al candidato sin necesidad de ser tan preciso

Opción 2: Calcular la 2º derivada y sustituir el punto candidato en esta. Si el resultado es + será un mínimo, si el resultado es - será un máximo

f''(m) = -k_1

Hacer lo mismo para los puntos $n$ y $t$

4️⃣

De los puntos candidatos, que sean máximo o mínimos, dependiendo de lo que estemos buscando, los sustituiremos en la función original para hallar el que maxímiza o minimiza el resultado de esta

max\{f(m), f(t)\}

Suponiendo que como $n$ será un mínimo no hace falta cancularlo

💡

Si esta derivada da

0

, repetir con la

f'''

Método de Newton

💡

El método de Newton es útil para cuando el método analítico es imposible o muy dificil

ℹ️

El método de Newton es un método iterativo que intenta dibujar una parábola que se aproxima mucha a la función para un púnto concreto.

💡

El método de newton se hace para una función la cual es posible calcular su segunda derivada

💡

Pasos para resolver un ONL por el método de Newton

2️⃣

Datos

$\epsilon$ → Margen de error

$x_0$ → Valor de $x$ inicial

1️⃣

Seleccionamos un punto inicial $x_0$ y una tolerancia $\epsilon >0$

2️⃣

Iteramos mientras que $|f'(x_k)|>\epsilon$

Columnas de tabla de iteraciones
$k$ → Número de Iteración
$x_k$ → Valor de $x$ resultante de la operación de la siguiente función, siendo $x_k$ el valor de la fila de arriba para esa columna. Siendo $x_{k+1}$ el valor de la fila actual
$x_{k+1} = x_k - \frac{f'(x_k)}{f''(x_k)}$
$f'(x_k)$ → Valor de $x$ en la primera derivada
$f''(x_k)$ → Valor de $x$ en la segunda derivada

$k$	$x_k$	$f'(x_k)$	$f''(x_k)$
0	Dato de valor inicial	Sustituimos $x_k$ de esta fila en la primera derivada	Sustituimos $x_k$ de esta fila en la segunda derivada
1	Aplicamos la fórmula de $x_{k+1}$ con el valor de arriba	Sustituimos $x_k$ de esta fila en la primera derivada	Sustituimos $x_k$ de esta fila en la segunda derivada
2	Aplicamos la fórmula de $x_{k+1}$ con el valor de arriba	Sustituimos $x_k$ de esta fila en la primera derivada. Comprobamos si debemos seguir iterando	Sustituimos $x_k$ de esta fila en la segunda derivada
…	…	…	…

3️⃣

Conclusiones

Cuando paremos de iterar, tendremos que hayar los maximizadores o minimizadores, y los máximos y mínimos.

💡

Realmente solo hace falta calculas los mínimos en los problemas de minimización, e igual para los máximos

Para saber si es maximizador o minimizador y si $x^*$ será máximo o mínimo
Si $f''(x^*) < 0$ entonces $x^*$ es un maximizador
Si $f''(x^*) > 0$ entonces $x^*$ es un minimizador

Hallar el min/maximizador
El último valor de la tabla de la columna $x_k$
$x^* \rightarrow x_k$

Hallar el mínimo/máximo
Sustituimos $x^*$ en la función original
$f(x^*) = m$

💡

Este método nos sirve también para problemas de maximización

Vector gradiente y Matriz hessiana

💡

Los conceptos de esta sección sirven para analizar la funciones multidimensionales, osea que tienen varias variables:

f(x_1,\ x_2)

🔖

Conceptos

Gradiente → El equivalente a la pendiente para las funciones de más de una variable

$\overline x$ → Vector de valores para sustituir en la función multidimensional

Punto de silla → Punto en el cual una variable es un máximizador y la otra es minimizador

ℹ️

Para calcular el gradiente de un punto, podemos aplicar la siguiente fórmula

\nabla f(x) = \bigg(\frac{\partial f}{\partial x_1},\ \frac{\partial f}{\partial x_2}\bigg)^\top

Explicación del vector $\nabla f$
El primer elemento $(\nabla f_1)$ es la derivada de $f$ respecto de $x_1$
El segundo elemento $(\nabla f_2)$ es la derivada de $f$ respecto de $x_2$

🔚

El valor del gradiente se halla sustituyendo los valores de $\overline x$ en la función $f$ : $f(\overline x)$

ℹ️

Matriz hessiana

La matriz hessiana es el siguiente paso después de calcular

\nabla f

. Es el equivalente a calcular la segunda derivada.

H(x) = \begin{pmatrix} \frac{\partial^2 f}{\partial^2 x_1} && \frac{\partial^2 f}{\partial x_1 \partial x_2} \\ \frac{\partial^2 f}{\partial x_1 \partial x_2} && \frac{\partial^2 f}{\partial^2 x_2} \end{pmatrix}

Explicación de la matriz
Derivada, de $\nabla f_1$ respecto de la variable $x_1$
Derivada, de $\nabla f_2$ respecto de la variable $x_1$
Derivada, de $\nabla f_1$ respecto de la variable $x_2$
Derivada, de $\nabla f_2$ respecto de la variable $x_2$

💡

La matriz hessiana es una matriz simétrica

🔚

El valor de la matriz hessiana se halla sustituyendo los valores de $\overline x$ en la función $h$ : $h(\overline x)$

🗃️

Definitud de la matriz hessiana

ℹ️

Cuando decimos todos los determinantes de $H$ , nos referimos a los determinantes de de las submatrices de

H

hasta

H

en orden creciente desde

H_{11}

siendo este el primer determinante

Ejemplo

Dada una matriz de orden $n$ siendo en este ejemplo $n=3$ , tendremos que calcular determinantes
$H_{1}$ = $det(1) = 1$
$H_2 = det(H_{22}) = 1·5-2·4 = -3$
$H_3 = det(H) = 0$

Para cuando la matriz es diagonal (analizamos la diagonal principal)

Para que $H$ sea definida positiva
Todos los elementos de la diagonal principal son mayores que cero

Para que $H$ sea semidefinida positiva
Todos los elementos de la diagonal principal son mayores o iguales que cero

Para que $H$ sea definida negativa
Todos los elementos de la diagonal principal son menores que cero

Para que $H$ sea semidefinida negativa
Todos los elementos de la diagonal principal son menores o iguales que cero

Para que $H$ sea indefinida
Resto de casos:
El signo empieza en positivo y hay algún elemento negativo

Para cuando la matriz es simétrica y no diagonal (analizamos los determinantes)

Para que $H$ sea definida positiva
Todos los determinantes son mayores que cero

Para que $H$ sea semidefinida positiva
El signo de todos los determinantes de $H$ es positivo, pero al menos uno es cero (que no sea el primero)

Para que $H$ sea definida negativa
El signo del primer determinante es negativo y el resto alternados en signo

Para que $H$ sea semidefinida negativa
El signo del primer determinante es negativo y el resto alternados en signo o cero

Para que $H$ sea indefinida
Si el primer determinante es cero

📝

Ejemplo 16 - Matriz Hessiana

Hallar los puntos óptimos (minimizadores y máximizadores)

🥇

Condiciones de optimalidad de primer orden

🔚 Hallar los puntos estacionarios: $\nabla f(x)=0$

Dado un vector gradiente

\nabla f(\overline x) = (f'(x_1),\ f'(x_2))

entonces para hallar los puntos estacionarios resolveremos el sistema:

\begin{cases} f'(x_1) = 0 \\ f'(x_2) = 0 \end{cases}

Los puntos estacionarios serán la combinación de soluciones para

x_1

con

x_2

Ejemplo

Dado un gradiente cuyos elementos son
$\begin{cases} 4x_1^2(x_1-3) = 0 \\ 6(x_2-5) = 0 \end{cases}$
Las soluciones de $x_1$ son: $x_1=0$ y $x_1=3$
Las soluciones de $x_2$ son: $x_2 = 5$

Por lo que los puntos estacionarios son
$\overline x = (0, 5)$
$\overline x = (3,5)$

🥈

Condiciones de optimalidad de segundo orden

🔚 Verificar si los puntos hallados anteriormente son estacionarios

Sustituiremos en

H

los puntos estacionarios hallados

(\overline x)

$H(\overline x) > 0$ → Es un mínimo local

$H(\overline x) < 0$ → Es un máximo local

$H(\overline x)$ indefinida → Es un punto de silla

📖

Se dice que si el punto

x^*

pertenenciente a una matriz hessiana…

Si dicha matriz es semidefinida, entonces se entiende que cumple la Condición Necesaria de Optimalidad de segundo Orden (CNO2)

Si dicha matriz es definida, entonces se entiende que cumple la Condición Suficiente de Optimalidad de segundo Orden (CSO2)

Si dicha matriz es infefinida, entonces la función representa un Punto de silla

Métodos de optimización multidimensional

Método del gradiente

📖

Método del gradiente

💡

Mejoraremos el punto

x^k

siendo que

La dirección de máximo descenso (problemas de minimización)

$d^k = -\nabla f(x^k)$

La dirección de mínimo descenso (problemas de maximización)

$d^k = +\nabla f(x^k)$

Pasos del método del gradiente

0️⃣

Seleccionamos los valores iniciales

Seleccionamos la solución inicial, osea el valor de $x^{(k=0)} = sol$ . Observamos que se utiliza el exponenete $0$ para denotar la solución inicial, este exponente se corresponde con el valor inicial de el índice de solución $k$ , y siendo $sol$ dicho valor inicial.

Seleccionamos el índice de solución $k$ , osea el valor que iremos incrementando en cada iteración

Seleccionamos la toreancia, osea el valor umbral $\epsilon > m$ , siendo $m$ dicho umbal

1️⃣

Calculamos el gradiente

Calculamos el vector gradiente de la función $\nabla f(x^{(k)})$ , para la solución actual. La solución actual es $f(x^{(k)})$ siendo $k$ el valor del índice de solución de la iteración actual

2️⃣

Comprobamos proximidad a un punto estacionario

Si el valor absoluto de

\nabla f(x^{(k)})

es menor que el umbral deninfido para la tolerancia, entonces el punto

x^{(k)}

está suficientemente cerca de un punto estacionario. Esto se calcula con el producto escalar (raiz de la suma de cuadrados, osea, como hacer pitágoras)

3️⃣

Elegimos la dirección del gradiente (valor de $x$ para el siguiente índice de solución)

Si la función objetivos es de maximización
$d^k = \nabla f(x^{(k)})$

Si la función objetivos es de minimización
$d^k = -\nabla f(x^{(k)})$

4️⃣

Expresión para calcular el siguiente punto

El siguiente punto se debe calcular con respecto al punto actual más el valor de la dirección

(d^0)

multiplicado por una incognita

⁍

5️⃣

Calcular el nuevo punto

Ahora sustituiremos el nuevo punto en la función inicial

f(x)

el punto

x^{k+1}

. Esta operación no dará como resultado una función unidimensional la cual ahora podremos calcular

f(x^{k+1}) = 0

Despejaremos

\lambda

de la expresión anterior y nos dará su valor. Ahora, calcularemos el nuevo punto sustituyendo el valor de lamda en la expresión hallada en el paso anterior(paso 4️⃣) →

x^{k+1}(\lambda)

El resultado será el nuevo punto

6️⃣

Incrementar el índice de solución

Ahora, incrementaremos el valor del índice de solución, $k$ , ahora

k=k+1

Volvemos al paso uno tras incrementar

k

Método de Newton (multidimensional)

🚧

Sin hacer

Derivada, de $\nabla f_1$ respecto de la variable $x_1$	Derivada, de $\nabla f_2$ respecto de la variable $x_1$
Derivada, de $\nabla f_1$ respecto de la variable $x_2$	Derivada, de $\nabla f_2$ respecto de la variable $x_2$