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). 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 el recocido simulado . Su característica principal es la aproximación de gradiente que requiere sólo dos mediciones de la función objetivo, independientemente de la dimensión del problema de optimización. Recuerde 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 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 numérica positiva que converge a 0. Si es un vector p -dimensional, el componente del estimador de gradiente simétrico de diferencias finitas 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}}$

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}}},}$

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 evaluaciones 2p 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 del gradiente de perturbación estocástico es: ${\displaystyle \Delta _{n}}$ ${\displaystyle i^{th}}$

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}}}.}$

Obsérvese que FD perturba sólo 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 la función de pérdida necesarias en el método SPSA para cada una 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 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 sigue 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

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

el sesgo en el estimador . Supongamos que todos son mutuamente independientes con segundos momentos acotados, de media cero 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 usar el condicionamiento 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 ${\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 deriva de la hipótesis de que →0. ${\displaystyle c_{n}}$

A continuación resumimos 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 , los valores de los parámetros y la distribución de los términos de perturbación . Primero, los parámetros del algoritmo deben cumplir 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 opció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 con respecto a cero, con . El primer y segundo momento inversos del 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 de 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. ${\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: . Tambien como . ${\displaystyle |J^{(3)}(u)|<a_{3}<\infty }$ ${\displaystyle |J(u)|\rightarrow \infty }$ ${\displaystyle u\rightarrow \infty }$

Además, Lipschitz debe ser 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) (ver 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 eficientemente la matriz de Hesse de la función de pérdida basándose en mediciones de pérdidas ruidosas o mediciones de gradientes ruidosos (gradientes estocásticos). Al igual que con el método SPSA básico, solo se necesita un pequeño número fijo 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 del gradiente estocástico .

Referencias

• Bhatnagar, S., Prasad, HL y Prashanth, LA (2013), Algoritmos estocásticos recursivos para la 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 mediante aproximación estocástica de perturbación simultánea", IEEE Transactions on Automatic Control , vol. 53, págs. 780-783.
• Spall, JC (1987), “A Stochastic Approximation Technique for Generating Maximum Likelihood Parameter Estimates”, Actas de la Conferencia Estadounidense de Control , Minneapolis, MN, junio de 1987, págs.
• Spall, JC (1992), “Aproximación estocástica multivariada 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 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)

1. Él, Ying; Fu, Michael C.; Steven I., Marcus (agosto de 2003). "Convergencia de aproximación estocástica de perturbaciones simultáneas para optimización no diferenciable". Transacciones IEEE sobre control automático . 48 (8): 1459-1463. doi : 10.1109/TAC.2003.815008 . Consultado el 6 de marzo de 2022 .