Aproximación estocástica de perturbación simultánea

Algoritmo de optimización

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 completo sobre el tema es Bhatnagar et al. (2013). Un artículo temprano sobre el tema es Spall (1987) y el artículo fundacional 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 el annealing simulado . Su característica principal es la aproximación por gradiente que requiere solo dos mediciones 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 : ${\displaystyle u^{*}}$ ${\displaystyle J(u)}$

${\displaystyle u^{*}=\arg \min _{u\in U}J(u).}$

Tanto la aproximación estocástica de diferencias finitas (FDSA) como la SPSA utilizan el mismo proceso iterativo:

${\displaystyle u_{n+1}=u_{n}-a_{n}{\hat {g}}_{n}(u_{n}),}$

donde representa la iteración, es la estimación del gradiente de la función objetivo evaluada en , y es una secuencia de números positivos que converge a 0. Si es un vector p -dimensional, el componente del estimador de gradiente de diferencias finitas simétricas es: ${\displaystyle u_{n}=((u_{n})_{1},(u_{n})_{2},\ldots ,(u_{n})_{p})^{T}}$ ${\displaystyle n^{th}}$ ${\displaystyle {\hat {g}}_{n}(u_{n})}$ ${\displaystyle g(u)={\frac {\partial }{\partial u}}J(u)}$ ${\displaystyle {u_{n}}}$ ${\displaystyle \{a_{n}\}}$ ${\displaystyle u_{n}}$ ${\displaystyle i^{th}}$

Día de la Madre: ${\displaystyle ({\hat {g_{n}}}(u_{n}))_{i}={\frac {J(u_{n}+c_{n}e_{i})-J(u_{n}-c_{n}e_{i})}{2c_{n}}},}$

1 ≤i ≤p , donde es el vector unitario con un 1 en su lugar, y es un número positivo pequeño que disminuye con n . Con este método, se necesitan 2p evaluaciones de J para cada uno . Cuando p es grande, este estimador pierde eficiencia. ${\displaystyle e_{i}}$ ${\displaystyle i^{th}}$ ${\displaystyle c_{n}}$ ${\displaystyle g_{n}}$

Sea ahora un vector de perturbación aleatorio. El componente del estimador de gradiente de perturbación estocástica es: ${\displaystyle \Delta _{n}}$ ${\displaystyle i^{th}}$

ES: ${\displaystyle ({\hat {g_{n}}}(u_{n}))_{i}={\frac {J(u_{n}+c_{n}\Delta _{n})-J(u_{n}-c_{n}\Delta _{n})}{2c_{n}(\Delta _{n})_{i}}}.}$

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 ). La cantidad de mediciones de la función de pérdida necesarias en el método SPSA para cada uno es siempre 2, independientemente de la dimensión p . Por lo tanto, SPSA utiliza p veces menos evaluaciones de funciones que FDSA, lo que lo hace mucho más eficiente. ${\displaystyle g_{n}}$

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 pronunciada , comportándose como el método del gradiente. Por otro lado, SPSA, con la dirección de búsqueda aleatoria, no sigue exactamente la trayectoria del gradiente. Sin embargo, en promedio, lo sigue casi porque la aproximación del gradiente es un estimador casi imparcial del gradiente, como se muestra en el siguiente lema.

Lema de convergencia

Denotar por

${\displaystyle b_{n}=E[{\hat {g}}_{n}|u_{n}]-\nabla J(u_{n})}$

el sesgo en el estimador . Supongamos que son todos mutuamente independientes con media cero, segundos momentos acotados y uniformemente acotados. Entonces →0 wp 1. ${\displaystyle {\hat {g}}_{n}}$ ${\displaystyle \{(\Delta _{n})_{i}\}}$ ${\displaystyle E(|(\Delta _{n})_{i}|^{-1})}$ ${\displaystyle b_{n}}$

Bosquejo de la prueba

La idea principal es utilizar el condicionamiento para expresar y luego utilizar una expansión de Taylor de segundo orden de y . Después de las manipulaciones algebraicas utilizando la media cero y la independencia de , obtenemos ${\displaystyle \Delta _{n}}$ ${\displaystyle E[({\hat {g}}_{n})_{i}]}$ ${\displaystyle J(u_{n}+c_{n}\Delta _{n})_{i}}$ ${\displaystyle J(u_{n}-c_{n}\Delta _{n})_{i}}$ ${\displaystyle \{(\Delta _{n})_{i}\}}$

