2.6: Optimización sin restricciones: métodos numéricos
- Page ID
- 111370
Los tipos de problemas que resolvimos en la sección anterior fueron ejemplos de problemas de optimización sin restricciones. Es decir, intentamos encontrar puntos locales (y quizás incluso globales) máximos y mínimos de funciones de valor real\(f (x, y)\), donde los puntos\((x, y)\) pudieran ser cualquier punto en el dominio de\(f\). El método que utilizamos nos requirió encontrar los puntos críticos de\(f\), lo que significaba tener que resolver la ecuación\(\nabla f = \textbf{0}\), que en general es un sistema de dos ecuaciones en dos incógnitas (\(x \text{ and }y\)). Si bien esto fue relativamente sencillo para los ejemplos que hicimos, en general este no será el caso. Si las ecuaciones involucran polinomios en\(x \text{ and }y\) grado tres o superior, o expresiones complicadas que involucran funciones trigonométricas, exponenciales o logarítmicas, entonces resolver incluso una de esas ecuaciones, y mucho menos dos, podría ser imposible por medios elementales.
Por ejemplo, si una de las ecuaciones que había que resolver era
\[\nonumber x^3 +9x−2 = 0 ,\]
es posible que tenga dificultades para obtener las soluciones exactas. Prueba y error no ayudaría mucho, sobre todo porque la única solución real resulta ser
\[\nonumber \sqrt[3]{\sqrt{28}+1-\sqrt[3]{\sqrt{28}-1}}.\]
En una situación como esta, la única opción puede ser encontrar una solución usando algún método numérico que dé una secuencia de números que converjan a la solución real. Por ejemplo, el método de Newton para resolver ecuaciones\(f (x) = 0\), que probablemente aprendiste en el cálculo de una sola variable. En esta sección describiremos otro método de Newton para encontrar puntos críticos de funciones de valor real de dos variables.
Dejar\(f (x, y)\) ser una función de valor real suave, y definir
\[\nonumber D(x, y) = \dfrac{∂^2 f}{ ∂x^2} (x, y) \dfrac{∂^2 f}{ ∂y^2} (x, y)− \left (\dfrac{∂^2 f}{∂y∂x} (x, y)\right )^2 \]
Algoritmo de Newton: Escoge un punto inicial\((x_0 , y_0)\). Para\(n\) = 0,1,2,3,..., defina:
\[ x_{n+1}=x_n - \dfrac{\begin{vmatrix} \dfrac{∂^2 f}{ ∂y^2} (x_n, y_n) & \dfrac{∂^2 f}{∂x∂y} (x_n, y_n) \\[4pt] \dfrac{∂f}{∂y} (x_n, y_n) & \dfrac{∂f}{∂x} (x_n, y_n)\\[4pt] \end{vmatrix}}{D(x_n, y_n)},\quad y_{n+1}=y_n - \dfrac{\begin{vmatrix} \dfrac{∂^2 f}{ ∂x^2} (x_n, y_n) & \dfrac{∂^2 f}{∂x∂y} (x_n, y_n) \\[4pt] \dfrac{∂f}{∂x} (x_n, y_n) & \dfrac{∂f}{∂y} (x_n, y_n)\\[4pt] \end{vmatrix}}{D(x_n, y_n)}\label{Eq2.14}\]
Entonces la secuencia de puntos\((x_n, y_n)_{n=1}^{\infty}\) converge a un punto crítico. Si hay varios puntos críticos, entonces tendrás que probar diferentes puntos iniciales para encontrarlos.
\(f (x, y) = x^ 3 − x y− x+ x y^3 − y^ 4\text{ for }−1 ≤ x ≤ 0 \text{ and }0 ≤ y ≤ 1\)
La derivación del algoritmo de Newton, y la prueba de que converge (dada una elección “razonable” para el punto inicial) requiere técnicas más allá del alcance de este texto. Ver RALSTON y RABINOWITZ para más detalles y para discusión de otros métodos numéricos. Nuestra descripción del algoritmo de Newton es el caso especial de dos variables de un algoritmo más general que se puede aplicar a funciones de\(n \ge 2\) variables.
En el caso de funciones que tienen un máximo o mínimo global, el algoritmo de Newton puede ser utilizado para encontrar esos puntos. En general, los máximos y mínimos globales tienden a ser más interesantes que las versiones locales, al menos en aplicaciones prácticas. Un problema de maximización siempre se puede convertir en un problema de minimización (¿por qué?) , por lo que se han desarrollado un gran número de métodos para encontrar el mínimo global de funciones de cualquier número de variables. Este campo de estudio se llama programación no lineal. Muchos de estos métodos se basan en la técnica de descenso más pronunciada, la cual se basa en una idea que discutimos en la Sección 2.4. Recordemos que el gradiente negativo\(- \nabla f\) da la dirección de la tasa más rápida de disminución de una función\(f\). El quid de la idea de descenso más empinada, entonces, es que a partir de algún punto inicial, se mueve cierta cantidad en la dirección de\(-\nabla f\) en ese punto. Dondequiera que eso te lleve se convierte en tu nuevo punto, y luego sigues repitiendo ese procedimiento hasta que finalmente (ojalá) llegues al punto donde f tiene su valor más pequeño. Existe un método de descenso “puro” más empinado, y una multitud de variaciones en él que mejoran la tasa de convergencia, facilidad de cálculo, etc. De hecho, el algoritmo de Newton puede interpretarse como un método de descenso más empinado modificado. Para mayor discusión de esto, y de la programación no lineal en general, ver BAZARAA, SHERALI y SHETTY.