Методы нахождения условного и безусловного экстремума

Содержание

1.              Задание на курсовую работу             

2.              Реферат             

3.              Введение             

4.              Нахождение безусловного экстремума             

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

4.2              Метод равномерного симплекса             

4.3              Метод Хука-Дживса             

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

4.5              Метод Коши             

4.6              Метод Ньютона             

4.7              Метод сопряженных градиентов             

4.8              Квазиньютоновский метод             

5.              Нахождение условного экстремума             

5.1              Метод штрафных функций (квадратичный штраф)             

6.              Заключение             

7.              Приложение 1. Листинг программы             

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

ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ФАКУЛЬТЕТ АВТОМАТИКИ И ВЫЧИСЛИТЕЛЬНОЙ ТЕХНИКИ

КАФЕДРА «АВТОМАТИКИ И ТЕЛЕМЕХАНИКИ»

1.     Задание на курсовую работу

По дисциплине « Методы оптимизации »

Тема: « Методы нахождения условного и безусловного экстремума. »

Студент:  Огарков А. В.                                                                                              Группы:    У-22

Задание:

Найти минимум целевой функции f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2 :

1.        методом равномерного симплекса;

2.        методом Хука-Дживса;

3.        методом сопряжённых направлений Пауэлла;

4.        методом Коши;

5.        методом Ньютона;

6.        методом сопряжённых градиентов;

7.        квазиньютоновским методом;

8.        методом штрафных функций (получив ограничения на решение).

Предварительно необходимо найти стационарную точку Х и определить характер экстремума из необходимых и достаточных условий.

Исходные данные для решения:

начальная точка поиска х(0) = [-10;-10]Т;

Окончание поиска:

1.        в методе равномерного симплекса после завершения одного оборота симплекса в области расположения стационарной точки;

2.        в методе Хука-Дживса после первого сокращения шага поиска;

3.        в методе Коши после выполнения четырёх итераций;

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

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

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

(подпись)

Задание принял                                                        /   Огарков А. В.   /                                          2003 г

(подпись)

2.     Реферат

     Огарков А. В. Методы нахождения условного и безусловного экстремума: ТПЖА 2101 022.014 ПЗ: Курс. работа / ВятГУ, каф. АТ; рук. В. И. Микрюкова.– Киров, 2003. ПЗ 29 с., 9 рис., 1 таблица., 4 источника, 1 прил., текст программы
10 c.

МЕТОДЫ ПРЯМОГО ПОИСКА, МЕТОД ПОИСКА ПО СИМПЛЕКСУ, МЕТОД ХУКА-ДЖИВСА, МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ ПАУЭЛЛА, ГРАДИЕНТНЫЕ МЕТОДЫ, МЕТОД КОШИ, МЕТОД НЬЮТОНА, МЕТОД СОПРЯЖЕННЫХ ГРАДИЕНТОВ, КВАЗИНЬЮТОНОВСКИЙ МЕТОД, НАХОЖДЕНИЕ УСЛОВНОГО ЭКСТРЕМУМА, МЕТОД ШТРАФНЫХ ФУНКЦИЙ.

Цель работы – изучение прямых и градиентных методов нахождения безусловного экстремума функции двух переменных; изучение методов поиска условного экстремума этой же функции.

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

3.     Введение

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

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

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

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

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

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

4.     Нахождение безусловного экстремума

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

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

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2.

Частные производные f(x1,x2)  по x1 и x2:

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

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

                            ,                            .

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

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

,

;  ;  ; ;

= 3.

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

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

4.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 )

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

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

Исходные данные:

f(х1,х2)=(х1–4)2+(х2–4)2 +х1·х2;

x(0) = [-10,-10]T – начальная точка;

α = 5 – масштабный множитель.

Минимизируем целевую функцию до первого уменьшения размера симплекса.

1-я итерация:

х(0) = [-10;-10]T ;

х(1) = [-10+4.8296;-10+1.2941]T=[-5.1704;-8.7059]T;

х(2) = [-10+1.2941; -10+4.8296]T=[-8.7059;-5.1704]T.

f(x(0))= 492 - max => заменяем

f(x(1))= 290.549;

f(x(2))= 290.549;

х(3) = х(1) + х(2) ‑ х(0);

х(3) = [-3.8763;-3.8763]T.

2-я итерация:

х(1) =[-5.1704;-8.7059]T; х(2) =[-8.7059;-5.1704]T; х(3) =[-3.8763;-3.8763]T.

f(x(1))= 290.549;

f(x(2))= 290.549.

f(x(3))= 139.098;

Так как f(x(2))= f(x(1))=max, то заменить можно x(1) и x(2). Заменим x(1).

х(4) = х(2) + х(3) ‑ х(1);

х(4) = [-7.4118;-0.3408]T

3-я итерация:

х(2) =[-8.7059;-5.1704]T; х(3) =[-3.8763;-3.8763]T; х(4) = [-7.4118;-0.3408]T.

f(x(2))= 290.549 – max => заменяем

f(x(3))= 139.098;

f(x(4))= 151.598.

х(5) = х(3) + х(4) ‑ х(2);

х(5) = [-2.5822;0,9533]T.

4-я итерация:

х(3) =[-3.8763;-3.8763]T; х(4) = [-7.4118;-0.3408]T; х(5) = [-2.5822;0,9533]T.

f(x(3))= 139.098;

f(x(4))= 151.598 – max => заменяем

f(x(5))= 50.149.

х(6) = х(3) + х(5) ‑ х(4);

х(6) = [-0.9533;-2.5822]T.

5-я итерация:

х(3) = [-3.8763;-3.8763]T; х(5) = [-2.5822;0,9533]T; х(6) = [-0.9533;-2.5822]T.

f(x(3))= 139.098 – max => заменяем

f(x(5))= 50.149;

f(x(6))= 50.149.

х(7) = х(5) + х(6) ‑ х(3);

х(7) = [2.2474; 2.2474]T.

6-я итерация: