Число шагов в методе градиентного спуска (нелинейный МНК)

[shto-delat]

Для подгонки численного решения краевой задачи к экспериментальному графику используется нелинейный МНК - метод градиентного спуска. К сожалению, в каких-то случаях он требует очень большого числа шагов, что очень затратно с точки зрения времени выполнения программы.

Задача многопараметрическая (всего 4 параметра), поэтому за 1 цикл МНК процедура требует вычисления решения краевой задачи 4 раза. Число циклов в некоторых случаев достигает 500.

Необходимо уменьшить либо число вызовов решения краевой задачи за 1 цикл, либо число циклов. Какими методами это можно сделать?

[мат-ламер]

shto-delat. Метод градиентного спуска имеет медленную сходимость. А какой метод использовать - зависит от специфики задачи. Вы сами всё программировать будете (или используете какой-либо мат. пакет)? Вот тут http://dxdy.ru/topic24224.html я имел неосторожность посоветовать на первых этапах использовать метод градиентного спуска с переходом в дальнейшем к методу Ньютона. Ничего хорошего не получилось. Попробуйте воспользоваться методом сопряжённых градиентов.

[shto-delat]

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

все дело в том, что метод градиентного спуска до недавних пор давал условно приемлемые результаты, когда исходная функция была монотонной. но в определенном этапе усложнения модели появились интервалы возрастания и убывания решения. при этом градиентный метод стал работать значительно хуже.

[мат-ламер]

Сам я квазиньютоновские методы не программировал, но использовал готовые функции в MATLABe, и работали они достаточно быстро и стабильно. С Вашими затруднениями с монотонностью я не разобрался. Возможно целевая функция приобрела "овражный" характер, где градиентный метод плохо работает. Хуже, если это многоэкстремальность. У квазиньютоновских методов есть несколько реализаций. Какая из них лучше - я не знаю. Можете посмотреть книгу - Гилл, Мюррей, Райт. Практическая оптимизация.

[shto-delat]

мат-ламер
спасибо, ее сейчас как раз и смотрю.

[shto-delat]

Столкнулся с проблемой. Есть ли какие-то определенные методики выбора ньютоновского шага $\alpha_k$, а также шага разностной аппроксимации $h_j_k$?

Как выбирать нулевое приближение матрицы Гессе?
Как я понял, ее диагональные элементы как-то должны коррелировать с порядком величин, которые представляют собой параметры. Я прав?

Нашел, вроде бы критерий вида

\left|g(x_k+\alpha p_k)^Tp_k\right|\geq\gamma g_k^Tp_k

Но непонятно, как отсюда выразить $\alpha_k$

[shto-delat]

Итак, я решил эту задачу.
Рад рапортовать об успехе. Для будущих поколений рассказываю, что получилось.

Результат вполне оправдал ожидания. Лучшие реализации метода наискорейшего спуска давали до сих пор для одного случая 411 итераций. Метод переменной метрики (квазиньютоновский) для этого случая дает выигрыш почти в 100 раз, требуя всего 12 итераций (!), при этом точность получается вдвое выше.

Что я делал и как справлялся с проблемами.
В качестве нулевого приближения матрицы Гессе я использовал единичную матрицу (то есть нулевой шаг -- наискорейший спуск). Для расчета последующих приближений матрицы я использовал BFGS-формулу. После нахождения матрицы на k+1 шаге я использовал метод золотого сечения чисел Фибоначчи для того, чтобы реализовать одномерный поиск вдоль направления убывания суммы квадратов. При поиске градиента я использовал правую аппроксимацию.

Вопрос можно считать закрытым. Всем спасибо за внимание.