Обсуждение:Методы оптимизации в машинном обучении (курс лекций)/2012/Задание 1

Материал из MachineLearning.

• Какой критерий сходимости используют в методе парабол? Когда я выбираю тройки чисел, такие чтобы в центральной значение функции было минимально, у меня часто оказывается ситуация, когда один из краёв отрезка долго не меняется. При этом длина интервала между крайними точками долго остаётся слишком грубой оценкой, потом наконец выбирается другой край, и длина резко падает, например до 1e-8, что сильно точнее того что мы хотим. При этом остановиться, получив точность 1e-5, можно было сильно раньше. Shapovalov 14:51, 9 октября 2012 (MSD)

  Критерий сходимости в методе парабол такой же, как и в других методах одномерной оптимизации: когда текущий интервал поиска решения сокращается до заданной длины. Действительно, в некоторых случаях в методе парабол интервал в итерациях сокращается очень слабо. Решать эту проблему можно различными модификациями метода парабол, например, использованием схемы Брента. В ней, в частности, отклоняются параболические точки, которые приводят к слишком маленьким сокращениям интервала поиска решения, и вместо них используется золотое сечение или деление отрезка пополам. В рамках задания не требуется модифицировать метод парабол на все случаи жизни. Необходимо лишь удостовериться в различным проблемах, связанных с его использованием на практике. При этом реализация схемы Брента должна справляться со всеми сложностями в оптимизации. — Д.А. Кропотов 22:11, 10 октября 2012 (MSD)

Кажется, в конспекте опечатка в псевдокоде Брента: в методе золотого сечения «если x < (c − a)/2 то» — похоже, должно быть среднее арифметическое. Shapovalov 16:08, 11 октября 2012 (MSD)

Ещё одна вещь мне помогла избавиться от нескольких лишних итераций трисекции перед самой сходимостью в методе Брента: если находится в -окрестности границы интервала, то не запускаем трисекцию сразу же, а двигаем в допустимую зону и пытаемся идти по параболическому приближению. В противном случае, если реальная точка минимума оказывается на границе интервала, то приходится зазря сужать интервал трисекциями. Такой вариант используется в “Numerical recipes”. Shapovalov 20:05, 11 октября 2012 (MSD)

Вопрос с запозданием, но все же: в методе парабол нужно просто брать точку вершины параболы или еще и проверять, что это точка минимума? Тот же вопрос про кубические аппроксимации: если на данном отрезке при приравнивании производной к нулю получили только точку максимума, то нужно ли ее принять или считать, что метод разошелся?