Алгоритм пассивного поиска минимума

 Алгоритм пассивного поиска минимума

Отрезок [a,b] исходный отрезок неопределенности. Пусть N - число точек, в которых необходимо провести вычисления целевой функции f(x), т.е. N экспериментов. Точки, в которых необходимо провести эксперименты, определяются следующим образом:

Среди вычисленных значений {f(xi)} (i=1,N), ищется точка xj , в которой достигается минимум:

f(xj)= min f(xi)         1iN

Найденная точка принимается за приближенное решение задачи . Исходный отрезок неопределенности [a,b] после экспериментов в N точках сужается до [xj-1,xj+1], длина которого равна:

Точность найденного решения равна половине отрезка неопределенности, т.е. , где  и x* - точное решение.

Алгоритм равномерного блочного поиска

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

Шаг 1.  Задаются исходный отрезок неопределенности [a,b],  - точность приближенного решения , число экспериментов в блоке – n (нечетное, n=2k-1). Проводим эксперимент в середине отрезка [a,b], т.е. вычисляем yk=f(xk), где xk=(a+b)/2.

Шаг 2.  Проводим эксперименты в остальных точках блока: yi=f(xi), где xi=a+i*(b-a)/(n+1), i=1,2,..,n, ik. Находим точку xj,  в которой достигается минимум среди вычисленных значений: f(xj)=min f(xi), следовательно, точное значение минимума x* содержится на отрезке [xj-1,xj+1].

Шаг 3.  Полагаем a=xj-1, b=xj+1, xk=xj, yk=yj. Если b-a2, то ,  и поиск заканчивается. Иначе перейти к шагу 2. Если заданная точность  достигнута после т итераций, т.е. после экспериментов в m блоках, то длина отрезка неопределенности после всех N вычислений (N=n+(m-1)(n-1)=(n-1)m+1) будет:

и  

Алгоритм деления интервала пополам

Это вариант предыдущего алгоритма при n=3.

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

Шаг 1. Задаются a,b,. Производим эксперимент в точке x2=(a+b)/2, т.е. вычисляем y2=f(x2).

Шаг 2.  Проводим эксперименты в остальных точках блока: x1=(a+x2)/2, y1=f(x1), x3=(x2+b)/2, y3=f(x3).

Находим xj такую, что f(xj)=min {f(xi)}.

1 ≤ i  ≤ 3  Тогда точное решение x* содержится на отрезке [xj-1,xj+1]. Предполагается .

Шаг 3. Полагаем a=xj-1, b=xj+1, x2=xj, y2=yj. Если b-a2, то   и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число проведенных экспериментов равно N=2к+1, а длина получившегося отрезка неопределенности будет , где [z] – целая часть числа z. Следовательно, достигнутая точность будет , =1/2LN.

Метод дихотомии

Это алгоритм блочного поиска для ni=n=2, т.е. когда в блоке два эксперимента. Так как пассивная составляющая алгоритма, т.е. блок, содержит четное число экспериментов, то оптимальный выбор точек xij, в которых необходимо провести эксперименты, будет неравномерным, в отличие от предыдущих алгоритмов, где число экспериментов в блоке было нечетным и, соответственно, расположение точек равномерным. Если блок содержит два эксперимента, то оптимальное (дельта оптимальное) расположение точек, в которых будут проводится эксперименты, это как можно ближе к середине отрезка. Такое расположение точек позволяет получить наименьший отрезок неопределенностей после экспериментов в блоке.

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

Шаг 1.  Задаются a,b, и  - малое положительное число, значительно меньшее чем .

Шаг 2.  Определяется середина отрезка x=(a+b)/2. Производятся эксперименты в двух точках близких середине: y1=f(x-), y2=f(x+).

Шаг 3.  Определяется следующий отрезок локализации, т.е. определяется какой из отрезков [a,x+] или [x-,b] содержит точное решение x*. Если y1y2, то это отрезок [a,x+] и b=x+, иначе это отрезок [x-,b] и a=x-, т.е. выбранный отрезок локализации мы снова обозначили как [a,b].

