Метод сопряженных градиентов

В рассмотренных методах на каждой итерации никак не использовалась информация, полученная на предыдущих итерациях. Очевидно, используя эту информацию, т.е. учитывая «предысторию» процесса поиска, можно рассчитывать на ускорение его сходимости. Методы поиска, в которых новое приближение формируется на основе нескольких предыдущих, называются многошаговыми. Одним из многошаговых методов является двухшаговый метод сопряженных градиентов. Идея метода заключается в построении нового приближения x^k+1 по следующей схеме:

где параметры h^k и b ^k подбираются на каждой итерации оптимальным образом, т.е. из условия

В общем случае найти решение данной задачи в явном виде не удается. Однако для случая квадратичной функции методу можно придать следующий вид […]

	(5.8)
	(5.9)

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

Несмотря на то, что последний алгоритм записан для квадратичной функции f( x), метод успешно может применяться и для неквадратичных функций. Правда, теперь метод уже не будет конечным. При этом оказывается целесообразным через каждые п шагов производить обновление метода, т.е. полагать b^k = 0 при k = 0, п, 2 n, ... Метод сопряженных градиентов, являясь по форме методом первого порядка и поэтому простым в реализации, выгодно отличается от обычных градиентных методов тем, что он обладает, по существу, всеми достоинствами метода второго порядка (в том числе квадратичной сходимостью).

Существуют и другие схемы реализации метода сопряженных градиентов […].

 

Упражнение 1. Получить выражения (5.8), (5.9) для определения параметров b ^k-1, h^k.

Упражнение 2. Решить задачу минимизации функции  методом сопряженных градиентов, приняв в качестве начальной точку x⁰ c координатами . Построить траекторию поиска.

Квазиньютоновские методы

Рассмотрим теперь группу методов, называемых квазиньютоновскими, сущность которых состоит в воспроизведении квадратичной аппроксимации функции f( x) по значениям ее градиентов в ряде точек. Тем самым эти методы объединяют достоинства градиентных методов (т.е. не требуется вычисление вторых производных) и методов Ньютона (быстрая сходимость вследствие использования квадратичной аппроксимации). Структура методов этой группы такова:

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

а матрица H^k формируется и пересчитывается на основе k-й итерации так, чтобы в пределе она переходила в матрицу, обратную гессиану . Тем самым в пределе методы этой группы переходят в ньютоновские методы.

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

После введения обозначения

нетрудно установить, что в этом случае имеет место равенство

,
или .

Учитывая последнее равенство, потребуем, чтобы оно выполнялось и для нового приближения H ^k+1, т.е.

Последнее условие принято называть квазиньютоновским. Кроме того, потребуем, чтобы Hⁿ = A^-1. Оказывается можно предложить различные алгоритмы пересчета матриц H^k, удовлетворяющих сформулированным условиям. Приведем лишь некоторые из них […]

а) алгоритм Давидона — Флетчера — Пауэлла

б) алгоритм Бройдена

 в) алгоритм Бройдена — Флетчера — Шенно

Можно показать, что все представленные алгоритмы для квадратичных функций f( x) совпадают. Для неквадратичных функций эффективность этих алгоритмов зависит от их вида.

 

Методы одномерного поиска

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

Ограничимся рассмотрением так называемых унимодальных функций, т.е. функций, имеющих на исследуемом интервале [а, b]единственный локальный минимум. Унимодальные функции не обязательно должны быть гладкими или непрерывными (см. рис. 5.5). Выпуклые функции являются частным случаем унимодальных.

Рис.	5.5	Примеры унимодальных функций

 

Величину интервала [a, b ], называемого также начальным интервалом неопределенности, обозначим через L₀. Будем по-прежнему для минимизируемой функции использовать обозначение f( x), считая, однако, теперь, что х — скаляр. В частном случае под х понимается шаг поиска h, который должен быть выбран в рассмотренных выше алгоритмах.

Обычный перебор

Простейшим методом одномерного поиска является обычный перебор значений f( x_j) минимизируемой функции f( x) в конечном числе точек  переменной х, равномерно распределенных на интервале [а, b], с последующим выбором наименьшего значения  Значение  в силу свойства унимодальности может быть приближенно принято за искомое оптимальное значение. Очевидно, точность такого процесса определяется количеством экспериментов, связанных с измерением вычислением функции f( x), и характеризуется интервалом неопределенности после проведения всех экспериментов, равным  (поправил ф-лу) Таким образом, эффективность процесса поиска можно оценить отношением

