Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков)




Скачать 234.7 Kb.
НазваниеЛабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков)
страница1/3
Дата публикации01.06.2014
Размер234.7 Kb.
ТипЛабораторная работа
literature-edu.ru > Информатика > Лабораторная работа
  1   2   3
Лабораторная работа № 2
Тема: Многомерная безусловная оптимизация (методы первого и нулевого порядков).

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


  1. Краткие теоретические сведения.




    1. О численных методах многомерной оптимизации.


Задача многомерной безусловной оптимизации формулируется в виде:

min f(x),

xX

где 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.
  1   2   3

Добавить документ в свой блог или на сайт

Похожие:

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛабораторная работа № применение модели rgb в медицинской диагностике...
Лабораторная работа № представление и смешение цветов с помощью модели rgb

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconТема Методы психолого-педагогических исследований
Тема Научно-исследовательская работа магистранта и требования к ее организации и оформлению

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconРабочая программа по дисциплине ен. Р. 1 «Методы моделирования и...
Омский институт водного транспорта (филиал) фбоу впо «Новосибирская государственная академия водного транспорта»

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconКонтрольная работа 4 Задание 1 Тема : методы нивелирования
Инструкция по нивелированию I, II, III и IV классов. Федеральная служба геодезии и картографии России. М, Картгеоцентр-Геодезиздат,...

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛюдмила Григорьевна Пучко Жизнь и здоровье человека в вопросах и ответах Многомерной медицины
Биолокация для всех», «Многомерная медицина», «Радиэстезическое познание человека», «Многомерный человек», «Многомерная медицина....

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛабораторная работа №1
Создание и отладка консольных приложений в интегрированной среде ms visual Studio. Net 2005

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛабораторная работа №2 по дисциплине «Физика-1»
Томский государственный университет систем управления и радиоэлектроники (тусур) Факультет дистанционного обучения

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛабораторная работа №7 по дисциплине «Физика-1»
Целью работы является изучение спектра излучения атомов водорода и экспериментальное определение постоянной Ридберга

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛабораторная работа №8 по дисциплине «Физика-1»
...

Лабораторная работа №2 Тема : Многомерная безусловная оптимизация (методы первого и нулевого порядков) iconЛабораторная работа №6 по дисциплине «Физика-1»
Целью данной работы является изучение дифракции Фраунгофера на щели и определение размеров щели дифракционным методом

Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции