43271

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

Курсовая

Информатика, кибернетика и программирование

Цель задания: Найти минимум функции методами прямого поиска и градиентными методами. Цель работы отработка навыков решения задач безусловной оптимизации функции нескольких переменных методами прямого поиска и отработка навыков решения задач безусловной оптимизации градиентными методами. Решена задача безусловной оптимизации функции нескольких переменных методами прямого поиска и градиентными методами. Нахождение стационарной точки Целевая функция: ; Частные производные f по x1 и x2: ∂f ∂x1=2x1 x2 –6; ∂f ∂x2=x1 2x2 –4; Приравниваем...

Русский

2013-11-04

730.5 KB

13 чел.

29

PAGE  23

PAGE 23 NUMPAGES 35

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

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

Факультет автоматики и вычислительной техники

Кафедра автоматики и телемеханики

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

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

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

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

ТПЖА 220201. 023 ПЗ

   Разработал студент гр. У                        ____________________   /Волосков И. Н./

                                       (подпись)

       

           

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

(подпись)

Киров 2011

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

                        ФАКУЛЬТЕТ АВТОМАТИКИ И ТЕЛЕМЕХАНИКИ

Кафедра Автоматики и телемеханики

ЗАДАНИЕ НА КУРСОВУЮ РАБОТУ

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

ТЕМА: “Решение задач оптимизации”

Студент ______________________________________________________

Группа     ________

  1.  Исходные данные: Функция двух переменных:

.

 х(0)=[-10,-10]T-начальная точка.

  1.  Цель задания: Найти минимум функции методами прямого поиска и градиентными методами.
  •  методом равномерного симплекса;
  •  методом Хука-Дживса;
  •  методом сопряжённых направлений Пауэлла;
  •  методом Коши;
  •  методом Ньютона;
  •  методом сопряжённых градиентов;
  •  квазиньютоновским методом;
  •  методом штрафных функций (получив ограничения на решение).

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

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

  1.  в методе равномерного симплекса после завершения одного оборота симплекса в области расположения стационарной точки.
  2.  в методе Хука-Дживса после первого сокращения шага поиска;
  3.  в методе Коши после выполнения четырёх итераций;

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

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

             (подпись)          (Ф.И.О. преподавателя)

Задание принял      ___________________  /_________________/  __.__.2011 г.

              (подпись)                 (Ф.И.О. студента)

  Реферат

Волосков И.Н. Методы нахождения условного и безусловного экстремума: ТПЖА 220201.011 ПЗ: Курс. работа / ВятГУ, каф. АТ; рук. В. И. Микрюкова.– Киров, 2011. ПЗ 29 с., 8 рис., 1 таблица., 4 источника

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

Объект исследования – изучение методов решения задач оптимизации.

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

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

Содержание

  1.  Задание на курсовую работу ………………………………………….
  2.  Содержание…………………………………………………………….
  3.  Введение………………………………………………………………..
  4.  Основная часть…………………………………………………………
    1.   Методы безусловной оптимизации
      1.  Методы прямого поиска

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

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

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

         4.1.2 Градиентные методы          

4.1.2.1 Метод Коши…………………………………………

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

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

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

         4.1.3 Методы Условного экстремума          

               4.1.3.1 Метод штрафных функций…………………………

4.2 Выводы……………………………………………………………..

  1.  Заключение………………………………………………………… 37     
  2.  Библиографический список литературы………………………     38

2

4

5

6

7

13

17

21

24

26

29

31

36

 

 

 

 

 

Введение

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

Развитие численных линейных методов решения задач линейного программирования очень важно в нынешнее время, поскольку сложность решаемых задач взваливает всю работу на современные ЭВМ, работающие с « единичками» и « ноликами», и « неподозревающих» о существовании производных, первообразных, интегралов и пр. И нахождение оптимального решения сводится к представлению его в виде численных методов.

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

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

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

;

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

f/∂x1=2•x1 + x2 –6;

f/∂x2=x1 + 2•x2 –4;

