Cтраница 2
Если эти х удовлетворяют ограничениям ( 34), то пара ( х т () является допустимым решением исходной задачи. Для минимизации h был использован метод Флетчера и Пауэлла. [16]
Сравнение рассматриваемых методов [50] показывает, что при движении вдоль дна узкого извилистого оврага метод Флетчера - Пауэлла имеет преимущество. На первых этапах поиска, при спуске в овраг, оба метода равноценны ( первое направление совпадает с антиградиентом); они равноценны также при поиске в окрестности экстремума, так как оба метода - квадратична сходящиеся и полностью совпадают для квадратичной функции. При практическом использовании необходимо, однако, учитывать, что метод Флетчера - Пауэлла гораздо сложнее, требует большего объема памяти и, хотя; число итераций получается меньше, общее время решения конкретной задачи может оказаться примерно одинаковым для обоих методов. [17]
Если схема корректировки в (5.2.19) излишне сложна, то способ выбора направления спуска слишком прост. Значительно более совершенные алгоритмы получаются с использованием приведенных градиентов в комбинации с квазиньютоновскими методами и методами сопряженных направлений. Два из них, рассчитанные на задачи с линейными ограничениями, представлены в предыдущей главе. Оба опираются на метод Флетчера - Ривза. Аналогичный алгоритм, но для задач с нелинейными ограничениями подробно описан в цитированной выше работе Абади и Кар-пентье. [18]
Индекс k указывает на последовательность вычислений в процессе итераций. Новые направления называются сопряженными и соответствуют текущей локальной квадратичной аппроксимации функции. Затем по новому направлению проводят одномерный поиск и, найдя минимум, проверяют, достигнута ли требуемая степень сходимости. Если проверка показывает, что это так, то счет прекращается. В противном случае определяют новые сопряженные направления, k увеличивают на единицу и продолжают процесс до тех пор, пока не будет обеспечена сходимость или пока поиск не будет проведен по всем Ы направлениям. Закончив цикл поиска по N - - направлениям, начинают новый цикл, в котором опять используется направление наискорейшего спуска. Достоинство этого алгоритма состоит в том, что он позволяет использовать преимущества градиентных методов, проявляющиеся при исследовании целевой функции с разрывными производными. Так как N - - направлений поиска второй совокупности отличаются от направлений единичных векторов градиента, то поиск не зависает на изломе, а идет вдоль линии, соединяющей точки изломов линии уровня, которая, как правило, проходит через точку оптимума. Вообще можно утверждать, что методы, основанные на определении новых направлений поиска на основе накопленных данных о локальном поведении функции, по самой своей природе более эффективны, чем методы, в которых направление поиска задается заранее. Именно поэтому метод Флетчера - Ривса обладает большими преимуществами по сравнению с методами наискорейшего спуска или подъема. Его недостаток состоит в том, что, будучи сложнее указанных методов, он требует разработки более сложных программ. [19]