Стохастическая аппроксимация одновременных возмущений

Стохастическая аппроксимация одновременных возмущений (SPSA) — это алгоритмический метод оптимизации систем с несколькими неизвестными параметрами . Это тип алгоритма стохастической аппроксимации . В качестве метода оптимизации он подходит для крупномасштабных моделей населения, адаптивного моделирования, оптимизации моделирования и моделирования атмосферы . Многие примеры представлены на веб-сайте SPSA http://www.jhuapl.edu/SPSA . Подробную книгу по этой теме можно найти в книге Bhatnagar et al. (2013). Ранней статьей на эту тему является Сполл (1987), а основополагающей статьей, дающей ключевую теорию и обоснование, является Сполл (1992).

SPSA — это метод спуска, способный находить глобальные минимумы, разделяющий это свойство с другими методами, такими как имитация отжига . Его главной особенностью является градиентная аппроксимация, требующая всего двух измерений целевой функции независимо от размерности оптимизационной задачи. Напомним, что мы хотим найти оптимальное управление $u^{*}$ с потерейфункция $J(u)$:

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

Стохастическая аппроксимация обеих конечных разностей (FDSA)и SPSA используют один и тот же итерационный процесс:

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

где $u_{n}=((u_{n})_{1},(u_{n})_{2},\ldots ,(u_{n})_{p})^{T}$представляет собой $n^{th}$ повторять, ${\hat {g}}_{n}(u_{n})$ — оценка градиента целевой функции $g(u)={\frac {\partial }{\partial u}}J(u)$ оценивается в ${u_{n}}$, и $\{a_{n}\}$ – положительная числовая последовательность, сходящаяся к 0. Если $u_{n}$ является p -мерным вектором, $i^{th}$ Компонент симметричной оценки градиента конечной разности:

