Размер шага адаптивного градиентного спуска, когда вы не можете найти строку

У меня есть целевая функция $E$ зависит от значения $\phi(x, t = 1.0)$, где $\phi(x, t)$это решение для PDE. Я оптимизирую$E$по градиентному спуску на исходное состояние ФДЭ:$\phi(x, t = 0.0)$, То есть я обновляю$\phi(x, t = 0.0)$а затем придется интегрировать PDE, чтобы вычислить мой остаток. Это означает, что если бы мне пришлось искать строку для шага градиентного спуска (назовите его$\alpha$), для каждого потенциального значения $\alpha$ Мне пришлось бы заново интегрировать PDE.

В моем случае это было бы слишком дорого. Есть ли другой вариант для шага адаптивного градиентного спуска?

Я не просто ищу математически принципиальные схемы (хотя, конечно, лучше, если что-то существует), но был бы рад всему, что в целом лучше, чем статический размер шага.

Спасибо!

Я начну с общего замечания: информация первого порядка (т. Е. Использование только градиентов, которые кодируют наклон) может дать вам только информацию о направлении: она может сказать вам, что значение функции уменьшается в направлении поиска, но не в течение какого времени , Чтобы решить, как далеко идти вдоль направления поиска, вам нужна дополнительная информация (градиентный спуск с постоянной длиной шага может не сработать даже для выпуклых квадратичных задач). Для этого у вас есть два варианта:

1. Используйте информацию второго порядка (которая кодирует кривизну), например, используя метод Ньютона вместо градиентного спуска (для которого вы всегда можете использовать длину шага$1$ достаточно близко к минимизатору).
2. Метод проб и ошибок (что, конечно, я имею в виду, используя правильный поиск строки, такой как Armijo).

Если, как вы пишете, у вас нет доступа ко вторым производным, и оценка функции объектива стоит очень дорого, ваша единственная надежда - пойти на компромисс: используйте достаточно приблизительную информацию второго порядка, чтобы получить подходящую длину шага кандидата, такую ​​что строка поиск нужен только $\mathcal{O}(1)$ оценки (т. е. не более (небольшая) постоянная кратность усилий, необходимых для оценки градиента).

Одной из возможностей является использование длины шага Барзилай - Борвейна (см., Например, Флетчер: О методе Барзилай-Борвейна . Оптимизация и управление с приложениями, 235–256, Appl. Optim., 96, Springer, New York, 2005 ). Идея состоит в том, чтобы использовать конечно-разностную аппроксимацию кривизны вдоль направления поиска, чтобы получить оценку размера шага. В частности, выберите$\alpha_0>0$ произвольный набор $g^0:=\nabla f(x^0)$ а затем для $k=0,...$:

1. Набор $s^k = -\alpha_k^{-1} g^k$ а также $x^{k+1}=x^k+s^k$
2. оценивать $g^{k+1}=\nabla f(x^{k+1})$ и установить $y^k = g^{k+1}-g^{k}$
3. Набор $\alpha_{k+1} = \frac{(y^k)^Ty^k}{(y^k)^Ts^k}$

Можно показать, что этот выбор сходится (на практике очень быстро) для квадратичных функций, но сходимость не является монотонной (т. Е. Значение функции$f(x^{k+1})$ может быть больше чем $f(x^k)$, но только время от времени; см. график на стр. 10 в статье Флетчера). Для неквадратичных функций вам необходимо объединить это с поиском строк, который необходимо изменить, чтобы справиться с немонотонностью. Одна возможность выбора$\sigma_k \in (0,\alpha_k^{-1})$ (например, путем возврата), так что

$$f(x^k - \sigma_k g^k) \leq \max_{\max(k-M,1)\leq j\leq k} f(x^j) - \gamma \sigma_k (g^k)^Tg^k,$$ где - типичный параметр Armijo, а управляет степенью монотонности (например, ). Есть также вариант, в котором вместо значений функции используются значения градиента, но в вашем случае вычисление градиента даже дороже, чем функции, поэтому здесь это не имеет смысла. (Примечание: Вы, конечно, можете попытаться слепо принять длину шага BB и довериться удаче, но если вам нужна какая-либо надежность - как вы написали в своих комментариях - это было бы действительно плохой идеей.)$\gamma\in(0,1)$$M$$M=10$

Альтернативный (и, на мой взгляд, гораздо лучший) подход будет использовать это приближение конечных разностей уже при расчете направления поиска; это называется квазиньютоновским методом . Идея состоит в том, чтобы постепенно построить аппроксимацию гессиана , используя различия градиентов. Например, вы можете взять (единичная матрица) и для решить и установить с помощью как указано выше, и . (Это называется Broyden update$\nabla^2 f(x^k)$$H_0=\mathrm{Id}$$k=0,\dots$

$$H_{k}s^{k} = -g^{k},\label{cc1}\tag{1}$$ $$H_{k+1} = H_k + \frac{(y^k-H_ks^k)^T(s^k)^T}{(s^k)^Ts^k}$$ $y^k$$x^{k+1} = x^k +s^k$и редко используется на практике; Лучшим, но немного более сложным обновлением является обновление BFGS , для которого - и больше информации - я обращаюсь к книге « Численная оптимизация» Носедала и Райта .) Недостатком является то, что а) для этого потребуется решение линейной системы на каждом этапе (но только размером неизвестного, который в вашем случае является начальным условием, следовательно, усилия должны основываться на решении PDE для получения градиента, а также существуют правила обновления для приближений обратного гессиана, которые требуют вычисления только одной матрицы -векторный продукт) и б) вам все еще нужен поиск строки, чтобы гарантировать сходимость ...

К счастью, в этом контексте существует альтернативный подход, который использует каждую функцию оценки. Идея состоит в том, что для симметричной и положительно определенной (что гарантировано для обновления BFGS) решение эквивалентно минимизации квадратичной модели В методе области доверия вы должны сделать это с дополнительным ограничением, которое , где - это правильно выбранный радиус доверительной области (который играет роль длины шага ). Ключевая идея заключается в том, чтобы теперь адаптивно выбирать этот радиус на основе вычисленного шага. В частности, вы смотрите на соотношение $H_k$$\eqref{cc1}$

$$q_k(s) = \frac12 s^T H_k s + s^T g^k.$$ $\|s\| \leq \Delta_k$$\Delta_k$$\sigma_k$ $$\rho_k := \frac{f(x^k)-f(x^k+s^k)}{f(x^k)-q_k(s^k)}$$ фактического и прогнозируемого уменьшения значения функции. Если очень мало, ваша модель была плохой, и вы отбрасываете и попробуйте снова с . Если близко к , ваша модель хороша, и вы устанавливаете и увеличиваете . В противном случае вы просто устанавливаете и оставляете покое. Чтобы вычислить фактический минимизатор из$\rho_k$$s^k$$\Delta_{k+1}<\Delta_k$$\rho_k$$1$$x^{k+1}=x^k+s^k$$\Delta_{k+1}>\Delta_k$$x^{k+1}=x^k+s^k$$\Delta_k$$s^k$$\min_{\|s\|\leq \Delta_k} q_k(s)$существует несколько стратегий, позволяющих избежать решения проблемы полной ограниченной оптимизации; мой фаворит - усеченный метод компьютерной графики Стейхауга . Для более подробной информации, я снова обращаюсь к Nocedal и Wright.