Приравниваем эти производные к нулю:

     2•x1 + x2 –6 = 0;

     x1 + 2•x2 –4= 0;

Совместное решение этих уравнений даёт результат:

x2 = 2/3 ;

x1 = 8/3 ;

Таким образом, экстремумом целевой функции является точка с координатами x[8/3;2/3], значение целевой функции, в которой

[x(8/3;2/3)] = 1.

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

;

= 3;

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

Задача определения экстремума свелась к нахождению минимума целевой функции f(x).

 

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

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

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

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

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

 Некоторые замечания:

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

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

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

x(i) =        xj(0) + 2, если i j.

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

;

;

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

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

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

;

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

xнов( j ) = x( j ) + λ•(xcx( j ));

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

xнов( j ) = 2•xcx( j );

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

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

   Задание:

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

   Начальные данные :

- начальный масштабный множитель;

- начальная точка;

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

   Решение:

,

,

   1.

 ; заменяем

;

;

;

;

   2.

;

;

; заменяем

;

;

   3.

;

; заменяем

;

;

;

   4.

; заменяем

;

;

;

;

   5.

;

;

; заменяем

;

;

   6.

; заменяем

;

;

;

;

   7.

;

; ; заменяем

;

;

;

   8.

; ; заменяем

; ;

; ;

;

;

   9.

; ;

; ;

;  ; заменяем

;

;

   10.

; ; заменяем

; ;

; ;

;

;

   11.

;;

;; заменяем

;;

;

;

   12.

; заменяем

; 

;

;

;

  

 13.

;

; заменяем

;

;

;

14.

;

; заменяем

;

;

;

Координаты точек, полученные на 14-й итерации, совпадают с координатами, полученными на 11-й итерации. Симплекс накрыл точку минимума. Далее следует уменьшить масштабный множитель   (например, в 2 раза) и построить новый исходный симплекс, взяв в качестве исходной точку

Полученное решение   не является точным, поэтому имело бы смысл продолжить вычисления.

 

Графическое приложение к Симплекс-методу.

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

Метод относится к категории эвристических методов оптимизации.  Процедура Хука - Дживса представляет собой комбинацию “исследующего” поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направления вдоль “оврагов”. Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по “оврагам”.

Исследующий поиск

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

Поиск по образцу

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

xр(к + 1) = x(к) + [x(к) - x(к - 1)] ;

Как только движение по образцу не приводит к уменьшению целевой функции, точка xр(к + 1)  фиксируется в качестве временной базовой точки и выполняется исследующий поиск. При улучшении значения целевой функции эта точка рассматривается как новая базовая точка. Если же исследующий поиск не дал результата, необходимо вернуться в предыдущую точку и провести исследующий поиск.

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

 

 

 

 

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

Dх – векторная величина приращения

Dх = 1;

a - коэффициент уменьшения шага.

a = 1;

e - минимальное значение приращения α, при котором ещё стоит искать минимум.

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

Будем искать минимум до первого уменьшения приращения.

f(x) = (x1-3)2 + (x2-2)2 + x1•x2;

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

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

  1.  Исследующий поиск вокруг базовой точки х(0):

фиксируя х2, даём приращение переменной х1:

х2=-10; х1=-10+1=-9  f =378<413удача

фиксируя х1, даём приращение переменной х2:

х1=-9;  х2=-10+1=-9  f = 346<378удача

х(1) = [-9;-9]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp(2) = 2•х(1) – х(0);

хp (2) = [-8;-8]T f =285

  1.  Исследующий поиск вокруг точки хp (2):

фиксируя х2, даём приращение переменной х1:

х2=-8; х1=-8+1=-7  f = 256<285удача

фиксируя х1, даём приращение переменной х2:

х1=-7;  х2=-8+1=-7  f = 230<256удача

х(2) = [-7;-7]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (3) = 2•х(2) – х(1);

хp (3) = [-5;-5]T  f =138

  1.  Исследующий поиск вокруг точки хp (3):

фиксируя х2, даём приращение переменной х1:

