Метод коллинеарных градиентов (МКГ)Tolstykh V.K. Collinear Gradients Method for Minimizing Smooth Functions // Oper. Res. Forum. — 2023. — Vol. 4. — No. 20. — doi: s43069-023-00193-9Толстых В.К. Практическая оптимизация, идентификация распределённых систем. М. : Наука. 2026. 358 с. www.elibrary.ru — итерационный метод направленного поиска локального экстремума гладкой функции многих переменных с движением к экстремуму вдоль вектора такого, где градиенты и коллинеарные. Это метод первого порядка (использует только первые производные ) с квадратичной скоростью сходимости. Может применяться к функциям высокой размерности с несколькими локальными экстремумами. МКГ можно отнести к семейству методов Truncated Newton method
Идея метода
Для гладкой функции в относительно большой окрестности точки найдётся точка , где градиенты и коллинеарные. Направлением на экстремум из точки будет направление . Вектор указывает на максимум или на минимум в зависимости от положения точки . Она может быть спереди или сзади от относительно направления на (см. рисунок). Далее будем рассматривать минимизацию.
Очередная : (1) где оптимальное находится аналитически из предположения квадратичности одномерной функции :
(2)
Угловые скобки — это скалярное произведение в евклидовом пространстве . Если выпуклая функция в окрестности , то для передней точки получаем число , для задней . Делаем шаг (1).
Для строго выпуклой квадратичной функции
т.е. (метод второго порядка с квадратичной скоростью сходимости), где — матрица Гессе. Такие шаги обеспечивают МКГ квадратичную скорость сходимости.
В общем случае, если имеет переменную выпуклость и возможны седловые точки, то следует контролировать направление минимизации по углу между векторами и . Необходимо , если , то — это направление максимизации и в (1) следует брать с обратным знаком. Для функций с особенно большим числом седловых точек, если оказывается , следует делать шаг методом наискорейшего спуска.
Поиск коллинеарных градиентов оценивается невязкой их ортов, которая имеет вид системы уравнений для поиска корня : (3) где знак позволяет одинаково оценивать коллинеарность градиентов по одну или разные стороны от минимума , .
Система (3) решается итерационно (подитерации ) методом сопряжённых градиентов в предположении, что она линейна в окрестности :
(4)
где вектор , , , , произведение матрицы Гессе на находится численным дифференцированием:
(5)
где , — малое положительное число такое, что .
Начальное приближение задаётся под 45° ко всем осям координат длинной :
(6)
Подитерации завершаются при выполнении хотя бы одного из условий:
— достигнута точность; — прекратилась сходимость; — предотвращение избыточности подитераций.
Алгоритм выбора направления минимизации
Параметры: . Входные данные: . Выходные: . , находим из (6). Вычисляем и находим из (3) при . Если , или , или { и }, тогда: ; возвращаем ; подитерации. Если , задаём , иначе . Вычисляем . Находим шаговый множитель для подитераций: задаём , вычисляем , и находим из (5); если , тогда и переходим к шагу 4; находим . Делаем подитерацию . , переходим к шагу 2.
Параметр . Для функций без седловых точек рекомендуется , . Для «обхода» седловых точек рекомендуется , .
Описанный алгоритм позволяет приблизительно найти коллинеарные градиенты из системы уравнений (3). Полученное направление для алгоритма МКГ (1) будет (truncated Newton method).
ДемонстрацииTolstykh V.K. Демонстрационное Windows-приложение, версия 8.3, 10 апреля 2026 Optimization (для разархивирования удалите тип .txt) Во всех демонстрациях МКГ показывает сходимость не хуже, а иногда и лучше (для функций переменной выпуклости), чем метод Ньютона.
Тестовая функция «повёрнутый эллипсоид»
Строго выпуклая квадратичная функция:
На рисунке для заданы три чёрные стартовые точки . Серые точки — подитерации с (показано пунктиром, завышено для демонстрации). Параметры , . Для всех потребовалась одна итерация и подитераций не более двух.
При (параметр ) с начальной точкой МКГ достиг с точностью 1% за 3 итерации и 650 вычисления и . Другие методы первого порядка: Квазиньютоновский BFGS (работа с матрицами) потребовал 66 итераций и 788 вычислений; сопряжённых градиентов (Fletcher-Reeves) — 274 итерации и 2236 вычислений; конечно-разностный метод Ньютона — 1 итерация и 1001 вычислений. Метод Ньютона второго порядка — 1 итерация.
С ростом размерности , вычислительные погрешности при реализации условия коллинеарности (3), могут заметно возрастать. Поэтому МКГ, по сравнению с методом Ньютона, в рассматриваемом примере потребовал более одной итерации.
Тестовая функция Розенброка
Параметры , , . Траектория спуска МКГ полностью совпадает с методом Ньютона. На рисунке синяя начальная точка , красная — . В каждой точке нарисованы орты градиентов.
Тестовая функция Химмельблау
Параметры , , .
по количеству вычислений и . Благодаря формуле (2), он не требует затратных вычислений шагового множителя посредством линейного поиска (например, методом золотого сечения и т.п.).
Примечания
Категория:Алгоритмы и методы оптимизации Категория:Алгоритмы оптимизации