Ecuaciones no Lineales y Optimización | 5ta Parte

in #steemstem5 years ago


Saludos queridos lectores, bienvenidos nuevamente a mi Blog. En la ciencia, como en la Ingeniería, las ecuaciones no lineales, es un tema de gran interés, ya que las mayoría de los fenómenos físicos o de la vida real, están modelados por ecuaciones no lineales; estos fenómenos naturales por lo general se dicen que están fuera de equilibrio es estos casos y las ecuaciones dependerán de la naturaleza del fenómeno, es decir, discretas o continuas, en cuyos casos se representan por mapeo o ecuaciones diferenciales respectivamente. En esta publicación continuaremos tratando el tema de las Ecuaciones no Lineales y Optimización, en su quinta entrega. A continuación continuaremos hablando de aspectos importantes, acerca de la minimización de funciones en una variable real, de la misma manera mostraremos los Script y funciones desarrolladas en GNU Octave para tal fin. Espero sigan disfrutando; esta publicación está dirigida a profesionales e investigadores con algunas destrezas en temas de análisis real, cálculo avanzado, entre otros. Al final, les dejare una corta bibliografía, donde podrán consultar algunos tópicos especiales para los interesados. Estoy abierto a sus comentarios y dudas que puedan surgir dentro del tema. Sin perder más tiempo, comencemos.


Título

Supongamos que tenemos f(t) una función unimodal en el intervalo [a, b] si existe un punto g en el intervalo [a, b] con la propiedad que f es estrictamente monótona decreciendo en el intervalo [a, g] y estrictamente monótona creciente en el intervalo [g, b]. Esto es una derivada libre o una forma de decir que f tiene un mínimo global único en g. Así, la función que construimos en la publicación anterior (Ecuaciones no Lineales y Optimización | 4ta Parte) SeparacionMercurioTierra es unimodal en [900, 950].

El método de búsqueda de la sección dorada se puede utilizar para encontrar g. En este método se a g en un intervalo [a, b] de paso a paso además de un par de puntos interiores c y d que satisfacen lo siguiente:



Aquí, 0 < r < 1/2 es un número real que se determina de una manera especial. Si f(c) < f(d), entonces de la unimodalidad se deduce que f es creciente en [d, b] y así g esta en [a, d]. Por otro lado, si f(c) > f(d), entonces un argumento similar nos dice que g esta en el intervalo [c, b]. Así podemos escribir el siguiente script para reducir el espacio de búsqueda:


Script de optimización del espacio de búsquedad. Elaborado con GNU Octave, por @abdulmath.

Después de este paso, la longitud del intervalo de búsqueda se reduce en un factor de (1 - r). Observe que se requieren dos evaluaciones de función en cada paso, y aquí es donde entra en juego la cuidadosa elección de el valor de r. Si podemos elegir r de tal manera que

  1. en el caso fc<=fd el nuevo valor de d sea igual al antiguo valor de c y
  2. en el caso fc > fd el nuevo valor de c sea igual al antiguo valor de d, entonces el paso de actualización se puede escribir en el siguiente script:


    Script elaborado en GNU Octave por @abdulmath.

En este nuevo ajuste sólo se requiere una nueva evaluación de la función. El valor de r buscado debe cumplir dos condiciones:



La manipulación de cualquiera de estas ecuaciones obtenemos que


De la definición de d, tenemos d - a = (1 - r)(b - a) y así r debe satisfacer


Esto conduce a la ecuación cuadrática


La raíz que queremos es


y con esta opción el factor de reducción de la longitud del intervalo es


el cual es conocido como el radio dorado. Si unimos todas estas ideas, creamos la siguiente función


Función de Búsqueda Dorada. Elaborada en GNU Octave por @abdulmath.

Un trazo de (a, c, d, b) donde el mínimo es encontrado cuando se aplica a la función SeparacionMercurioTierra. La figura que mostraremos a continuación muestra la ubicación de a, b, c, y d al principio de los primeros cinco pasos. Observe que sólo se requiere una nueva evaluación de la función por paso.


