Программирование градиентный метод многомерной глобальной оптимизации. Многомерная безусловная оптимизация (методы первого и нулевого порядков). Задачи многомерной безусловной минимизации

Лабораторная работа № 2

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

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

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

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

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

min f (x ),

x  X

где x ={ x (1) , x (2) ,…, x (n ) } – точка в n -мерном пространстве X = IR n , то есть целевая функция f (x )= f (x (1) ,…, f (x (n ) ) – функция n аргументов.

Так же как и в первой лабораторной работе мы рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек { x k }, удовлетворяющих условию f (x 0 )> f (x 1 )>…> f (x n )>… . Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности { x k } вычисляются по формуле:

х k +1 = x k +  k p k , k =0,1,2,… ,

где p k – направление спуска,  k – длина шага в этом направлении.

Различные методы спуска отличаются друг от друга способами выбора направления спуска p k и длины шага  k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции, относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д.

1.2. Градиентные методы.

1.2.1. Общая схема градиентного спуска.

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

x k +1 = x k -  k f ’(x k ),  k >0, k =0,1,2,… .

В координатной форме этот процесс записывается следующим образом:

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

1.2.2. Градиентный метод с постоянным шагом.

Основная проблема в градиентных методах – это выбор шага  k . Достаточно малый шаг  k обеспечивает убывание функции, то есть выполнение неравенства:

f (x k -  k (x k ))) < f (x k ),

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

Схема алгоритма

Шаг 1.

0 , постоянный шаг  , условия останова алгоритма  3

Шаг 2.

Х к+1 = х к -  f ’(x k ),

или, в координатной форме:

Шаг 3.

к+1 :

или, в координатной форме:

Шаг 4.

Если ||||  3

1.2.3. Градиентный метод с дроблением шага.

В методе градиентного спуска с дроблением шага величина шага  к выбирается так, чтобы было выполнено неравенство:

f (x k -  k )- f (x k )  -  k |||| 2 ,

Где 0<  <1 – произвольно выбранная постоянная (одна и та же для всех итераций). Это требование на выбор шага  к более жесткое, чем условие убывания, но имеет тот же смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства.

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

Схема алгоритма

Шаг 1.

Задаются х 0 ,  3 ,  и начальное значение шага  . Вычисляется значение градиента – направление поиска. Присваивается к=0.

Шаг 2.

Проверяется условие: f (x k -  )- f (x k )  -  |||| 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) и т. д.

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

Спуск по всем координатам составляет одну «внешнюю» итерацию. Пусть к – номер очередной внешней итерации, а j – номер той координаты, по которой производится спуск. Тогда формула, определяющая следующее приближение к точке минимума, имеет вид:

Где к=0,1,2,… ; j =1,2,… n .

В координатной форме формула выглядит так:

После j = n счетчик числа внешних итераций к увеличивается на единицу, а j принимает значение равное единице.

Величина шага  к выбирается на каждой итерации аналогично тому, как это делается в градиентных методах. Например, если  к =  постоянно, то имеем покоординатный спуск с постоянным шагом.

Схема алгоритма покоординатного спуска с постоянным шагом

Шаг 1.

0 ,  1 ,  .

Шаг 2.

j (j =1,2,…, n kn по формуле:

Шаг 3.

Иначе к=к+1 и переходим к шагу 2.

Если же шаг  к выбирается из условия минимума функции:

то мы получаем аналог метода наискорейшего спуска, называемый обычно методом Гаусса – Зейделя.

Схема метода Гаусса – Зейделя

Шаг 1.

При к=0 вводятся исходные данные х 0 ,  1 .

Шаг 2.

Осуществляется циклический по j (j =1,2,…, n ) покоординатный спуск из точки х kn по формулам:

Где  kn + j -1 является решением задачи одномерной минимизации функции:

Шаг 3.

Если || x (k +1) n – x kn ||  1 , то поиск минимума заканчивается, причем:

Иначе к=к+1 и переходим к шагу 2.

1.4. Методы оврагов

1.4.1. Общая характеристика.

Градиентные методы медленно сходятся в тех случаях, когда поверхности уровня целевой функции f (x ) сильно вытянуты. Этот факт известен в литературе как «эффект оврагов». Суть эффекта в том, что небольшие изменения одних переменных приводят к резкому изменению значений функции – эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дно оврага», функция меняется незначительно. На рисунке изображены линии уровня «овражной» функции траектория градиентного метода характеризуется довольно быстрым спуском на «дно оврага», и затем медленным зигзагообразным движением в точку минимума.

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

1.4.2. Эвристические алгоритмы.

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

Первая эвристическая схема содержит два основных этапа. Оба этапа представляют собой аналоги градиентного спуска с постоянным шагом. Только вместо градиента используется вектор g (x ), формируемый из координат, но на каждом из этапов по разным правилам.

На первом этапе задается малое число  1 <<1 и используется градиентный спуск, где вместо градиента берется вектор

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

На втором этапе задается некоторое большое число  2 >>1 и используется процедура спуска, где вместо градиента берется вектор g (x )={ g (1) (x ),…, g (n ) (x )}, который определяется следующим образом:

В этом случае перемещение происходит по «берегу» оврага вдоль его «дна». Как и на первом этапе, спуск продолжается до тех пор, пока метод не зациклится.

После выполнения первого и второго этапов принимается решение о завершении работы или продолжении. Для этого сравнивается норма разности предыдущей точки, то есть точки, которую мы имели до применения первого и второго этапов, с текущей точкой, то есть полученной после применения с точностью решения задачи  1 . Если эта норма меньше  1 и норма градиента в текущей точке меньше  3 , то поиск заканчивается и последняя вычисленная точка принимается за приближенное решение задачи. Иначе для текущей точки вновь повторяем первый и второй этапы и т. д.

Схема алгоритма

Шаг 1.

Задаются х 0 ,  1 ,  3 ,  1 ,  2 ,  1 – постоянный шаг пункта 1 и  2 – постоянный

Шаг пункта 2 ( 1 <  2 ). Присваивается к=0.

Шаг 2. (Первый этап).

Из точки х к осуществляется спуск на «дно оврага» с постоянным шагом

 1 . При спуске вычисление очередной точки осуществляется с

Использованием формул:

x j +1 = x j -  1 g (x j ), где g (x )={ g (1) (x ),…, g (n ) (x )},

Пусть этот процесс остановится в точке x l .

Шаг 3. (Второй этап).

Из точки x l осуществляется спуск вдоль «дна оврага» с постоянным шагом  2 . При спуске используются формулы: x j +1 = x j -  2 g (x j ), где

g (x )={ g (1) (x ),…, g (n ) (x )},

Пусть этот процесс остановился в точке x m .

Шаг 4.

Если || x k – x m ||   1 и ||||   3 , то полагаем:

И поиск минимума заканчивается.

Иначе k = m и переходим к шагу 2.

1.4.3. Овражные методы (Метод Гельфанда).

Вторая эвристическая схема, предложенная И.М. Гельфандом, состоит в следующем.

Пусть х 0 и - две произвольные близкие точки. Из х 0 совершают обычный градиентный спуск с постоянным шагом и после нескольких итераций с малым шагом  попадем в точку u 0 . Тоже самое делаем для точки, получая точку. Две точки u , лежат в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг»  в полученном направлении, перемещаясь «вдоль дна оврага» (шаг  называют овражным шагом). В результате получаем точку х 1 . В ее окрестности выбираем точку и повторяем процедуру.

Схема овражного метода 1.

Шаг 1.

Вводятся начальное приближение х 0 , точность решения  1 и  3 , шаг  для

Градиентного спуска, начальное значение  для овражного шага. Из точки х 0

 на дно оврага. В

Результате получается точка u 0 . Полагается к=0.

Шаг 2.

В окрестности х к берется точка и из нее осуществляется градиентный

Спуск. В результате получается точка.

Шаг 3.

Новая точка х к+1 определяется следующим образом. По формуле

или

вычисляется точка x" k +1 f ()< f (u k ), то полагаем x k +1 = и u k +1 =.

Иначе уменьшаем овражный шаг  (например в 2 раза  =  /2)и повторяем шаг 3.

Шаг 4.

Если || u k +1 - u k ||  1 и ||||  3 , то полагаем:

Рассмотрим другую реализацию той же идеи.

Пусть х 0 и х 1 – две произвольные близкие точки. Как и в предыдущем случае, из каждой точки осуществим градиентные спуски с постоянным шагом  . Получим точки u 0 и u 1 , лежащие в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг»  в полученном направлении. В результате получим точку х 2 . Из этой точки осуществим градиентный спуск и получим точку u 2 . А вот далее, для того чтобы осуществить «овражный шаг», берем предпоследнюю точку u 1 . Соединяя прямой точки u 2 и u 1 , делаем шаг  в полученном направлении и определяем х 3 . Дальше аналогичным образом вычисляются х 4 ,х 5 , … .

Схема овражного метода 2

Шаг 1.

Задаются начальное приближение х 0 , точность решения  1 и  3 , шаг  для градиентного спуска, начальное значение  для овражного шага.

Из точки х 0 осуществляется градиентный спуск с постоянным шагом  на «дно оврага». В результате получается точка u ’ 0 .

В окрестности х 0 берется точка х 1 , из которой тоже осуществляется градиентный спуск на «дно оврага». В результате получается точка u ’ 1 . Полагается к=1. Если f (u ’ 0 )< f (u ’ 1 ), то полагаем u 0 = u ’ 1 , u 1 = u ’ 0 . Если f (u ’ 0 )> f (u ’ 1 ), то u 0 = u ’ 0 , u 1 = u ’ 1 .

Шаг 2.

Новая точка х к+1 определяется следующим образом. По формуле:

Вычисляется точка x" k +1 . Из нее осуществляется градиентный спуск и мы получаем точку. Если f ()< f (u k ), то полагаем x k +1 = и u k +1 =.

Иначе уменьшаем овражный шаг  (например в 2 раза  =  /2)и повторяем шаг 2.

Шаг 3.

Если || u k +1 - u k ||  1 и ||||  3 , то полагаем:

и поиск минимума на этом заканчивается, иначе к=к+1 и переходим к шагу 2.

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

1.5.1. Общая характеристика.

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

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

1.5.2. Метод конфигураций (метод Хука и Дживса).

Алгоритм включает в себя два основных этапа поиска.

а) В начале обследуется окрестность выбранной точки (базисной точки), в результате находится приемлемое направление спуска;

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

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

