76

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

Курсовая

Математика и математический анализ

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

Русский

2012-11-18

770.5 KB

215 чел.

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

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

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

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

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

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

Студентка: Карпова Юлия Александровна

Группа: У-21

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

.

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

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

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

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

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

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

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

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

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

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

Реферат

Карпова Ю.А. Методы нахождения условного и безусловного экстремума: ТПЖА 220201.052 ПЗ: Курс. работа / ВятГУ, каф. АТ; рук. В. И. Микрюкова.– Киров, 2012. ПЗ 41 с., 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.  Заключение
  2.  Библиографический список литературы


Введение

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

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

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


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

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

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

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

по  и :

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

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

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

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

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

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

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

   Многомерные методы оптимизации, основанные на вычислении целевой функции 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. Задать:     1. Начальную точку х(0)   ;

                  2. Масштабный множитель α;

                              3. Приращения δ1 и δ2 ;

                             4.Условие окончания поиска. Перейти к шагу 2.

Шаг 2. Вычислить координаты вершин х(1) и  х(2)   симплекса. Перейти к

шагу 3.

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

Шаг 4. Вершина, которой соответствует наибольшее значение целевой функции , построена на предыдущей итерации?

                            Да: отображается вершина, которой соответствует следующее по величине значение целевой функции

                            Нет: отображается точка с наибольшим значением целевой функции относительно двух других вершин симплекса. Перейти к шагу 5.

Шаг 5. Проверка на условие окончания.

                            Да: закончить поиск; результат- точка с наименьшим значением целевой функции;

                            Нет: перейти к шагу 3.

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

   Задание:

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

   Решение:

Шаг 1.  - начальная точка;

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

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

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

;

;

Шаг 2-3.

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

- максимально, следовательно, заменяем

Шаг 3-5.

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

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

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

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

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

- максимально, следовательно, заменяем

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

- максимально, следовательно, заменяем

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

Таким образом, точка  - точка минимума, значение функции в которой .

Рис 2. Графическое пояснение метода равномерного симплекса

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

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

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

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

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

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

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

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

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

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

Шаг 1. Задать:        1. Начальную точку ;

                        2. Приращение ,;

                        3. Коэффициент уменьшения шага ;

                        4. Параметр окончания поиска .

Шаг 2. Произвести исследующий поиск.

Шаг 3. Поиск удачный:

                       Да: перейти к шагу 5;

                       Нет: продолжить.

Шаг 4. Проверка на окончание поиска: ?

                       Да: прекратить поиск;

                       Нет: уменьшить приращение по формуле:

,; Перейти к шагу 2.

Шаг 5. Провести поиск по образцу:

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

Шаг 7. Выполняется ли условие ?

                       Да: продолжить ; ;

перейти к шагу 5;

                       Нет: перейти к шагу 4.

Ход решения:

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

- целевая функция;

Шаг 1.

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

- векторная величина приращения;

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

     Минимизируем значение целевой функции до первого сокращения шага поиска

       1.

   

Шаг 2. Исследующий поиск вокруг базовой точки :

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

; ;  - поиск удачен;

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

       ; ;  - поиск удачен;

Шаг 3.

       

Так как поиск удачен, то переходим к поиску по образцу (Шаг 5):

Шаг 6.   2.  Исследующий поиск вокруг точки (Шаг 2.):

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

; ;  - поиск удачен;

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

; ;  - поиск удачен;

Шаг 7.

Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :

Шаг 6. 3.Исследующий поиск вокруг точки :

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

; ;  - поиск неудачен;

; ;  - поиск неудачен;

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

; ;  - поиск удачен;

Шаг 7.

Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.):

Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск.

4.

  

Шаг 6. Исследующий поиск вокруг базовой точки :

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

; ;  - поиск неудачен;

; ;  - поиск неудачен;

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

; ;  - поиск удачен;

Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :

Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск (Шаг 6.).

5.

  

Исследующий поиск вокруг базовой точки :

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

; ;  - поиск неудачен;

; ;  - поиск неудачен;

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

