Выбор метода одномерной оптимизации в градиентном поиске

[Andrey_Kireew]

Алгоритм градиентного поиска описывается рекуррентным соотношением:

$$\bold x_{k+1}=\bold x_{k}-\mu \cdot \nabla\xi,$$

где $\bold x$ вектор оптимизируемых параметров, $\xi$ - оптимизируемый функционал.

Разные варианты метода отличаются друг от друга способом выбора шага $\mu$. Среди них самый эффективный - метод наискорейшего спуска, в котором $\mu$ определяется в ходе решения одномерной оптимизации.

Собственно вопрос. Какие методы одномерной оптимизации для этого обычно используются?
В литературе удалось найти информацию только о методе золотого сечения. Понятно, что подойдёт и метод бисекции.
Но у обоих методов есть недостаток - нужно задать интервал неопределённости. Минимальное значение шага, понятно $\mu=0$,
но о максимальном значении шага информации может и не быть. Какими соображениями руководствоваться в этом случае?

[podih]

Проблема очень общая для существования строгого решения. "Почувствуйте" функцию, задавая различные начальные шаги. Затем то же самое предложите программе: чтоб она запоминала размер удачных шагов и применяла преимущественно шаги, дающие их минимальный набор. В любом случае это будет random на диапазоне, к тому же с переменными границами.

[ewert]

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

Но есть у него и достоинство -- в определённом смысле абсолютная надёжность. При этом медленная сходимость оборачивается и некоторым преимуществом. Нет никакой необходимости добиваться на каждом шаге точной одномерной минимизации -- достаточно оказаться не слишком далеко от точного минимума. Допустим, это замедлит алгоритм в пару раз (за счёт увеличения знаменателя прогрессии); это многократно окупится упрощением самого шага.

Простейшая идея такова. Сравниваем целевую функцию $\Phi_k(\mu)=\xi(x_k-\mu\,\nabla\xi(x_k))$ и линейную $\widetilde\Phi_k(\mu)=\xi(x_k)-\frac12\mu|\nabla\xi(x_k)|^2$. Для достаточно далёких итераций эти две функции в точке минимума почти совпадают, поскольку вторая -- это секущая, проходящая через точку $\mu=0$ и вершину параболы (в предположении квадратичности $\xi$). Поэтому сначала увеличиваем предыдущее значение $\mu_k$ в определённое количество раз (скажем, в полтора-два) до тех пор, пока не начнёт нарушаться неравенство $\Phi_k(\mu_k)<\widetilde\Phi_k(\mu_k)$. А потом уменьшаем в то же количество раз до тех пор, пока это неравенство не начнёт выполняться. На этом и успокаиваемся.

[Andrey_Kireew]

Спасибо ewert, я по пробовал и кажется работает.
Пробный шаг задаю так, чтобы наиболее быстро изменяющаяся в направлении градиента переменная, менялась ровно на 1% (конечно, можно взять и другое значение). Потом, проверяя неравенство

$$\Phi_k(\mu_k)<\widetilde\Phi_k(\mu_k)$$

при необходимости, увеличиваю шаг. В результате, получаю интервал неопределённости. Внутри него, нахожу минимум золотым сечением.

Всё это пока работает, и неплохо, но у меня есть опасения. Что если найденный интервал неопределённости не будет в действительности содержать искомый минимум? Ведь предпосылка о квадратичной форме $\xi$ выполняется лишь приближенно. Тогда золотое сечение уже не гарантирует произвольной точности. В таком случае положение одной из границ исходного интервала неопределённости не изменится. Это, по крайней мере, легко определить и, как то, продолжить поиск.

Можно сразу дробить исходный интервал на основе того же неравенства, но тогда, точность будет гарантировано ограниченной. Можно ли как то её вообще оценить? Или, что тоже самое, как определить критерий останова?

Какой путь на Ваш взгляд лучше?

[vpb]

Andrey_Kireew в сообщении #1398984 писал(а):

результате, получаю интервал неопределённости. Внутри него, нахожу минимум золотым сечение

Много писать не могу, но в целом так.
Раньше (до середины 1960-х) считалось, что при градиентном спуске надо на каждом шаге задачу одномерной минимизации решать как можно точнее, из того интуитивно-очевидного соображения, что чем лучше минимизируем на каждом шаге, тем лучше будет в целом (так называемый метод наискорейшего спуска, steepest descent). Но потом выяснилось, что это совершенно неверно. От слова совсем, как говорят нынче. Поэтому первый совет такой: если получаете для $\mu$ интервал неопределенности в разностью концов в полтора-два раза, как советует ewert, больше внутри этого интервала никакой поиск не производите, ибо только хуже сделаете, и притом время потратите.
А содержит ли этот интервал неопределенности в действительности минимум, это тоже пустые хлопоты. Даже если не содержит, в том беды нет.