Gráfico del trazo (a, c, d, b). Elaborada en GNU Octave, por @abdulmath.

A continuación les dejo el script donde mostramos como ilustrar lo que hemos venido discutiendo hasta el momento:


Script construido para ilustrar el método de la búsqueda de la sección dorada. Elaborado en GNU Octave, por @abdulmath.

Una observación importante que hacer sobre los criterios de terminación en Dorado es que se utiliza la raíz cuadrada del redondeo de la unidad. La razón de ello es la siguiente: Si f' y f" existen, entonces



ya que f'(x+) = 0. Si exite un error O(eps) en la evaluación de f, entonces no habrá diferencia significativa entre el valor calculado de f en x+ y el valor calculado de f en x+ + delta2 < eps. Por lo tanto, no tiene sentido iterar más si el espaciado relativo de los números flotantes es menor que la raíz cuadrada de eps.

Si usamos la función Dorado para minimizar la función de separación Mercurio-Tierra con el intervalo inicial [900, 950], entonces se requieren 29 iteraciones, haciendo que la solución x+ = 927.1243.

La función Dorado siempre converje, pero si la función f no es unimodal a lo largo del intervalo inicial, entonces el punto límite no necesita tener ninguna relación con la búsqueda de un minimizador local. La unimodalidad es para la función Dorado como el requisito de que f(a)f(b) < 0 en el método de Bisección: Sin esta condición no podemos garantizar que de la iteración obtengamos algo interesante.



Título

El método de búsqueda de la sección dorada converge linealmente, como el método de bisección. Para obtener un método convergente más rápido, podríamos usar el framework de Newton para encontrar ceros de la derivada f', asumiendo que esta función y f" existen. Sin embargo, este enfoque requiere la codificación tanto de la primera como de la segunda función derivada, y esto puede ser una tarea final que consume mucho tiempo.

El minimizador de Octave fminbnd sortea este problema pero todavía muestra una convergencia de tipo cuadrático. Utiliza una combinación de búsqueda de sección dorada y un método de ajuste parabólico que se basa únicamente en evaluaciones. Para usarlo, escribimos



aplica el método a la función SeparacionMercurioTierra en el intervalo [900, 950] y devuelve el valor del minimizador tm = 927.1243.



Título

Para concluir con las consideraciones que hemos realizado acerca del minimizador de funciones, tomaremos en cuenta algunas observaciones que tocan la simetría, la dimensión y la elección de una función objetivo.

Vincularemos la discusión a un bonito problema geométrico:



Un tetraedro es un poliedro con cuatro caras triangulares, la afirmación del problema es ambigua porque asume que tenemos alguna forma de medir el tamaño de un tetraedro. Trabajemos con el área de la superficie y veamos que obtenemos en su desarrollo. Si


entonces nuestro objetivo es maximizar

Dado que los cuatro vértices tienen cada uno una posición con latitud



y una longitud


parece que se trata de un problema con ocho incógnitas ya que


Además, con esta formulación hay un número infinito de soluciones porque cualquier tetraedro, incluyendo el óptimo que buscamos, puede deslizarse dentro de la esfera. Para hacer la situación menos fluida sin perder la generalidad, fijaremos P0 en el polo norte y confinamos P1 al meridiano cero. Con esta maniobra, el número de incógnitas se reduce a cinco, a saber:


Un argumento de simetría reduce aún más el número de parámetros libres si pensamos en P0 como el ápice y en el triángulo definido por los otros tres vértices como la base. Está claro que para el tetraedro óptimo, los vértices base P1, P2 y P3 tendrán la misma latitud y definirán un triángulo equilátero. (Esto puede ser un poco exagerado si no se está lo suficientemente familiarizado con la geometría sólida, pero puede ser verificado formalmente). Con estas observaciones, el número de incógnitas se reduce a una:

Sea T el tetraedro con estos vértices. La función que debemos optimizar es una función de una sola variable:



la cual podemos observar en el gráfico siguiente. En el mismo podemos observar que la misma tiene un máximo en algún punto del intervalo [-0.5, 0].


Gráfica de la función que deseamos maximizar. Elaborado con GNU Octave por @abdulmath.