Схема алгоритма

Шаг 1.

Задаются начальное приближение (первая базисная точка)

, начальный шаг h для поиска направления спуска, точность решения  (предельное значение для шага h ). Присваивается к=0.

Шаг 2. (Первый этап).

Определяется направление минимизации целевой функции f (x )= f (x (1) , x (2) ,…, x (n ) ) в базисной точке. Для этого последовательно дают приращение переменным x (j ) в точке х к . Присвоим z = x k . Циклически даем приращение переменным x (j ) и формируем z (j ) = x k (j ) + h , если f (z )< f (x k ), если же нет, то z (j ) = x k (j ) - h , если f (z )< f (x k ), иначе z (j ) = x k (j ) . Так для всех j (j =1,2,…, n ).

Шаг 3.

Если z = x k , то есть не определилось подходящее направление, то обследование окрестности базисной точки х к повторяется, но с меньшим шагом h (например, h = h /2).

Если h >  , то перейти к шагу 2, то есть повторить обследование точки х к .

Если h  , то поиск заканчивается, то есть достигнуто предельное значение для шага h и найти приемлемое направление спуска не удается. В этом случае полагается

Шаг 4. (Второй этап).

Если z  x k , то требуется найти новую базисную точку в направлении

вектора z - x k : x k +1 = x k +  (z - x k ), где  - коэффициент «ускорения поиска».

Определяется такое значение  =  к , при котором достигается наименьшее значение целевой функции в выбранном направлении, то есть функции

f (x k +  (z - x k ) =  ( ).

В зависимости от способа выбора  к возможны варианты метода:

а)  к =  = const постоянная для всех итераций;

б) задается начальное  0 =  , а далее  к =  к-1 , если f (x k +1 )< f (x k ), иначе дробим  к , пока не выполнится это условие;

в)  к определяется решением задачи одномерной минимизации функции  ( ).

Таким образом определяется новая базисная точка x k +1 = x k +  (z - x k ). Полагаем к=к+1 и поиск оптимального решения повторяется с шага 2.

1.5.3.Метод симплекса.

Под симплексом понимается n -мерный выпуклый многогранник n -мерного пространства, имеющий n +1 вершину. Для n =2 это треугольник, а при n =3 это тетраэдр.

Идея метода состоит в сравнении значений функции в n +1 вершинах симплекса и перемещении симплекса в направлении лучшей точки. В рассматриваемом методе симплекс перемещается с помощью операций отражения. Далее принято следующее: х 0 (k ), х 1 (k ), … , х n (k ) – вершины симплекса, где к - номер итерации.

Схема алгоритма

Шаг 1.

Для этого задаются начальная точка х 0 (0) и длина ребра симплекса l

x i (0) = x 0 (0) + l * e i (i =1,2,…, n ), где e i – единичные векторы.

Шаг 2.

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

f (x min (k ))  f (x i (k ))  f (x max (k )),

где min , max , i – номера соответствующих вершин симплекса. Определим центр тяжести всех точек, исключая точку x max (k ),

C k =( x i (k ))/ n .

Тогда направление улучшения решения определяется вектором C k - x max (k ).

Шаг 3.

Построение отраженной точки.

Замена вершины x max (k ) с максимальным значением целевой функции на новую точку с помощью операции отражения, результатом которой является новая точка:

u k = c k +(c k - x max (k ))=2 c k - x max (k )

x (2)

Шаг 4.

Вычисляем f (u k ). При этом возможен один из двух случаев:

а) f (u k )< f (x max (k );

б) f (u k )  f (x max (k ).

Случай а): вершина x max заменяется на u k , чем определяется набор вершин к+1-й итерации и к-я итерация заканчивается.

u k , значение функции в которой еще хуже, чем в точке x max , то есть отражать симплекс некуда. Поэтому в этом случае производится пропорциональное уменьшение симплекса (например, в 2 раза) в сторону вершины x min (k ):

x i (k+1)=x ^ i =(x i (k)+x min (k))/2, где i=0,1,…,n.

На этом к-я итерация заканчивается.

Шаг 5.

Проверка сходимости.

Если

1.5.4. Метод деформируемого симплекса (метод Нелдера – Мида).

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

В рассматриваемом методе симплекс перемещается с помощью трех основных операций над симплексом: отражение, растяжение и сжатие.

Схема алгоритма.

Шаг 1.

Построение начального симплекса.

Задаются начальная точка х 0 (0) и длина ребра l . Формируются остальные вершины симплекса: x i (0)= x 0 (0)+ le i (i =1,2,…, n ), где e i – единичные векторы.

Шаг 2.

Определение направления улучшения решения.

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

f (x min (k )) f (x i (k )) f (x m (k )) f (x max (k )),

где min , m , max , i -номера соответствующих вершин симплекса. Определим центр тяжести всех точек, исключая точку x max (k),

Тогда направление улучшения решения определяется векторов

C k - x max (k ).

Шаг 3.

Построение нового симплекса.

Замена вершины x max (k ) с максимальным значением целевой функции на новую точку с помощью операции отражения, результат которой является новая точка

u k = C k +  *(C k - x max (k )), где  -коэффициент отражения.

Шаг 4.

Построение нового симплекса.

Вычисляем f (u k ), при этом возможно один из трех случаев:

