La aproximación estocástica de perturbación simultánea (SPSA) es un método algorítmico para optimizar sistemas con múltiples parámetros desconocidos . Es un tipo de algoritmo de aproximación estocástica . Como método de optimización, es adecuado para modelos de población a gran escala, modelado adaptativo, optimización de simulación y modelado atmosférico . Se presentan muchos ejemplos en el sitio web de SPSA http://www.jhuapl.edu/SPSA . Un libro reciente y completo sobre el tema es Bhatnagar et al. (2013). Uno de los primeros artículos sobre el tema es Spall (1987) y el artículo fundamental que proporciona la teoría clave y la justificación es Spall (1992).
SPSA es un método de descenso capaz de encontrar mínimos globales, compartiendo esta propiedad con otros métodos como recocido simulado . Su característica principal es la aproximación de gradiente que requiere solo dos medidas de la función objetivo, independientemente de la dimensión del problema de optimización. Recordemos que queremos encontrar el control óptimo con función de pérdida :
Tanto la aproximación estocástica de diferencias finitas (FDSA) como la SPSA utilizan el mismo proceso iterativo:
dónde representa el iterar, es la estimación del gradiente de la función objetivo evaluado en , y es una secuencia numérica positiva que converge a 0. Si es un vector p -dimensional, elEl componente del estimador de gradiente simétrico en diferencias finitas es:
- FD:
1 ≤i ≤p , donde es el vector unitario con un 1 en el lugar, y es un pequeño número positivo que disminuye con n . Con este método, 2p evaluaciones de J para cadaSe necesitan. Claramente, cuando p es grande, este estimador pierde eficiencia.
Vamos ahora ser un vector de perturbación aleatorio. La componente del estimador de gradiente de perturbación estocástica es:
- SP:
Observe que FD perturba solo una dirección a la vez, mientras que el estimador SP perturba todas las direcciones al mismo tiempo (el numerador es idéntico en todos los componentes p ). El número de mediciones de función de pérdida necesarias en el método SPSA para cadaes siempre 2, independiente de la dimensión p . Por lo tanto, SPSA usa p veces menos evaluaciones de funciones que FDSA, lo que lo hace mucho más eficiente.
Experimentos simples con p = 2 mostraron que SPSA converge en el mismo número de iteraciones que FDSA. Este último sigue aproximadamente la dirección de descenso más empinada , comportándose como el método de gradiente. Por otro lado, SPSA, con la dirección de búsqueda aleatoria, no sigue exactamente la ruta del gradiente. Sin embargo, en promedio, lo rastrea casi porque la aproximación del gradiente es un estimador casi insesgado del gradiente, como se muestra en el siguiente lema.
Lema de convergencia
Denotamos por
el sesgo en el estimador . Asumir que son todos mutuamente independientes con segundos momentos limitados de media cero, y uniformemente delimitado. Luego→ 0 wp 1.
Bosquejo de la prueba
La idea principal es utilizar el condicionamiento en para expresar y luego usar una expansión de Taylor de segundo orden de y . Después de manipulaciones algebraicas usando la media cero y la independencia de, obtenemos
El resultado se deriva de la hipótesis de que→ 0.
A continuación, resumimos algunas de las hipótesis bajo las cuales converge en probabilidad al conjunto de mínimos globales de. La eficacia del método depende de la forma de, los valores de los parámetros y y la distribución de los términos de perturbación . Primero, los parámetros del algoritmo deben satisfacer las siguientes condiciones:
- > 0, → 0 cuando n → ∝ y . Una buena eleccion seria a> 0;
- , donde c> 0, ;
- deben ser variables aleatorias de media cero mutuamente independientes, distribuidas simétricamente alrededor de cero, con . El primer y segundo momentos inversos del debe ser finito.
Una buena eleccion para es la distribución de Rademacher , es decir, Bernoulli + -1 con probabilidad 0.5. También son posibles otras opciones, pero tenga en cuenta que las distribuciones uniforme y normal no se pueden usar porque no satisfacen las condiciones de momento inverso finito.
La función de pérdida J (u) debe ser tres veces diferenciable continuamente y los elementos individuales de la tercera derivada deben estar acotados:. También, como .
Además, debe ser Lipschitz continuo, acotado y la EDO debe tener una solución única para cada condición inicial. En estas condiciones y algunas otras, converge en probabilidad al conjunto de mínimos globales de J (u) (ver Maryak y Chin, 2008).
Extensión a métodos de segundo orden (Newton)
Se sabe que una versión estocástica del algoritmo estándar (determinista) de Newton-Raphson (un método de "segundo orden") proporciona una forma asintóticamente óptima o casi óptima de aproximación estocástica. SPSA también se puede utilizar para estimar eficientemente la matriz hessiana de la función de pérdida en base a mediciones de pérdida ruidosas o mediciones de gradientes ruidosas (gradientes estocásticos). Al igual que con el método SPSA básico, solo se necesita un pequeño número fijo de medidas de pérdida o medidas de gradiente en cada iteración, independientemente de la dimensión del problema p . Vea la breve discusión en Descenso del gradiente estocástico .
Referencias
- Bhatnagar, S., Prasad, HL y Prashanth, LA (2013), Algoritmos recursivos estocásticos para optimización: métodos de perturbación simultánea , Springer [1] .
- Hirokami, T., Maeda, Y., Tsukada, H. (2006) "Estimación de parámetros mediante aproximación estocástica de perturbación simultánea", Ingeniería eléctrica en Japón, 154 (2), 30-3 [2]
- Maryak, JL y Chin, DC (2008), "Optimización aleatoria global por aproximación estocástica de perturbación simultánea", Transacciones IEEE sobre control automático , vol. 53, págs. 780-783.
- Spall, JC (1987), "Una técnica de aproximación estocástica para generar estimaciones de parámetros de máxima verosimilitud", Actas de la Conferencia Estadounidense de Control , Minneapolis, MN, junio de 1987, págs. 1161-1167.
- Spall, JC (1992), “Aproximación estocástica multivariante usando una aproximación de gradiente de perturbación simultánea”, Transacciones IEEE sobre control automático , vol. 37 (3), págs. 332–341.
- Spall, JC (1998). "Descripción general del método de perturbación simultánea para una optimización eficiente" 2 . Recopilación técnica de Johns Hopkins APL , 19 (4), 482–492.
- Spall, JC (2003) Introducción a la búsqueda y optimización estocásticas: estimación, simulación y control , Wiley. ISBN 0-471-33052-3 (Capítulo 7)