х2=-5; х1=-5+1=-4  f = 118<138удача

фиксируя х1, даём приращение переменной х2:

х1=-4;  х2=-5+1=-4  f = 101<118удача

х(3) = [-4;-4]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (4) = 2•х(3) – х(2);

хp (4) = [-1;-1]T  f =26

  1.  Исследующий поиск вокруг точки хp (4):

фиксируя х2, даём приращение переменной х1:

х2=-1; х1=-1+1=0  f = 18<26удача

фиксируя х1, даём приращение переменной х2:

х1=0;  х2=-1+1=0  f =13<18удача

х(4) = [0;0]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (5) = 2•х(4) – х(3);

хp (5) = [4;4]T  f =21.

5. Исследующий поиск вокруг точки хp (5):

фиксируя х2, даём приращение переменной х1:

х2=4;  х1=4+1=5  f = 28>21неудача

 х1=4-1=3  f = 16<21удача

фиксируя х1, даём приращение переменной х2:

х1=3;  х2=4+1=5  f =24>16неудача

                   х2=4-1=3  f =10<16удача

х(5) = [3;3]T;

Т.к. поиск был удачным, переходим к поиску по образцу:

хp (6) = 2•х(5) – х(4);

хp (6) = [6;6]T  f =61.

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

α = 1/2=0.5;

Далее необходимо произвести исследующий поиск вокруг точки

х (5) = [3][3],  используя новое значение приращения α =0.5;

Когда α достигнет какого-то небольшого значения, заданного пользователем, поиск экстремума можно прекратить.

Т.о. мы получили точку х = [3;3]Т, значение функции в которой

f(x) = 10. Это значение значительно приближено к значению функции в стационарной точке (1), однако дальнейший ход решения укажет на улучшение результата.

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

Графическое приложение к методу Хука-Дживса:

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

Метод относится к категории теоретических методов оптимизации.  Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция N переменных приведена к сумме квадратов, то ее оптимум может быть найден  в результате реализации N одномерных поисков по преобразованным координатным (сопряженным) направлениям. Сопряженные направления определяются алгоритмически. Для нашего двумерного случая реализация метода требует три одномерных поиска. Для нахождения экстремума квадратичной функции N переменных необходимо выполнить N2 одномерных поисков.

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

Решение:

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

Начальная точка:

Значение целевой функции в этой точке:

Шаг 1. Зададим исходные точки S(1) и S(2):

S(1) = [1;0]       S(2) = [0;1]

Шаг 2. Найдем значение , при [Х(0)+2S(2)]. Произвольная точка на луче из точки Х(0) в направлении S(2) определяется как

Х = Х(0) + S(2) = [-10;-10] + [0;1]

откуда       X1 = -10         X2 = - 10

Подставляя эти значения  в целевую функцию, получаем

 (Х) =

Дифференцируем это выражение по  и приравниваем нулю:

’(X) = 2 - 34

2 - 34 = 0

Отсюда находим :

= 17

X(1) = [-10;-10] + 17[0;1] = [-10;7]

[X(1)] = 124

 

Аналогично найдем значение , при [Х(1)+S(1)].

Х = Х(1) + S(1) = [-10;7] + [1;0]

откуда       X1 =  -10         X2 =7

Подставляя эти значения  в целевую функцию, получаем

 (Х) =

Дифференцируем это выражение по  и приравниваем нулю:

’(X) = 2 - 19

2 - 19 = 0

Отсюда находим :

= 9.5

X(2) = [-10;7] + 9.5[1;0] = [-0.5;7]

[X(2)] = 33.75

Также найдем значение , при [Х(2)+2S(2)].

Х = Х(2) + S(2) = [-0.5;7] + [0;1]

откуда       X1 = -0.5         X2 = 7 +

Подставляя эти значения  в целевую функцию, получаем

 (Х) =

Дифференцируем это выражение по  и приравниваем нулю:

’(X) = 2+9.5

9.5 + 2 = 0

Отсюда находим :

= -4.75

X(3) = [-0.5;7] -4.75[0;1] = [-0.5;11.75]

[X(3)] = 101.44

Шаг 3. Положим

S(3) = X(3) – X(1) = [9.5;-4.75]

Направление S(3) оказывается сопряженным с направлением S(2). Поскольку N = 2, то оптимизация вдоль направления S(3) дает искомый результат.
Шаг 4.  Найдем такое значение , при  [X(3) + S(3)]  

X = X(3) + [9.5;-4.75]= [-0.5;2.25] + [9.5;-4.75]

X1 = -0.5 + 9.5          X2 = 2.25-4.75

’(X) = 135.38-45.13

отсюда

= 0.33335

тогда

Х(4) = [-0.5;2.25]+0.333*[9.5;-4.75] = [2.6635; 0.66825]

Таким образом, получили точку х= [2.6635; 0.66825]T, значение функции в которой f(x) = 1, совпадает со стационарной точкой.

Вывод: метод сопряженных направлений Пауэлла обеспечивает высокоточный при малом количестве итераций по сравнению с предыдущими методами.

Графическое пояснение метода сопряженных направлений Пауэлла:

Методы прямого поиска являются удобными при простых целевых функциях, или когда необходимо найти оптимум с невысокой степенью точности. Но требуют больших затрат времени и вычислительных ресурсов, из-за большого числа проводимых итераций: метод поиска по симплексу – 16 итераций, метод Хука-Дживса – 5 итераций, метод сопряженных направлений Пауэлла – 4 итерации.

Градиентные методы поиска экстремума функции

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

Описание метода Коши

В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента. Алгоритм метода выглядит следующим образом:

      x(k + 1) = x(k) - (k)f(x(k)),  где f (x) – градиент.

  Значение (k) на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума f(x) вдоль направления градиента f(x(k)). Если в качестве (k) взять некоторое положительное число, то получится простейший градиентный алгоритм:

      f(k + 1) = x(k) - f(x(k));

Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие

       f(x(k + 1))   f(x(k));

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

Метод Коши:

f(x)= (х1 - 3)2 + (х2 – 2)2 +х1•х2

Условие окончания поиска: выполнение четырех итераций.

f/∂x1=2•x1 + x2 – 6              ∂f/∂x2=x1 + 2•x2 –4

Зададим начальное приближение х(0) = [-10;-10]Т .

Новое приближение определим по формуле:

х(1) = х(0) – α (0)f (x(0) ).

f (x(0) ) = [-36;-34]T

  1.  Выбираем α (0) такое, чтобы минимизировать функцию f (x(1) ).

x(1) = [-10;-10]T- α (0) [-36;-34]T = [-10+ α (0)•36;-10 + α (0)•34]T

По аналогии с предыдущим методом найдем  α (0) = 0.333;

x(1) = [2.005; 1.338]T

  1.  Далее найдём точку x(2) = х(1) - α (1)f (x(1) ).

f (x(1) ) =[-0.651; 0.682]T

x(2) = [2.005; 1.338]T - α (1)•[-0.651; 0.682]T

Найдем α (1) = 0.999;

x(2) = [2.656; 0.657]T

  1.  Далее найдём точку x(3) = х(2) - α (2)f (x(2) ).

f (x(2) ) = [0.65;1.332]T

x(3) = [2.656; 0.657]T - α (2)• [0.65;1.332]T

Найдем α (2) = 0.343;

x(3) = [2.666; 0.667]T

После выполнения трех итераций получено практически точное решение х* = х(3), при котором значение целевой функции f*=1,0036.

Графическое пояснение метода Коши

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

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

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

        x(k + 1) = x(k) - 2f(x(k))-1f(x(k)),  где 2f(x) – матрица Гессе.

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

Нахождение минимума целевой функции методом Ньютона:

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

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

Нахождение минимума целевой функции методом Ньютона:

f(x) = x12 - 4•x1 + x2 2 - 14•x2 + x1•x2 + 51;

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

