40842

Методы первого порядка (градиентные методы)

Лекция

Информатика, кибернетика и программирование

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

Русский

2013-10-22

302.5 KB

27 чел.

Основные понятия.

1. X- множество вариантов или допустимое множество.

  1.  f : XR1 - целевая функция.

Точка x*X - оптимальная, если выполняется f(x*)=min f(x), xX  (*).

    Если верно (*) для любого xX, то точка x- точка глобального минимума.

    Если нет, но существует R1,  >0 такое что:

         f(x) f(x*), для любого x из - окрестности, то есть ||x-x*||< , то  

    x* - точка локального минимума.

Надо найти экстремумы функции f на множестве X.

Содержание курса состоит в поисках экстремумов.

Будем искать min f(x), xX , так как max f(x)= - min(-f(x)), xX.

Множество X бывает:

  1.  Конечным (конечное множество элементов, например графы).
  2.  Конечномерным (когда совпадает или является подмножеством множества евклидова пространства).
  3.  Бесконечномерным (не вкладывается в евклидово пространство ,например множество непрерывных функций на отрезке).

Соответствие методов и множеств.

  1.  Методы решения переборных задач (метод ветвей и границ, динамическое   

   программирование и др.)

  1.  Методы решения задач математического программирования

    (условная/безусловная минимизация, нелинейное, выпуклое и линейное

   программирование).

  1.  Методы вариационного исчисления и методы оптимального управления

   (уравнение Эйлера-Лагранжа, принцип максимума).

  1.  Безусловная оптимизация (многомерные функции).

min f(x), x = Rn, то есть минимизация на всем пространстве.

Определение:

Минимизация заданная неравенствами, равенствами и другими             ограничениями называется условной.

Пусть:

  1.  x = Rn  (евклидово n-мерное пространство);
  2.  Функция f дифференцируема хотя бы один раз,

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

f(x)=0, где

(вектор частных производных по каждому аргументу)

f(x)= 

            

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

  1.  xiX,i;
  2.  f(x0)>f(x1)>...;
  3.  xix* = argmin f(x), i, xX.

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

Общая схема безусловной оптимизации  

xRn

xk+1 = xk+ tkSk , где Sk -вектор, определяющий направление изменения xk

                              tk - скаляр, определяющий длину шага.

Sk может зависеть от xk: Sk = (xk), а может от xk-1. В зависимости от этого критические методы делятся на:

одношаговые ((xk));

двухшаговые ((xk, xk+1)).

Эти методы имеют основное распространение.

  1.  Методы первого порядка (градиентные методы)

Для вычисления t и S используются значение функции и первая производная.

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

Пусть Sk = -f(xk), tk - длина шага.

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

Пусть tk = t (т.е. не зависит от к-пост.)

xk+1 = xk -  tf(xk)

Видно, что останавливаемся в любой точке, где f(xk)=0.

Пример:

f(x) = ax2, a>0, x-скаляр

xk+1=xk - 2taxk = (1- 2at)xk

Отсюда

1-2at<1 at<1- необходимое и достаточное условие существования предела

Если 0<tk<1/a - сходится,

        tk>1/a -  расходится,

        tk=1/a - зацикливается.( tk=1/a x1=x0-2x0= -x0  x2=x1-2x1= -x1=x0 и т.д.)

Выбор постоянного шага приводит к осложнениям. Оценим сходимость этого метода в общем случае.

Теорема (о сходимости метода градиентов)

Пусть f(x)- дифференцируема на Rn, f(x) удовлетворяет условию Лифшица:

|| f(x)-f(y) || L ||x-y || (*) 

(||x2|| = xi2 ), f(x)- ограничена снизу

f(x) f* >- (**) и 0< t< 2/L(***), L -const.

Тогда в методе xk+1= xk-tf(xk), градиент стремится к нулю,

т.е. limf(xk) =0, при k, а функция f(x)  монотонно убывает f(xk+1)f(xk). Точнее f(xk+1) f(xk)-t(1-tL/2)||f(xk) ||2(градиент характеризует скорость убывания и множитель)

Доказательство

Известно из мат.анализа:

  (1)

Пусть x=xk, y= -tf(xk)  (2)

