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

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 . Se trata de un algoritmo de aproximación estocástica . Como método de optimización, resulta idóneo para modelos de población a gran escala, modelado adaptativo, optimización de simulaciones y modelado atmosférico . En el sitio web de SPSA (http://www.jhuapl.edu/SPSA ) se presentan numerosos ejemplos . Un libro exhaustivo sobre el tema es el de Bhatnagar et al. (2013). Un artículo pionero sobre el tema es el de Spall (1987), y el artículo fundamental que proporciona la teoría y la justificación clave es el de Spall (1992).

SPSA es un método de descenso capaz de encontrar mínimos globales, compartiendo esta propiedad con otros métodos como el recocido simulado . Su característica principal es la aproximación del 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${\displaystyle u^{*}}$con función de pérdida${\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}),}$

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

FD:${\displaystyle ({\hat {g_{n}}}(u_{n}))_{i}={\frac {J(u_{n}+c_{n}e_{i})-J(u_{n}-c_{n}e_{i})}{2c_{n}}},}$

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

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

SP:${\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}}}.}$

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

Experimentos sencillos con p=2 demostraron que SPSA converge en el mismo número de iteraciones que FDSA. Este último sigue aproximadamente la dirección de descenso más pronunciado , 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, la sigue de forma bastante precisa, ya que la aproximación del gradiente es un estimador casi insesgado del mismo, como se muestra en el siguiente lema.

Denotemos por

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

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

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

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

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

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

• ${\displaystyle a_{n}}$>0,${\displaystyle a_{n}}$→0 cuando n→∝ y${\displaystyle \sum _ {n=1}^{\infty }a_ {n}=\infty}$Una buena opción sería${\displaystyle a_{n}={\frac {a}{n}};}$a>0;
• ${\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${\displaystyle \Delta _{ni}<a_{1}<\infty }$. Los momentos inversos primero y segundo de la${\displaystyle \Delta _{ni}}$debe ser finito.

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

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:${\displaystyle |J^{(3)}(u)|<a_{3}<\infty}$. También,${\displaystyle |J(u)|\rightarrow \infty }$como${\displaystyle u\rightarrow \infty }$.

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

Se ha demostrado que la diferenciabilidad no es necesaria: la continuidad y la convexidad son suficientes para la convergencia. ^{[ 1 ]}

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. El SPSA también puede utilizarse para estimar eficientemente la matriz hessiana de la función de pérdida basándose en 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 un número pequeño y fijo de mediciones de pérdida o de gradiente en cada iteración, independientemente de la dimensión del problema p . Véase la breve explicación en Descenso de gradiente estocástico .

• Bhatnagar, S., Prasad, HL y Prashanth, LA (2013), Algoritmos recursivos estocásticos para la optimización: métodos de perturbación simultánea , Springer.
• 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
• 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, pp. 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 multivariada mediante una aproximación de gradiente de perturbación simultánea”, IEEE Transactions on Automatic Control , vol. 37(3), pp. 332–341.
• Spall, JC (1998). "Descripción general del método de perturbación simultánea para una 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)