f/∂x1=2•x1 + x2 –6;

f/∂x2=x1 + 2•x2 –4;

2f/∂x12=2

2f/∂x1∂x2=1

            

2f/∂x22=2

2f/∂x2∂x1=1

f(x) = [2•x1 + x2 –6;x1 + 2•x2 –4]T

2f(x) =                      =3

f (x(0) ) = [-36;-34]T;

x(1) = x(0) – [2f(x)]-1f (x(0) );

f(x(1)) = 1;

Мы получили точку х = [2.667;0.667]Т, значение функции в которой f(x) = 1 за одну итерацию, что говорит о пригодности метода для нахождения минимума без использования ЭВМ.

Графическое приложение к методу Ньютона:

Вывод: методом Ньютона точка оптимума найдена за одну итерацию, что гораздо лучше, чем 2 итерации метода Коши, и десятки итераций при методах прямого поиска. Недостатками метода является необходимость знать 1 и 2 производные целевой функции. Иногда это трудно или невозможно. Также при значительно удаленном от оптимального решения  x(0) метод Ньютона не отличается точностью, однако весьма эффективен вблизи точки x*.

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

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

                       x(k + 1) = x(k) + (k)s(x(k)) ;

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

                       s(k) = -g(k) + s(k - 1) ;

В этом случае направление s(k)  будет С - сопряжено со всеми ранее построенными направлениями поиска.

Если функция f(x1, x2, ... , xN) квадратичная, то для нахождения точки экстремума требуется определить N-1 таких направлений и провести поиски вдоль каждой прямой.  Если f(x) не является квадратичной, то количество поисков возрастет.

Нахождение минимума целевой функции методом сопряжённых градиентов:

Решение:

f(x)= (х1 - 3)2 + (х2 – 2)2 +х1•х2

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

ШАГ 1:

f(x) = [2•x1 + x2 – 6 ; x1 + 2•x2 –4]T

f(x(0) ) = [-36;-34]T

s(0) = -g(0) = -f(x(0) ) = -[-36;-34]T

ШАГ 2:

Поиск вдоль прямой:

х(1) = х(0) - a(0)f(x(0) )  a(0) =0.333;

х(1) = [-10;-10]Т – 0.333•[-36;-34]T = [2.005; 1.338]T

ШАГ 3:

Определим направление s(1):

g(1) = [-0.651; 0.682]Т

s(1) = -g(1) + [ |g(1)|2 / | g(0)|2 ]•s(0) ;

s(1) = -[-0.651; 0.682]Т - [0.424 / 0.889] • [-36;-34]T = [0.664; -0.67]T

ШАГ 4:

Поиск вдоль прямой:

x(2) =  x(1) + a(1)s(1)   a(1) = 0.987;

х(2) = [2.005; 1.338]T + 0.987*[0.664; -0.67]T = [2.6606;0.6776]T

Таким образом, проделав 2 итерациb, мы пришли к точке х(2)= [2.6606;0.6776]T, отличной от точки экстремума х*=[2.6667; 0.6667] во втором знаке после запятой, что говорит о влиянии сокрашений на результат .

Графическое приложение к методу сопряжённых градиентов:

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

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

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

                                              x(k+1) = x(k) + (k)s(k) .

Направление поиска определяется выражением

s(k) = -A(k)(X(k)),  где A(k) - матрица порядка NN.

Матрица A – вычисляется по формуле

          A(k) = A(k-1) +Ac(k-1),где 

                    Ac(k-1) = ;      (1)

,где g(k) = g(k) - g(k-1)   изменение градиента на предыдущем шаге.

Нахождение минимума целевой функции Квазиньютоновским методом:

Нахождение минимума целевой функции Квазиньютоновским методом:

f(x) = x12 - 6•x1 +9+ x2 2 - 4•x2 +4+ x1•x2;

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

f/∂x1=2•x1 + x2 –6              ∂f/∂x2=x1 + 2•x2 –4

ШАГ 1:

f(x) = [2•x1 + x2 –6; x1 + 2•x2 –4]T