О минимизации одномерных функций вообще можно почитать в учебнике Сухарев-Тимохов-Федоров, глава 2. О различных правилах выбора $\mu$ на одном шаге --- Дэннис-Шнабель, пар.6.3. (правила Армихо, Голдстейна). Еще больше --- Nocedal, Wright, Numerical Optimization, chapter 3. Наконец, есть разные стратегии для выбора последовательности $\mu_k$ в целом.

[B@R5uk]

Andrey_Kireew, а у вас какая задача стоит? Если познакомится с методом градиентного спуска и его вариациями — это одно. А если вы хотите оптимизировать что-то практическое, то настоятельно рекомендую присмотреться к другим методам. Например, когда размерность не очень велика и не хочется/нет возможности считать производные целевой функции, то есть замечательный алгоритм Нелдера-Мида. Он достаточно простой и к тому же обладает хорошей устойчивостью в тех задачах, где градиентный спуск просто глохнет.

Кстати, вы уже знаете про функцию Розенброка? Замечательный пример "плохой" функции применительно к вопросу оптимизации. Входит в группу первых тестовых образцов, скармливаемых любому новоиспечённому алгоритму поиска экстремума.

[Andrey_Kireew]

Спасибо vpb за очередную книгу, нашел в ней много для себя интересного.

Пользуясь случаем, хотелось бы прояснить момент касающийся точности шага $\mu$, так как многие участники целесообразность погони за точностью выбора шага в данном случае ставят под сомнение.
Действительно, точность выбора шага в градиентном поиске не критична. Судя по моим наблюдениям отклонения $\pm10 \%$ практически не меняет форму кривой сходимости. Есть простые способы обеспечить сходимость градиентного поиска, не требующие точного вычисления шага. Часто намного выгоднее вместо увеличения точности $\mu$ увеличить число шагов.

Однако, если цена вычисления градиента высока, точность вычисления $\mu$ становится существенной. По крайней мере $\pm 5-10 \%$ нужно обеспечить, иначе эффективность алгоритма резко падает. Думаю несложно догадаться, что в перспективе планируется опробовать и метод сопряженных направлений. Доработка там требуется минимальная, но точность $\mu$ нужна совсем другая.

В общем имеется цель создать простой и надёжный алгоритм линейного поиска, позволяющий находить $\mu$ с любой, наперёд заданной точностью. Ничего сверхъестественного в этой задаче я не вижу.

Спасибо B@R5uk за информацию, но алгоритм Нелдера-Мида мне наверное никак не подойдёт, размерность слишком большая. Вообще, методы не самоцель, у меня конкретная задача. Пытаюсь использовать разные методы, пока с попеременным успехом. Сейчас склоняюсь к тому, что в классическом варианте, не подойдёт ни один из них. Градиентный алгоритм нужен больше для сравнения с другими алгоритмами.

[B@R5uk]

Andrey_Kireew в сообщении #1399198 писал(а):

В общем имеется цель создать простой и надёжный алгоритм линейного поиска, позволяющий находить $\mu$ с любой, наперёд заданной точностью. Ничего сверхъестественного в этой задаче я не вижу.

Вы точно понимаете механизм поиска $\mu$? Я имею в виду то, что численная оптимизация этой величины при фиксированном градиенте требует вычисления многих значений оптимизируемой функции? Как правило, сложность вычисления градиента не на много выше сложности вычисления самой функции. Ресурсы процессора алгоритм будет потреблять, а к минимум приближаться не будет ни на йоту (а то и удалится будет).

[Andrey_Kireew]

B@R5uk в сообщении #1399296 писал(а):

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

спасибо за информацию, раньше я об этом не догадывался

[B@R5uk]

Andrey_Kireew в сообщении #1399198 писал(а):

Вообще, методы не самоцель, у меня конкретная задача. Пытаюсь использовать разные методы, пока с попеременным успехом. Сейчас склоняюсь к тому, что в классическом варианте, не подойдёт ни один из них.

А можно по-подробнее о том, какую целевую функцию вы оптимизируете? Я понимаю, что мы немного отъезжаем от начальной темы топика, но всё же. Именно свойства целевой функции определяют то, каким алгоритмом стоит пользоваться.

[Andrey_Kireew]

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

$$step_0=\xi_0/|\nabla_0|^2$$

-- 15.06.2019, 00:29 --

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

$$step_1=\frac{1}{2}\frac{step_0\cdot|\nabla_0|^2}{|\nabla_0|^2+\frac{\xi_1-\xi_0}{step_0}}$$

.