Подставим (2) в(1):

f(xk+1)=f(xk)-t||f(xk) ||2-t-f(xk),f(xk))dT 

f(xk)-t+Lt2||f(xk) ||2 =f(xk)-t(1-Lt/2) ||f(xk) ||2

Обозначим a = t(1-Lt/2); a>0, так как (***)

Отсюда  f(xk+1) f(xk)-a||f(xk) ||2

Выразим f(xk+1) через f(x0)

Пусть k=0: f(x1) f(x0)- a||f(x0) ||2

                 k=1: f(x2) f(x1)- a||f(x1) ||2 f(x0)- a||f(x0) ||2 - a||f(x1) ||2.........

f(xk+1) f(x0)- a2

так как a>0, то 2 a-1(f(x0)-f(xs+1)) a-1(f(x0)-f*), для любого S

то есть < ( сумма ограничена) ||f(xk) ||0, то есть теорема доказана.

Замечание:

Сходимость градиента к нулю не гарантирует сходимости к минимуму.

Пример:

, градиент сходится к нулю, но функция не имеет минимума.

Равенство градиента нулю- необходимое условие минимума, достаточное условие- положительность второй производной.

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

Выпуклые функции и множества

Определение

Множество X называется выпуклым, если x1,x2X, [0,1], выполняется

x1+(1-)x2X, то есть вместе с любыми двумя точками оно содержит и отрезок их соединяющий.

На рис 1 изображено выпуклое множество, на рис 2 - невыпуклое.

рис 1                                   рис2

Определение

Точка Z называется выпуклой комбинацией точек x1,x2,...,xm, если

, ,,

Теорема (о выпуклом множестве)

Выпуклое множество X содержит все выпуклые комбинации своих точек.

Определение

Функция f(x) называется выпуклой если ее область определения выпукла и для любого x1,x2X, (0,1) выполняется f(x1+(1-)x2) f(x1)+(1-)f(x2)

(функция выпукла, если ее график под хордой )

Определение

Функция f(x), для которой -f(x) выпукла называется вогнутой.

Определение

Функция f(x) на Rn называется строго выпуклой, если xy, 0<<1 выполняется

f(x+(1-)y)<f(x)+(1-)f(y),

сильно выпуклой с константой l>0, если при 0  1 выполняется

f(x+(1-)y)f(x)+(1-)f(y)-l(1-)||x-y||2/2

Cвойства выпуклых функций

1.Теорема:

Любая точка локального min выпуклой функции является в то же время точкой глобального минимума.

Под интегралом:

(f(xk-tf(xk))-f(xk),-tf(xk))

Из условия теоремы известно:

||f(x)-f(y)|| L||x-y||

В данном случае:

x-y = -tf(xk), то есть ||f(xk-tf(xk))-f(xk)|| L||- tf(xk)||

и тогда соответствующее скалярное произведение:

L(- tf(xk), - tf(xk)) = Lt2||f(xk)||2

Доказательство

Пусть x*- точка локального минимума функции, она не является точкой глобального минимума, то есть yX такая что:

f(y)<f(x*)  (*)

Рассмотрим точки вида x = y+(1-)x* ,(0,1)

Так как X выпукло, то xX (по определению). Из выпуклости функции f(x)

и из (*) следует:

f(x)=f(y+(1-)x*)(по вып.)f(y)+(1-)f(x*)<(*)f(x*)+(1-)f(x*)=f(x*)

Получено: f(x)<f(x*) 

Но это противоречит условию, говоря о том, что х*- локальный минимум, так как при малых точка х находится в достаточно малой окрестности точки х*.

Тогда теорема доказана от противного.

Теорема(о сильно выпуклой функции)   

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

Без доказательства

2.Теорема:

Пусть функция  f (х)  имеет вторую непрерывную производную. Для того,

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

производная была неотрицательна.

Без доказательства   

Для сильно выпуклых функций: 2f (x)  l*I., где I- единичная матрица, l>0

Эту теорему можно рассматривать как критерий выпуклости

дифференцируемых функций.

 

Замечание:

Не все выпуклые функции дифференцируемы.

Примеры:

1.f(x) = x-выпуклая, не дифференцируемая