; ;  - поиск неудачен;

; ;  - поиск неудачен;

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

Итерации продолжаются, пока величина шага не укажет на окончание поиска в окрестности точки минимума.

Рис 3. Графическое пояснение метода Хука-Дживса

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

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

Описание алгоритма:

Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:

приводится к виду сумма полных квадратов

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

В методе Пауэлла поиск реализуется в виде:

вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.

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

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

Шаг 1. Задать исходные точки ,  и направление . В частности, направление  может совпадать с направлением координатной оси;

Шаг 2. Произвести одномерный поиск из точки  в направлении  получить точку , являющуюся точкой экстремума на заданном направлении;

Шаг 3. Произвести одномерный поиск из точки  в направлении  получить точку ;

Шаг 4. Вычислить направление ;

       Шаг 5.  Провести одномерный поиск из точки  (либо ) в направлении  с выводом в точку .

Ход решения:

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

Шаг 1.

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

, .

Шаг 2.       

а) Найдем значение , при котором  минимизируется в направлении :

       Откуда ; .

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

Продифференцируем полученное выражение по , получим:

. Приравняв его к нулю, находим ;

Получили

б) Аналогично находим значение  минимизирующее функцию

в направлении :

Откуда ; .

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

Продифференцируем полученное выражение по , получим:

. Приравняв его к нулю, находим ;

Получили

в) Найдем значение  минимизирующее :

Откуда ; .

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

Продифференцируем полученное выражение по , получим:

. Приравняв его к нулю, находим ;

Получили

Шаг 3.         

Шаг4. Найдем такое значение , при котором  минимизируется в направлении .

Откуда ; .

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

Продифференцируем полученное выражение по , получим:

. Приравняв его к нулю, находим ;

Получили

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

Рис 4. Графическое пояснение метода сопряженных

направлений Пауэлла

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

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

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

Метод Коши.

Описание алгоритма:

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

- градиент функции

Алгоритм метода выглядит следующим образом:

, где  - градиент.

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

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

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

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

Шаг 1. Задать:                   1. Начальную точку х(0)  ;

                                           2. Условие окончания поиска. Перейти к шагу 2.

Шаг 2. Вычислить направление поиска в виде антиградиента функции

s(x(k) ) = - f(x(k) );

. Перейти к шагу 3.

    Шаг 3. Найти новое приближение

          , где  - величина шага относительно

текущего приближения. Перейти к шагу4.

     Шаг 4. Проверка условия окончания поиска.

                            Да: закончить поиск;

                            Нет: перейти к шагу 2.

Ход решения:

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

Шаг 1.

- начальная точка (начальное приближение);

       Вычислим компоненты градиента:

Шаг 2.

Шаг 3. Начальное приближение

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

Шаг 2.

       

Выбираем  такое, чтобы минимизировать функцию

Шаг 3.

2. Далее найдем точку:

Шаг 2.

Шаг 3.

3. Далее найдем точку:

Шаг 2.

Шаг 3.

       

4. Далее найдем точку:

Шаг 2.

Шаг 3.

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

 

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

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

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

            

Описание алгоритма:

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

, где:

- гессиан (матрица Гессе)

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

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

Шаг 1. Задать: начальную точку х(0). Перейти к шагу 2.

Шаг 2. Вычислить направление поиска в виде

 s(x(k)) = – .

Шаг 3. Найти новое приближение (являющееся решением задачи для квадратичной функции)

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

Шаг 4. Проверка на условие окончания вычислений.

Да: закончить процесс;

Нет: перейти к шагу 2.

Ход решения:

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

       - целевая функция;

Шаг 1.

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

Шаг 2.

       

Шаг 3.

;

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

Рис 6. Графическое пояснение метода Ньютона

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

Описание алгоритма:

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

Операции аргумента проводятся по формуле:

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

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

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

Используемые в методе формулы:

Изменение градиента при переходе от точки  к точке :

Изменения аргумента:

Направление поиска:

,  ,  .

(рекуррентная формула Флетчера-Ривса).

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