f(x(0) ) = [-36;-34]T

Положим s(0) =  -f(x(0) ) = [36;34]T;

ШАГ 2:

Поиск вдоль прямой:

х(1) = х(0) - a(0)f(x(0) )  a(0) = 0.333;

х(1) = [-10;-10]Т – 0.333 •[-36;-34]T = [2.0052; 1.3382]T;

ШАГ 3:

А(0) = Е =

х(0) = [2.0052; 1.3382]T - [-10;-10]T =  [12.005; 11.338]T;

g(0) = g(1) – g(0) = [3,7328; -2,8982]T -  [-36;-34]T = [35.349; 34.682]T;

А(1) = A(0) + Ac(0);

s(1) = - A(1)g(1);

s(1) = [0.662; -0.672]T;

ШАГ 4:

Поиск вдоль прямой:

х(2)  = x(1) + (1)s(1) = ;

 (1) =1.003;

x(2) =  [2,6686; 0.6646]Т

Точность метода позволяет уже на четвертом шаге считать текущую точку точкой-экстремумом. Т.е. х* = х(2) = [2,6686; 0.6646]Т;

f(x*) =1,012;

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

Графическое приложение к квазиньютоновскому методу:

Поиск условного экстремума

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

Метод штрафных функций

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

min  f (x),        ХRN 

при ограничениях    

          gj (x)  ≥  0

hk(x)  =  0,    k = 1...K

то преобразованная задача имеет вид:

P(x,R) = f(x) + [R, h(x),g(x)]

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

    Виды штрафов

 

  Квадратичный штраф имеет вид = R{h(x)}2. Этот вид штрафов используется для учёта ограничений-равенств. Функция непрерывна и имеет непрерывную производную, откуда следует, что если непрерывны и дифференцируемые f(x) и h(x), то стационарную точку можно найти ана-литически.       

 Логарифмический штраф

     = - Rln(g(x));

Этот штраф положителен для всех х таких, что 0 < g(x) <1, и отрицателен при g (x) > 1. Логарифмический штраф – это барьерная функция, неопределённая в точках, где g (x) < 0. Поэтому на начальном этапе поиска, когда значение шага поиска велико, необходимо обеспечить защиту процедуры от попадания рабочей точки в недопустимую область.

 Штраф, заданный обратной функцией

= R•1/g(x);

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

Штраф типа квадрата срезки

= R•<g(x)>2,

              α, если α ≤ 0,

< α > =

    0,если α  >  0.

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

Задача

Метод штрафных функций:

Нахождение минимума целевой функции :

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

- начальная точка;

Ограничение на решение:

Преобразуем целевую функцию  введением в неё заданного квадратичного штрафа: 

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

Совместное решение даёт:

Устремляя  к нулю, получаем

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

Исследуем функцию при различных значениях параметра    , то есть    

1.

2.

3.

4.

Сведем все данные в таблицу:

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

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

Графическое приложение к методу штрафных функций:

Выводы по основной части работы

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

   Методы прямого поиска, хотя и не требуют большей, чем значения целевой функции, информации о поведении последней, однако, производят большое количество итераций при доставлении решения с высокой точностью, так как поиск производится ими «вслепую». Так, эвристические алгоритмы поиска достигают решения за несколько десятков итераций, а теоретические выполняют до десяти итераций (в зависимости от вида функции).

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

Их достоинством является высокая точность получения решений.

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


Заключение

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

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


Библиографический список литературы:

  1.  Карманов В.Г. Математическое программирование. – М: Наука. Главная редакция физико-математической литературы, 1986
  2.  Коршунов Ю.М. Математические основы кибернетики. – М: Энергия, 1980.
  3.  Микрюкова В. И. Методы оптимизации. Методические указания по выполнению курсовой работы. Киров, 2010.
  4.  Микрюкова В. И.: курс лекций по дисциплине «Методы оптимизации».


Изм.

Лист

№ докум.

Подпись

Дата

Лист

4

