40842

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

Лекция

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

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

Русский

2013-10-22

302.5 KB

28 чел.

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

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-  шагов. Это один из лучших методов прямого поиска.

                                          


 

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

23099. Явище обертання площини поляризації падаючого світла в речовинах 96 KB
  Явище обертання площини поляризації падаючого світла в речовинах. Якщо лінійно поляризоване світло проходить через плоскопаралельний шар речовини то в деяких випадках площина поляризації світла виявляється повернутою відносно свого вихідного положення. Це явище називається обертанням площини поляризації або оптичною активністю. Кут поворота площини поляризації залежить від довжини хвилі.
23100. Квантування енергії лінійного гармонічного осцилятора 202.5 KB
  Тоді гамільтоніан для такої системи буде: Класичний гармонічний осцилятор має розвязки: і де А амплітуда ω частота δ початкова фаза коливань. Перетворимо це рівняння введемо безрозмірні величини та З урахуванням останнього рівняння Шредігера перепишеться як 1 Асимптотична поведінка розвязку рівняння 1 при х→∞: Тоді 2 причому uzобмежена на нескінченності. Шукаючи розвязок у вигляді степеневого ряду знаходимо рекурентну формулу для коефіцієнтів ряду: Розвязки можуть бути або парними або непарними тобто або...
23101. Хвилі де Бройля. Хвильові властивості частинок 5.03 MB
  Хвилі де Бройля. Тобто інколи відбувається прояв як хвилі інколи як частинки. Тоді можна отримати вираз для хвилі де Бройля. Оберемо напрям вздовж за напрям розповсюдження хвилі де фаза хвилі що пересувається у просторі з фазовою швидкістю що шукається з умови що переміщується так щоб фаза залишалась постійною.
23102. Принципова схема лазера. Властивості лазерного випромінювання. Типи лазерів та їх застосування 51.5 KB
  При падінні хвилі з власною частотою переходу системи: змінюються заселеності рівнів N1 i N2 кількість атомів в одиниці обєму що знаходяться на 1 та на 2 енергетичних рівнях відповідно. dN12=BN1dt ; кількість частинок що перейшли з 1 рівня на 2 dN21= AN2dt BN2dt кількість частинок що перейшли з 2 рівня на 1 де Акоеф. Крім того в стаціонарному режимі при умові термодинамічної рівноваги виконуються рівняння: N1N2=N=const кількість частинок в системі є сталою. В дворівневій системі не можна забезпечити умову N2 N1 бо навіть в...
23103. Рівняння Шредингера. Інтерпретація хвильової функції 49 KB
  Рівняння Шредингера. Для цього необхідне рівняння: 1. Рівняння повинно бути лінійним і однорідним хвиля задовольняє принц. Це рівняння Шредингера.
23104. Співвідношення невизначеності Гейзенберга, приклади його проявів 74.5 KB
  Нехай стан частинки опивується хв. Остаточно Співвідношення невизначеностей проявляється при будьякій спробі вимірювання точного положення або точного імпульса частинки. Виявляється що уточнення положення частинки впливає на те що збільшується неточність в значенні імпульса і навпаки. Часто втрачає зміст ділення повної енегрії частинкияк квантового обєкту на потенціальну і кінетичну .
23105. Сестринский процесс при холециститах 25.25 MB
  Воспаление желчного пузыря регистрируется почти у 10% населения планеты, причем в 3-4 раза чаще холециститом страдают женщины. Большинство людей не следят за своим рационом, ведут сидячий образ жизни.
23106. Теорія молекули водню. Обмінна взаємодія 371 KB
  Оскільки гамільтоніан не залежить від спінових змінних то хвильова функція зображається добутком спінової функції на просторову . За допомогою хвильової функції знаходимо середнє значення повного гамільтоніана системи: де кулонівський інтеграл К характаризує ел. наближені хвильові функції Кулонівський інтеґрал К є малим числом і головну роль відіграє обмінний інтеґрал який у ділянці малих є додатною величиною а при змінює знак. Таким чином для симетричної просторової функції є можливим зв'язаний стан системи і теорія...
23107. Прискорювачі заряджених частинок та принципи їх роботи 62.5 KB
  При непрямих методах прискорення електричне поле індукується змінним магнітним полем або використовується змінне електричне поле у вигляді біжучих або стоячих хвиль. Ідея прискорення заряджених частинок електричним полем яке породжується змінним магнітним полем. Основна складова потужний електромагніт обмотка якого живиться змінним струмом з частотою сотні МГц. При зміні маг потока зявляється вихрове ел поле і на кожний електрон в камері діє сила eE.