Оптимизация при неограниченной матрице Гёссе

[Missir]

Есть одна задача оптимизации, в которой некоторые элементы матрицы Гёссе становятся неограниченными. Используя правило обращения блочной матрицы, матрицу Гёссе можно обратить, в этом случае строки и столбцы обратной матрицы, соответствующие неограниченным элементам становятся нулевыми. Таким образом, если применять метод Ньютона, то как только некоторые параметры матрицы Гёссе станут неограниченными, то соответствующие им параметры уже никогда не будут изменяться, так как их приращения после этого всегда будут нулевыми. Происходит "застревание". Одним из условий сходимости метода Ньютона является ограниченность всех первых и вторых производных оптимизируемого функционала. Т.е. застревание параметров - это проблема сходимости метода Ньютона и полученное таким образом решение в общем случае не будет оптимальным.

Как можно преодолеть данную проблему и выполнить оптимизацию в условиях неограниченности матрицы Гёссе?

[Утундрий]

Любопытная постановка вопроса. У вас имеется решаешь, способный работать с бесконечными величинами?

[dsge]

Missir в сообщении #1680274 писал(а):

Как можно преодолеть данную проблему и выполнить оптимизацию в условиях неограниченности матрицы Гёссе?

Отказаться от Ньютона, перейти к gradient descent или к методам без производных.
Метод Ньютона-Канторовича, если в начальной точке Гессиан конечен.
В самом экстремуме Гессиан неограничен или ограничен?

[Missir]

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

в самом экстремуме матрица Гёссе разумеется не ограничена, в этом то и проблемы.

Идеи есть разные, например вначале придавать небольшие смещения параметрам, с тем, чтобы не допустить неограниченность матрицы Гёссе, и постепенно их уменьшать. Но это в общем не гарантирует того, что алгоритм также не застрянет. Или есть вариант сначала оптимизировать градиентом, а потом выполнить итерацию методом Ньютона. Что характерно, при градиентном спуске матрица Гёссе почему то никогда не становится неограниченной.
Или есть вариант оптимизировать методом Ньютона, а "застрявшие" параметры двигать в направлении градиента. По идее, это может позволить выйти из затруднения. Если градиент не нулевой, то решение не оптимально и оптимизация будет продолжаться.
Здесь поинтересовался, так как думал что есть какие то общепринятые способы преодоления таких затруднений.

А Вы думаете как лучше сделать?

[Утундрий]

Missir в сообщении #1680279 писал(а):

в самом экстремуме матрица Гёссе разумеется не ограничена

Значит криво поставлена задача.

[dsge]

Missir
1. Задача выпуклая?
2. Бесконечности в гессиане на диагонале или вне?
3. Была ли проверка, что Решение у задачи вообще существует?

[zgemm]

Missir в сообщении #1680274 писал(а):

Как можно преодолеть данную проблему и выполнить оптимизацию в условиях неограниченности матрицы Гёссе?

Это довольно распространенная заморочка в BFGS и других квази-ньютонах - часть сингулярных значений обратной матрицы идет в ноль, и это только помогает сходиться. В учебниках многие теоретики-идиоты рекомендуют рестарт, и я очень много раз велся на такие высказывания, но было только хуже и все переставало сходиться. Я всегда стараюсь работать не с Ньютоновской матрицей, а с ее обратной. Вот если она растет, то ее надо регуляризаторами, типа Тихонова, но как я понимаю, у Вас она не растет.

А у Вас откуда Ньютоновская матрица получается, из BFGS? Так запишите формулы для обратной и только с ней работайте, а если у Вас явно Ньютоновская матрица задана какой-то специальной аппроксимацией, тогда надо искать как в этой аппроксимации записать обратную минуя исходную.

[мат-ламер]

Missir в сообщении #1680274 писал(а):

Есть одна задача оптимизации, в которой некоторые элементы матрицы Гёссе становятся неограниченными.

А можно простейший модельный пример такой задачи? Если мы ищем, к примеру, минимум функции $f(x)=x^4$ , то при увеличении $x$ тут вторая производная растёт неограниченно. Однако, мы ищем минимум, который находится в нуле. И здесь вторая производная зануляется. Это даёт некий негативный эффект на скорость сходимости метода Ньютона (вероятно, преодолимый). Однако, видимо, это не то, чем вы интересуетесь.

[Missir]

zgemm в сообщении #1680339 писал(а):

Так запишите формулы для обратной и только с ней работайте

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

-- 30.03.2025, 16:34 --

dsge
задача выпуклая, бесконечности на диагонали, решение существует

-- 30.03.2025, 16:36 --

мат-ламер в сообщении #1680349 писал(а):

А можно простейший модельный пример такой задачи? Если мы ищем, к примеру, минимум функции

там в некоторых местах есть изломы, из-за них и возникают бесконечности

[zgemm]

Missir в сообщении #1680401 писал(а):

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

тогда viel gluck, мы тут не экстрасенсы.

[Евгений Машеров]

Если элементы матрицы Гессе неограничены, значит, функция не может быть приближена квадратичной зависимостью. Судя по упоминанию "изломов" - ничего удивительного в этом нет.
То есть нужен другой метод, возможно (судя по "изломам"), вообще не использующий производных. Наверно, зная постановку, можно перепараметризовать задачу, но без подробного описания ничего сказать нельзя.
Если градиентный метод достигает некоего оптимума, но это "не то" - возможно, в задаче есть локальные оптимумы. Искать хорошее начальное приближение или случайным поиском выбирать начальную точку, многократно повторяя оптимизацию.

[dsge]

Missir
Могут быть разные варианты:
1. Особенность для градиента в виде $x^{\alpha}, 0<\alpha<1$, тогда переход к градиентным методам должет дать правильный результат из-за выпуклости, при условии, что вы перед градиентом правильно подобрали параметр сходимости, то что в машинном обучении зовется обучающийся параметр.
2. Особенность для градиента в виде $x^{-\alpha}, 0<\alpha. В этом случае градиент может уходить в бесконечность или перестать существовать. Надо применять безградиентные методы, например, типа Nelder-Mead simplex algorithm.