${\displaystyle E[({\hat {g}}_{n})_{i}]=(g_{n})_{i}+O(c_{n}^{2})}$

El resultado se desprende de la hipótesis de que →0. ${\displaystyle c_{n}}$

A continuación retomamos algunas de las hipótesis bajo las cuales converge en probabilidad al conjunto de mínimos globales de . La eficiencia del método depende de la forma de , de los valores de los parámetros y de la distribución de los términos de perturbación . En primer lugar, los parámetros del algoritmo deben satisfacer las siguientes condiciones: ${\displaystyle u_{t}}$ ${\displaystyle J(u)}$ ${\displaystyle J(u)}$ ${\displaystyle a_{n}}$ ${\displaystyle c_{n}}$ ${\displaystyle \Delta _{ni}}$

• ${\displaystyle a_{n}}$>0, →0 cuando n→∝ y . Una buena elección sería a>0; ${\displaystyle a_{n}}$ ${\displaystyle \sum _{n=1}^{\infty }a_{n}=\infty }$ ${\displaystyle a_{n}={\frac {a}{n}};}$
• ${\displaystyle c_{n}={\frac {c}{n^{\gamma }}}}$, donde c>0, ; ${\displaystyle \gamma \in \left[{\frac {1}{6}},{\frac {1}{2}}\right]}$
• ${\displaystyle \sum _{n=1}^{\infty }({\frac {a_{n}}{c_{n}}})^{2}<\infty }$
• ${\displaystyle \Delta _{ni}}$deben ser variables aleatorias de media cero mutuamente independientes, distribuidas simétricamente alrededor de cero, con . Los momentos primero y segundo inversos de deben ser finitos. ${\displaystyle \Delta _{ni}<a_{1}<\infty }$ ${\displaystyle \Delta _{ni}}$

Una buena opción 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 no se pueden utilizar las distribuciones uniforme y normal porque no satisfacen las condiciones de momento inverso finito. ${\displaystyle \Delta _{ni}}$

La función de pérdida J(u) debe ser tres veces continuamente diferenciable y los elementos individuales de la tercera derivada deben estar acotados: . Además, como . ${\displaystyle |J^{(3)}(u)|<a_{3}<\infty }$ ${\displaystyle |J(u)|\rightarrow \infty }$ ${\displaystyle u\rightarrow \infty }$

Además, debe ser Lipschitz continua, acotada y la EDO debe tener una solución única para cada condición inicial. Bajo estas condiciones y algunas otras, converge en probabilidad al conjunto de mínimos globales de J(u) (véase Maryak y Chin, 2008). ${\displaystyle \nabla J}$ ${\displaystyle {\dot {u}}=g(u)}$ ${\displaystyle u_{k}}$

Se ha demostrado que no se requiere diferenciabilidad: la continuidad y la convexidad son suficientes para la convergencia. ^[1]

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 de manera eficiente la matriz hessiana de la función de pérdida en función de mediciones de pérdida ruidosas o mediciones de gradiente ruidosas (gradientes estocásticos). Al igual que con el método SPSA básico, solo se necesita una pequeña cantidad fija de mediciones de pérdida o mediciones de gradiente en cada iteración, independientemente de la dimensión del problema p . Consulte la breve discusión en Descenso de 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 utilizando 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 mediante aproximación estocástica de perturbación simultánea", IEEE Transactions on Automatic Control , 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 Americana de Control , Minneapolis, MN, junio de 1987, págs. 1161–1167.
• Spall, JC (1992), “Aproximación estocástica multivariante utilizando una aproximación de gradiente de perturbación simultánea”, IEEE Transactions on Automatic Control , vol. 37(3), págs. 332–341.
• Spall, JC (1998). "Descripción general del método de perturbación simultánea para optimización eficiente" 2. Johns Hopkins APL Technical Digest , 19(4), 482–492.
• Spall, JC (2003) Introducción a la búsqueda y optimización estocástica: estimación, simulación y control , Wiley. ISBN  0-471-33052-3 (Capítulo 7)

1. He, Ying; Fu, Michael C.; Steven I., Marcus (agosto de 2003). "Convergencia de la aproximación estocástica de perturbación simultánea para la optimización no diferenciable". IEEE Transactions on Automatic Control . 48 (8): 1459–1463. doi :10.1109/TAC.2003.815008 . Consultado el 6 de marzo de 2022 .