Сравнение методов нелинейного программирования

В настоящее время известно большое количество численных методов решения нелинейных экстремальных задач. Большое разно­образие методов объясняется тем, что попытка найти наилучший метод, который позволил бы решать широкий круг задач, встречаю­щихся на практике, сталкивается со значительными трудностями.

Согласно литературным источникам [3, 37, 39, 86, 103], ме­тоды нелинейного программирования разграничивают на три основные группы: прямого поиска; методы, использующие первые частные производные целевой функции; а также методы, требующие знания вторых производных. При разработке методов даются эксперимен­тальные либо теоретические характеристики эффективности приме­нения (например, скорости сходимости). Теоретические оценки по­лучены не для всех методов. Если они известны, то, как правило, их определяют на основе жестких требований к целевой функции, которые нелегко проверить на практике. Поэтому наиболее часто выполняют экспериментальную оценку алгоритмов на основе сравнитель­ного анализа различных методов, используя реально существующие (не теоретические) объекты исследования (тестовые задачи).

Важную роль при экспериментальном сравнении алгоритмов играет выбор критериев сравнения. Обычно таковыми служат: точ­ность решения, определяющаяся локализацией достаточно малой окрестности экстремума, т.е. близость вектора переменных к ис­тинным экстремальным значениям; количество вычисленных значе­ний целевой функции и время счета на ЭВМ [103]. При сравнении методов необходимо также учитывать широту области применения алгоритма, простоту его реализации и надежность работы в труд­ных ситуациях. Результаты экспериментального сравнения зависят от того, как запрограммированы алгоритмы для ЭВМ и какие тесто­вые примеры выбраны для сравнения.

Для выполнения сравнительного анализа применим следующие известные методы нелинейного программирования: наискорейшего спуска; Хука - Дживса; Нелдера-Мида; Пауэлла; релаксации и ме­тод Ньютона.

С целью общности экспериментальных исследований предусмот­рим минимизацию только целевой функции (2.10).

Для сравнения методов выберем семь тестовых примеров, ин­формация о которых помещена в приложении I. В табл. 2.3 указа­ны виды засечек, начальные координаты откуда начинались итера­ции и в последней колонке таблицы дано отношение малой к боль­шой полуоси эллипса ошибок. Чем меньше это отношение, тем труднее выполняется поиск минимума. Для вычисления весов измерений принято s_b = 1.0²; s_S = 0,02 м; для разности и суммы расстояний s_DS = s_SS = 0,10 м.

Все вычисления выполнялись по специально составленным программам для ЭВМ ЕС-1022 на алгоритмическом языке Фортран-4. Результаты вычислений (j - количество итераций и Т - время счета) представлены в табл. 2.4. Проведён сравнительный ана­лиз методов нелинейного программирования, давая последователь­ную характеристику каждому из них.

Метод наискорейшего спуска (I) быстро сходится к минимуму, но для тестовых примеров 3 и 6 не найдено решение из-за малой области сходимости.

Метод Хука-Дживса (II) имеет большую область сходимости, легко программируется, но затрачивает много машинного времени.

Метод Нелдера-Мида (III) имеет наилучшие характеристики из всех примененных методов.

Метод Пауэлла (IV) быстро сходится к минимуму для всех вы­пуклых функций, но обладает самой маленькой областью сходимости. Вот почему им не решены тестовые примеры 3 - 6.

Метод релаксации (V) прост в программировании и надежен в работе. Особенно характерно для него то, что им может быть локализована сколь угодно малая область минимума.

Метод Ньютона-Гаусса (VI) быстрее всех методов приводит к решению, но не для всех примеров характеризуется большой об­ластью сходимости, что в дальнейшем будет в 2.2.3 предметом специального изучения.

Таблица 2.3

Дополнительные сведения о тестовых примерах

Таблица 2.4

Результаты минимизации целевой функции

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