Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
ВЯТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
Вечерне-заочный факультет
Кафедра автоматики и телемеханики
Пояснительная записка
курсовая работа по дисциплине
"методы оптимизации"
ТПЖА
Разработал студент:
Руководитель: к.т.н., доцент Микрюкова В.И.
Работа завершена с оценкой:
Члены комиссии:
Киров
2012 год
Задание на курсовую работу по дисциплине
"методы оптимизации".
ТЕМА: Методы безусловной оптимизации функции нескольких
переменных.
Студент: ____________ 10-УИ-522
1.Введение.
2.Исходные данные, нахождение стационарной точки.
3.Нахождение безусловного экстремума методами прямого поиска
3.1.Метод поиска по симплексу.
3.2.Метод поиска Хука-Дживса.
3.3.Метод сопряженных направлений Пауэлла.
4.Нахождение безусловного экстремума градиентными методами.
4.1.Метод Коши.
4.2.Метод Ньютона.
4.3.Метод сопряженных градиентов.
4.4.Квазиньютоновский метод.
5.Заключение.
руководитель работы: Микрюкова В.И.
задание принял:
Содержание
Введение……………………………………………………………………………..
2.1.Метод поиска по симплексу....…………………………………………….
2.2.Метод поиска Хука-Дживса................................................…………….
2.3.Метод сопряженных направлений Пауэлла......……………………….
3.1. Метод Коши..............................................................................................
3.2Метод Ньютона........................................................................................
3.3.Метод сопряженных градиентов............................................................
3.4.Квазиньютоновский метод.......................................................................
4.Заключение……………………………………………………………………...
5.Библиографический список………....................……………………………..
Лист.
ТПЖА
Дата
Подпись
№ докум.
Лист
Изм.
Листов
Лист
Методы
безусловной
оптимизации
Провер.
Микрюкова В.И.
Разраб.
Реценз.
Н. Контр.
Утверд.
кафедра АТ
гр. УИ , 3 к., з/о
4
Введение
Оптимизация как раздел математики существует достаточно давно. Оптимизация - это выбор, т.е. то, чем постоянно приходится заниматься в повседневной жизни. Термином "оптимизация" в литературе обозначают процесс или последовательность операций, позволяющих получить уточненное решение. Конечной целью оптимизации является отыскание наилучшего или "оптимального" решения.
Практика порождает все новые и новые задачи оптимизации причем их сложность растет. Требуются новые математические модели и методы, которые учитывают наличие многих критериев, проводят глобальный поиск оптимума. Реальные прикладные задачи оптимизации очень сложны. Современные методы оптимизации далеко не всегда справляются с решением реальных задач без помощи человека.
Оптимизационные методы минимизации и максимизации приобретают всё большую ценность и востребованность.
Методы оптимизации эффективно применяются в самых различных областях человеческой деятельности. Значительные успехи достигнуты при решении задач синтеза и анализа систем различного целевого назначения. Ускоренные темпы теоретических разработок в инженерную практику в существенной степени обусловлены широким распространением и совершенствованием средств вычислительной техники.
В настоящее время для инженера знание методов оптимизации также необходимо, как знание основ математического анализа, физики, радиоэлектроники и других дисциплин.
Целевая функция:
Для того, чтобы в точке функция f(x) имела безусловный локальный экстремум необходимо, чтобы все её частные производные обращались в точке в нуль.
Найдем для данной целевой функции частные производные
по и :
Приравняв полученные выражения к нулю, получим систему уравнений:
Решение системы уравнений даёт результат:
Таким образом, экстремум целевой функции является точка с координатами х* =Т, значение целевой функции, в которой: .
Для определения характера стационарной точки составим определитель матрицы Гессе. Под определителем Гессе понимается определитель, составленный из вторых производных исходной целевой функции.
Так как гессиан функция - положительно определенная матрица (выполняются условия Сильвестра: все диагональные элементы матрицы Гессе - положительные величины, все ведущие главные определители положительные величины), стационарная точка является точкой минимума.
рис.1 линии уровня функции и точка экстремума x*
2.Методы прямого поиска безусловной оптимизации
Задача безусловной оптимизации состоит в нахождении минимума или максимума функции в отсутствие каких-либо ограничений. Несмотря на то что большинство практических задач оптимизации содержит ограничения, изучение методов безусловной оптимизации важно с нескольких точек зрения. Многие алгоритмы решения задачи с ограничениями предполагают сведение ее к последовательности задач безусловной оптимизации. Другой класс методов основан на поиске подходящего направления и последующей минимизации вдоль этого направления. Обоснование методов безусловной оптимизации может быть естественным образом распространено на обоснование процедур решения задач с ограничениями.
2.1. Метод поиска по симплексу
Описание алгоритма:
Суть метода заключается в исследовании целевой функции в вершинах некого "образца", построенного в пространстве вокруг "базовой" точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве - тетраэдр.
Работа алгоритма начинается с построения регулярного симплекса в пространстве независимых переменных и оценивания значений целевой функции в каждой точке. Затем определяется вершина с максимальным значением целевой функции и проектируется через центр тяжести оставшихся вершин в новую точку.
Процедура продолжается до тех пор, пока не будет накрыта точка минимума.
Некоторые правила:
1. Если вершина с максимальным значением целевой функции построена на предыдущем шаге, то отбрасывается вершина со следующим по величине значением целевой функции.
2. Если вокруг одной из вершин начинается циклическое движение, то необходимо уменьшить размеры симплекса.
Поиск заканчивается тогда, когда размеры симплекса или разность значений целевой функции становятся достаточно малыми.
При заданной начальной точке и масштабном множителе , координаты остальных вершин симплекса в - мерном пространстве вычисляются по формуле:
Приращения и определяется по формулам:
Величина выбирается исследователем, исходя из характеристики решаемой задачи. При ребро симплекса имеет единичную длину.
Вычисление центра тяжести:
Если - точка, подлежащая отражению, то координаты центра тяжести определяются по формуле:
Координаты новой вершины удовлетворяют уравнению:
Для того чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, т.е.
Если некоторая вершина симплекса не исключается на протяжении нескольких итераций, то необходимо уменьшить размер симплекса и построить новый симплекс, выбрав в качестве базовой точку с минимальным значением целевой функции.
Алгоритм метода:
Шаг 1. Задать: 1. Начальную точку х(0) ;
2. Масштабный множитель α;
3. Приращения δ1 и δ2 ;
4.Условие окончания поиска. Перейти к шагу 2.
Шаг 2. Вычислить координаты вершин х(1) и х(2) симплекса. Перейти к
шагу 3.
Шаг 3. Определить значения целевой функции в вершинах симплекса. Перейти к шагу 4.
Шаг 4. Вершина, которой соответствует наибольшее значение целевой функции , построена на предыдущей итерации?
Да: отображается вершина, которой соответствует следующее по величине значение целевой функции
Нет: отображается точка с наибольшим значением целевой функции относительно двух других вершин симплекса. Перейти к шагу 5.
Шаг 5. Проверка на условие окончания.
Да: закончить поиск; результат- точка с наименьшим значением целевой функции;
Нет: перейти к шагу 3.
Ход решения :
Исходные данные:
- целевая функция;
- начальная точка;
- масштабный множитель;
Пусть масштабный множитель -
;
Вычисляем координаты двух других вершин симплекса
Значения целевой функции в этих точках соответственно равны:
Так как в точке целевая функция принимает максимальное значение, то необходимо отразить точку относительно центра тяжести остальных вершин симплекса.
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Наблюдается циклическое движение вокруг точки . Для получения более точного решения необходимо уменьшить размер симплекса.
Уменьшаем размер симплекса.
Пусть масштабный множитель -
В качестве новой базисной точки, примем точку . Вычислим координаты остальных двух вершин базиса:
Так как в точке целевая функция принимает максимальное значение, то необходимо отразить точку относительно центра тяжести остальных вершин симплекса.
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Наблюдается циклическое движение вокруг точки . При данных условиях, точку можно считать точкой экстремума. Для получения более точного решения необходимо уменьшить размер симплекса.
Искомая точка:
рис.2 Графическое пояснение к методу поиска по симплексу
2.2. Метод поиска Хука-Дживса
Описание алгоритма:
Процедура Хука-Дживса представляет собой комбинацию "исследующего" поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление направления вдоль "оврагов". Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по "оврагам".
Исследующий поиск:
Для проведения исследующего поиска необходимо задать величину шага, которая может быть различна для разных координатных направлений, и изменяться в процессе поиска. Поиск начинается в некоторой исходной точке. Делается пробный шаг вдоль одного из координатных направлений. Если значение целевой функции в пробной точке меньше, чем в исходной, то шаг считается удачным. В противном случае возвращаются в исходную точку и делают шаг в противоположном направлении. После перебора всех координат исследующий поиск заканчивается. Полученную в результате исследующего поиска точку называют базовой.
Поиск по образцу:
Поиск по образцу заключается в реализации единственного шага из полученной базовой точки вдоль прямой, соединяющей эту точку с предыдущей базовой точкой. Новая точка определяется по формуле:
Как только движение по образцу не приводит к уменьшению целевой функции, точка фиксируется в качестве временной базовой точки и выполняется исследующий поиск. При уменьшении значения целевой функции эта точка рассматривается как базовая точка. Если же исследующий поиск не дал результата, необходимо вернуться в предыдущую точку и провести исследующий поиск заново. Если такой поиск не приводит к успеху, то необходимо уменьшить величину шага. Поиск завершается, когда величина шага приращения становится достаточно малой.
Алгоритм метода:
Шаг 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.):
Шаг 6. Исследующий поиск вокруг точки :
фиксируя , даём приращение переменной :
; ; - поиск удачен;
; ; - поиск неудачен;
; ; - поиск неудачен;
Шаг 7.
Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :
Шаг 6. Исследующий поиск вокруг точки :
фиксируя , даём приращение переменной :
; ; - поиск удачен;
; ; - поиск неудачен;
; ; - поиск удачен;
Шаг 7.
Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :
Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск (Шаг 6.):
Исследующий поиск вокруг базовой точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск удачен;
Шаг 7.
Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :
Шаг 6. Исследующий поиск вокруг точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск удачен;
Шаг 7.
Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :
Шаг 6. Исследующий поиск вокруг точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск неудачен;
В результате исследующего поиска не было достигнуто уменьшение значения целевой функции, то есть значение шага (векторной величины приращения) уменьшить в раз, до величины , затем необходимо произвести исследующий поиск вокруг точки , используя новое значение приращения .
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск удачен;
Шаг 7.
Шаг 5. Так как поиск удачен, то переходим к поиску по образцу (Шаг 5.) :
Значение целевой функции увеличилось, поэтому возьмём последнюю точку за временную базовую и проведём исследующий поиск (Шаг 6.):
Исследующий поиск вокруг базовой точки :
фиксируя , даём приращение переменной :
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск неудачен;
; ; - поиск неудачен;
В результате исследующего поиска не было достигнуто уменьшение значения целевой функции, то есть значение шага (векторной величины приращения) уменьшить в раз, до величины , затем необходимо произвести исследующий поиск вокруг точки , используя новое значение приращения .
Итерации продолжаются, пока величина шага не укажет на окончание поиска в окрестности точки минимума.
рис.3 Графическое пояснение метода Хука-Дживса
2.3. Метод сопряженных направлений Пауэлла
Описание алгоритма:
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, что если квадратичная функция:
приводится к виду сумма полных квадратов
то процедура нахождения оптимального решения сводится к одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде:
вдоль направлений , , называемых -сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции переменных необходимо выполнить одномерных поисков.
Алгоритм метода:
Шаг 1. Задать исходные точки , и направление . В частности, направление может совпадать с направлением координатной оси;
Шаг 2. Произвести одномерный поиск из точки в направлении получить точку , являющуюся точкой экстремума на заданном направлении;
Шаг 3. Произвести одномерный поиск из точки в направлении получить точку ;
Шаг 4. Вычислить направление ;
Шаг 5. Провести одномерный поиск из точки (либо ) в направлении с выводом в точку .
Ход решения:
Исходные данные:
Шаг 1.
- начальная точка
Шаг 2.
а) Найдем значение , при котором минимизируется в направлении :
Откуда ;
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
б) Аналогично находим значение минимизирующее функцию
в направлении :
Откуда ; .
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
в) Найдем значение минимизирующее :
Откуда ; .
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , получим:
. Приравняв его к нулю, находим ;
Получили
Шаг 3.
Шаг4. Найдем такое значение , при котором минимизируется в направлении .
Откуда ; .
Значение функции в этой точке: ;
Продифференцируем полученное выражение по , и приравняем его к нулю, находим ;
Получили
Таким образом, получили точку , значение функции в которой равно , что максимально приближено к стационарной точке.
рис.4 Графическое пояснение метода сопряженных направлений Пауэлла
3.Нахождение безусловного экстремума
градиентными методами
В отличии от методов прямого поиска градиентные методы поиска используют информацию о производных функции. Это позволяет уменьшить
количество необходимых вычислений значений функции. Эти методы делятся на две группы: методы, использующие информацию только о первых производных , и методы, учитывающие информацию и первых, и вторых производных.
3.1. Метод Коши
Описание алгоритма:
В методе Коши или методе наискорейшего спуска в качестве направления поиска выбирается направление антиградиента.
- градиент функции
Алгоритм метода выглядит следующим образом:
, где - градиент.
Значение на каждой итерации вычисляется путем решения задачи одномерного поиска экстремума вдоль направления градиента . Если в качестве взять некоторое положительное число, то получится простейший градиентный алгоритм:
Одно из главных достоинств метода Коши является его устойчивость, так как всегда выполняется условие:
Однако вблизи экстремума скорость сходимости алгоритма становится недопустимо низкой, так как вблизи экстремума значение градиента стремится к нулю.
Алгоритм метода:
Шаг 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 Графическое пояснение метода Коши
3.2. Метод Ньютона
Описание алгоритма:
Этот метод использует информацию о вторых производных целевой функции. Эта информация появляется при квадратичной аппроксимации целевой функции, когда при её разложении в ряд Тейлора учитываются члены ряда до второго порядка включительно. Алгоритм метода выглядит следующим образом:
, где:
- гессиан (матрица Гессе)
В случае, когда гессиан положительно определён, направление по методу Ньютона оказывается направлением спуска.
Алгоритм метода:
Шаг 1. Задать: начальную точку х(0). Перейти к шагу 2.
Шаг 2. Вычислить направление поиска в виде
s(x(k)) = – .
Шаг 3. Найти новое приближение (являющееся решением задачи для квадратичной функции)
x(k+1) = x(k) + s(x(k)) = x(k) –.
Шаг 4. Проверка на условие окончания вычислений.
Да: закончить процесс;
Нет: перейти к шагу 2.
Ход решения:
Исходные данные:
- целевая функция;
Шаг 1.
- начальная точка;
Шаг 2.
Шаг 3.
;
Таким образом, точка минимума , значение функции в которой найдена за одну итерацию.
рис.6 Графическое пояснение метода Ньютона
3.3. Метод сопряженных градиентов
Описание алгоритма:
Данный метод обладает положительными свойствами методов Коши и Ньютона. Кроме того, этот метод использует информацию только о первых производных исследуемой функции. Метод сопряженных градиентов позволяет получить решение за шагов в -мерном пространстве и обладает квадратичной сходимостью. В основе метода лежит организация поиска вдоль сопряженных направлений, причем для получения сопряженных направлений используется квадратичная аппроксимация целевой функции и значения компонент градиента.
Операции аргумента проводятся по формуле:
Направление поиска на каждой итерации определяется с помощью формулы:
В этом случае направление будет -сопряжено со всеми ранее построенными направлениями поиска.
Если функция квадратичная, то для нахождения точки экстремума требуется определить таких направлений и провести поиски вдоль каждой прямой. Если не является квадратичной, то количество поисков возрастёт.
Используемые в методе формулы:
Изменение градиента при переходе от точки к точке :
Изменения аргумента:
Направление поиска:
, , .
(рекуррентная формула Флетчера-Ривса).
Алгоритм метода:
Шаг 1. Задать: начальную точку х(0). Перейти к шагу 2.
Шаг 2. Вычислить направление поиска. Произвести поиск вдоль прямой .
Шаг 3. Вычислено ли N-1 направлений.
Да: закончить поиск;
Нет: перейти к шагу 2.
Ход решения:
Исходные данные:
Шаг 1.
- начальная точка;
Шаг 2.
Поиск вдоль прямой:
отсюда: ; .
. Приравняв его к нулю, находим
Шаг 2.
Определим направление :
Поиск вдоль прямой:
отсюда: ; .
. Приравняв его к нулю, находим
Таким образом, решение (точка минимума) , значение функции в которой , получено в результате двух одномерных поисков, поскольку целевая функция квадратична.
рис.7 Графическое пояснение метода сопряженных градиентов
3.4 Квазиньютоновский метод
Описание алгоритма:
Данный метод обладает положительными чертами метода Ньютона, однако, использует информацию только о первых производных. В этом методе приближение к очередной точке в пространстве оптимизируемых параметров задается формулой:
Направление поиска определяется выражением:
, где - матрица порядка (метрика).
Матрица - вычисляется по формуле.
, где:
Где изменение градиента на предыдущем шаге.
Данный алгоритм отличается устойчивостью, так как обеспечивает убывание целевой функции от итерации к итерации.
Алгоритм метода:
Шаг 1. Задать: начальную точку х(0). Перейти к шагу 2.
Шаг 2. Вычислить направление поиска s(k). Перейти к шагу 3.
Шаг 3. Произвести поиск вдоль прямой . Перейти
к шагу 4.
Шаг 4. Проверка условия окончания поиска.
Да: закончить поиск;
Нет: перейти к шагу2.
Ход решения:
Исходные данные:
- целевая функция;
Шаг 1.
- начальная точка;
Шаг 2.
Положим
Шаг 3.
Поиск вдоль прямой:
Шаг 2.
Шаг 3.
Поиск вдоль прямой:
Таким образом, точка минимума , значение функции в которой найдена за одну итерацию.
рис.8 Графическое пояснение квазиньютоновского метода
Заключение.
Анализируя результаты исследования (сравнения) всех рассмотренных выше методов, можно прийти к выводу о том, что каждый из них имеет свои достоинства и недостатки и более применим для задач одних видов и менее – для других. Однако, пользователь всегда сможет найти подходящий алгоритм для решения своей конкретной проблемы, выбирая как из вышеприведенного множества методов, так и из огромного спектра их модифицированных, усовершенствованных и комбинированных вариантов.
Однако, есть целый класс проблем, где найти оптимум либо крайне сложно, либо вообще невозможно получить точное решение с помощью алгоритмов данных категорий. К таким задачам относится, например, моделирование глобальных социально-экономических процессов.
При реализации алгоритмов также возникает много дополнительных обстоятельств, строгий учет которых невозможен (ошибки округления, приближенное решение различных вспомогательных задач и т.д.) и которые могут сильно повлиять на ход процесса.
Поэтому на практике часто сравнение алгоритмов проводят с помощью вычислительных экспериментов при решении так называемых специальных тестовых задач. Эти задачи могут быть как с малым, так и с большим числом переменных, иметь различный вид нелинейности. Они могут быть составлены специально и возникать из практических приложений, например задача минимизации суммы квадратов, решение систем нелинейных уравнений и т.п.
Библиографический список:
Реферат
Талантов А.С. Методы безусловной оптимизации функции нескольких переменных: ТПЖА 220201.022 ПЗ: 3 курс. работа/ ВятГУ, каф. АТ; рук. В.И. Микрюкова. - Киров 2012. ПЗ 32 с, 8 рис, 3 источников.
Оптимизация, экстремум, метод, прямой поиск, градиент, симплекс, сопряженные направления, безусловная оптимизация, матрица Гессе, частные производные, аппроксимация, масштабный множитель, центр тяжести.
Объект разработки:
методы безусловной оптимизации.
Цель работы:
исследовать методы поиска в нахождении безусловного экстремума функции двух
переменных.
Результат работы:
исследованы методы прямого поиска и градиентные методы безусловной оптимизации по заданным исходным данным целевой функции и начальной точки поиска. Приведены графики для каждого метода.