Шаг 1. Задать:   начальную точку х(0). Перейти к шагу 2.

Шаг 2. Вычислить направление поиска. Произвести поиск вдоль прямой .  

Шаг 3. Вычислено ли N-1 направлений.

                                       Да: закончить поиск;

                                       Нет: перейти к шагу 2.

Ход решения:

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

        

Шаг 1.

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

       

       

Шаг 2.

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

Шаг 2.

Определим направление :

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

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

Рис 7. Графическое пояснение метода сопряженных градиентов.

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

Описание алгоритма:

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

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

, где  - матрица порядка  (метрика).

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

, где:

(1)

Где  изменение градиента на предыдущем шаге.

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

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

Шаг 1. Задать:   начальную точку х(0). Перейти к шагу 2.

Шаг 2. Вычислить направление поиска s(k). Перейти к шагу 3.

Шаг 3. Произвести поиск вдоль прямой . Перейти

к шагу 4.

Шаг 4. Проверка условия окончания поиска.

                                      Да: закончить поиск;

                                      Нет: перейти к шагу2.

Ход решения:

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

- целевая функция;

Шаг 1.

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

      

Шаг 2.

Положим

Шаг 3.

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

Шаг 2.

Шаг 3.

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

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

Рис 8. Графическое пояснение квазиньютоновского метода

Нахождение условного экстремума методом штрафных функций.

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

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

Пусть исходная задача имеет следующий вид:

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

Тогда преобразованная задача определится выражением:

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

Виды штрафов:

Квадратичный штраф имеет вид: . Этот вид штрафов используется для учёта ограничений - равенств. Функция  непрерывна и имеет непрерывную производную, откуда следует, что если непрерывны и дифференцируемы  и , то стационарную точку можно найти аналитически.

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

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

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

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

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

, где

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

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

Шаг 1. Задать начальные данные:

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

- начальное значение штраф параметра

- параметр окончания работы алгоритма

Шаг 2. Построить штрафную функцию:

Шаг 3. Находим , доставляющее экстремум , методом Ньютона.

Шаг 4.  Выполняется ли условие:

Да: , процесс решения закончен.

Нет: перейти к шагу 5.

Шаг 5. , перейти к шагу 2.

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

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

Шаг 1.

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

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

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

Шаг 2.

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

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

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

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

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

Шаг 5,2-3.

1.

2.

3.

4.

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

-18.443

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

Рис 9. Графическое пояснение метода штрафных функций

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

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

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

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

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

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

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


Заключение

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

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


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

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


 

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

60915. Основи САПР 4.18 MB
  Мета дисципліни є ознайомлення з загальними принципами проектування, класифікацією сучасних систем автоматизованого проектування та навчання студентів принципам побудови, функціонування та особливостям роботи з програмними засобами розробки електротехнічних пристроїв і електромеханічних систем.
60917. Крыша. Устройство крыши 4.92 MB
  Поэтому архитекторы и строители уделяют особенное внимание проектированию и монтажу кровли. Несмотря на это при сооружении конкретной кровли возникает огромное количество трудностей. Конструкция крыши и выбор кровельного материала определяется на стадии проекта и зависит от дизайна фасада здания и технологии настила кровли. Кровля из штучных материалов отличается наличием в ней специфических элементов которые присущи только такому типу кровли и предусмотрены для обеспечения ее надежности в процессе эксплуатации.
60918. Оцінка продуктів харчування за їхнім хімічним складом. Ознайомлення з інструкціями з використання окремих хімічних речовин як медичних препаратів, засобів побутової хімії тощо та оцінка їхньої небезпеки 210.5 KB
  Мета: Навчитися користуватися інструкціями до медикаментів вивчити цінність харчових продуктів скласти свій добовий харчовий раціон і визначити його хімічний склад на основі отриманих знань...
60919. Складання плану уроку виробничого навчання 50.5 KB
  Обладнання: плануюча документація майстра виробничого навчання методичний посібник Школа молодого майстра1 інструкція Підготовка майстра виробничого навчання до уроку додаток...