а ) f(u k )< f(x min (k));

б) f(u k )>f(x m (k));

в ) f(x min (k)) f(u k ) f(x m (k));

Случай а): отражённая точка является точкой с наилучшим значением целевой функции. Поэтому направление отражение является перспективным и можно попытаться растянуть симплекс в этом направлении. Для этого строиться точка

V k = C k +  *(u k - C k ), где  >1 –коэффициент расширения.

Если f (v k )< f (u k ), то вершина x max (k ) заменяется на v k , в противном случае на u k и k -ая итерация заканчивается.

Случай б): в результате отражения получается новая точка u k , которая, если заменить x max (k ), сама станет наихудшей. Поэтому в этом случае производится сжатие симплекса. Для этого строится точка v k :

где 0<  <1 –коэффициент сжатия.

Если f (v k )< min { f (x max (k )), f (u k )}, то вершина x max (k ) заменяется на v k .

В противном случае вершинам x i (k +1) (i =0,1,2,.., n ) присваивается значение:

и на этом k -ая итерация заканчивается.

в) вершина x max (k ) заменяется на u k , чем определяется набор вершин k +1-й итерации и k –ая итерация заканчивается.

Шаг 5.

Проверка сходимости.

Если

то поиск минимума заканчивается и полагается

В противном случае к=к+1 и происходит переход к шагу 2.

Опыт использования описанного алгоритма показывает, что целесообразно брать следующие значения параметров:

 =1,  =2,  =0.5.

2.Задание на лабораторную работу.

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

1. В соответствие с вариантом задания, определенным преподавателем, составить программы реализующие методы многомерной безусловной минимизации и найти точку минимума целевой функции f (x )= f (x (1) , x (2) ) с заданной точностью  указанными методами. Начальное приближение x 0 и точность  приводятся в условие задачи. Сравнить результаты, полученные разными методами для одной и той же целевой функции (в частности, сравнить число вычислении целевой функции и её производных, понадобившихся для получения заданной точности). Для каждого применяемого метода построить траекторию промежуточных точек, получаемых на очередных шагах метода и сходящихся к точке минимума.

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

3. Варианты задания.

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

а) градиентный метод с постоянным шагом;

б) градиентный метод с дроблением шага;

в) метод наискорейшего спуска (указание метода одномерного поиска);

г) метод покоординатного спуска с постоянным шагом;

д) метод Гаусса-Зейделя (указание метода одномерного поиска);

е) эвристический алгоритм;

ж) овражный метод  ;

з) овражный метод  ;

к) метод конфигураций;

л) метод симплекса;

м) метод деформируемого симплекса.

3.2 Варианты заданий.

Целевая функция f (x )= f (x (1) , x (2) ) зависит от двух аргументов. Функция f (x ) следующего вида:

f (x )= a * x (1) + b * x (2) + e c *(x ) + d *(x ) .

№	Целевая функция				Начальное приближение	Точность решения
		a	b	c			d
1	1	-1,4	0,01	0,11	(1;0)	0,0001
2	2	-1,3	0,04	0,12	(0;1)	0,00005
3	10	-0,5	0,94	0,2	(0;0)	0,0001
4	15	0	1,96	0,25	1,96	0,25
5	3	-1,2	0,02	1,3	(0;-1)	0,00005
6	11	-0,4	1	0,21	(-1;0)	0,0001
7	10	-1	1	2	(1;0)	0,0003
8	15	-0,5	2,25	2,5	(0;0)	0,0002
9	20	0,4	0,3	0,3	(0;-1)	0,0001
10	25	0,9	0,35	0,35	(1;0)	0,0004

Лабораторная работа № 2

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

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

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

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

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

Где x={x (1) , x (2) ,…, x (n) } – точка в n-мерном пространстве X=IR n , то есть целевая функция f(x)=f(x (1) ,…,f(x (n)) – функция n аргументов.

Так же как и в первой лабораторной работе мы рассматриваем задачу минимизации. Численные методы отыскания минимума, как правило, состоят в построении последовательности точек {x k }, удовлетворяющих условию f(x 0)>f(x 1)>…>f(x n)>… . Методы построения таких последовательностей называются методами спуска. В этих методах точки последовательности {x k } вычисляются по формуле:

Х k +1 = x k +  k p k , k=0,1,2,… ,

Где p k – направление спуска,  k – длина шага в этом направлении.
Различные методы спуска отличаются друг от друга способами выбора направления спуска p k и длины шага  k вдоль этого направления. Алгоритмы безусловной минимизации принято делить на классы, в зависимости от максимального порядка производных минимизируемой функции, вычисление которых предполагается. Так, методы, использующие только значения самой целевой функции , относят к методам нулевого порядка (иногда их называют также методами прямого поиска); если, кроме того, требуется вычисление первых производных минимизируемой функции, то мы имеем дело с методами первого порядка; если же дополнительно используются вторые производные, то это методы второго порядка и т. д.

1.2. Градиентные методы.
1.2.1. Общая схема градиентного спуска.

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

X k +1 = x k -  k f’(x k),  k >0, k=0,1,2,… .

Но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны , слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка условия убывания на каждой итерации является довольно трудоемкой, поэтому в методе градиентного спуска с постоянным шагом задают = k постоянным и достаточно малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим количеством итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент ).

Схема алгоритма

Задаются начальное приближение х 0 , постоянный шаг  , условия останова алгоритма  3 . Вычисляется значение градиента – направление поиска. Присваивается к=0.

Определяется точка очередного эксперимента:

Если ||
|| 3 , то поиск точки минимума заканчивается и полагается:
Иначе к=к+1 и переход к шагу 2.
1.3.Метод покоординатного спуска.

При к=0 вводятся исходные данные х 0 ,  1 .

Осуществляется циклический по j (j=1,2,…,n) покоординатный спуск из точки х kn по формулам:

где  kn + j -1 является решением задачи одномерной минимизации функции:

Если ||x (k +1) n – x kn || 1 , то поиск минимума заканчивается , причем:

Иначе к=к+1 и переходим к шагу 2.

Задачи оптимизации (поиска наилучшего решения) не самые популярные в среде 1С-негов. Действительно, одно дело - учет выполнения каких-либо решений, и совершенно другое дело - принятие этих самых решений. В последнее время, однако, мне кажется 1С бросилась догонять конкурентов в данном вопросе. Действительно захватывающе объединить под одной крышей все, что может потребоваться современному менеджеру, догоняя в этом вопросе SAP и заменяя MS Project и другие системы планирования.

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

Итак, первая тема - метод градиентного спуска .

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

Давайте введем обозначения:

Множество переменных Х, от которых зависит значение целевой функции

И сама целевая функция Z, вычисляемая самым произвольным образом из множества Х

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

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

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

Теперь самый главный вопрос: а как нам найти эти самые d Z и dX1 , dX2 и т.д.? Очень просто! dXn - это бесконечно малое приращение переменной Xn , скажем 0,0001 от ее текущей величины. Или 0,0000000001 - главное, чтобы оно (приращение) было действительно малым:)

А как же вычисляется dZ ? Тоже элементарно! Вычисляем Z для набора переменных X , а затем изменяем в этом наборе переменную Xn на величину dXn . Снова вычисляем значение целевой функции Z для этого слегка модифицированного набора (Zn ) и находим разницу - это и будет dZ = Zn - Z . Ну а теперь коль нам известны dXn и dZ найти dZ/dXn проще пареной репы.

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

На следующем (k+1) этапе, нужно вычислить новые значения массива переменных X . Очевидно, что для приближения к минимуму целевой функции Z мы должны корректировать значения X предыдущего (k-го) этапа в направлении антиградиента по такой формуле:

Остается разобраться с этой самой альфой в формуле. Зачем она нужна и откуда она берется.

