Программный продукт, реализующий алгоритм метода "Наискорейшего спуска" с тестированием на функции Розенброка в среде DELPHI. Разработка интерфейса пользователя и модуля графического отображения поиска решения. Апробация алгоритма на тестовых примерах.
Аннотация к работе
Целью работы является создание программы, находящей экстремум функции с помощью метода наискорейшего спуска. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Алгоритм наискорейшего спуска реализует итерационную процедуру движения к минимуму из произвольно выбранной точки начального приближения в направлении наиболее сильного уменьшения функции, определенном в окрестности текущего значения аргумента минимизируемой функции. Такое направление противоположно направлению, задаваемому вектором градиента минимизируемой функции F(x1, . .В общем случае критерий выбора представляет собой компромисс между точностью приближения к точке экстремума, затратами ресурсов ЭВМ для этой цели и простотой требуемых аналитических выкладок (от которой зависят затраты времени разработчика на отладку). С целью сравнения эффективности различных алгоритмов разработаны специальные (т.наз. тестовые) функции, имеющие "неприятные" для методов поиска экстремума особенности.Общий алгоритм работы программы представлен в виде блок-схемы на рисунке 3.До начала работы программы нужно выбрать, каким методом будет находиться экстремум, далее ввести начальные значения: начальный шаг, необходимую точность и начальное приближение X01 и X02 (рисунок 3). Для вывода расчетных данных следует нажать кнопку «Показать расчет».При выполнении индивидуального задания была разработана программа нахождения экстремума параболоида и функции Розенброка.begin alpha:=(25*pi)/180; if f(x01,x02)<f(x1,x2) then begin chp1:=chp1-tmp1; chp2:=chp2-tmp2; d:=-d; x1:=x01 d*chp1; x2:=x02 d*chp2; end else begin x01:=x1; x02:=x2; x1:=x01 d*chp1; x2:=x02 d*chp2; end; if x1<x01 then begin a1:=x1; b1:=x01; end else begin a1:=x01; b1:=x1; end; if x2<x02 then begin a2:=x2; b2:=x02; end else begin a2:=x02; b2:=x2; end; begin if form2.Visible=false then begin form2.Visible:=true; button2.Caption:="Убрать рассчет"; end else begin form2.Visible:=false; button2.
План
Содержание
Введение
1. Математическая часть задачи
2. Тестовый расчет
2.1 Назначение тестовой функции и ее форма
3. Алгоритм работы программы
4. Руководство пользователя
Заключение
Список использованных источников
Приложение А
Введение
Целью работы является создание программы, находящей экстремум функции с помощью метода наискорейшего спуска.
Градиентный спуск - метод нахождения локального минимума (максимума) функции с помощью движения вдоль градиента. Для минимизации функции в направлении градиента используются методы одномерной оптимизации, например, метод золотого сечения. Также можно искать не наилучшую точку в направлении градиента, а какую-либо лучше текущей.
Сходимость метода градиентного спуска зависит от отношения максимального и минимального собственных чисел матрицы Гессе в окрестности минимума (максимума). Чем больше это отношение, тем хуже сходимость метода.
Методом наискорейшего спуска может быть найден минимум функции n переменных F(x1, . . . ,xn) или найдены решения системы уравнений вида: Fi(x1,x2, . . .,xn)=0, i=1, . . ,n.
Алгоритм наискорейшего спуска реализует итерационную процедуру движения к минимуму из произвольно выбранной точки начального приближения в направлении наиболее сильного уменьшения функции, определенном в окрестности текущего значения аргумента минимизируемой функции. Такое направление противоположно направлению, задаваемому вектором градиента минимизируемой функции F(x1, . . . ,xn)
1. Математическое описание
Основной целью программы является вычисление экстремума функции.
В методе наискорейшего спуска в качестве направления поиска минимума заданной функции выбирается вектор, направление которого противоположно направлению вектора градиента функции F(X), где X={x1, x2, x3, … xn}. Координаты этого вектора :
В математическом анализе доказывается, что вектор GRADF(X) характеризует направление наиболее быстрого возрастания функции. Поэтому вектор - GRADF(X) (антиградиента) является направлением наиболее быстрого ее убывания. Каждое последующее приближение получается из предыдущего смещением в направлении антиградиента функции F(X) (смотри рис.1).
Рис. 1
Задавшись начальным приближением X0, ищется следующее приближение с помощью реккурентного соотношения вида: , i=0,1,2…
Приведенное соотношение не определяет алгоритм однозначно, поскольку ничего не сказано о выборе параметра li. Например, его можно определять из условия минимума величины:
Рассматриваемая функция является функцией одного параметра l и ее минимум находится или методами одномерной минимизации или решением уравнения, которое имеет вид: , минимальный неотрицательный корень этого уравнения и является искомым значением l i.
Поиск прекращается при выполнении условия
, так как градиент в точке минимума функции = 0, а при приближенных вычислениях .
Вывод
При выполнении индивидуального задания была разработана программа нахождения экстремума параболоида и функции Розенброка.
Программа обеспечивает нахождение экстремума с помощью метода наискорейшего спуска и градиентного метода. В программе учитывается отображение самой функции Розенброка, промежуточных данных и найденного экстремума, а также справка.
Список литературы
Б. Банди, «Методы оптимизации» стр. 51 - 56.
В.В. Салмин, «Методы оптимального управления».
СТО СГАУ 02068410-004-2007. Общие требования к учебным текстовым документам. Самара 2007