Градиентный метод оптимизации с равномерным поиском

Содержание

Введение

Глава I. Теоретическая часть

. Постановка задачи оптимизации

.1 Необходимые и достаточные условия экстремума

.2 Характеристика класса задачи и ее место в общей классификации оптимизационных задач

.3 Описание метода решения и расчетного алгоритма

Глава II. Практическая часть

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

.1 Разработка блок-схемы машинного алгоритма и программы

.2 Проверка необходимых и достаточных условий экстремума для найденной точки минимума

.3 Разработки программы проверки ограничений

Заключение

Список литературных источников

Введение

Область применения оптимизационных задач чрезвычайно широка, любая деятельность связана с решением задач оптимизации.

К примеру, это такие сферы как: распределение ресурсов в экономике, управленческие решения в социальной сфере, проектирование технических устройств и систем и это лишь некоторые сферы.

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

Задачи к выполнению курсовой работы:

1.   Проверить необходимые условия существования экстремума многомерной функции для своего варианта функции.

Воспользоваться средствами Mathcad, составив программу.

.     Проверить достаточные условия существования экстремума многомерной функции для своего варианта функции.

Воспользоваться средствами Mathcad, составив программу.

. Разработать машинный алгоритм и программу в Mathcad многомерной оптимизации.

.     Определить по составленной программе в Mathcad экстремум функции.

.     Проверить ограничения используя программу в Mathcad.

Исходные данные: Целевая функция

Z(x, y) = F(x) + H(y)

Где

Критерий оптимизации: точка экстремума (локальный экстремум)

Метод оптимизации: градиентный метод с использованием метода равномерного поиска.

Компьютерные средства: Вычислительная среда Mathcad.

Глава I. Теоретическая часть

1.      Постановка задачи оптимизации

Оптимизация - выбор предпочтительного варианта проекта по принятым критериям.

В основе оптимизации лежит функция цели Z(x,y), которая строиться на основе суммы двух других целевых функций

 и

 , и характеризует качество объекта.

1.1.   Необходимые и достаточные условия экстремума

Необходимым условием экстремума функции в точке Хо является равенство нулю всех первых производных или равенство нулю градиента функции.

Достаточным условием минимума функции является положительная определенность G[F(X)] |x=xo условием максимума является отрицательная определенность G[F(X)] |x=xo ;

Матрица G[F(X)] положительно определенная, если все миноры главной диагонали от 1 до n положительны, тогда F(Xm)=minF(X). Если все миноры главной диагонали отрицательны, то F(Xm)=max F(X).

1.2.   Характеристика класса задачи и ее место в общей классификации оптимизационных задач

Задача, представленная в курсовой работе, имеет два критерия оптимизации x и y, следовательно, она многокритериальная. Так же она является параметрической, так как область определения целевой функции Z(x,y) непрерывное множество точек. Будем считать, что функция унимодальна и имеет параметрические ограничения.

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

Градиентный метод, в соответствии с нашей задачей, можно классифицировать как: многомерный, численный, поисковый, при ограничениях.

1.3.   Описание метода решения и расчетного алгоритма

Метод градиента основан на том, что вектор градиента в каждой точке Х Î ХN совпадает с направлением наискорейшего возрастания функции.

Требуется найти: minF(X), если XÎ XN, x=x(x1, x2 ,.., xn), N=1,..,.n.

Алгоритм метода.

. Выбор стартовой точки Хо.

. Вычислить F(X) и gradF(X)

. Из точки х11 и из любой точки хi,k в антиградиентном направлении с шагом hi в xi,k+1 и т.д. по формуле:

где « - » из-за антиградиентного направления.

. Вычисление F(X) на каждом шаге, если Fk+1 < Fk, то

Графическая интерпретация метода градиента для двумерного случая приведена на рисунке 1. Целевая функция отображена линиями уровней: F(x)=const=a, а траектория движения к точке оптимума - {х0, х1, х2, х3 , х4, х5}

Рисунок 1 - Траектория движения к точке оптимума по методу градиента

Вычисление градиента в точке x0 начинается с серии пробных шагов. Сначала величине x1 дается небольшое приращение ∆ x1> 0, причем в это время x2 неизменно. Затем определяется полученное при этом приращении значение ΔF, которое можно считать пропорциональным значению величины частной производной в рассматриваемой точке.

Далее дается приращение величины x2. В это время значение x1 -постоянно. Получаемое при этом приращение ∆F является мерой другой частной производной.

После нахождения составляющих градиента делаются шаги в направлении вектора градиента, если стоит задача определения максимума и в направлении противоположном, если решается задача поиска минимума.