α - это коэффициент на который домножается антиградиент для обеспечения достижения возможного минимума функции в заданном направлении. Сам по себе градиент или антиградиент не являются мерой сдвига переменной, а указывают лишь направление движения. Геометрический смысл градиента - это тангенс угла наклона касательной к функции Z в точке Xn (отношение противолежащего катета dZ к прилежащему dXn ), но двигаясь по касательной мы неизбежно отклонимся от линии функции до достижения ее минимума. Смысл касательной в том, что она дает отображение в виде прямой произвольной криволинейной функции в очень узком промежутке - окрестностях точки Xn .

Поиск значения параметра α выполняется одним из методов одномерной оптимизации. Значения переменных {X} нам известны, известны и их градиенты - остается минимизировать целевую функцию в окрестностях текущего решения по одному единственному параметру: α .

Останавливаться на одномерной оптимизации я здесь на буду - методы достаточно просты для понимания и реализации, скажу лишь, что я использовал в своем решении метод "золотого сечения". ОДЗ для α находится в промежутке от 0 до 1.

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

1. Формируем начальное опорное решение, присваивая искомым переменным случайные значения из ОДЗ.
2. Находим градиенты и антиградиенты для каждой переменной как отношения прироста целевой функции при относительно малом увеличении значения переменной к значению приращения этой самой переменной.
3. Находим коэффициент α , на который нужно умножать антиградиенты перед добавлением к исходным значениям опорного решения методом одномерной оптимизации. Критерий оптимизации - наименьшее из возможных значение целевой функции для скорректированных таким образом значений {X} .
4. Пересчитываем {X} в соответствии с наденными значениями антиградиентов и коэффициента сдвига α .
5. Проверяем достигнута ли необходимая точность (ε ) вычисления минимума целевой функции:

6. Если условие выполнено и от этапа к этапу значение целевой функции изменилось ниже установленного нами же критерия это значит, что необходимая точность достигнута и текущее множество {X} является решением задачи, иначе - переход к шагу 2.

Теперь давайте перейдем к практической задаче, которая решена в обработке.

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

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

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

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

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

Вот, собственно, и все. Вопросы, пожелания и замечания жду в комментах. Спасибо за внимание.

Размер: px

Начинать показ со страницы:

Транскрипт

1 Курс: Методы оптимизации в машинном обучении, Продвинутые методы многомерной оптимизации Рассмотрим задачу безусловной оптимизации в многомерном пространстве: f(x) min x R N. Ранее для решения этой задачи были рассмотрены методы покоординатного и градиентного спуска, метод Ньютона, а также комбинированные методы. Во всех этих подходах очередное направление оптимизации d вычисляется только с использованием информации от оракула в текущей точке x. Таким образом, траектория оптимизации никак не учитывается. В методах оптимизации, рассматриваемых ниже, очередное направление оптимизации d существенно зависит от траектории оптимизации и, в частности, зависит от предыдущих направлений d,...,d. Решение СЛАУ с помощью метода сопряжённых градиентов Рассмотрим задачу минимизации квадратичной функции с положительно-определённым гессианом: Приравнивая к нулю градиент f, получаем: f(x) = xt Ax x T b min x, A = A T. () f(x) = Ax b = Ax = b. Таким образом, задача минимизации f эквивалентна решению СЛАУ Ax = b. Назовём набор векторов {d i } сопряжённым относительно положительно-определённой матрицы A, если выполнено условие: d T i Ad j = i j. Примером сопряжённых направлений является набор собственных векторов матрицы A. Действительно, в этом случае d T i Ad j = λ i d T i d j =. Последнее условие выполнено, т.к. собственные вектора, отвечающие различным собственным значениям, ортогональны, а среди собственных векторов с одинаковым собственным значением всегда можно выбрать ортогональный набор. Набор сопряжённых векторов является линейно-независимым. Рассмотрим нетривиальную линейную комбинацию сопряжённых векторов: α i d i =, α i. Домножим слева это уравнение на d T j A для некоторого j. В результате получим: α i d T j Ad i = α j = α j =. Последнее условие следует из того, что матрица A является строго положительно-определённой. Из линейной независимости вытекает, что сопряжённый набор{d i } N является базисом всего пространстваrn. В частности, решение СЛАУ x можно разложить по этому базису с некоторыми коэффициентами α i: Домножая это уравнение слева на d T j A, получаем: d T j Ax = N x = N α i d T j Ad i = α j α j = dt j Ax α i d i. () = dt j b d T j Ad. () j это не совсем так при использовании адаптивной коррекции длины шага На самом деле набор сопряжённых векторов можно рассматривать как ортогональный базис относительно скалярного произведения x,y = x T Ay. Отсюда становится очевидным линейная независимость векторов, а также то, что матрица A должна быть положительно-определённой (иначе не будет скалярного произведения).

2 Последнее равенство вытекает из того, что x решение СЛАУ, т.е. Ax = b. Здесь становится очевидным преимущество сопряжённого набора векторов относительно других базисов для поиска x: для сопряжённого набора коэффициенты разложения α j вычисляются аналитически. Поиск x по формуле () с коэффициентами () можно представить в виде итерационного процесса: x =, x + = x +α d, α = dt b d T Ad, =,...,N. В результате x N+ = x. Теперь получим аналогичный итерационный процесс для поиска x, который начинается с произвольного ненулевого вектора x. Для этого разложим вектор x x по сопряжённому базису: Домножая это равенство на d T j A слева, получаем: x x = N d T j A(x x) = α j α j = dt j A(x x) α i d i. = dt j (b Ax) = dt j g = dt j g j d T j Ad. (4) j Здесь и далее через g j обозначается градиент функции f в точке x j. Для квадратичной функции g j = Ax j b. Докажем последний переход в формуле (4): (j) d T j (g j g) = d T j (Ax j b Ax +b) = d T j A j α i d i = α i d T j Ad i = d T j g j = d T j g. (5) Таким образом, получаем следующий итерационный процесс для поиска x из произвольного начального приближения x: x + = x +α d, α = dt g d T Ad, =,...,N. (6) Можно показать, что данный итерационный процесс является процессом наискорейшего спуска для функции f вдоль сопряжённых направлений {d i } N. Для этого достаточно убедиться в том, что коэффициент α j, вычисляемый по формуле (4), доставляет минимум по α функции f(x j +αd j). Действительно, α f(x j +αd j) = f(x j +α j d j) T d j = g T j+d j = (Ax j +α j Ad j b) T d j = α=αj = (Ax j b) T d j +α j = g T j d j d T j g j =. (7) Одновременно здесь было доказано, что g T j+ d j =. Покажем, что g T j+ d i = i j. Действительно, g T j+ d i = (Ax j+ b) T d i = (A(x + j α i d i) b) T d i = (Ax b) T d i +α i d T i Ad i = g T d i g T i d i =. Последнее равенство следует из (5). Условие ортогональности градиента g j+ всем предыдущим направлениям оптимизации означает, что x j+ доставляет минимум функции f в линейной оболочке L(d,...,d j). Более того, можно показать, что точка x j +αd j минимизирует функцию f в линейной оболочке L(d,...,d j) для любого α. Действительно, f(x j +αd j) T d i = (A(x j +αd j) b) T d i = (Ax j b) T d i +αd T j Ad i = g T j d i =. i < j. Таким образом, при движении вдоль очередного сопряжённого направления оптимизацию по предыдущим направлениям проводить не нужно. Это одна из отличительных особенностей метода сопряжённых направлений. Для проведения итерационного процесса (6) необходимо указать полный набор сопряжённых направлений для матрицы A. Рассмотрим следующую схему генерации d: d = g, d + = g + +β d, β = gt + Ad d T Ad, =,...,N. (8) Верна следующая последовательность рассуждений: d = g L(g), g = g +α Ad = g α Ag L(g,Ag), d = g +β d L(g,Ag), g = g +α Ad L(g,Ag,A g), d = g +β d L(g,Ag,A g),...

3 В результате набор {d,...,d i }, генерируемый по схеме (8), и набор {g,...,g i } принадлежат одному и тому же линейному пространству L(g,Ag,...,A i g). Следовательно, вектор Ad i можно представить в базисе {d,...,d }, > i, а вектор g i можно представить в базисе {d,...,d i }: Ad i = g i = a j d j, (9) j= i b j d j. () j= Покажем теперь, что схема (8) позволяет построить набор сопряжённых направлений для матрицы A. Кроме того, покажем, что при её использовании g T d i = i < и g T g i = i <. Проведём доказательство по индукции. Пусть известно, что g T d i = i <, d T Ad i = i <, g T g i = i <. Докажем, что аналогичные утверждения верны для +. Из рассуждений (7) следует, что g T + d =. Далее g T +d i = (g +α Ad) T d i = g T d i +α d T Ad i =. Последнее утверждение выполняется, исходя из предположения индукции. Покажем теперь, что d T + Ad i = i. Используя (8), получим, что d T + Ad = (g + +β d) T Ad = g T + Ad +g T + Ad =. Далее с помощью (9) заключаем, что для i < d T + Ad i = (g + +β d) T Ad i = g + Ad i = g + a j d j = Осталось показать, что g T + g i = i <. Используя (), получаем i g T + g i = g T + b j d j = j= j= i b j g T + d j =. j= a j g T + d j =. В результате получаем, что набор {d,...,d N } действительно является сопряжённым относительно матрицы A. Заметим, что в доказательстве сопряжённости существенно используется тот факт, что первое направление выбирается в соответствии с антиградиентом. При другом выборе d итерационный процесс (8) не приводит к набору сопряжённых направлений. С помощью доказанных выше свойств g T d i = i < и g T g i = i < можно несколько упростить выражения для α и β в итерационных процессах (6), (8): α = g d d T Ad β = gt + Ad d T Ad = g (g +β d) d T Ad = gt g d T Ad, = gt + (g + g) d T Ad = gt + g + α g T g. () В результате получаем итоговый алгоритм решения СЛАУ Ax = b, который получил название метода сопряжённых градиентов:. Задаём начальное приближение x и требуемую точность ε;. Инициализация d = g, = ;. x + = x +α d, где α = gt g d T Ad ; 4. Если α d < ε, то стоп; Пространства такого вида известны в линейной алгебре как пространства Крылова j=

4 5. d + = g + +β d, где β = gt + g + g T g ; 6. = + и переход к шагу. Данный алгоритм гарантированно сходится к решению за N шагов, где N размерность пространства решения. На каждом шаге итерационного процесса требуется проводить только одно умножение матрицы A на вектор d (векторax + при этом вычисляется какax +α Ad). Остальные операции в алгоритме являются векторными: скалярное произведение двух векторов и сумма двух векторов. На рис. показан пример применения этого алгоритма. Для сравнения показана также траектория метода наискорейшего спуска Рис. : Пример работы метода наискорейшего спуска (зеленая траектория) и метода сопряжённых градиентов (красная траектория) для оптимизации квадратичной функции. Основные преимущества метода сопряжённых градиентов связаны с пространствами большой размерности. При N методы решения СЛАУ, основанные на матричных разложениях, например, разложении Холецкого или QR-разложении, перестают быть применимыми в силу необходимости итерационного пересчета матриц, размер которых совпадает с размером матрицы A. Напротив, в методе сопряжённых градиентов все операции производятся только для векторов размерности N, а самая сложная операция в алгоритме это умножение матрицы A на очередной вектор d. Для ряда матриц специального вида, например, разреженных матриц или матриц, представляющих базис Фурье, такое умножение может быть проведено эффективнее общего случая. Метод сопряжённых градиентов для минимизации произвольной функции Рассмотрим теперь задачу оптимизации произвольной гладкой функции f. Тогда в схеме метода сопряжённых градиентов матрицаaзаменяется на гессианh в текущей точкеx. Практически данный подход превращается в метод Ньютона, в котором квадратичная аппроксимация функции минимизируется с помощью сопряжённых градиентов. Поэтому метод сопряжённых градиентов имеет квадратичную скорость сходимости в малой окрестности оптимального решения. Для того, чтобы застраховаться от возможной неадекватности квадратичного приближения функции f в текущей точке, в методе сопряжённых градиентов предлагается решать одномерную задачу оптимизации при движении вдоль очередного направления d: x + = x +α d, α = argmin α f(x +αd). Заметим, что в этом случае отпадает необходимость вычисления гессиана, и метод превращается в метод оптимизации первого порядка. При использовании формулы () для β соответствующий метод сопряжённых градиентов получил название Флетчера-Ривса (Fletcher-Reeves). В методе Полака-Рибье (Pola-Ribiere) предлагается использовать другую формулу для β: β = gt + g + g T + g g T g. Для случая квадратичной функции последняя формула переходит в формулу (), т.к. g T + g =. Однако, для произвольной функции она позволяет добиться более устойчивой и качественной работы метода. В методе сопряжённых градиентов направление d + зависит от d, а, значит, неявно зависит от всех предыдущих направлений d,...,d. Для повышения устойчивости работы метода для неквадратичной функции предлагается устанавливать β = после каждой N-ой итерации, т.е. периодически «очищать» предысторию, в которой могут накапливаться неудачные направления. Обнуление β соответствует выбору направления оптимизации по антиградиенту. На рис.,a показан пример применения метода сопряжённых градиентов без использования обнуления. В результате в ходе итераций метод «проскочил» оптимальную точку [,] T за счет 4

5 (a) (b) (c) Рис. : Примеры работы метода сопряжённых градиентов для функции Розенблока. Случай (a): без использования обнуления β, всего 64 итерации, случай (b): с использованием обнуления, всего 6 итераций, случай (c): использование bactracing, всего 6 итераций. сильной зависимости от предыдущих направлений. Напротив, использование обнуления (см. рис.,b) позволило успешно обнаружить минимум за меньшее число итераций. Как было отмечено выше, в методе сопряжённых градиентов очередное направление оптимизации выбирается таким образом, чтобы при движении вдоль него сохранить минимум по всем предыдущим направлениям. За счёт этого удаётся избежать ступенчатого поведения, характерного для покоординатного и градиентного спуска. Однако, такой подход неявно предполагает, что вдоль очередного направления проводится точная оптимизация, т.к. в дальнейшем возврат к этому направлению не запланирован. На рис.,c показан пример работы метода, в котором на этапе одномерной оптимизации используется bactracing. В результате метод начинает работать крайне неустойчиво, а сходимость достигается только за 6 итераций. В реальности метод сопряжённых градиентов может устойчиво сходиться и при использовании неточной одномерной оптимизации. Однако, её использование связано с определёнными рисками. Квази-ньютоновские методы В квази-ньютоновских методах оптимизации пересчёт осуществляется по формуле x + = x α S g. () Здесь S некоторая положительно-определённая матрица. Условие положительной определённости S гарантирует возможность уменьшения функции f вдоль направления d = S g. Действительно, α f(x αs g) = g T S g <. α= Если S = I, то () переходит в градиентный спуск. Если S = H, то () переходит в метод Ньютона. По аналогии с методом сопряжённых градиентов, рассмотрим сначала квази-ньютоновские методы для случая минимизации квадратичной функции (). Введем обозначения: δ = x + x = α S g, γ = g + g. Для квадратичной функции γ = g + g = Aδ. В результате [γ γ... γ N ] = A[δ δ... δ N ]. Пусть в первый момент времени задано некоторое начальное приближение x. Положим S = I 4 и будем пересчитывать S по правилу S + = S + C, где C некоторая матрица. Проведем N шагов вида () и получим набор {δ,...,δ N }, набор {γ,...,γ N } и набор матриц S,S,...,S N. Если оказывается, что S N [γ γ... γ N ] = [δ δ... δ N ], то матрица S N = A и следующий шаг по схеме () соответствует шагу Ньютона, т.е. x N+ = x. По аналогии с методом сопряжённых градиентов, в котором существуют разные формулы для β и, соответственно, разные итерационные схемы пересчета d, для квази-ньютоновских методов также предложено несколько способов выбора C. Однако, все эти способы гарантируют выполнение следующих свойств:. Метод сходится за N шагов для квадратичной функции; 4 это соответствует использованию направления антиградиента 5

6 (a) (b) Рис. : Примеры работы метода L-BFGS для функции Розенблока. Случай (a): точная одномерная оптимизация, случай (b): использование метода Флетчера.. Для квадратичной функции набор векторов {δ,...,δ N } образует сопряжённый базис относительно матрицы A;. Матрица S всегда остаётся положительно-определённой. Последнее свойство важно для принципиальной возможности уменьшения f на каждой итерации. Рассмотрим несколько схем выбора C: Схема DFP (Davidon-Fletcher-Powell). Схема BFGS (Broyden-Fletcher-Goldfarb-Shanno). S + = S + δ δ T δ T γ S γ γ T S γ T S. γ (S + = S + + γt S) γ δ δ T γ T δ γ T δ δ γ T S +S γ δ T γ T δ. Схема L-BGFS (Limited Memory BFGS). Формула пересчета аналогична BFGS, но для S = I: Подставляя эту формулу в (), получаем: (S + = I + + γt γ) δ δ T γ T δ γ T δ δ γ T +γ δ T γ T δ. d + = S + g + = g + +A δ +B γ, A = gt + δ (γ T δ + γt γ) γ T δ + gt + γ γ T δ, B = gt + δ γ T δ. Заметим, что все квази-ньютоновские методы являются методами первого порядка. В случае квадратичной функции направления δ,...,δ N являются сопряжёнными относительно A. Поэтому в этом случае все квази-ньютоновские методы эквивалентны методу сопряжённых градиентов. При этом существенным моментом является использование направления антиградиента в первый момент времени (S = I). При использовании другой матрицы S генерируемые направления оптимизации δ,...,δ N теряют свойства сопряжённости, а сам метод свойство гарантированной сходимости за N итераций. На рис.,а показан пример работы метода L-BFGS для функции Розенблока. Заметим, что в отличие от метода сопряжённых градиентов, в квази-ньютоновских методах нет необходимости «очищать» предысторию и периодически приравнивать S = I. Кроме того, квази-ньютоновские методы являются более толерантными к использованию неточной одномерной оптимизации (см. рис.,b). 6

Лекция 4 МЕТОДЫ ПЕРВОГО ПОРЯДКА Постановка задачи Пусть дана функция f (), ограниченная снизу на множестве R n и имеющая непрерывные частные производные во всех его точках. Требуется найти локальный минимум

ЛЕКЦИЯ 6 1. Метод покоординатного спуска 2. Градиентный метод 3. Метод Ньютона Методы решения конечномерных задач оптимизации (Задачи безусловной оптимизации) -1- Численные методы НЛП Задача поиска безусловного

Методы оптимизации, ФКН ВШЭ, зима 2017 Практическое задание 2: Продвинутые методы безусловной оптимизации. Срок сдачи: 9 марта 2017 (23:59). Язык программирования: Python 3. 1 Алгоритмы В этом задании

Методы оптимизации, ФКН ВШЭ, зима 2017 Семинар 7: Квазиньютоновские методы 21 февраля 2017 г 1 Квазиньютоновские методы 11 Мотивация Рассмотрим стандартную задачу гладкой безусловной оптимизации: min f(x),

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики процессов управления А. П. ИВАНОВ, Ю. В. ОЛЕМСКОЙ ПРАКТИКУМ ПО ЧИСЛЕННЫМ МЕТОДАМ МИНИМИЗАЦИЯ КВАДРАТИЧНОЙ ФУНКЦИИ Методические

ЛЕКЦИЯ 11 МНОГОМЕРНАЯ ИНТЕРПОЛЯЦИЯ ЗАДАЧА ОПТИМИЗАЦИИ На прошлой лекции были рассмотрены методы решения нелинейных уравнений Были рассмотрены двухточечные методы, которые используют локализацию корня,

УДК 59.8 О. А. Юдин, аспирант ПОИСК МИНИМУМА ФУНКЦИЙ, КОТОРЫЕ ИМЕЮТ РАЗРЫВЫ ЧАСТНЫХ ПРОИЗВОДНЫХ Проанализированы возможные варианты решения задачи поиска минимума функции, которая имеет разрыв частной

ЛЕКЦИЯ 14 Численные методы нелинейного программирования 1. Градиентный метод 2. Теоремы сходимости 3. Метод Такахаши (дуализация/градиентный метод) -1- Численные методы НЛП Задача поиска безусловного минимума:

ОПТИМАЛЬНЫЙ ГРАДИЕНТНЫЙ МЕТОД МИНИМИЗАЦИИ ВЫПУКЛЫХ ФУНКЦИЙ М. В. Долгополик [email protected] 10 ноября 2016 г. Аннотация. В докладе обсуждается в некотором смысле оптимальный градиентный метод

Уральский федеральный университет, Институт математики и компьютерных наук, кафедра алгебры и дискретной математики Ортогональные и ортонормированные наборы векторов Из определения угла между векторами

К. В. Григорьева Методические указания Тема. Методы решения задачи минимизации квадратичной функции Факультет ПМ-ПУ СПбГУ 7 г. ОГЛАВЛЕНИЕ. ПОСТАНОВКА ЗАДАЧИ. ВСПОМОГАТЕЛЬНЫЕ СВЕДЕНИЯ.... МЕТОДЫ СПУСКА

Семинары по линейным классификаторам Евгений Соколов 27 октября 2013 г. Пусть X R d пространство объектов, Y = { 1,+1} множество допустимых ответов, X l = (x i,y i) l i=1 обучающая выборка. Каждый объект

ЛЕКЦИЯ 15 1. Метод Ньютона (метод второго порядка) 2. Метод внешних штрафов 3. Метод внутренних штрафов 4. Метод покоординатного спуска -1- МЕТОД НЬЮТОНА Пусть f дважды непрерывно дифференцируемая функция

Лекция 5 Постановка и возможные пути решения задачи обучения нейронных сетей Частичная задача обучения Пусть у нас есть некоторая нейросеть N. В процессе функционирования эта нейронная сеть формирует выходной

Санкт-Петербургский государственный политехнический университет Факультет технической кибернетики Кафедра распределённых вычислений и компьютерных сетей Реферат Тема: «Методы оптимизации без ограничений,

ЛЕКЦИЯ 6 СПЕКТРАЛЬНЫЕ ЗАДАЧИ. Методы спуска На прошлой лекции были рассмотрены итерационные методы вариационного типа. Для системы Au = f, для которой выполняется A = A, был введен функционал Φ(u, u)

Тема 2-11: Собственные векторы и собственные значения А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия

Лекция 0. Глава 4. Матрицы. В этой главе мы рассмотрим основные виды матриц, операции над ними, понятие ранга матрицы и их приложения к решению систем линейных алгебраических уравнений. 4.. Основные понятия.

ГЛАВА 8. ПОДПРОСТРАНСТВА 1 1. СУММА И ПЕРЕСЕЧЕНИЕ ПОДПРОСТРАНСТВ Множество L векторов линейного пространства X называется подпространством, если из того, что x, y L вытекает, что αx + βy L при любых комплексных

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ,

Методы оптимизации в машинном обучении, ВМК+Физтех, осень 2017 Практическое задание 3: Метод барьеров. 1 Метод барьеров Срок сдачи: 15 ноября 2017 (среда), 23:59 для ВМК 17 ноября 2017 (пятница), 23:59