Шаг 4.  Если b-a2, то x=(a+b)/2,  и поиск заканчивается. Иначе перейти к шагу 2.

После к итераций общее число экспериментов будет N=2к, а длина получившегося отрезка неопределенности . Следовательно, .ъ

Метод золотого сечения

Для того чтобы уменьшить отрезок неопределённости [a,b], нам необходимо вычислить значение целевой функции f(x), по крайней мере, в двух точках на отрезке [a,b].

В результате этих двух экспериментов отрезок неопределённости сузится до отрезка [a,x2] или [x1,b]. Так как у нас нет никаких оснований предпочесть один из этих вариантов, то точки x1 и x2  должны быть симметричны относительно середины отрезка [a,b]. В этом случае длины отрезков [a,x2] и [x1,b] будут равны. Таким образом, остаётся вопрос как выбрать точку x1.

В методе золотого сечения точка x1  выбирается из соображения, что должно выполняться соотношение:

т.е. точка x1 делит отрезок [a,b] по правилу «золотого сечения», где λ  - есть «золотое отношение». Точка x2 определяется как точка симметричная к x1 относительно середины отрезка.

В результате экспериментов у нас получается отрезок неопределённости [a,x2], содержащий точку x1, или отрезок неопределённости [x1б], содержащий точку x2. Оказывается, что остающаяся точка на суженном отрезке неопределённости делит его вновь по правилу «золотого сечения». Следовательно, чтобы, в свою очередь, уменьшить новый отрезок неопределённости, нам не достаёт одного эксперимента, а именно, вычисления целевой функции в точке, симметричной к оставшейся точке относительно середины этого нового отрезка. Всё продемонстрировано на рисунке,

а)

б)

где буквы со штрихами обозначают новый отрезок неопределённости. Вариант а) соответствует случаю, если новым отрезком неопределённости будет [a,x2], а вариант б) – отрезку [x1,b].

В приводимой ниже схеме алгоритма остающиеся отрезки неопределённости переименовываются каждый раз как [a,b], а точки, в которых проводятся эксперименты на этом отрезке, обозначается через x1 и x2, причём . Кроме того, y1  и y2  имеют следующие значения: y1 =f(x1) и y2 =f(x2).

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

Шаг1. Задаются  a,b,ε и λ=1.618… Вычисляют .

Шаг2.  а) Если , то полагают  и вычисляют .

б) Если y1>y2, то полагают  и вычисляют .

Шаг3.  Если b-a>ε, то переходят к шагу 2. Иначе если y1<y2, то полагают  и  если y1≥y2, то полагают  и

Закончить поиск.

После каждой итерации длина отрезка неопределённости уменьшается в λ раз. Так как первая итерация начинается после двух экспериментов, то после N экспериментов длина отрезка неопределённости будет .

Метод чисел Фибоначчи

Этот метод применяется, когда число экспериментов N заранее задано. Метод чисел Фибоначчи, также как и метод золотого сечения относится к симметричным методам, т.е. точки, в которых выполняются два эксперимента, на основе которых происходит уменьшение отрезка неопределённости, расположены симметрично относительно середины отрезка. Вот только выбор точки x1 происходит на основе других соотношений. Для этого используются числа Фибоначчи: , где   и F0=F1=1.Точка x1 определяется из соотношения:

т.е. . Точка x1 делит [a,b] на две неравные части. Отношение малого отрезка к большему равно . Точка x2 определяется как точка, симметричная к x1 относительно середины отрезка [a,b]. Поэтому . При этом будет выполняться условие x1<x2.

В результате экспериментов в точках x1 и x2 у нас получится отрезок неопределённости [a,x2], содержащий точку x1, или отрезок неопределённости [x1,b], содержащий точку x2. Остающаяся точка делит новый отрезок неопределённости на две неравные части в отношении:

. То есть в методе Фибоначчи остающаяся точка делит отрезок на две неравные части в пропорциях определяемых числами Фибоначчи. Так на к-ом шаге это отношение равно  а длины отрезков равны:  и . Всё это показано на рисунке:

а)                                                                               

б)

 

Для того чтобы в свою очередь уменьшить получившийся отрезок неопределённости, надо определить симметричную точку относительно середины отрезка и произвести эксперимент в ней. Этот процесс продолжается, пока не будет проведено N экспериментов.

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

Шаг 1.  Задаются a,b,N Вычисляются числа Фибоначчи . Определяется:

Шаг 2.  а) Если y1≤y2, то полагают  и вычисляют .

б) Если y1>y2, то полагают  и вычисляют .

Повторить шаг 2 N-2 раза.

Шаг 3.  Если y1<y2, то полагают  и . Если y1≥y2, то полагают  и .

Закончить поиск.

Длина отрезка неопределённости в методе Фибоначчи .

Метод касательных

Пусть функция f(x) выпукла и дифференцируема на [a,b]. Идея метода состоит в следующем. Пусть [a,b] - отрезок неопределённости и  - результаты вычислений в точках a и b. По этой информации строится аппроксимирующая функция, представляющую из себя кусочно-линейную функцию, состоящую из касательной  к f(x) в точке a и касательной  к f(x) в точке b.

Полученная аппроксимирующая функция есть ломанная состоящая из прямой La(x) на [a,c] и Lb(x) на [c,b], где с – точка пересечения касательных. Легко заметить, что при f(a)>0 и f(b)>0 минимум аппроксимирующей функции достигается в точке с. Значение точки пересечения с можно определить по формуле

В точке с производятся вычисления  f(c) и f``(c). Если f``(c)=0, то решением задачи будет x*=c. Если же f `(c)>0, то в качестве следующего отрезка неопределённости будет [a,c]. Если же f``(c)<0, то – отрезок [c,b]. Процесс повторяется до тех пор, пока f `(c)=0  или отр–к неопр–ти не достигнет заданной точности.

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

Шаг 1.  Заданы  a,b,ε. Вычислить .

Шаг 2.  Если b-a≤2ε, то полагаем . Поиск окончен. Если b-a>2ε, то вычислить . Если z=0, то полагаем  и поиск окончен. Если z<0, то . Если z>0, то . Повт–ть шаг2 .

Метод парабол

Рассмотрим алгоритм квадратичной интерполяции или метод парабол, т.е. в качестве аппроксимирующей функции используется парабола. Для однозначного задания параболы необходимы три точки. Пусть имеются три точки, для кот–х вып–ся   a<c<b,  f(c)f(a),  f(c)f(b). Так как [a,b] – отрезок неопределенности и f(x) – унимодальная функция, то найти такую точку c  нетрудно. Парабола, проходящая через три точки (a,f(a)), (c,f(c)), (b,f(b)), имеет вид

Поскольку f – унимодальная функция, то хотя бы одно из неравенств     f(c)f(a), f(c)f(b) строгое и, следовательно, коэф–т при старшем члене P(x) положителен. Тогда P(x) достигает минимума в точке

,

причем (a+c)/2t(c+b)/2. Эта точка и выбирается в качестве точки очередного вычисления знач–я функции.

Если оказалось, что t=c, условимся в качестве точки очередного вычисления выбирать точку (a+c)/2. Итак, следующее вычисление проводится в точке

Определим новый отрезок неопределенности с лежащей внутри него точкой, для которой выполняются условия аналогичные условиям, которым удовлетворяла точка c. В силу унимодальности функции f и  в зависимости от выполнения или невыполнения условий x<c, f(x)<f(c), f(x)=f(c) это будут отрезки с точкой внутри: [a,c] и x; [x,b] и c; [x,c] и (x+c)/2; [a,x] и c; [c,b] и x; [c,x] и (x+c)/2. Смотри рисунок. Далее строится парабола, определяется ее минимум, и т.д., до тех пор, пока длина отрезка неопределенности не удовлетворяет заданной точности.

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