2.y = x2         выпуклые, проверка выпуклости

   y = -ln(x)    по второй производной

3.Теорема (неравенство Йенсена):

Чтобы фукция f (x) была выпукла необходимо и достаточно, чтобы

m 2, x1,x2,…,xmХ  и  i 0  i =1  выполнялось:

      m                              m            

 f (  i* xi )    i * f (xi ).  (*)

     i=1                            i=1

Доказательство:

  1.  Достаточность, т.е. справедлива (*), нужно доказать выпуклость: пусть

m = 2, тогда f (x) – выпукла по определению.

  1.  Необходимость, т.е. дана выпуклость, нужно доказать (*): при m = 2 (*) 

выполняется по определению.

3.Пусть при m = k теорема доказана (индукционное предположение).

Докажем при m = k + 1:

 k+11, тогда i xi = k+1*xk+1 + (1 - k+1)* i * xi /(1 - k+1),

тогда i * xi Х., так как выпуклое множество содержит все выпуклые

комбинации своих множеств.

Воспользуемся свойством выпуклости функций:

                                

 f (i* xi )  k+1*f (xk+1) + (1 - k+1)* f ( i* xi/(1 - k+1))

Предположим, что теорема доказана для m=k

i/(1-k+1)= (1-k+1)/ (1-k+1)=1 удовлетворяет условиям теоремы (сумма всех коэффициентов равна 1)

 k+1*f (xk+1) + (1 - k+1)* i * f (xi)/(1 - k+1) = i * f (xi )

Неравенство доказано.

 

4.Теорема:

Выпуклая функция f (x) , определенная на выпуклом множестве X непрерывна в

каждой внутренней точке этого множества и имеет в каждой внутренней точке

производную в любом направлении.

Без доказательства

Пусть есть направление s ( ||s||=1-норма вектора):

f (x)/ s = lim = f s(x)= (f (x), s)-производная по направлению

        0,   0

5.Теорема:

Для дифференцируемой функции f (x) на выпуклом множестве X выпуклость

эквивалентна неравенству:

f (x +y) f (x) + (f(x),y )

Строгая выпуклость эквивалентна неравенству:

f (x +y) f (x) + (f(x),y )

Сильная выпуклость эквивалентна неравенству:

f (x +y) f (x) + (f(x),y ) + l*||y||2/2, где l=const

Без доказательства

6. Для сильно выпуклых функций справедливы соотношения:

1.  f (x) f (x*) + l*|| x - x*||2/2

2. (f(x), x-x*)  l*|| x - x*||2

3. ||f(x)||  l* || x - x* ||

Без доказательства

Градиентные методы (продолжение)

xk+1 = xk - *f ( x k )

Оценим скорость сходимости для выпуклых функций:

Теорема:

Пусть f (x) дваждыдифференцируема и  l*I  2f (x) L*I, где l>0, L>0  x (*),

то есть f (x) – выпукла, тогда при  0   2/L выполняется неравенство:

|| xk –x*|| || x0 –x*||*qk – геометрическая сходимость,

где q = max {|1-*l|,|1-*L |}, при этом  min q() = (L-l)/(L+l)<1 и достигается при

= *=2/(L+l).

Доказательство: Применим формулу

f (x+y)= f (x)+(x+*y)y d   к производной:

f (xk)= f (x*) + 2f (x*+*(xk-x*))( xk-x*) d = Ak*( xk-x*),

где матрица Ak=2f(x*+*(xk-x*))d симметричная и неотрицательно определена.

Из (*) следует l*I Ak  L*I,

|| xk+1 –x*|| = || xk*f ( x k ) - x*|| = || xk – x* - * Ak( x k - x*)|| =

= || (I- *Ak)*( x k - x*)|| || I- *Ak ||*|| x k - x*||

Для любой симметричной матрицы А выполняется:

|| I- A|| = max {|1-1|,|1-k|}, где 1,k – соответственно наименьшее и наибольшее собственные числа (значения) матрицы А.

Поэтому || xk+1 –x*|| || xk –x*||*q, где q = max {|1-*l|,|1-*L |}

так как 0   2/L и 0< l <L, то |1-*l| <1, |1-*L |<1 q<1.