ФД: $({\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 , где $e_{i}$ - единичный вектор с 1 в $i^{th}$место и $c_{n}$— небольшое положительное число, которое уменьшается с ростом n . С помощью этого метода 2p оценки J для каждого $g_{n}$ необходимы. Когда p велико, эта оценка теряет эффективность.

Пусть сейчас $\Delta _{n}$ — случайный вектор возмущения. $i^{th}$ Компонент оценки градиента стохастических возмущений:

СП: $({\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}}}.$

Заметим, что FD возмущает одновременно только одно направление, тогда как оценка SP возмущает все направления одновременно (числитель одинаков во всех p- компонентах). Количество измерений функции потерь, необходимое в методе SPSA для каждого $g_{n}$ всегда равно 2, независимо от размерности p . Таким образом, SPSA использует в p раз меньше оценок функций, чем FDSA, что делает его намного более эффективным.

Простые эксперименты с p=2 показали, что SPSA сходится за то же количество итераций, что и FDSA. Последний следует примерно по направлению самого крутого спуска и ведет себя как градиентный метод. С другой стороны, SPSA со случайным направлением поиска не следует точно градиентному пути. Однако в среднем он почти отслеживает его, потому что градиентная аппроксимация является почти несмещенной. оценку градиента, как показано в следующей лемме.

Лемма о сходимости

Обозначим через

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

смещение в оценке ${\hat {g}}_{n}$. Предположим, что $\{(\Delta _{n})_{i}\}$ все взаимно независимы с нулевым средним, ограниченным вторыммоменты и $E(|(\Delta _{n})_{i}|^{-1})$ равномерно ограничено. Затем $b_{n}$→0 п.п. 1.

доказательства

Основная идея состоит в том, чтобы использовать кондиционирование на $\Delta _{n}$ выражать $E[({\hat {g}}_{n})_{i}]$ а затем использовать разложение Тейлора второго порядка $J(u_{n}+c_{n}\Delta _{n})_{i}$ и $J(u_{n}-c_{n}\Delta _{n})_{i}$. После алгебраических манипуляций с использованием нулевого среднего и независимости $\{(\Delta _{n})_{i}\}$, мы получаем

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

Результат следует из гипотезы о том, что $c_{n}$→0.

Далее мы остановимся на некоторых гипотезах, согласно которым $u_{t}$ сходится по вероятности к множеству глобальных минимумов $J(u)$. Эффективностьметод зависит от формы $J(u)$, значения параметров $a_{n}$ и $c_{n}$ и распределение членов возмущения $\Delta _{ni}$. Во-первых, параметры алгоритма должны удовлетворятьследующие условия:

• $a_{n}$ >0, $a_{n}$→0, когда n→∝ и $\sum _{n=1}^{\infty }a_{n}=\infty$. Хорошим выбором будет $a_{n}={\frac {a}{n}};$ а>0;
• $c_{n}={\frac {c}{n^{\gamma }}}$, где с>0, $\gamma \in \left[{\frac {1}{6}},{\frac {1}{2}}\right]$;
• $\sum _{n=1}^{\infty }({\frac {a_{n}}{c_{n}}})^{2}<\infty$
• $\Delta _{ni}$ должны быть взаимно независимыми случайными величинами с нулевым средним, симметрично распределенными относительно нуля, с $\Delta _{ni}<a_{1}<\infty$. Обратные первый и второй моменты $\Delta _{ni}$ должно быть конечным.

Хороший выбор для $\Delta _{ni}$ — распределение Радемахера , т.е. Бернулли +-1 с вероятностью 0,5. Возможны и другие варианты, но учтите, что равномерное и нормальное распределения использовать нельзя, поскольку они не удовлетворяют условиям конечного обратного момента.

Функция потерь J(u) должна быть трижды непрерывно дифференцируемой , а отдельные элементы третьей производной должны быть ограничены: $|J^{(3)}(u)|<a_{3}<\infty$. Также, $|J(u)|\rightarrow \infty$ как $u\rightarrow \infty$.

Кроме того, $\nabla J$ должно быть липшицевым, ограниченным и ОДУ ${\dot {u}}=g(u)$ должно иметь единственное решение для каждого начального условия.В этих и некоторых других условиях $u_{k}$ сходится по вероятности к множеству глобальных минимумов J(u) (см. Марьяк и Чин, 2008).

Показано, что дифференцируемость не требуется: для сходимости достаточно непрерывности и выпуклости.

методов второго порядка (

Известно, что стохастическая версия стандартного (детерминированного) алгоритма Ньютона-Рафсона (метод «второго порядка») обеспечивает асимптотически оптимальную или близкую к оптимальной форму стохастической аппроксимации. SPSA также можно использовать для эффективной оценки матрицы Гессе функции потерь на основе измерений зашумленных потерь или измерений зашумленного градиента (стохастических градиентов). Как и в случае с базовым методом SPSA, на каждой итерации требуется лишь небольшое фиксированное количество измерений потерь или измерений градиента, независимо от размерности задачи p . См. краткое обсуждение в разделе Стохастический градиентный спуск .

Ссылки

• Бхатнагар С., Прасад Х.Л. и Прашант Л.А. (2013), Стохастические рекурсивные алгоритмы для оптимизации: методы одновременного возмущения , Springer [1] .
• Хироками Т., Маэда Ю., Цукада Х. (2006) «Оценка параметров с использованием стохастической аппроксимации одновременных возмущений», Электротехника в Японии, 154 (2), 30–3 [2]
• Марьяк, Дж.Л., и Чин, округ Колумбия (2008), «Глобальная случайная оптимизация с помощью стохастической аппроксимации с одновременными возмущениями», Транзакции IEEE по автоматическому управлению , том. 53, стр. 780-783.
• Сполл, Дж. К. (1987), «Техника стохастической аппроксимации для генерации оценок параметров максимального правдоподобия», Труды Американской конференции по контролю , Миннеаполис, Миннесота, июнь 1987 г., стр. 1161–1167.
• Сполл, Дж. К. (1992), «Многомерная стохастическая аппроксимация с использованием одновременной аппроксимации градиента возмущений», IEEE Transactions on Auto Control , vol. 37(3), стр. 332–341.
• Сполл, Дж. К. (1998). «Обзор метода одновременных возмущений для эффективной оптимизации» 2 . Технический дайджест Johns Hopkins APL , 19 (4), 482–492.
• Сполл, Дж. К. (2003) Введение в стохастический поиск и оптимизацию: оценка, моделирование и контроль , Wiley. ISBN   0-471-33052-3 (глава 7)