Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков)
|
Скачать 234.7 Kb.
|
|
Лабораторная работа № 2 Тема: Многомерная безусловная оптимизация (методы первого и нулевого порядков). Цель работа: знакомство с методами многомерной безусловной оптимизации первого и нулевого порядка и их освоение, сравнение эффективности применения этих методов конкретных целевых функций.
Задача многомерной безусловной оптимизации формулируется в виде: min f(x), xX где x={x(1), x(2),…, x(n)} – точка в n-мерном пространстве X=IRn, то есть целевая функция f(x)=f(x(1),…,f(x(n)) – функция n аргументов. Так же как и в первой лабораторной работе мы рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {xk}, удовлетворяющих условию f(x0)>f(x1)>…>f(xn)>… . Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {xk} вычисляются по формуле: хk+1 = xk + kpk, k=0,1,2,… , где pk – направление спуска, k – длина шага в этом направлении. Различные методы спуска отличаются друг от друга способами выбора направления спуска pk и длины шага k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции, относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д. 1.2. Градиентные методы. 1.2.1. Общая схема градиентного спуска. Как известно, градиент функции в некоторой точке xk направлен в сторону наискорейшего локального возрастания функции и перпендикулярен линии уровня (поверхность постоянного значения функции f(x), проходящей через точку xk). Вектор, противоположный градиенту , называется антиградиентом, который направлен в сторону наискорейшего убывания функции f(x). Выбирая в качестве направления спуска pk антиградиент -в точке xk, мы приходим к итерационному процессу вида: xk+1 = xk - k f’(xk), k>0, k=0,1,2,… . В координатной форме этот процесс записывается следующим образом: Все итерационные процессы, в которых направление движения на каждом шаге совпадает с антиградиентом функции, называются градиентными методами. Они отличаются друг от друга только способом выбора шага k. Существует много различных способов выбора k, но наиболее распространены: метод с постоянным шагом, метод с дроблением шага и метод наискорейшего спуска. 1.2.2. Градиентный метод с постоянным шагом. Основная проблема в градиентных методах – это выбор шага k. Достаточно малый шаг k обеспечивает убывание функции, то есть выполнение неравенства: f(xk - k( xk))) < f(xk), но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка условия убывания на каждой итерации является довольно трудоемкой, поэтому в методе градиентного спуска с постоянным шагом задают =k постоянным и достаточно малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим количеством итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент ). Схема алгоритма Шаг 1. Задаются начальное приближение х0, постоянный шаг , условия останова алгоритма 3. Вычисляется значение градиента – направление поиска. Присваивается к=0. Шаг 2. Определяется точка очередного эксперимента: хк+1 = хк - f’(xk), и ли, в координатной форме: Шаг 3. Вычисляется значение градиента в точке хк+1: , и ли, в координатной форме: Шаг 4. Если ||||3, то поиск заканчивается, при этом: Иначе к=к+1 и переходим к шагу 2. 1.2.3. Градиентный метод с дроблением шага. В методе градиентного спуска с дроблением шага величина шага к выбирается так, чтобы было выполнено неравенство: f(xk-k)-f(xk)-k||||2, где 0<�<1 – произвольно выбранная постоянная (одна и та же для всех итераций). Это требование на выбор шага к более жесткое, чем условие убывания, но имеет тот же смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства. Процесс выбора шага протекает следующим образом. Выбираем число >0, одно и то же для всех итераций. На к-й итерации проверяем выполнение неравенства при к=. Если оно выполнено, полагаем к= и переходим к следующей итерации. Если нет, то шаг к дробим, например уменьшаем каждый раз в два раза, до тех пор, пока оно не выполнится. Схема алгоритма Шаг 1. Задаются х0, 3, и начальное значение шага . Вычисляется значение градиента – направление поиска. Присваивается к=0. Шаг 2. Проверяется условие: f(xk-)-||||2. Если выполняется, то переходим к шагу 3, иначе дробим значение (=/2) и повторяем шаг 2. Шаг 3. Определяется точка очередного эксперимента: хк+1 = хк - . Шаг 4. Вычисляется значение градиента в точке хк+1: . Шаг 5. Если ||||3, то поиск заканчивается, при этом: Иначе к=к+1 и переходим к шагу 2. 1.2.4. Метод наискорейшего спуска. В градиентном методе с постоянным шагом величина шага, обеспечивающая убывание функции f(x) от итерации к итерации, оказывается очень малой, что приводит к необходимости проводить большое количество итерации для достижения точки минимума. Поэтому методы спуска с переменным шагом являются более экономными. Алгоритм, на каждой итерации которого шаг к выбирается из условия минимума функции f(x) в направлении движения, то есть: называется методом наискорейшего спуска. Разумеется, этот способ выбора к сложнее ранее рассмотренных вариантов. Реализация метода наискорейшего спуска предполагает решение на каждой итерации довольно трудоемкой вспомогательной задачи одномерной минимизации. Как правило, метод наискорейшего спуска, тем не менее, дает выигрыш в числе машинных операций, поскольку обеспечивает движение с самым выгодным шагом, ибо решение задачи одномерной минимизации связано с дополнительными вычислениями только самой функции f(x), тогда как основное машинное время тратится на вычисление ее градиента . Следует иметь в виду, что одномерную минимизацию можно производить любым методом одномерной оптимизации, что порождает различные варианты метода наискорейшего спуска. Схема алгоритма Шаг 1. Задаются х0, 3. Вычисляется градиент , направление поиска. Присваивается к=0. Шаг 2. Определяется точка очередного эксперимента: хк+1 = хк - к, где к – минимум задачи одномерной минимизации: Шаг 3. Вычисляется значение градиента в точке хк+1: . Шаг 4. Если ||||3, то поиск точки минимума заканчивается и полагается: Иначе к=к+1 и переход к шагу 2. 1.3.Метод покоординатного спуска. Желание уменьшить объем вычислительной работы, требуемой для осуществления одной итерации метода наискорейшего спуска, привело к созданию методов покоординатного спуска. Пусть - начальное приближение. Вычислим частную производную по первой координате и примем: где е1={1,0,…,0}T – единичный вектор оси х(1). Следующая итерация состоит в вычислении точки х2 по формуле: где е2={0,1,0,…,0}T – единичный вектор оси х(2) и т. д. Таким образом, в методах координатного спуска мы спускаемся по ломанной, состоящей из отрезков прямых, параллельных координатным осям. х(2) Спуск по всем координатам составляет одну «внешнюю» итерацию. Пусть к – номер очередной внешней итерации, а j – номер той координаты, по которой производится спуск. Тогда формула, определяющая следующее приближение к точке минимума, имеет вид: где к=0,1,2,… ; j=1,2,…n. В координатной форме формула выглядит так: После j=n счетчик числа внешних итераций к увеличивается на единицу, а j принимает значение равное единице. Величина шага к выбирается на каждой итерации аналогично тому, как это делается в градиентных методах. Например, если к= постоянно, то имеем покоординатный спуск с постоянным шагом. Схема алгоритма покоординатного спуска с постоянным шагом Шаг 1. При к=0 вводятся исходные данные х0, 1, . Шаг 2. Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки хkn по формуле: Шаг 3. Если ||x(k+1)n – xkn||1, то поиск минимума заканчивается, причем: Иначе к=к+1 и переходим к шагу 2. Если же шаг к выбирается из условия минимума функции: то мы получаем аналог метода наискорейшего спуска, называемый обычно методом Гаусса – Зейделя. Схема метода Гаусса – Зейделя Шаг 1. При к=0 вводятся исходные данные х0, 1. Шаг 2. Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки хkn по формулам: где kn+j-1 является решением задачи одномерной минимизации функции: Шаг 3. Если ||x(k+1)n – xkn||1, то поиск минимума заканчивается, причем: Иначе к=к+1 и переходим к шагу 2. |
Добавить документ в свой блог или на сайт
Похожие:
 |
Лабораторная работа № применение модели rgb в медицинской диагностике... Лабораторная работа № представление и смешение цветов с помощью модели rgb |
|
Тема Методы психолого-педагогических исследований Тема Научно-исследовательская работа магистранта и требования к ее организации и оформлению |
 |
Рабочая программа по дисциплине ен. Р. 1 «Методы моделирования и... Омский институт водного транспорта (филиал) фбоу впо «Новосибирская государственная академия водного транспорта» |
|
Контрольная работа 4 Задание 1 Тема : методы нивелирования Инструкция по нивелированию I, II, III и IV классов. Федеральная служба геодезии и картографии России. М, Картгеоцентр-Геодезиздат,... |
|
Людмила Григорьевна Пучко Жизнь и здоровье человека в вопросах и ответах Многомерной медицины Биолокация для всех», «Многомерная медицина», «Радиэстезическое познание человека», «Многомерный человек», «Многомерная медицина.... |
|
Лабораторная работа №1 Создание и отладка консольных приложений в интегрированной среде ms visual Studio. Net 2005 |
|
Лабораторная работа №2 по дисциплине «Физика-1» Томский государственный университет систем управления и радиоэлектроники (тусур) Факультет дистанционного обучения |
|
Лабораторная работа №7 по дисциплине «Физика-1» Целью работы является изучение спектра излучения атомов водорода и экспериментальное определение постоянной Ридберга |
|
Лабораторная работа №8 по дисциплине «Физика-1» ... |
|
Лабораторная работа №6 по дисциплине «Физика-1» Целью данной работы является изучение дифракции Фраунгофера на щели и определение размеров щели дифракционным методом |