Найдем min q()

       

q()

                                     max =q()

         1-l

                                                                                         1-l

    1

                    L-1  *                                      l-1                                           

  1-l**= -(1-L*)  *=2/(L+ l).

Тогда q(*) = (L-l) / (L+ l)

  

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

Как известно выбор постоянного шага может привести к осложнениям.

xk+1 = xk - tk*f ( x k )-градиентный метод. Если шаг выбрать с условием, что  f(xk+1) - f(xk) -* tk * || f(xk)|| (*), где 0   < 1, то результат будет лучше значительно.

Иллюстрация:

Необходимо двигаться к х*. В начальной точке проводим касательную к линии уровня и делаем по перпендикуляру к касательной в этой точке, шаг соответствующей величины. Если оказываемся «далеко», то делим шаг пополам, проводим линию уровня, касательную и шагаем по перпендикуляру и т.д.

    

Алгоритм:

1.Выбираем t=const.

2.Проверяем выполнение соотношения (*).

3.Если выполняется, то вычисляем следующую точку; если не выполняется, тогда длину шага t делим на 2, проверяем (*) и так далее.

Там, где f ( x )  = 0- останавливаемся.

Теорема(о градиентном метоле с дроблением шага) 

Градиентный метод с дроблением шага обеспечивает геометрическую скорость сходимости в точке минимума || xk –x*|| const.*qk, где 0<q<1.

Без доказательства.

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

Определяет оптимальное значение шага на каждом такте.

     

Значение функции, полученное этим методом, меньше чем в предыдущем  методе.

Характерная черта метода: градиенты функции в соседних точках ортогональны.

Графическая интерпретация:

В начальной точке проводим касательную к линии уровня и делаем шаг оптимальной величины в направлении перпендикуляра к касательной в данной точке. Получив новую точку, повторяем действия и так далее.

Теорема (о скорости сходимости метода наискорейшего спуска) 

Скорость сходимости метода наискорейшего спуска - геометрическая.

, где (L,l -указаны ранее)

Без доказательства

4.Масштабирование.

Пусть f(x)  имеет вид:, где ai>0  сильно различаются между собой. Поверхности уровней функции вытянуты вдоль тех осей xi, которым соответствуют малые ai.

Для более эффективного применения градиентных методов необходимо превращение поверхностей уровня в круги                                               

                                             x0 

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

В случае, когда f(x) не квадратичная, а достаточно гладкая функция общего вида выбирают:

 

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

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

Разложим f(x) в ряд Тейлора до 2-го слагаемого включительно:

(*)

- вектор

 - матрица Гессе, матрица вторых производных.

Будем рассматривать квадратичную аппроксимацию f(x) тогда получим (*) без  то есть предполагаем, что f(x) квадратичная форма. Эта форма  имеет единственную точку min, который является корнем уравнения  f ’(x)=0.

В данном случае:

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

Пример: 

Сделаем одну итерацию метода Ньютона для квадратичной функции

Этот пример показывает связь решения системы уравнений Ax-b = 0 и поиска минимума соответствующей функции f(x).

= A - матрица вторых производных.

Одна итерация метода Ньютона:

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

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

Оценим скорость сходимости метода Ньютона:

Теорема (о скорости сходимости метода Ньютона): 

Пусть f(x) дважды дифференцируема, матрица  удовлетворяет условию

Липшица с константой L :

f(x) сильно выпукла: 0 l I 2 f(x) и начальное приближение удовлетворяет условию:

Тогда метод Ньютона сходится х* с квадратичной скоростью

Доказательство:

 Известно, что:

1)

Если на g’(x) удовлетворяет условию Липшица , то

Применим это отношение к 2 f(x), тогда

Пусть x = xk , тогда

Дано (см. условие) тогда:

Таким образом  .

Пусть q1=  (обозначим). Рассмотрим полученное неравенство

.........................................................................

Для сильно выпуклых функций известно

Тогда

Теорема доказана.

Если начальные условия не удовлетворяют требованиям теоремы, то метод может не сходиться.

Пусть метод обеспечивает выполнение следующего неравенства  

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

Если обозначить k = , тогда скорость сходимости