Перечень методов,включенных в задачи к экзаменационным билетам. Билет 20 (метка) Метод Ньютона Билет 12 (метка) калькулятор http://math.semestr.ru/simplex/simplex_manual.php Построить двойственную задачу

Тема 2-4: Подпространства А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (2 семестр)

Содержание Элеметарная теория погрешностей. Решение СЛАУ. 4. Нормы в конечномерных пространствах... 4. Обусловленность СЛАУ............ 5.3 Итерационные методы решения линейных систем......................

Симплекс-метод решения задач линейного программирования Основным численным методом решения задач линейного программирования является так называемый симплекс-метод. Термин «симплекс-метод» связан с тем

ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ ÌÃÒÓ Московский государственный технический университет имени Н.Э. Баумана Факультет «Фундаментальные науки» Кафедра «Математическое моделирование» À.Í. Êàíàòíèêîâ

А.П.Попов Методы оптимальных решений Пособие для студентов экономических специальностей вузов Ростов-на-Дону 01 1 Введение В прикладной математике имеется несколько направления, нацеленных в первую очередь

1 Материалы к установочной лекции Вопрос 37. Итеративные методы решения уравнений. Метод Ньютона. 1. Решение скалярных уравнений. Метод Чебышева Рассмотрим уравнение f(x) =0,x , и пусть на указанном

Московский государственный технический университет имени НЭ Баумана Факультет «Фундаментальные науки» Кафедра «Высшая математика» Е Б Павельева В Я Томашпольский Линейная алгебра Методические указания

Решение нелинейных уравнений Не всегда алгебраические или трансцендентные уравнения могут быть решены точно Понятие точности решения подразумевает:) возможность написания «точной формулы», а точнее говоря

Линейные преобразования Определение линейного преобразования Пусть V линейное пространство Если указано правило по которому каждому вектору x из V ставится в соответствие единственный вектор y из V то

Системы линейных алгебраических уравнений Основные понятия Системой линейных алгебраических уравнений (СЛАУ) называется система вида a a a, a a a, a a a Ее можно представить в виде матричного уравнения

ПРИМЕНЕНИЕ МЕТОДА НЬЮТОНА В СИММЕТРИЧНОЙ ПРОБЛЕМЕ СОБСТВЕННЫХ ЗНАЧЕНИЙ О.О. Хамисов Иркутский госуниверситет Существует множество различных проблем, таких как устойчивость системы линейных уравнений или

УДК 519.615.7 Физико-математические науки Предлагается квазиньютоновский численный метод безусловной минимизации, показываются его преимущества перед методом Бройдена Флетчера Гольдфарба Шанно. Ключевые

Лекция3. 3. Метод Ньютона (касательных. Зададим некоторое начальное приближение [,b] и линеаризуем функцию f(в окрестности с помощью отрезка ряда Тейлора f(= f(+ f "((-. (5 Вместо уравнения (решим

Решения задач по алгебре за второй семестр Д.В. Горковец, Ф.Г. Кораблев, В.В. Кораблева 1 Линейные векторные пространства Задача 1. Линейно зависимы ли векторы в R 4? a 1 = (4, 5, 2, 6), a 2 = (2, 2, 1,

Лабораторная работа Методы минимизации функций одной переменной, использующие информацию о производных целевой функции Постановка задачи: Требуется найти безусловный минимум функции одной переменной (

Методы решения сеточных уравнений 1 Прямые и итерационные методы В результате разностной аппроксимации краевых задач математической физики получаются СЛАУ, матрицы которых обладают следующими свойствами:

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М.В.ЛОМОНОСОВА Механико математический факультет Кафедра вычислительной математики И. О. Арушанян Практикум на ЭВМ Безусловная минимизация функций многих переменных

ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ В разделе «Численные методы линейной алгебры» рассматриваются численные методы решения систем линейных алгебраических уравнений (СЛАУ) и численные методы решения задач

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

Занятие 1. Векторный анализ. 1.1. Краткое теоретическое введение. Физические величины, Z Z (M) для определения которых K достаточно задать одно число Y K (положительное или Y отрицательное) называются

4 Итерационные методы решения СЛАУ Метод простых итераций При большом числе уравнений прямые методы решения СЛАУ (за исключением метода прогонки) становятся труднореализуемыми на ЭВМ прежде всего из-за

ЛЕКЦИЯ 3 ЧИСЛЕННОЕ РЕШЕНИЕ СЛАУ Вспомним основные результаты, полученные на предыдущей лекции 1 Норма вектора = u Были введены следующие нормы вектора: =1 1 Октаэдрическая норма: 1 = max u, где p = 2 Кубическая

Лекция 11. Оптимальное управление 11.1 Постановка задачи Задана динамическая система с управлением, описываемая системой дифференциальных уравнений в форме Коши { ẋi = f i (x, u(t)), (11.1) (i = 1,...,

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ Факультет прикладной математики процессов управления М. Э. АББАСОВ МЕТОДЫ ОПТИМИЗАЦИИ Учебное пособие Санкт-Петербург 014 УДК 519.85 ББК.18 А 13 Р е ц е

ЛИНЕЙНАЯ АЛГЕБРА ВМЕСТЕ С MAPLE Усов В.В. 1 Скалярное произведение в арифметическом пространстве 1.1 Определение. Основные свойства Скалярное произведение (X, Y) векторов X = (x 1, x 2,..., x n), Y =

Методы решения сеточных уравнений 1 Прямые и итерационные методы В результате разностной аппроксимации краевых и начально-краевых задач математической физики получаются СЛАУ матрицы которых обладают следующими

Math-Net.Ru Общероссийский математический портал Л. Н. Полякова, Некоторые методы минимизации максимума квадратичных функций, Владикавк. матем. журн., 2006, том 8, номер 4, 46 57 Использование Общероссийского

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

Тема 2-15: Ортогональность А. Я. Овсянников Уральский федеральный университет Институт математики и компьютерных наук кафедра алгебры и дискретной математики алгебра и геометрия для механиков (2 семестр)

12. Линейные операторы на векторных пространствах (продолжение) Единственность жордановой нормальной формы F алгебраически замкнутое поле Теорема 9. τ Пусть A M n (F), A J и A J где J, J жордановы матрицы.

1. Численные методы решения уравнений 1. Системы линейных уравнений. 1.1. Прямые методы. 1.2. Итерационные методы. 2. Нелинейные уравнения. 2.1. Уравнения с одним неизвестным. 2.2. Системы уравнений. 1.

79 Линейные функции Определение и примеры линейных функций Определение Будем говорить, что на линейном пространстве L задана функция от одного вектора, если каждому вектору x L сопоставлено число (x)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ ПЕНЗЕНСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ЧИСЛЕННЫЕ МЕТОДЫ ЛИНЕЙНОЙ АЛГЕБРЫ Методические указания к выполнению лабораторных работ ПЕНЗА 7 Приведена методика и

Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Комсомольский-на-Амуре государственный технический

Митюков В.В. Ульяновское высшее авиационное училище гражданской авиации институт, программист ОВТИ, [email protected] Универсальное моделирование дискретно заданных множеств непрерывными зависимостями КЛЮЧЕВЫЕ

Планы ответов на вопросы экзаменационных билетов госэкзамена по курсу ОПТИМИЗАЦИЯ И ЧИСЛЕННЫЕ МЕТОДЫ, лектор проф. М. М. Потапов Вопрос: 4. Симплекс-метод для канонической задачи линейного программирования:

345 4 Ряды Фурье по ортогональным системам функций Пусть ((x - ортогональная система функций в L [ ; ] Выражение c (x + c1 (x + 1 c (x + + (c (x = c (x (41 = называется обобщенным рядом Фурье по

Численная оптимизация Функции многих переменных: условная оптимизация 26 ноября 2012 г. Численная оптимизация 26 ноября 2012 г. 1 / 27 x (l) i f(x) min, g j (x) 0, h k (x) = 0, x R n j = 1,..., J k = 1,...,

Рассмотрим методы отыскания экстремума функ­ции R ( x ) без активных ограничений. Активными принято называть такие ограничения, на границе которых находится решение. Величина шага  х в соотношении

x i +1 = x i +  x i

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

x i =  ( gradR ( x i )),

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

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

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

Рис. 3.5 . Иллюстрация траекторий поис­ка минимума функции градиентными

методами:

1 - оптимум; 2 -- траекто­рия метода градиента; 3 - траектория метода

тяжелого шарика; 4 - траек­тория метода наискорейшего спуска;

5 - траектория метода сопряженных градиентов;

Кроме того, для всех приве­денных траекторий выбраны различные начальные условия, с тем, чтобы не загромождать построения. На этом и последующих ри­сунках зависимость R ( x 1 , x 2 ) приведена в виде линий уровня на плоскости в координатах x 1 - x 2 .

Основные методы

Метод градиента.

Метод градиента в чистом виде формирует шаг по переменным как функцию от градиента R ( x ) в текущей точке поиска. Простейший алгоритм поиска min R ( x ) записывается в векторной форме следующим образом:

или в скалярном виде:

- порядковый номер аргумента,

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

Поиск каждой новой точки состоит из двух этапов:

1) оценка градиента R ( x ) путем вычисления частных производных от R ( x ) по каждой переменной х j ,

2) рабочий шаг по всем переменным одновременно.

Величина h сильно влияет на эффективность метода. Большей эффективностью обладает вариант метода, когда шаг по переменной определяется направляющими косинусами градиента.

где cosφ j =

В этом случае величина рабочего шага не зависит от величи­ны модуля градиента, и ею легче управлять изменением h . В рай­оне оптимума может возникать значительное "рыскание", поэто­му используют различные алгоритмы коррекции h .

Наибольшее распространение получили следующие алго­ритмы:

1. h i = const = h (без коррекции);

2. h i = h i -1 /2, если R (x i ) < R (x i -1 ) ; h i = h i -1 , R (x i ) > R (x i -1 ) ;

3. h i = h i -1 , если  1 ≤  ≤ 2 ; h i =2h i -1 , если 1 >;
если 2 < .

где  - угол между градиентами на предыдущем и текущем ша­ге;  1 и  2 - заданные пороговые значения выбираются субъек­тивно (например,  1 = π/6,  2 = π/3).

Вдали от оптимума направление градиента меняется мало, по­тому шаг можно увеличить (второе выражение), вблизи от опти­мума направление резко меняется (угол между градиентами R ( x ) большой), поэтому h сокращается (третье выражение).

Для оценки частных производных используются разностные методы:

1 . Алгоритм с центральной пробой

2. Алгоритм с парными пробами

где g j - пробный шаг по j -й переменной, выбираемый достаточ­но малым для разностной оценки производной.

Первый алгоритм требует меньших затрат по сравнению со вторым (обычно затраты выражаются количеством вычислений критерия оптимальности), но позволяет получить решение менее точно, чем второй, и эта погрешность зависит от величины проб­ного шага.

На рис. приведена одна из возможных траекторий поиска минимума двумерной функции градиентным методом (наряду с другими ниже рассматриваемыми методами).

Условием окончания поиска может являться малость модуля градиента R ( x ) , т.е. |grad R ( x ) | <  .

Рис. Иллюстрация получения производной с центральной и парными пробами.

Пример 1.

Требуется найти минимумфункции

R ( x 1 , x 2 ) = х 1 3 + 2 х 2 2 - 3х 1 - 4x 2 ,

2. Интервал поиска квадрат: х 1нач = -2, х 1кон = 2, х 2нач = -2, х 2кон = 2.

3. Начальная точка: х 10 = - 0,5, х 20 = -1.

4. Параметры поиска: коэффициент шага h = 0,1, пробный g = 0,01, погрешность  = 0,01.

5. Алгоритм метода: алгоритм 1 (х i +1 =х i - h grad R ( x i ) ).

6. Алгоритм коррекции шага: без коррекции коэффициента пропорциональности шага (h = const).

7. Способ вычисления производной: вычисление grad R с парными пробами.

Результаты вычислений . В начальной точке вычисляем градиент функции:

Значение критерия R = 7,3750. Делаем рабочий шаг по формуле 5, получаем

х 1 = - 0,275, х 2 = - 0,2.

В новой точке опять вычисляем производные:

Значение критерия R = 1,3750.

Делаем рабочий шаг, получаем x 1 = 0,002, х 2 = 0,280.

Таблица 18

			dR /dx 1	dR /dx 2

В последней точке модуль градиента меньше заданной по­грешности (0,0063 < 0,01), поэтому поиск прекращается.

Построить зависимость градиента от № шага

Пример 2.

Отличается от предыдущего только величиной коэффициента пропорциональности шага h , теперь h = 0,4. Ниже, в табл. 19 при­ведены только первые 14 шагов (как и в предыдущем случае). Целесообразно сопоставить их путем построения траекторий поиска при обоих значениях h в координатах х 1 – х 2 .

Таблица 19

			dR /dx 1	dR /dx 2

В этом случае поиск носит явно колебательный характер, плохо приближаясь к решению.

номер итерации	параметр оптимизации h=0,4	параметр оптимизации h=0, 1

Рис. 2.5. Сравнение сходимости градиентного метода при использовании различного шага.

Метод наискорейшего спуска.

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

В текущей точке вычисляется grad R ( x ) , и затем в направлении градиента ищется min R ( x ) . Практически это может быть осуществлено любым методом одномерной оптимизации (поиск по одному направлению - направлению градиента), наиболее часто используется сканирование до первого локального минимума по направлению grad R ( x ) .

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

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

Условием окончания может являться малость модуля градиента R ( x ) | grad R ( x ) | <  . Можно также использовать и малость прира­щений по переменным в результате шага, но только в том случае, если на данном шаге мы "проскочили" оптимум, иначе может оказаться, что малость шага обусловлена не близостью к оптиму­му, а малостью коэффициента пропорциональности шага h .

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

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

Пример.

Для сравнения с методом градиента рассмотрим решение пре­дыдущего примера при h = 0,1.

Результаты расчетов. Расчет производных детально рассмотрен выше, поэтому здесь не приводится. Ниже, в табл. 20 приводятся результаты движения по градиенту с постоянным ша­гом.

Таблица 20

			dR /dx 1	dR /dx 2

В следующей точке (0,400, 2,00) значение критерия (R = -0,256) оказывается хуже, чем в последней (R =-2,1996). По­этому в найденной точке оптимума по направлению снова вычис­ляем градиент и по нему совершаем шаги, до тех пор, пока не най­дем наилучшую точку (табл. 21).

Таблица 21

			dR /d х 1	dR /d х 2
Второй поиск по градиенту
Третий поиск по градиенту
Четвертый поиск по градиенту
Пятый поиск по градиенту

Метод сопряженных градиентов (пропустить).

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

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

Метод сопряженных градиентов является попыткой объединить достоинства методов первого и второго порядка с исключе­нием их недостатков. На начальных этапах (вдали от оптимума) метод ведет себя как метод первого порядка, а в окрестностях оптимума приближается к методам второго порядка.

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

Алгоритм метода можно записать следующим образом (в век­торной форме):

Величина  может быть приближенно найдена из выражения

Алгоритм работает следующим образом. Из начальной точки х 0 ищут min R ( x ) в направлении градиента (методом наискорейшего спуска), затем, начиная с найденной точки и далее, направ­ление поиска min определяется по второму выражению. Поиск минимума по направлению может осуществляться любым спосо­бом: можно использовать метод последовательного сканирова­ния без коррекции шага сканирования при переходе минимума, поэтому точность достижения минимума по направлению зави­сит от величины шага h .

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

Одна из возможных траекторий поиска минимума двумерной функции методом сопряженных градиентов приведена на рис. 17.