Методы безусловной оптимизации
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ
Федеральное государственное бюджетное образовательное учреждение
высшего профессионального образования
Вятский государственный университет
Вечерне-заочный факультет
Решение задач многомерной оптимизации
Пояснительная записка
Курсовая работа по дисциплине
«Методы оптимизации»
ТПЖА.220201.623 ПЗ
Разработал студент гр. 21-УТ ______________________________
(подпись)
Руководитель работы
(подпись)
Киров 2012
Содержание
Введение…………………………………………………………
1 Методы безусловной оптимизации…………….…………………..…...
1.1 Методы прямого поиска…..……....
1.1.1 Нахождение стационарной точки…
1.1.2 Метод поиска по симплексу………………………............
1.1.3 Метод Хука-Дживса…………………………………………………
1.1.4 Метод сопряженных направлений Пауэлла………………………….17
1.2 Градиентные методы………………………….…
1.2.1 Метод Коши……………………………………………………
1.2.2 Метод Ньютона………………………………………………………..
1.2.3 Метод сопряженных градиентов …………….........................
1.2.4 Квазиньютоновский метод.………………….................
Заключение……………………………………………………
Список
литературы……………………………………………………
Введение
Необходимость
решения задач оптимизации
Задачи
нахождения оптимального решения являются
самыми распространенными на сегодняшний
день. Из-за увеличения объемов производства,
люди вынуждены решать сколько потратить
ресурсов на тот или иной проект,
ведь на все задуманное ресурсов стало
не хватать. Во многих странах производится
строгий учет потребления природных
и человеческих ресурсов, а следовательно
необходимо каждый день находить новые
способы решения задач по оптимизации
различных процессов. Особо остро
стоит проблема коммуникаций в городах.
Под коммуникациями можно рассматривать
не только телефоны, факсы и прочие
устройства, но также и транспортные
коммуникации и компьютерные сети.
Для последних особенно характерна
проблема «трафика», так как существующие
линии не способны обеспечить передачу
необходимых объемов
Оптимальная задача – экономико-математическая задача, содержащая критерий оптимальности и ограничения, то есть направленная на поиск лучшего в определенных условиях (оптимального) значения показателя.
Из всего выше написанного следует, что характерной тенденцией в построении современных систем автоматического управления является стремление получить системы, которые в некотором смысле являются наилучшими. При управлении компьютерными сетями это стремление выражается в том, чтобы получать максимальные объемы требуемой информации за наименьшее время при ограниченных пропускных способностях кабелей и коммуникаторов.
В системах
управления кораблями, самолетами, ракетами
стремятся минимизировать время, по
истечении которого объект выходит
в заданную точку или на заданную
траекторию при ограничении угла
отклонения рулей, количества расходуемого
топлива и т.п. В следящих и
стабилизирующих системах представляет
интерес достижения максимальной точности
при наличии возможных
Данная работа рассматривает некоторые методы нахождения безусловного экстремума (метод Коши, Хука-Дживса, Ньютона и др.) для функции двух переменных.
1 Методы безусловной оптимизации
- Методы прямого поиска
1.1.1 Нахождение стационарной точки
Целевая функция:
Для того, чтобы в точке функция f(x) имела безусловный локальный экстремум необходимо, чтобы все её частные производные обращались в точке в нуль.
Найдем для данной целевой функции частные производные
по и :
Приравняв полученные выражения к нулю, получим систему уравнений:
Решение системы уравнений даёт результат:
Таким образом,
экстремум целевой функции
Для определения характера стационарной точки составим определитель матрицы Гессе. Под определителем Гессе понимается определитель, составленный из вторых производных исходной целевой функции.
Так как
гессиан функция - положительно определенная
матрица (выполняются условия
Рисунок.1-Линии уровня функции и стационарная точка
1.1.2 Метод поиска по симплексу
Суть метода заключается в исследовании целевой функции в вершинах некого «образца», построенного в пространстве переменных вокруг «базовой» точки. Вершина, давшая наибольшее значение целевой функции отображается относительно двух других вершин и таким образом становится новой базовой точкой, вокруг которой строится новый образец и снова выполняется поиск. В рассматриваемом методе таким образцом является регулярный симплекс. В случае двух переменных симплексом является равносторонний треугольник, в трёхмерном пространстве – тетраэдр.
Работа
алгоритма начинается с построения
регулярного симплекса в
Процедура продолжается до тех пор, пока не будет накрыта точка минимума.
Некоторые правила:
1. Если вершина с максимальным значением целевой функции построена на предыдущем шаге, то отбрасывается вершина со следующим по величине значением целевой функции.
2. Если
вокруг одной из вершин
Поиск заканчивается тогда, когда размеры симплекса или разность значений целевой функции становятся достаточно малыми.
При заданной начальной точке х(0) и масштабном множителе a, координаты остальных N вершин симплекса в N–мерном пространстве вычисляются по формуле:
xj(0) + d1, если i = j;
x(i) =
xj(0) + d2, если i ¹ j.
Приращения d1 и d2 определяются по формулам:
,
.
Величина
α выбирается исследователем, исходя
из характеристики решаемой задачи. При
α=1 ребро симплекса имеет
Вычисление центра тяжести:
Если х(i) – точка, подлежащая отражению, то координаты центра тяжести определяется по формуле:
.
Координаты новой вершины удовлетворяют уравнению
xнов( j ) = x( j ) + λ·(xc – x( j )).
Для того, чтобы симплекс обладал свойством регулярности, отображение должно быть симметричным, т.е. λ = 2.
xнов( j ) = 2·xc – x( j )
Если некоторая вершина симплекса не исключается на протяжении нескольких итераций, то необходимо уменьшить размер симплекса и построить новый симплекс, выбрав в качестве базовой точку с минимальным значением целевой функции.
Нахождение
минимума целевой функции симплекс-
Задание:
Найти минимум функции
Решение:
Для построения исходного симплекса необходимо задать начальную точку и масштабный множитель. Пусть .
Тогда:
Вычисляем координаты двух других вершин симплекса
Значения целевой функции в этих точках соответственно равны:
Так как в точке целевая функция принимает максимальное значение, то необходимо отразить точку относительно центра тяжести остальных вершин симплекса.
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке , т.е. наблюдается уменьшение целевой функции. Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку относительно центра тяжести точек и
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Наблюдается циклическое движение вокруг точки . Для получения более точного результата уменьшаем размер симплекса.
Уменьшаем размер симплекса.
В качестве новой базисной точки, примем точку . Вычислим координаты остальных двух вершин базиса:
Так как в точке целевая функция принимает максимальное значение, то необходимо отразить точку относительно центра тяжести остальных вершин симплекса.
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Следует отразить точку относительно центра тяжести точек и .
В полученной точке . Новый симплекс образован вершинами , причём точке соответствует максимальное значение целевой функции. Но она построена на предыдущем шаге. Наблюдается циклическое движение вокруг точки . Завершаем поиск.
Искомая точка:
Для получения более точного результата необходимо уменьшить размер симплекса.
Решение поставленной задачи симплекс методом представлено на рисунке 2.
Рисунок 2 – Решение задачи симплекс-методом |
1.1.3 Метод Хука-Дживса
Процедура Хука-Дживса представляет собой комбинацию “исследующего” поиска с циклическим изменением переменных и ускоряющего поиска по найденному образцу. Исследующий поиск ориентирован на выявление характера локального поведения целевой функции и определение направления вдоль “оврагов”. Полученная в результате исследующего поиска информация используется затем в процессе поиска по образцу при движении по “оврагам”.
Исследующий поиск:
Для проведения
исследующего поиска необходимо задать
величину шага, которая может быть
различна для разных координатных направлений,
и изменяться в процессе поиска.
Поиск начинается в некоторой
исходной точке. Делается пробный шаг
вдоль одного из координатных направлений.
Если значение целевой функции в
пробной точке меньше, чем в
исходной, то шаг считается удачным.
В противном случае возвращаются
в исходную точку и делают шаг
в противоположном направлении.
После перебора всех N координат
исследующий поиск
Поиск по образцу:
Поиск по
образцу заключается в
xр(к + 1) = x(к) + [x(к) - x(к - 1)].
Как только
движение по образцу не приводит к
уменьшению целевой функции, точка
xр(к + 1) фиксируется в качестве
временной базовой точки и
выполняется исследующий поиск.
При уменьшении значения целевой
функции эта точка
Шаг1. Задать:
1. Начальную точку х(0);
2. Приращение Di , i=1,2…,N;
3. Коэффициент уменьшения шага a>1;
4. Параметр окончания поиска e>0.
Шаг2. Произвести исследующий поиск.
Шаг3. Поиск удачный
Да: Перейти к шагу 5;
Нет: продолжить.
Шаг4. Проверка на окончание поиска. ||D||<e ?
Да: прекратить поиск;
Нет: уменьшить приращение по формуле Di=Di/a, i=1,2…N;
Перейти к шагу 2.
Шаг5. Провести поиск по образцу xр(к + 1) = x(к) + [x(к) - x(к - 1)]
Шаг6. Провести исследующий поиск, используя xр(к + 1) в качестве базовой точки ; x(к + 1) - полученная в результате точка.
Шаг7. Выполняется ли f(x(k+1))<f(x(k))?
Да: положить x(к - 1)= хк; xк= x(к + 1);
Перейти к шагу 5;
Нет: Перейти к шагу 4.
Нахождение минимума целевой функции методом Хука-Дживса.
Исходные данные:
Для того, чтобы применить данный метод необходимо задать следующие величины:
Итерации начинаются с исследующего поиска вокруг точки , которой соответствует значение функции
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Таким образом, в результате исследующего поиска была найдена точка
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать успешным и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать удачным, и становится новой базовой точкой при следующем проведении поиска по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать неудачным,
отбрасывается и становится новой базовой точкой при следующем проведении исследующего поиска :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Исследующий поиск не дал результатов, поэтому уменьшаем шаг: , базовая точка
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку исследующий поиск был удачным, переходим к поиску по образцу:
Далее производим исследующий поиск вокруг точки :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Получаем новую точку:
Поскольку , поиск по образцу следует считать неудачным,
отбрасывается и становится новой базовой точкой при следующем проведении исследующего поиска :
Фиксируя , даём приращение переменной :
Следовательно, необходимо зафиксировать и дать приращение переменной :
Исследующий поиск не дал результатов, поэтому прекращаем поиск. Искомая точка оптимума:
Решение поставленной задачи методом Хука-Дживса представлено на рисунке 3.
Рисунок 3 – Решение задачи методом Хука-Дживса |
1.1.4 Метод сопряженных направлений Пауэлла
Метод ориентирован на решение задач с квадратичными целевыми функциями. Основная идея алгоритма заключается в том, если квадратичная функция
q(x) = a + bTx + ½ xT C x
приводится к виду суммы полных квадратов
Q(x) = xT C x,
то процедура нахождения оптимального решения сводится к N одномерным поискам по преобразованным координатным направлениям.
В методе Пауэлла поиск реализуется в виде
х(k+1) = x(k) + l×s(j)
вдоль направлений s(j), j = 1,2,...,N, называемых C-сопряженными при линейной независимости этих направлений.
Сопряженные направления определяются алгоритмически. Для нахождения экстремума квадратичной функции N переменных необходимо выполнить N2 одномерных поисков.
Шаг 1. задать исходные точки х(1), х(2) и направление d. В частности, направление d может совпадать с направлением координатной оси;
Шаг 2. произвести одномерный поиск из точки х(1) в направлении d и получить точку y(1), являющуюся точкой экстремума на заданном направлении;
Шаг 3. произвести поиск из точки х(2) в направлении d и получить точку y(2);
Шаг 4. вычислить направление (y(2) – y(1));
Шаг 5. провести одномерный поиск из точки у(1) (либо у(2)) в направлении (y(2) – y(1)) с выходом в точку х*.
Нахождение минимума целевой функции
методом сопряжённых
Исходные данные:
Итерация 1:
- найдём значение , при котором минимизируется в направлении , т.е.
Произвольная точка на луче из точки в направлении определяется как:
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
2) Аналогично находим значение , при котором минимизируется в направлении , т.е.
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Аналогично находим значение , при котором минимизируется в направлении , т.е.
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Положим .
Направление оказывается сопряжённым с направлением . Оптимизация вдоль направления даёт искомый экстремум.
Находим значение , при котором минимизируется в направлении , т.е.
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Итерация 2:
- найдём значение , при котором минимизируется в направлении , т.е.
Произвольная точка на луче из точки в направлении определяется как:
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
2) Аналогично находим значение , при котором минимизируется в направлении , т.е.
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
3)Аналогично находим значение , при котором минимизируется в направлении , т.е.
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Положим .
Направление оказывается сопряжённым с направлением . Оптимизация вдоль направления даёт искомый экстремум.
Находим значение , при котором минимизируется в направлении , т.е.
, откуда , . Подставляя эти значения в выражение целевой функции, получаем:
Дифференцируем по и приравниваем к 0, получаем:
Получаем:
Решение поставленной задачи методом сопряжённых направлений Пауэлла представлено на рисунке 4.
Рисунок 3 – Решение задачи методом сопряжённых направлений Пауэлла |
- Градиентные методы
- Методы борьбы и предотвращение мошенничества
- Методы борьбы и профилактика лесных пожаров
- Методы борьбы с безработицей
- Методы борьбы с вибрацией
- Методы борьбы с детскими страхами
- Методы борьбы с инфляцией
- Методы борьбы с инфляцией
- Методы антикризисного управления предприятием
- Методы антикризисного управления предприятием на основе инновационного развития
- Методы антимонопольной политики
- Методы аппроксимации
- Методы аппроксимации функций
- Методы атомной спектроскопии в анализе почв, природных и промышленных вод
- Методы аудиторского риска
