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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 2.3

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

Номер тестового примера	Название засечки	Начальные координаты		в/а
		Х (м)	Y (м)
1	Линейно-угловая	33005,75	106188,63	0,65
2	Линейная	77459,29	93000,00	0,70
3	Обратная	20000,00	57000,00	0,14
4	Прямая	40000,00	108000,00	0,70
5	Гиперболическая	33000,00	108000,00	0,56
6	Линейно-угловая	20000,00	80000,00	0,28
7	Комбинированная	33005,75	106188,63	0,60

Таблица 2.4

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

Номер тестового примера	Номер метода нелинейного программирования
	I		II			III			IV			V			VI
	j	T		j	T		j	T		j	T		j	T		j	T
1	17	2		12	6		27	2		4	1		21	3		4	0-1
2	20	1		9	2		34	1		8	2		25	2		5	0-1
3	¾	¾		5	4		59	4		¾	¾		92	11		5	1
4	20	2		10	5		41	3		¾	¾		28	4		4	0-1
5	20	2		11	3		25	1		¾	¾		20	2		4	0-1
6	¾	¾		10	6		86	6		¾	¾		62	9		¾	¾
7	19	1		10	7		23	3		4	2		36	5		4	0-1

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