ТПЖА 220201.023 ПЗ

Разраб.

Волосков И.Н.

Провер.

икрюкова В.И.

Реценз.

Н. Контр.

Утверд.

Методы оптимизации для

функций нескольких

переменных

Лит.

Листов

38

гр. У-22

  1.  1

1      2

  1.     0

0      1


 

А также другие работы, которые могут Вас заинтересовать

48496. КОНСТИТУЦИОННОЕ ПРАВО ЗАРУБЕЖНЫХ СТРАН 80 KB
  Особенности конституционно-правовых школ США Великобритании Франции ФРГ Италии и Индии. Конституции писаные США Индия Франция Италия Мексика Япония и неписаные Великобритания Новая Зеландия жесткие США Франция Япония Индия и гибкие Великобритания Новая Зеландия. Общие черты и особенности президентских республик США Мексика. Общие черты и основные особенности положения органов власти и управления субъектов Федерации в США ФРГ и Индии.
48498. КРИМИНОЛОГИЯ 172 KB
  Криминология изучает преступность виды преступности преступления; их причины иные виды их взаимосвязей с различными явлениями и процессами; результативность принимавшихся мер по борьбе с преступностью. Предмет это закономерности: преступности во всех ее проявлениях детерминации и причинности преступности подверженности преступности различным воздействиям. Преступность в различных ее проявлениях включает: преступление или индивидуальное преступное поведение; отдельные виды преступности выделяемые по объекту посягательств...
48499. Курс молодого избирателя 128.5 KB
  И в первую очередь с помощью продвижения идей местного самоуправления в среде старшеклассников. Идея формирование опыта самоуправления деятельности человека. Основное предназначение ученического самоуправления удовлетворять потребности учащихся направленные прежде всего на защиту их гражданских прав и интересов участие в решении реальных проблем школы. Смысл ученического самоуправления заключается не в управлении одних детей другими а в обучении всех детей основам демократических отношений в обществе в обучении их управлять собой...
48500. СТРАТЕГИЧЕСКИЙ МАРКЕТИНГ. КОНСПЕКТ ЛЕКЦИЙ 329 KB
  Стратегический маркетинг представляет собой постоянный и систематический анализ потребностей рынка выводящий на разработку эффективных товаров предназначенных для конкретных групп покупателей и обладающих особыми свойствами отличающими их от товаровконкурентов и таким образом создающими изготовителю устойчивое конкурентное преимущество. Роль стратегического маркетинга – прослеживать эволюцию заданного рынка и выявлять различные существующие либо потенциальные рынки или их сегменты на основе анализа потребностей нуждающихся в...
48501. Логика: язык, основные логические законы 657 KB
  Понятия Понятие как форма мышления. Отношения между понятиями. Понятие как форма мышления Обратить внимание на соотношение понятия и слова синонимы омонимы. Неточные молодой человек лысый человек и неясные человек понятия.
48502. КУРС ВИЩОЇ МАТЕМАТИКИ 2.83 MB
  КУРС ВИЩОЇ МАТЕМАТИКИ ЧАСТИНА 2 2005 Диференціальне числення функції однієї змінної. Похідна функції її геометричний і фізичний зміст. Похідної функції fx у точці х = х0 називається границя відносини приросту функції в цій точці до приросту аргументу якщо він існує. Тоді – тангенс кута нахилу січної МР до графіка функції.
48503. УЧЕБНАЯ РАДИО- ЭЛЕКТРОМОНТАЖНАЯ ПРАКТИКА 13.68 MB
  В процессе подготовки будущие специалисты должны получить определённую квалификацию, практические навыки. Особенно важно иметь хорошую практическую подготовку для специалиста, который, овладев теоретическими знаниями, должен уметь выполнить ту или иную конкретную работу.
48504. Методика профессионального обучения как наука и учебная дисциплина 416.77 KB
  Методика профессионального обучения как наука и учебная дисциплина. обучения как научной области педагогических знаний. обучения и методической терминологии. обучения с другими науками и перспективы ее развития.