Таким образом, определяются новые значения x1 и x2 в соответствующей точке. После каждого шага оценивается приращение ΔF величины F.

Если ΔF>0 при поиске максимума или ΔF<0 при поиске минимума, то движение происходит в правильном направлении, иначе необходимо уменьшить величину шага.

Численное значение координаты при движении по градиенту для переменной xi в последующей k+1 точке вычисляется при помощи численного значения этой координаты на предыдущем шаге по следующей формуле:

xi,k+1 = xi,k ± hk * Si,k (+ для поиска максимума; - для поиска минимума),

где, =1,2 , … ,n ; k=0,1,2, … ,.

n - число варьируемых переменных, k - номер шага поиска.

Величина называется нормой градиента в соответствующей

точке поиска экстремума целевой функции и вычисляется по формуле:

hk - шаг поиска в точке, который выбирается произвольно.

Глава II. Практическая часть

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

2.1.   Разработка блок-схемы машинного алгоритма и программы

Программа для нахождения минимума будет начинаться с функции L(x0,y0,e), входными параметрами которой являются x0 - точка приближения по x, y0 - точка приближения по y и точность приближенного решения e. Равномерный поиск реализован основным соотношением

Результатом функции будет значение аргументов функции, доставляющих минимум рассматриваемой функции, само значение этого минимума. Приведем блок-схему машинного алгоритма (Рисунок 2).

Рисунок 2 - Блок-схема программы

Реализация градиентного метода в Mathcad представлена на рисунке 3.

Рисунок 3 - Листинг программы в Mathcad

Результат выполнения программы представлен на рисунке 4.

Рисунок 4 - Результат выполнения программы

Результат, выданный программой, показывает координаты точки минимума x=0.67859 y=0.65174 и значение функции в этой точке Z(x,y)=5.73321.

Построим графики функций (Рисунок 5, Рисунок 6).

Рисунок 5 - График функции F(x)

Рисунок 6 - График функции H(y)

По графикам на рисунках 5 и 6 видно, что экстремум функции попадает в заданную область ограничений.

Так же построим 3D график нашей функции цели Z(x,y).

Рисунок 7 - 3D график функции цели Z(x,y)

2.2.   Проверка необходимых и достаточных условий экстремума для найденной точки минимума

Для проверки необходимого условия существования экстремума функции найдем первую производную Zpr(x,y) от целевой функции Z(x,y) и подставим получившиеся координаты точек x и y. Производная равна нулю (учитывая допустимую погрешность), следовательно, необходимое условие существования экстремума выполнено.

А для проверки достаточного условия нужно построить матрицу Гессе и с помощью встроенной функции в Mathcad найти её определитель, подставив координаты полученной точки.

Реализуем алгоритм проверки необходимого условия в Mathcad. Листинг программы представлен на рисунке 8.

Рисунок 8 - Листинг программы по проверке необходимого условия

Реализуем программу для проверки достаточного условия. Листинг программы представлен на рисунке 9.

Рисунок 9 - Листинг программы по проверке достаточного условия

По выполненной программе на рисунке 9 можно сделать вывод, что матрица Гессе положительно определена, это означает то что мы нашли точку минимума.

2.3.   Разработки программы проверки ограничений

Для проверки ограничений оптимизационной задачи рассмотренной в курсовой работе, мной была разработана программа. Функция программы названа Proverka. Программа заключается в том что, мы задаем два условия: если значение точки x попадает в промежуток от Ax до By и если значение y попадает в промежуток от Ay и By, которые должны быть верными и перемножаем их, в итоге программа должна выдать значение 1 (истина). На листинге программе приведенной на рисунке 9, мы видим, что найденная точка попадает в область допустимых значений.

Рисунок 10 - Листинг программы проверки ограничений

Заключение

В курсовой работе был рассмотрен градиентный метод оптимизации с равномерным поиском. Составлена программа в Mathcad, реализующая этот метод. Была найдена точка оптимума, являющаяся минимумом Z(x,y)=5.7332. В ней выполняются необходимые и достаточные условия.

Градиентный метод является эффективным. Однако могут возникнуть трудности с вычислением и исследованием матрицы вторых производных (матрицы Гессе).

Список литературных источников

1.   Сыроежкин Е.В. Методические указания по дисциплине «Методы оптимизации в управлении». - Москва, 2012 - 30с.

2.   Жилинскас А., Шалтянис В. Поиск оптимума: компьютер расширяет возможности.- М.: Наука, 1989.- 128 с

3.      Химмельблау Д. Прикладное нелинейное программирование.- М.: Мир, 1975. -534 с.