48263 (Программная модель поиска глобального минимума нелинейных "овражных" функций двух переменных), страница 2

Первая часть утверждения гарантирует сходимость лишь в смысле lim || f(xk) || = 0, т.е. сходимость по функции либо к точной нижней грани inf f(x), либо к значению функции f в некоторой стационарной точке х. При этом сама точка х не обязательно является точкой локального минимума; она может быть точкой седлового типа. Однако на практике подобная ситуация маловероятна и применение градиентных методов, как правило, позволяет получить приближенное значение минимума целевой функции (вообще говоря, локального).

Сравнивая рисунки 5 и 6, можно сделать вывод, что для целевой функции, линии уровня которой близки к окружностям, требуемая точность будет достигнута довольно быстро, тогда как если линии сильно вытянуты в окресности оптимальной точки, то градиентные методы приведут к медленному зигзагообразному продвижению в направлении на оптимальную точку. О функции, поверхность уровня которой сильно вытянуты , говорят, что она имеет «овражный» характер (в случаях двух переменных график такой функции действительно напоминает овраг).

х0

х1

х2

хmin

90

90

xmin

x0

Рисунок 5 Линии уровня (близкие к окружности)

Рисунок 6 Линии уровня (вытянутые)

О степени «овражности» функции f можно получить представление, зная минимальное (m) и максимальное (M) собственные числа матрицы Гессе ²f, вычисленной в оптимальной точке: чем меньше отношение m/M, тем больше “овражность” данной функции. Применение градиентных методов к таким функциям приводит к спуску на «дно оврага», после чего, поскольку направление спуска почти перпендикулярно «линии дна», точки последовательности {xk} будут поочередно находится то на одном «склоне оврага», то на другом и продвижение к оптимальной точке сильно замедляется.

1.2.3 Метод наискорейшего спуска

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

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

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

2. Инструментальные программные средства

Перед началом работы над курсовым проектом передо мной встал вопрос: в какой системе программирования или с помощью какого приложения я буду писать программу по данной мне теме. Мой выбор остановился на приложении Microsoft Excel. В настоящее время данный программный продукт можно найти практически на любом персональном компьютере, на котором установлена операционная система Windows 9x, 2000, NT 4.0, XP. Microsoft Excel обладает требуемым для расчетов модели математическим аппаратом. Кроме того, в данный программный продукт встроен редактор Visual Basic, с помощью которого можно писать макросы.

Среда редактора Visual Basic.

Visual Basic предоставляет единую законченную среду редактирования, схожую со средой автономной версии Visual Basic 5.0. Каждая книга Microsoft Excel имеет связанный с ней проект. Среда редактирования Visual Basic включает улучшенный редактор кода, иерархическое средство просмотра объектов, многооконный отладчик, окно отображения свойств и средство просмотра проектов для управления кодом и объектами проекта. Для облегчения создания синтаксически правильного кода среда редактирования Visual Basic имеет группу команд в меню Правка, включающую команды Список свойств/методов, Список констант и Параметры.

Использование объектов ActiveX в формах.

Visual Basic обеспечивает согласованные и расширяемые элементы управления и интерфейс диалоговых окон для всех программ Microsoft Office. Элементы ActiveX (ранее называвшиеся элементами управления OLE) могут быть внедрены непосредственно на листы, что позволяет пользователю создавать свои собственные формы.

События

Богатейшие возможности обработки событий предоставляют гибкие средства определения реакции на действия пользователя.

3. Блок-схема алгоритма моделирования

начало

Ввод

исходных данных

Вывод начальных

данных в таблицу

Присвоение переменным

h1 и h2 значения шага

Сохранение предыдущего значения функции

Вычисление новых начальных точек

Сравнение

нового значения функции с предыдущим

Да

Вычисление градиента поля функции и модуля градиента

Вывод значений точек, градиента, модуля градиента, функции

Сравнение

значения модуля градиента

и погрешности

Да

конец

Вывод в таблицу новых начальных точек и значение функции

Ввод данных осуществляется с помощью диалогового окно «Ввод данных» (см. рис. 7).

Рисунок 7 Вид формы для ввода данных

Вывод промежуточных и выходных данных осуществляется в таблицу (см. табл. 1)

Таблица 1

Результаты решения

X1	X2	dR/dX1	dR/dX2	|grad|	R(x)

4. Операционная среда

Минимальные требования предъявляемы к аппаратной части:

Процессор – 486 DX/2 80Mz

ОЗУ – 12Мб

Видеоадаптер – VGA 640-480

Монитор

Клавиатура

Мышь

В качестве операционной среды на персональном компьютере должна быть установлена одна из версий Windows (9x, 2000, NT 4.0, XP, Me), а также программный пакет Microsoft Office (97, 2000) или, хотя бы, Microsoft Excel.

Для того, чтобы начать работу с моделью нужно скопировать файл «Метод наискорейшего спуска» в папку «Мои документы» и с помощью программного приложения Microsoft Excel открыть файл.

5. Контрольная задача

Задача. Найти минимум функции

R(x)=a*x1^3+b*x2^2-c*x1-d*x2, где a = 1, b = 2, c = 3, d = 4.

Начальные точки: х1 = -0,5; х2 = -1. Пробный шаг g = 0,01. Коэффициент пробного шага h = 0,1. Погрешность е = 0,01.

Решение. В начальных точках х1=-0,5, х2=-1 вычислим по методу градиента значение функции, градиент поля функции, значение переменных в шаге и величину шага. Полученные данные занесем в таблицу и поставим номер шага. Затем по формуле xi+1 = xi – h*(dR/dxi) найдем новые значения переменных х1 и х2 и вычислим значение функции. Последние операции будем повторять до тех пор, пока значение функции не начнет возрастать. Когда это случится, предыдущее значение функции будем считать локальным минимумом. Вычислим значения градиента поля, модуль градиента, занесем результаты в таблицу и укажем следующий номер шага.

Все вычисления закончим, когда значение модуля градиента будет меньше или равно значению погрешности. Результаты решения приведены в таблице 2.

Таблица 2

Результаты решения контрольной задачи

Х1	X2	dR/dx1	DR/dx1	|R|	R(X)	№Шага
-0,5	-1	-2,2499	-8	8,310358	7,375	1
-0,27501	-0,2				1,684231
-0,05002	0,6				-1,53007
0,17497	1,4				-2,19955
0,17497	1,4	-2,90806	1,6	3,319155	-2,19955	2
0,465776	1,24				-3,18108
0,756581	1,08				-3,82387
1,047387	0,92				-3,98036
1,047387	0,92	0,291158	-0,32	0,432635	-3,98036	3
1,018271	0,952				-3,99438
0,989155	0,984				-3,99914
0,989155	0,984	-0,06462	-0,064	0,090946	-3,99914	4
0,995617	0,9904				-3,99976
1,002078	0,9968				-3,99997
1,002078	0,9968	0,012583	-0,0128	0,017949	-3,99997	5
1,00082	0,99808				-3,99999
0,999562	0,99936				-4
0,999562	0,99936	-0,00253	-0,00256	0,003599	-4	6

Проанализировав результаты в таблице 2, мы видим, что если не учитывать промежуточные значения, минимум функции R(x) найден на 6-ом шаге. Если сравнить результаты, полученные при поиске минимума методом градиента и методом наискорейшего спуска, мы заметим, что метод наискорейшего спуска оправдывает свое название, т.к. минимум функции найден на 6-ом шаге, а метод градиента найдет этом минимум только на 15-ом. Отсюда вывод, метод наискорейшего спуска также эффективен, но работает гораздо быстрее.

Заключение