Шаг 1. Задаются a,c,b и . Вычислить ya=f(a), yc=f(c), yb=f(b).

Шаг 2. Вычислить , y=f(x), где

Шаг 3. А) При x<c.

Если y<yc, то b=c, c=x, yb=yc, yc=y.

Если y>yc, то a=x, ya=y.

Если y=yc, то a=x, b=c, c=(x+c)/2, ya=y, yb=yc, yc=f(c).

Б) При x>c.

Если y<yc, то a=c, c=x, ya=yc, yc=y.

Если y>yc, то b=x, yb=y.

Если y=yc, то a=c, b=x, c=(x+c)/2, ya=yc, yb=y, yc=f(c).

Шаг 4. Если b-a, то закончить поиск, положив , иначе перейти к шагу 2.

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

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

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

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

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

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

             хк+1 = хк - f’(xk),

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

Шаг 3. Вычисляется значение градиента в точке хк+1:

                    ,

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

Шаг 4. Если || f ` (xk+1) ||3, то поиск заканчивается, при этом:

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

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

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

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

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

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

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

Шаг 2. Проверяется условие: f(xk-)-||||2. Если выполняется, то переходим к шагу 3, иначе дробим значение  (=/2) и повторяем шаг 2.

Шаг 3. Определяется точка очередного эксперимента:    хк+1 = хк -  f`(xk).

Шаг 4. Вычисляется значение градиента в точке хк+1: f `(хк+1).

Шаг 5. Если || f`(xk+1) ||3, то поиск заканчивается, при этом:

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

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

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

называется методом наискорейшего спуска. Разумеется, этот способ выбора к сложнее ранее рассмотренных вариантов.

Реализация метода наискорейшего спуска предполагает решение на каждой итерации довольно трудоемкой вспомогательной задачи одномерной минимизации. Как правило, метод наискорейшего спуска, тем не менее, дает выигрыш в числе машинных операций, поскольку обеспечивает движение с самым выгодным шагом, ибо решение задачи одномерной минимизации связано с дополн–ми вычислениями только самой функции f(x), тогда как основное машинное время тратится на вычисление ее градиента f ` (xk).

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

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

Шаг 1. Задаются х0, 3. Вычисляется градиент f `(x0), направление поиска.    

          Присваивается к=0.

Шаг 2.Опр–тся точка очередного эксперимента:

хк+1 = хк -  к f``(xk),   где к – минимум задачи одномерной минимизации:

Шаг 3.Вычисляется значение градиента в точке хк+1: f`(xk+1)..

Шаг 4. Если ||||3, то поиск точки минимума заканчивается и полагается:

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

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

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

Пусть                                    - нач–ое приближение. Вычислим частную производную по первой координате и примем:

      где е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 вводятся исходные данные х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.

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

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

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

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

 

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

На втором этапе задается некоторое большое число 2>>1 и используется процедура спуска, где вместо градиента f ` (xk) берется вектор 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. При спуске вычисление очередной точки осуществляется с          

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

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

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

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

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

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

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

Шаг 4.

Если ||xk – xm||  1 и || f ` (xm) ||  3, то полагаем:

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

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

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

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

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

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

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

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

   осуществляется градиентный спуск с постоянным шагом  на дно оврага. В

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

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

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

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

или

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

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

Шаг 4. Если ||uk+1-uk||1 и || f `(uk+1) ||3, то полагаем:

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

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

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

        

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

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

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

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

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

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

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

Шаг 3.

