Методы безусловной оптимизации

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И  НАУКИ РФ

Федеральное государственное бюджетное  образовательное учреждение

высшего профессионального образования

Вятский государственный университет

Вечерне-заочный факультет

 

 

 

 

 

 

 

 

 

 

 

Решение задач многомерной  оптимизации

 

 

Пояснительная записка 

 

Курсовая работа по дисциплине

«Методы оптимизации»

 

ТПЖА.220201.623 ПЗ

 

 

 

 

 

 

 

 

 

Разработал студент гр. 21-УТ _________________________________ / Фандеев Е.А./

          (подпись)

 

 

 

Руководитель работы              _________________________________ / Микрюкова В.И./

          (подпись)

 

 

 

 

 

 

Киров 2012 

 

Содержание

 

Введение………………………………………………………………..………………….......3

1 Методы безусловной оптимизации…………….…………………..….............................4

1.1 Методы прямого поиска…..…….....…………………………………………......4

1.1.1 Нахождение стационарной точки…………………………………….4

1.1.2 Метод поиска по симплексу………………………..............................5

1.1.3 Метод Хука-Дживса…………………………………………………...12

1.1.4 Метод сопряженных направлений Пауэлла………………………….17

1.2 Градиентные методы………………………….…………………........................21

1.2.1 Метод Коши……………………………………………………………21

1.2.2 Метод Ньютона………………………………………………………..24

1.2.3 Метод сопряженных градиентов ……………...................................25

1.2.4 Квазиньютоновский метод.………………….....................................28

Заключение……………………………………………………………………………….…30

Список  литературы………………………………………………………………………….31

 

Введение

 

Необходимость решения задач оптимизации достаточно часто возникает в последнее  время. Большинство из них требует  решения с помощью ЭВМ и  сложных программных комплексов, так как объём обрабатываемой информации очень велик и требует  соответствующих ресурсных затрат.

Задачи  нахождения оптимального решения являются самыми распространенными на сегодняшний  день. Из-за увеличения объемов производства, люди вынуждены решать сколько потратить  ресурсов на тот или иной проект, ведь на все задуманное ресурсов стало  не хватать. Во многих странах производится строгий учет потребления природных  и человеческих ресурсов, а следовательно  необходимо каждый день находить новые  способы решения задач по оптимизации  различных процессов. Особо остро  стоит проблема коммуникаций в городах. Под коммуникациями можно рассматривать  не только телефоны, факсы и прочие устройства, но также и транспортные коммуникации и компьютерные сети. Для последних особенно характерна проблема «трафика», так как существующие линии не способны обеспечить передачу необходимых объемов информации.

Оптимальная задача – экономико-математическая задача, содержащая критерий оптимальности  и ограничения, то есть направленная на поиск лучшего в определенных условиях (оптимального) значения показателя.

Из всего  выше написанного следует, что  характерной  тенденцией в построении современных  систем автоматического управления является стремление получить системы, которые в некотором смысле являются наилучшими. При управлении компьютерными  сетями это стремление выражается в  том, чтобы получать максимальные объемы требуемой информации за наименьшее время при ограниченных пропускных способностях кабелей и коммуникаторов.

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

Данная работа рассматривает некоторые методы нахождения безусловного экстремума (метод Коши, Хука-Дживса, Ньютона и др.) для функции двух переменных.

 

1 Методы безусловной оптимизации

 

1. Методы прямого поиска

 

1.1.1 Нахождение стационарной точки

 

Целевая функция:

   

 

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

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

 по  и :

Приравняв полученные выражения к нулю, получим  систему уравнений:

Решение системы уравнений даёт результат:

 

 

Таким образом, экстремум целевой функции является точка с координатами х* = Т, значение целевой функции, в которой: .

 

Для определения  характера стационарной точки составим определитель матрицы Гессе. Под  определителем Гессе понимается определитель, составленный из вторых производных исходной целевой функции.

 

 

 

  

Так как  гессиан функция - положительно определенная матрица (выполняются условия Сильвестра: все диагональные элементы матрицы  Гессе - положительные величины, все  ведущие главные определители положительные  величины), стационарная точка является точкой минимума.

 

 

Рисунок.1-Линии  уровня функции и стационарная точка

 

 

1.1.2 Метод поиска по симплексу

 

Суть  метода заключается в исследовании целевой функции в вершинах некого «образца», построенного в пространстве переменных вокруг «базовой» точки. Вершина, давшая наибольшее значение целевой  функции отображается относительно двух других вершин и таким образом  становится новой базовой точкой, вокруг которой строится новый образец  и снова выполняется поиск. В  рассматриваемом методе таким образцом является регулярный симплекс. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве – тетраэдр.

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

Процедура продолжается до тех пор, пока не будет  накрыта точка минимума. 

 

Некоторые правила:

 

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

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

 

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

 

При заданной начальной точке х(0) и масштабном множителе a, координаты остальных N вершин симплекса в N–мерном пространстве вычисляются по формуле:

 

           xj(0) + d1, если i = j;

x(i) =

           xj(0) + d2, если i ¹ j.

 

Приращения d1  и d2  определяются по формулам:

,

.

Величина  α выбирается исследователем, исходя из характеристики решаемой задачи. При  α=1 ребро симплекса имеет единичную  длину.

 

 

 

Вычисление  центра тяжести:

Если  х(i) – точка, подлежащая отражению, то координаты центра тяжести определяется по формуле:

.

Координаты  новой вершины удовлетворяют  уравнению

xнов( j ) = x( j ) + λ·(xc – x( j )).

Для того, чтобы  симплекс обладал свойством  регулярности, отображение должно быть симметричным, т.е. λ = 2.

xнов( j ) = 2·xc – x( j )

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

 

Нахождение  минимума целевой функции симплекс-методом

 

Задание:

Найти минимум  функции 

 

Решение:

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

Тогда:

 

Вычисляем координаты двух других вершин симплекса

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

Так как  в точке  целевая функция принимает максимальное значение, то необходимо отразить точку относительно центра тяжести остальных вершин симплекса.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

Уменьшаем размер симплекса.

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

Так как  в точке  целевая функция принимает максимальное значение, то необходимо отразить точку относительно центра тяжести остальных вершин симплекса.

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