(поправил ф-лу)

Совершенно очевидно, что равномерное распределение всех экспериментов на интервале поиска [а, b] не является наилучшим.

Метод дихотомии

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

Если перед проведением первой пары экспериментов величина интервала неопределённости, на которой находится искомый минимум, равна L₀, то интервал неопределённости L₂ после проведения двух экспериментов практически будет равен .

Если требуется провести ещё пару экспериментов, то наилучшее распределение их будет являться также симметричным, но теперь уже внутри интервала, величина которого равняется L₂. Следовательно, после проведения  четырёх экспериментов величина интервала неопределённости будет равна . Общая схема алгоритма метода дихотомии представлена на рис.5.6.

 

 

Рис.	5.6	Схема реализации метода дихотомии

 

 

Нетрудно сообразить, что при использовании метода дихотомии интервал неопределенности после проведения n/2 пар экспериментов практически будет равен . Следовательно, эффективность метода характеризуется величиной

. (поправил ф-лу)

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

Метод Фибоначчи

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

Рис.	5.7	Схема реализации метода Фибоначчи

 

Схема алгоритма метода представлена на рис. 5.7. Из симметричности расположения любых двух соседних экспериментов следует равенство (ПРОПУЩЕНО? )

Для последних двух экспериментов согласно методу дихотомии имеем

.
или                                 . Поэтому получаем
и т.д.

Введем в рассмотрение последовательность чисел Фибоначчи

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

При k = n-1 получаем

Так как проведение первого эксперимента не изменяет интервала неопределенности, т.е. то получаем оценку эффективности метода

(поправил ф-лу)

Эффективность метода оказывается наибольшей среди рассмотренных ранее. Например, при n= 12 она превышает эффективность метода дихотомии более, чем в 3, 5 раза. С ростом n преимущество метода еще более возрастает.

Недостаток метода Фибоначчи состоит в том, что количество экспериментов n должно быть задано заранее. Если же поиск методом Фибоначчи начат, то на любом шаге действия определяются просто — каждый последующий эксперимент располагается симметрично относительно предыдущего эксперимента, попавшего в этот же интервал неопределенности. Для проведения определения места приложения первых двух экспериментов необходимо предварительно найти величину L₂ . Сами эксперименты должны быть в соответствии со свойством симметрии проведены на расстояниях L₂, от левого и правого концов.

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

Метод золотого сечения

Метод золотого сечения, как и метод Фибоначчи, основан на симметрии экспериметов относительно текущего интервала неопределенности. Дополнительно он предполагает еще и постоянство отношений длин последовательных интервалов неопределенности L_j/ L_j+1 = c для всех j.

Рис.	5.8	Схема реализации метода золотого сечения

 

Последнее соотношение и обусловило название метода. «Золотым сечением» принято называть деление отрезка на две части так, чтобы отношение всего отрезка к большей части равнялось отношению большей части к меньшей

,

Разделим первое соотношение на L_j, получим

откуда находим единственное положительное решение для параметра  Поиск минимума по методу золотого сечения (рис. 5.8) производится так же, как и по методу Фибоначчи. Отличие заключается лишь в проведении двух первых экспериментов. В данном случае они располагаются симметрично на интервале [а, b] и на расстоянии L₀/с от его концов. После проведения n экспериментов интервал неопределенности будет равным

L n = L0 /c n -1.

Эффективность метода характеризуется величиной

L0 / L n = c n -1.

Сравнивая величины F n  и c ^n-1, можно установить, что при больших n эффективность метода золотого сечения приближается к эффективности метода Фибоначчи. Это обстоятельство и обусловило широкое распространение метода золотого сечения.

 

Упражнение. Сравнить эффективность методов одномерного поиска, построив зависимости ln( L₀/ L_n) от числа n для каждого из рассмотренных методов.

 

Методы нулевого порядка

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

В настоящее время предложено много различных прямых методов поиска. Характерным для этих методов является их эвристичность. В связи с этим сходимость и эффективность методов может быть подтверждена лишь экспериментально на примерах решения конкретных задач.

⇐ Предыдущая1234567Следующая ⇒

Поделиться: