38. Сравнение методов безусловной оптимизации

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

1. Методы нулевого порядка. Это метод циклического покоординатного спуска и метод сопряженных направлений Пауэлла, основанные на вычислении значений самой целевой функции и не использующие значений ее производных.

2. Методы первого порядка. Это метод наискорейшего спуска, методы сопряженных градиентов Флетчера – Ривса и Полака – Рибьера, квазиньютоновские методы Бройдена, ДФП и БФГШ, использующие значения первых производных целевой функции.

3. Методы второго порядка. Это метод Ньютона, метод Ньютона с одномерным поиском, метод Ньютона с направлением спуска и метод Марквардта, использующие значения первых и вторых производных целевой функции.

Эти методы многомерного поиска можно сравнить по скорости сходимости. Методы многомерного поиска должны порождать последовательность точек , для которой

.

Тогда по свойству предела

,

Поэтому выполняется неравенство

,

В этом случае говорят о Глобальной сходимости метода. Например, если непрерывно дифференцируемая функция удовлетворяет условию при , то для любой начальной точки метод наискорейшего спуска сходится к стационарной точке функции . Глобальная сходимость методов сопряженных градиентов Флетчера – Ривса и Полака – Рибьера обеспечена лишь в случае процесса с периодической сменой начала, то есть с рестартами. Тогда их глобальная сходимость следует из глобальной сходимости метода наискорейшего спуска. Метод Ньютона не обладает свойством глобальной сходимости: если начальная точка слишком далека от , то метод не сходится. Но методы Ньютона с одномерным поиском и с направлением спуска, а также метод Марквардта обладают глобальной сходимостью. Метод Бройдена не имеет глобальной сходимости. Квазиньютоновские методы Девидона – Флетчера – Пауэлла и Бройдена – Флетчера – Гольдфарба – Шанно обладают глобальной сходимостью только в случае применений рестартов.

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

Поведение последовательности точек в окрестности оптимальной точки позволяет установить характер Асимптотической сходимости. Если выполняется неравенство

И , то говорят, что имеет место Линейная сходимость и что – соответствующий Коэффициент сходимости.

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

,

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

Если выполняется равенство

,

То говорят, что имеет место Сверхлинейная сходимость. При этом, если существует такое , что

,

То говорят, что имеет место Сходимость порядка . В частности, если

,

То говорят, что имеет место Квадратичная сходимость.

Методы сопряженных градиентов Флетчера – Ривса и Полака – Рибьера имеют сверхлинейную скорость сходимости по шагам. Если матрица Гессе удовлетворяет условию Липшица, то для этих методов доказана квадратичная скорость сходимости по шагам.

Для квазиньютоновских методов ДФП и БФГШ доказана сверхлинейная скорость сходимости. Если матрица Гессе удовлетворяет условию Липшица, то для этих методов доказана квадратичная скорость сходимости. Это показывает преимущество квазиньютоновских методов перед методами сопряженных градиентов, которые требуют приблизительно в раз больше итераций для одного и того же асимптотического поведения. Однако это преимущество сильно снижается загрузкой памяти пропорционально и объемом промежуточных матричных вычислений пропорционально .

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

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

Пример 4.9. В табл. 4.1–4.4 приведены число итераций и число вычислений функции при минимизации функции Розенброка с допустимой погрешностью разными методами многомерной оптимизации: Ньютона с одномерным поиском (НОП), Ньютона с направлением спуска (ННС), Марквардта с одномерным поиском (МОП), Пауэлла (П), Полака – Рибьера (ПР), Бройдена (Б), ДФП и БФГШ. При этом для одномерного поиска использованы метод квадратичной интерполяции с тремя точками (И2) и метод кубической интерполяции с четырьмя точками (И3), а также различные значения допустимой погрешности одномерного поиска . Очевидно, что эффективность многомерного метода существенно зависит от применяемого метода одномерного поиска и значения его допустимой погрешности. Для минимизации функции Розенброка самыми надежными и эффективными оказались методы Ньютона с одномерным поиском и БФГШ.

Таблица 4.1 – Число итераций с методом И2

	НОП	ННС	МОП	П	ПР	Б	ДФП	БФГШ
10–5	12	12	15	12	17	17	17	17
10–4	12	13	15	12	–	17	19	17
10–3	12	15	16	12	–	20	–	20

Таблица 4.2 – Число вычислений функции с методом И2

	НОП	ННС	МОП	П	ПР	Б	ДФП	БФГШ
10–5	260	307	398	529	266	269	265	265
10–4	216	252	288	423	–	221	237	219
10–3	163	200	228	304	–	193	–	199

Таблица 4.3 – Число итераций с методом И3

	НОП	ННС	МОП	П	ПР	Б	ДФП	БФГШ
10–5	12	12	15	12	17	17	17	17
10–4	12	12	15	12	17	17	17	17
10–3	12	11	15	–	20	20	–	20

Таблица 4.4 – Число вычислений функции с методом И3

	НОП	ННС	МОП	П	ПР	Б	ДФП	БФГШ
10–5	148	148	186	242	150	151	148	148
10–4	140	138	178	230	138	140	137	136
10–3	131	119	164	–	139	147	–	141

< Предыдущая		Следующая >