Observemos que maximizar equivale a minimizar la siguiente función



que puede ser pasado con fminbnd para su minimización.

Ahora cambiemos el problema para que en lugar de maximizar la superficie, maximicemos el volumen, prevalezcan los mismos argumentos de simetría y se pueda demostrar que



es el volumen de T. La variable a optimizar puede obtenerse aplicando fminbnd a la función siguiente


Por último, también podríamos maximizar la longitud total de las aristas:


minimizando


de esta manera aplicando fminbnd a estas tres funciones objetivos, obtenemos los siguientes resultados resumidos en el siguiente cuadro:

Función ObjectivoTiempoTheta
Área1.000-0.3398369144798928
Volumen1.111-0.3398369181995862
Arista1.213-0.3398369274385691

Resulta que el mismo tetraedro resuelve cada problema, y este tetraedro es regular. Esto significa que las caras son idénticas en área y los bordes son iguales en longitud. Notemos que la precisión sólo es buena para la raíz cuadrada de la precisión de la máquina, confirmando las observaciones que ya habíamos mencionado anteriormente.

Debido a que el tetraedro óptimo es regular, podemos calcular dicha variable de una manera diferente. La función



es la diferencia entre la longitud de la arista P0P1 y la longitud de la arista P1P2. Esta función es cero en un valor t+ si T(t+) es el tetraedro de solución normal. Aplicando fzero a la función definida anteriormente, obtenemos t+ con una precisión total de la maquina total: -0.3398369094541218.

La solución exacta viene dada por


Para obtener este resultado, observamos que la función TV es cúbica de la forma:



En la ecuación anterior si p'(s) = 0, entonces podemos concluimos que para s = -1/3 existe un mínimo y por lo tanto obtenemos


La equivalencia matemática de estas formulaciones no necesariamente conduce a implementaciones que sean igualmente eficientes y precisas.



Queridos amigos y lectores, espero hayan disfrutado de esta segunda entrega de este tan apasionante e interesante tema del cálculo numérico, Ecuaciones no Lineales y Optimización | 5ta Parte apoyado con el entorno GNU Octave, en esta oportunidad pudimos estudiar algunas detalles o aspectos importantes, acerca de la minimización de funciones en una variable real. Espero que el mismo sea de apoyo a ustedes en sus trabajos, o quizás sirva de apoyo para sus hijos, nietos, sobrinos o amigos que quieran aprender un poco más del maravilloso mundo de las matemáticas y la programación. No olviden dejar sus comentarios. Saludos y nos leemos pronto.


Si desean consultar un poco más del tema pueden usar las siguientes referencias:

  • Demidovich, B. P., and I. A. Maron. Computational Mathematics Mir, Moscow, 1976.
  • Björck, Åke. Numerical methods in matrix computations. Vol. 59. Cham: Springer, 2015.
  • Burden, Richard L., and J. Douglas Faires. Numerical analysis. Ninth Edition. Cengage Learning. 2011.

Las imágenes, separadores y las ecuaciones fueron creadas y editadas por @abdulmath usando software libre, GNU Octave, , GIMP e Inkscape.



@SteemSTEM es un proyecto comunitario con el objetivo de promover y apoyar la Ciencia, la Tecnología, la Ingeniería y las Matemáticas en la blockchain Steem. @Stem-espanol es parte de esta comunidad, si desea apoyar el proyecto, puedes contribuir con contenido en español en las áreas de Ciencia, Tecnología, Ingeniería y Matemáticas, utilizando las etiquetas #steemstem y #stem-espanol.



Sort:  

Agradecido por el apoyo. Saludos cordiales!





This post has been voted on by the SteemSTEM curation team and voting trail in collaboration with @curie.

If you appreciate the work we are doing then consider voting both projects for witness by selecting stem.witness and curie!

For additional information please join us on the SteemSTEM discord and to get to know the rest of the community!

Coin Marketplace

STEEM 0.36
TRX 0.12
JST 0.039
BTC 69735.97
ETH 3533.64
USDT 1.00
SBD 4.72