Introducción

Mathematica tiene una colección de comandos que hacen optimización sin restricciones (FindMinimumandFindMaximum).
Estas funciones trabajan, en general, haciendo búsquedas; empiezan en un punto y toman pasos que reducen (aumentan) la función objetivo.
Los procesos de búsqueda son análogos a un montañista tratando de encontrar un valle (cima) a ciegas, siempre y cuando siga la pendiente de mayor valor se llegará a un máximo (mínimo) eventualmente.

Por ejemplo,x sin(x+1) no tiene mínimo global pero si una cantidad infinita de mínimos locales

Plot[x Sin[x + 1], {x, -50, 50}] ;

[Graphics:../HTMLFiles/optimizacion_24.gif]

Esta función muestra los pasos tomados por FindMinimum para la función x Sin[x + 1] empezando con x = 0.

g = FindMinimumPlot[x Sin[x + 1], {x, 0}]

[Graphics:../HTMLFiles/optimizacion_26.gif]

{{-0.240125, {x -0.520269}}, {Steps5, Function6, Gradient6}, ⁃Graphics⁃}

El comando FindMinimumPlot corre FindMinimum, mantiene cuenta de las evaluaciones de la función, su gradiente y los pasos que toma la búsqueda (utiliza  las opciones EvaluationMonitor y StepMonitor) y los uestra sobrepuestos sobre la gráfica de la función.
Los pasos se indican con líneas azules, evaluaciones de la función en verde, evaluzaciones del gradiente en rojo y el mínimo en negro.

Ahora se ve lo que hace FindMinimum para x Sin[x + 1]comenzando en x = 2.

FindMinimumPlot[x Sin[x + 1], {x, 2}, DisplayFunctionIdentity] ; Plot[x Sin[x + 1], {x ... }, DisplayFunctionIdentity] ; Show[%%[[3]], %, DisplayFunction$DisplayFunction] ;

[Graphics:../HTMLFiles/optimizacion_29.gif]

De este par de gráficas uno puede concluir que al empezar en un punto donde la función tiene una pendiente negativa, siempre se llegará al mínimo más cercano que esté en esa dirección. Pero este no es siempre el caso: los pasos que toma FindMinimum son determinados, típicamente, utilizando el valor de la función y sus derivadas, de forma que si la derivada es pequeña, FindMinimum dará pasos grandes para encontrar un mínimo

FindMinimumPlot[x Sin[x + 1], {x, 7}]

[Graphics:../HTMLFiles/optimizacion_31.gif]

{{-41.4236, {x41.4356}}, {Steps3, Function14, Gradient14}, ⁃Graphics⁃}

En dos dimensiones, los problemas son más complicados porque es necesario determinar tanto el tamaño del paso como la dirección de este

Aca se muestran los pasos tomados por FindMinimum para  encontrar un mínimo local de cos(x^2 - 3y) + sin(x^2 + y^2) empezando en   {x, y} = {1, 1}

FindMinimumPlot[Cos[x^2 - 3 y] + Sin[x^2 + y^2], {{x, 1}, {y, 1}}]

[Graphics:../HTMLFiles/optimizacion_35.gif]

{{-2., {x1.37638, y1.67868}}, {Steps9, Function13, Gradient13}, ⁃ContourGraphics⁃}

El comando FindMinimumPlot tiene las mismas convenciones que su contraparte unidimensional, pero muestra un gráfico de contorno.
En este ejemplo es claro que se necesito hacer un cambio de dirección varias veces para llegar al mínimo.
El primer paso se dio en la dirección del decenso más fuerte (perpendicular al contorno o paralelo al gradiente) , en los siguientes pasos este no es el caso, la búsqueda utiliza información de pasos previos para obtener información de la curvatura de la función, que generalmente da informacion sobre una mejor dirección.
Otra estrategia que converge más rapido, pero es más costosa, utiliza la segunda derivada (método de Newton).

FindMinimumPlot[Cos[x^2 - 3 y] + Sin[x^2 + y^2], {{x, 1}, {y, 1}}, MethodNewton]

[Graphics:../HTMLFiles/optimizacion_38.gif]

{{-2., {x1.37638, y1.67868}}, {Steps5, Function6, Gradient6, Hessian6}, ⁃ContourGraphics⁃}

Es claro que el método de Newton converge con menos pasos pero el hecho de tener que calcular la Hessiana y evaluarla en cada paso hace que, en general, sea más lento.

En la mayoría de los casos  los métodos de minimización local para una función f están basados en un modelo cuadrático

q_k(p) = f(x_k) + ∇f(x_k)^T p + 1/2 p^TB_k p . (1)

El subidice k se refiere al k-esimo paso iterativo.
En el modelo de Newton se utiliza la Hessiana exacta B_k = ∇^2f (x_k), pero otros métodos utilizan aproximaciones menos costosas.
Tipicamente se calcula un paso de prueba s_k como minimizador del modelo que satisface el sistema de ecuaciones lineales

B_ks_k   = - ∇f(x_k)

Si f es tiene una curvatura rasonable y x_k está cerca de un mínimo local, entonces con B_k = ∇^2f (x_k), la secuencia de pasos x_ (k + 1) = s_k + x_k converge al mínimo.
En una búsqueda típica el valor inicial no está suficientemente cerca del mínimo, ademas B_k es solo una aproximación de la Hessiana y en los primeros pasos la aproximación tiende a ser poco exacta.
Por lo tanto es obligatorio proveer algún tipo de control extra a la secuencia de pasos para mejorar la rata de convergencia.

Created by Mathematica  (August 9, 2004)