Если ||uk+1-uk||1 и  | f `(uk+1) ||3, то полагаем:

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

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

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

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

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

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

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

                                      ,   

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

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

Определяется направление минимизации целевой функции

f(x)=f(x(1),x(2),…,x(n)) в базисной точке

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

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

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

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

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

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

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

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

            f(xk +(z-xk) = ().

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

а) к==const постоянная для всех итераций; б) задается начальное 0=, а далее к=к-1, если f(xk+1)<f(xk), иначе дробим к, пока не выполнится это условие; в) к определяется решением задачи одномерной минимизации функции ().

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

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

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

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

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

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

Для этого задаются начальная точка х0(0) и длина ребра симплекса l. Формируются остальные вершины симплекса:

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

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

Для этого на к-й итерации вычисляются значения целевой функции в каждой точке симплекса. Пусть для всех i: f(xmin(k))f(xi(k))f(xmax(k)),  где min, max, i – номера соответствующих вершин симплекса. Опр–м центр тяжести всех точек, исключая точку xmax(k),  Ck=(xi(k))/n .

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

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

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

uk=ck+(ck-xmax(k))=2ck-xmax(k)

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

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

а) f(uk)<f(xmax(k);   б) f(uk)f(xmax(k).

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

Случай б): в результате отражения получается новая точка uk, значение функции в которой еще хуже, чем в точке xmax, то есть отражать симплекс некуда. Поэтому в этом случае производится пропорциональное уменьшение симплекса (например, в 2 раза) в сторону вершины xmin(k):            xi(k+1)=x^i=(xi(k)+xmin(k))/2, где i=0,1,…,n.

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

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

Если

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

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

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

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

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

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

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

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

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

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

f(xmin(k))≤ f(xi(k)) ≤ f(xm(k)) ≤  f(xmax(k)),

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

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

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

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

                        uk=Ck+*(Ck-xmax(k)),   где -коэффициент отражения.

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

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

 а)  f(uk)< f(xmin(k));

 б)  f(uk)>f(xm(k));

 в)  f(xmin(k))≤ f(uk) ≤  f(xm(k));

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

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

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

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

               

 

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

Если f(vk)<min{f(xmax(k)),f(uk)}, то вершина xmax(k) заменяется на vk .

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

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

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

Шаг 5.  

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

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

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

Опыт использования описанного алгоритма показывает, что целесообразно брать следующие значения параметров:   =1, =2, =0.5.

Метод Ньютона

В методе Ньютона последовательность точек спуска определяется формулой (4). Для текущей точки xk направление и величина спуска  определяется вектором pk = – (f ''(xk)) –1·f '(xk). Хотя в определении вектора pk фигурирует обратная к f ''(xk) матрица (f ''(xk)) –1, на практике нет необходимости вычислять последнюю, так как направление спуска pk можно найти как решение системы линейных уравнений

f ''(xk)·pk = – f '(xk) (5) каким-нибудь из методов.

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

шаг 1:На первой итерации, при  k = 0, вводятся начальное приближение x0 и условие останова ε3. Вычисляются градиент f '(x0) и матрица f ''(x0).шаг 2:Определяется направление спуска pk, как решение системы линейных уравнений f ''(xk)·pk = – f '(xk) (например, методом исключений Гаусса).шаг 3:Определяется следующая точка спуска:xk+1 = xk + pk.шаг 4:Вычисляются в этой точке xk+1 градиент f '(xk+1) и матрица f ''(xk+1).шаг 5:Если ||f '(xk+1)||  ε3, то поиск на этом заканчивается и полагается x = xk+1 и y = f(xk+1).Иначе k = k + 1 и переход к шагу 2.

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

В общем случае, когда минимизируемая функция не квадратична, вектор pk = – (f ''(xk)) –1·f '(xk) не указывает в точку её минимума, однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент. Этим и объясняется более высокая сходимость метода Ньютона по сравнению с градиентными методами при минимизации овражных целевых функций.

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

Методы с регулировкой шага (методы Ньютона – Рафсона)

Удачный выбор начального приближения x0 гарантирует сходимость метода Ньютона. Однако отыскание подходящего начального приближения – далеко не простая задача. Поэтому необходимо как-то изменить формулу (4), чтобы добиться сходимости независимо от начального приближения. Доказано, что в некоторых предположениях для этого достаточно в методе Ньютона кроме направления движения (f ''(x)) –1·f '(x) выбирать и длину шага вдоль него. Такие алгоритмы называются методами Ньютона с регулировкой шага (методами Ньютона – Рафсона) и выглядят так:

xk+1 = xk – k(f ''(xk)) –1·f '(xk). (6)

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

f(xk + kpk ) – f(xk)  ·k(f '(xk), pk),  (7)

где pk = – (f ''(xk)) –1·f '(xk) – направление спуска, а  0 <  < ½ – некоторое заданное число, общее для всех итераций. Если это неравенство выполнено при k = 1, то шаг принимается равным единице и осуществляется следующая итерация. Если нет – дробится до тех пор, пока оно не выполнится.

Схема метода Ньютона – Рафсона с дроблением шага.

шаг 1:На первой итерации, при  k = 0, вводятся исходные данные x0, , ε3. Вычисляются значения градиента f '(x0) и матрица f ''(x0).шаг 2:Присваивается  = 1. Определяется направление спуска pk, как решение системы линейных уравнений f ''(xk)·pk = – f '(xk).шаг 3:Проверяется условиеf(xk + kpk ) – f(xk)  ·k(f '(xk), pk).Если выполняется, то переход к шагу 4.Иначе дробим значение шага  (например,  = /2) и повторяем шаг 3.шаг 4:Определяется следующая точка:xk+1 = xk + ·pk.шаг 5:Вычисляются значение градиента f '(xk+1) в точке xk+1.шаг 6:Если ||f '(xk+1)||  ε3, то поиск на этом заканчивается и полагается x = xk+1 и y = f(xk+1).Иначе k = k + 1 и переход к шагу 2.

Второй метод определения шага k в схеме (6), как и в методе наискорейшего спуска состоит в минимизации функции

f(xk + kpk ) = min f(xk + kpk ).

Схема метода Ньютона – Рафсона с выбором оптимального шага.                                       α≥0

шаг 1:При  k = 0, вводятся x0, ε3. Вычисляются f '(x0) и f ''(x0).шаг 2:Определение направления спуска pk, как решение системы линейных уравнений f ''(xk)·pk = – f '(xk).шаг 3:Определяется следующая точка спуска:xk+1 = xk + pk,где  - решение задачи одномерной оптимизации: min f(xk + pk ).шаг 4:Вычисляются в точке xk+1:  f '(xk+1)  и  f ''(xk+1).шаг 5:Если ||f '(xk+1)||  ε3, то поиск заканчивается и полагается x = xk+1 и y = f(xk+1).                                                             α≥0Иначе k = k + 1 и переход к шагу 2.

Модификации метода Ньютона

Значительные трудности, возникающие при практической реализации метода Ньютона, связаны с необходимостью вычислить матрицу f ''(x). Мы рассмотрим две модификации метода Ньютона, которые используют не точные значения, а некоторые приближённые аналоги матрицы вторых производных. В результате уменьшается трудоёмкость методов, но, конечно, ухудшается их сходимость.

В качестве первой модификации метода Ньютона рассмотрим следующий алгоритм:

xk+1 = xk – k(f ''(xk)) –1·f '(xk),    k ≥ 0. (8)

здесь для построения направления спуска используется один раз вычисленная и обращённая матрица вторых производных f ''(x0).

Схема модификации I метода Ньютона.

шаг 1:При  k = 0, вводятся x0, ε3. Вычисляются f '(x0) и f ''(x0).шаг 2:Определение обратной матрицы (f ''(x0))–1.шаг 3:Определение направления спуска pk:pk = – f '(xk)·(f ''(x0))–1.шаг 4:Определение следующей точки:xk+1 = xk + ·pk,где  – решение задачи одномерной минимизации функцииφ() = f(xk + ·pk), при  ≥ 0.шаг 5:Вычисление в точке xk+1.градиента f '(xk+1) шаг 6:Если ||f '(xk+1)||  ε3, то поиск заканчивается и полагается x = xk+1 и y = f(xk+1).Иначе k = k + 1 и переход к шагу 3.

В рассмотренной схеме для выбора шага k используется способ аналогичный исп–му в методе наискорейшего спуска. Но можно было бы воспользоваться и способом аналогичным используемому в градиентном методе с дроблением шага.

Если матрица f ''(x) положительно определена, то итерационный процесс () является одной одной из модификаций градиентного спуска, независимо от начального приближения x0.

Другая модификация метода Ньютона

связана с обновлением матрицы вторых производных через определённое количество шагов. Формула вычисления очередной точки xk+1, в этом случае, будет выглядеть следующим образом:

Xjm+i+1 = xjm+i – jm+i· (f ''(xjm)) –1·f '(xjm+i),

jm+i ≥ 0, k = jm + i, j = 0, 1, 2, …,   i = 0, 1, …, m –1.

Здесь m > 0 – целое число, определяющее количество шагов через которое происходит обновление матрицы вторых производных f ''(x). Этот метод занимает промежуточное положение между методом Ньютона и его модификацией I.

Схема модификации II метода Ньютона.

шаг 1:Вводятся x0, ε3, m. Присваиваются j = 0 и k = 0. Вычисляется градиентf '(x0).шаг 2:Вычисляется (обновляется) матрица f ''(xjm) и обратная матрица(f ''(xjm))–1.шаг 3:Определение направления спуска pjm+1:pjm+1 = – f '(xjm+1)·(f ''(xjm))–1.шаг 4:Определение очередной точки xjm+i+1:xjm+i+1 = xjm+i + ·pjm+i,где  – решение задачи одномерной минимизации функцииφ() = f(xjm+i + ·pjm+i), при  ≥ 0.шаг 5:Вычисление в очередной точке xjm+i+1.градиента f '(xjm+i+1) шаг 6:Если ||f '(xjm+i+1)||  ε3, то поиск заканчивается и полагается x = xjm+i+1 и y = f(xjm+i+1).Иначе k = k + 1 и переход к шагу 7.шаг 7:Определяется i = i + 1.Если  i = m, то j = j + 1, i = 0 и переход к шагу 2 (т.е. будем обновлять матрицу f ''(x)).Иначе переход к шагу 3 (т.е. используется матрица f ''(x), вычисленная на одном из предыдущих шагов).

Метод  сопряженных градиентов

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

Два вектора x и y называют Н - сопряженными (или сопряженными по отношению к матрице Н) или Н - ортогональными, если

(x, H·y) = 0.  (9)

Сопряженность можно считать обобщением понятия ортогональности. В самом деле, когда  Н = Е, х и у в соответствии с уравнением (9) ортогональны. Рассмотрим квадратичную функцию n - переменных

f (x) = a + (x,b) + ½ (x, H·x).  (10)

с положительно определенной n·n матрицей. Оказывается, что квадратичная функция (10) может быть минимизирована методом сопряженных направлений не более чем за n шагов.

Чтобы воспользоваться этим методом минимизации квадратичной функции (10) нужно знать n - взаимно сопряженных направлений S0, S 1,…,S n-1. Эффективность таких направлений – самостоятельная проблема. Существует много взаимно сопряженных направлений S0, S 1,…,S n-1 и способов их построения. Ниже излагается метод сопряженных градиентов Флетчера - Ривса, в котором выбор Н - сопряженных направлений осуществляется совместно с одномерной минимизацией f (х) по α..

Метод Флетчера – Ривса.

Этот метод использует последовательность направлений поиска, каждая из которых является линейной комбинацией антиградиента в текущей точке и предыдущего направления спуска. Метод изменяется к квадратичной целевой функции   f (x) = a + (x,b) + ½ (x, H·x).

При минимизации ее методом Флетчера - Ривса векторы Sk вычисляются по формулам

                                      S0 = – f ' (x 0),  S k = – f '(x k ) + β  k-1·S k-1 , при k ≥ 1.

Величины β k-1  выбираются так, чтобы направления S k , S k-1 были  Н – сопряженными.

Точка х  k-1 ,определяется в результате минимизации функции f (х) в направлении S k, исходящем из точки x k, т.е.

х k+1 = x k + α k·S k, где α k доставляет минимум  по α k функции f (x k, α ·S k).

Итак, предлагаемая процедура минимизации функции  f (x) выглядит следующим образом. В заданной точке x0  вычисляется антиградиент

S0 = – f ' (x 0). Осуществляется одномерная минимизация в этом направлении и определяется точка x 1. В точке x 1 сново вычисляется антиградиент – f ' (x 1). Так как эта точка доставляет минимум функции f (x) вдоль направления S0 = – f ' (x 0), вектор f ' (x 1) ортогонален f ' (x 0). Затем по известному значению f ' (x 1) по формуле (11) вычисляется вектор S 1, который за счет выбора β 0 будет Н – сопряженным к S 0. Далее отыскивается минимум функции f (х) вдоль направления S 1 и т.д.

шаг 1:При  k = 0 ввод начального приближения x0. Вычисление антиградиента S0 = – f '(x0).шаг 2:Решение задачи одномерной минимизации по  функцииf(xk + ·Sk),  в результате чего определяется величина шага k и точка xk+1 = xk + k·Sk.шаг 3:Вычисление величин f(xk+1) и f '(xk+1).шаг 4:Если f '(xk+1) =0, то xk+1 – решение задачи.Иначе определяем новое направление поиска: Sk+1 из соотношения :Sk+1 = – f '(xk+1) +         ·SkДалее r = r + 1  и переход к шагу 2.

Это и есть окончательный вид алгоритма Флетчера-Ривса. Как было замечено ранее, он найдет минимум квадратичной функции не более чем за n шагов.

Минимизация неквадратичной целевой функции.

Метод Флетчера-Ривса может применятся для минимизации и неквадратичных функций. Он является методом первого порядка и в тоже время скорость его сходимости квадратична. Разумеется, если целевая функция не квадратична, метод уже не будет конечным. Поэтому после (n+1)-й итерации процедура повторяется с заменой x0 на xn+1, а счет заканчивается при ||f '(xk+1)||  ε, где ε – заданное число. При минимизации неквадратичных функций обычно применяется следующая модификация метода Флетчера-Ривса.

Схема алгоритма для неквадратичных целевых функций.

шаг 1:При  k = 0 ввод начального приближения x0 и условия останова ε3. Вычисление антиградиента S0 = – f '(x0).шаг 2:Решение задачи одномерной минимизации по  функцииf(xk + ·Sk),  в результате чего определяется величина шага k и точка xk+1 = xk + k·Sk.шаг 3:Вычисление величин f(xk+1) и f '(xk+1).шаг 4:Если ||f '(xk+1)||  ε3, то точка xk+1 – решение задачи и на этом поиск заканчивается.Иначе определяется коэффициент βk по формуле:βk = шаг 5:Вычисление Sk+1 по формуле Sk+1 = – f '(xk+1) + βk·Sk.Присваивается k = k + 1 и переход к шагу 2.

Здесь I – множество индексов, I = {0, n, 2n, 3n, …}. Значения k, для которых βk = 0, называют моментами обновления метода. Таким образом, обновление метода происходит через каждые n шагов.

← Предыдущая
Страница 1
Следующая →

Алгоритм равномерного блочного поиска Алгоритм деления интервала пополам Метод дихотомии Градиентный метод с постоянным шагом Метод наискорейшего спуска Схема метода Гаусса – Зейделя Овражные методы (Метод Гельфанда)

У нас самая большая информационная база в рунете, поэтому Вы всегда можете найти походите запросы

Искать ещё по теме...

Похожие материалы:

Сохранить?

Пропустить...

Введите код

Ok