d = , при k0 (k ).

Пусть k+1q k, 0 q 1. Для этого случая d =1- линейная скорость. Для метода Ньютона тогда k+1= const k2  d =2- поэтому скорость называется квадратичной.

Сравнительная таблица достоинств и недостатков градиентного метода и метода Ньютона:

Метод

Достоинства

Недостатки

градиентный метод

1. Глобальная сходимость, т.е. слабые требования на исходные данные, точка х0 может быть далека от х*.

2. Слабые требования к f(x), только f’(x) нужна

3. Относительная простота вычислений

1. Медленная скорость сходимости (геометрическая сходимость, скорость сходимости d = 1).

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

1. Быстрая сходимость (квадратичная)

  1.  Локальная сходимость, т.е. начальное приближение должно быть достаточно близко к х*)
  2.  Жесткие требования на саму функцию (должна быть дважды непрерывнодифференц.
  3.  Большой объем вычислений, связанный с необходимостью вычисления матрицы вторых производных и ее обращения.  

Полезен метод ньютона в случае квадратичной функции (сходится за один шаг).

Число обусловленности локального min.

 

Пусть  - поверхности уровней f(x).

Рассмотрим следующую величину

Очевидно, что у окружности r=1, а у эллипса r>1 (увеличивается с увеличением растянутости).

Определение: 

Числом обусловленности точки локального min называется

Оно число дает основание для выбора метода.

Определение:

Говорят, что точка локального min плохо обусловлена, если число обусловленности велико, и хорошо обусловлена если оно близко к 1.

Пример.

Пусть f(x) = 1/2 (Ax, x). А - диагональная матрица. Тогда число обусловленности есть отношение max диагонального элемента к min диагональному элементу.

Порядок применения методов.

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

На втором этапе ( мало)- методы второго порядка (Ньютона).

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

Существует метод Марквердта- Левенберга

Если   - градиентные методы

          0- метод Ньютона

1.3. Многошаговые ( двухшаговые ) методы.

Метод тяжелого шарика:

Общий вид метода тяжелого шарика:

xk+1= xk - f(xk)+(xk-xk-1)

Это разностное уравнение, полученое из ДУ, которое описывает движение шарика, катящегося по некоторой поверхности с постоянным трением.

Введение инерции (xk-xk-1) увеличивает скорость сходимости.

            

Теорема(о скорости сходимости метода тяжелого шарика):

Пусть 0 l I  2f(x) L I (сильная выпуклость)  

0    1, 0    (1-)/L,

тогда существует с=const такая, что || xk - x* || cqk ,  

Без доказательства

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

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

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

xk+1 =  xk - k f(xk) + k (xk-xk-1)

Отличается тем, что k и k зависят от шага и выбираются следующим образом:

(k , k) = argmin f(xk - kf(xk)+k(xk-xk-1))

      {,}

Для квадратичной функции

  1.  Метод сходится за конечное число шагов, не превосходящее размерности пространства  состояний.
  2.  Градиенты в методе попарно ортогональны (f(xi), f(xk))=0, ik

Но в Rn не может существовать более n ортогональных ненулевых векторов ,                       поэтому для некоторого k n будет  f(xk)=0, то есть точка xk- точка минимума.

  1.  Последовательные направления движения pk=xk-xk-1 удовлетворяют соотношению (Api, pj ) =0 ij

Определение:

Векторы pi , связанные  соотношением (Api, pj ) =0, называются сопряженными или А- ортогональными.

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

Модификация Полака-Ривьера

xk+1= xk+ kpk , где k = argmin f(xk+ kpk ), >0

pk= -f(xk)+kpk-1

   0 = 0     

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

Эту модификацию удобнее применять для произвольных (неквадратичных) функций.

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

То есть 0 = 0, затем n=0...... mn=0, следовательно pk= -f(xk)+0*pk-1= -f(xk)

(сдвиг в направлении антиградиента)

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

1.4.Квазиньютоновские методы

общая структура:                 xk+1 = xk - kkf(xk)

  1.  Если  Hk =I , то это градиентный метод.
  2.  Если  Hk = (2f(xk))-1, то это метод Ньютона.
  3.  Если  Hk = Hk (f(xi), i=1..k) (2f(xk))-1, т.е. матрица Hk пересчитывается рекурентным способом на основе информации, полученной на k-й итерации.

Достоинство:

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

Обозначим  pk = Hkf(xk)

         yk= f(xk+1) -f(xk),

,A>0

Тогда для квадратичной функции имеем

yk = A(xk+1-xk) = kApk

k pk = ykA-1,

поэтому матрицу Hk+1 (необязательно для квадратичной функции) выбирают так, чтобы выполнялось так называемое квазиньютоновское условие:

Hk+1yk= kpk  (Hk- должна стремиться к (2f(xk))-1

Метод Давидона- Флетчера- Пауэлла (ДФП)

          

 

Проверим выполнение квазиньютоновского условия:

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

Объединяет достоинства градиентных методов и метода Ньютона.

Процедура применения:

На очередном шаге, имея Hk,  делаем шаг в направлении pk. Получаем k (например, по методу наискорейшего спуска) , получаем xk+1 , вычисляем yk и пересчитываем Hk+1 для следующего шага .

Недостаток:

(по сравнению с методом сопряженных градиентов)

Надо хранить и пересчитывать Hk размерности mn.

Метод Бройдена-Флетчера –Шенно.

где

Примечание: 

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

  1.  Методы нулевого порядка

1. Методы апроксимации

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

Пусть ej - орт j-й оси.

f (x + ej) f(x) + f/xj + O(2)

f/xj = ( f(x + ej) - f(x) )/    ( f(x + ej)  -  f(x - ej) )/ (2)

Здесь под градиентом понимается конечная разность. Если слишком  мала, то слишком велики погрешности при вычислении производных. Если велика, то из-из O(2) погрешности тоже велики. Таким образом проблема этих  методов- выбор .

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

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

Алгоритм:

  1.  j :=1
  2.  min f(x-ej)=f(x’’), x’’:= x’- *ej 
  3.  j:=j+1, x= x’’
  4.  if j n  then  goto 2)
  5.  if not (условие окончания цикла) then goto 1

Достоинство:

Требуется min функции вдоль только одной прямой.

3.Метод симплексов (Нелдера- Нида)

Алгоритм:

1.Фиксируем xo…xn  ( n+1- точка)

Если n =2 , то (выбир. равнобедренный треугольник)

2.

                                        вычисление отраженной точки

xj

                    xj’  

Если f(xj) < f(xj), то xj := xj; k:=0, иначе k:=k+1

k- количество идущих подряд неудачных отражений

3. Если k<n, то (если j<n, то j:=j+1 , иначе j:=0) goto 2.

4.Иначе сжатие : xl = argmin f(xj), 0 j n - ищем вершину, в которой функция минимальна (то есть наименьшее значение из всех существующих вершин

5. Cжатие :  xj = xl + ( xj - xl), j (сжатие в раз)

Существует много модификации метода.

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

4 .Метод Пауэлла (сопряженных направлений)

Идея:

Для двух точек x0,x1 делается шаг в произвольном направлении p0. Получаем точки x2,x3. Следующий шаг делаем в направлении p1. Находится x*.

p1= x3-x2                                                   x2                x3p1

         x*        

           p0             p1

                        x0             x1 

Утверждается, что (Ap1,po)=0.

Поэтому для квадратичной функции сойдется за n-  шагов. Это один из лучших методов прямого поиска.

                                          


 

А также другие работы, которые могут Вас заинтересовать

67630. Какие родители – такие и дети 33 KB
  По мнению психологов, на психологическое развитие детей влияет то, какими методами родители общаются с ними. Понятно, что родители свои модели общения переняли от своих родителей, а те от своих… Но, может кто-то сможет найти в себе силы и прервать ту цепочку, которая приведёт к непониманию между детьми и родителями...
67632. Как помочь своему ребенку улучшить чтение 38 KB
  В норме чтение представляет собой сложный психофизиологический процесс в котором участвуют различные анализаторы: зрительный речедвигательный речеслуховой. Егоров выделяет следующие ступени формирования навыка чтения: 1 овладение звуко-буквенными обозначениями; 2 послоговое чтение...