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

                                          


 

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

46553. Смазочные материалы. Назначение. Классификация. Основные параметры и свойства смазочных материалов 22.23 KB
  Полутвёрдыми полужидкими расплавленные металлы солидолы консталины и др жидкими автомобильные и другие машинные масла газообразными углекислый газ азот инертные газы. Растительные масла получают путем переработки семян определенных растений. – животные масла вырабатывают из животных жиров баранье и говяжье сало технический рыбий жир костное и спермацетовые масла и др. – органические масла по сравнению с нефтяными обладают более высокими смазывающими свойствами и более низкой термической устойчивостью.
46554. THE ADVERB 19.95 KB
  The adverb is a word denoting circumstances or characteristics which attend or modify an action, state, or quality. It may also intensify a quality or characteristics From this definition it is difficult to define dverbs s clss becuse they comprise most heterogeneous group of words nd there is considerble overlp between the clss nd other word clsses. longside such undoubtful dverbs s here now often seldom lwys there re mny others which lso function s words of other clsses. Thus dverbs like ded ded tired cler to get cler wy clen I've clen forgotten slow esy he would sy tht slow nd esy coincide with corresponding djectives ded body cler wters clen hnds. dverbs like pst bove re...
46555. Система Управления БД 19.99 KB
  БД это именованная совокупность данных отражающая состояние объектов и их отношений в заданной предметной области. Банк данных является современной формой организации хранения и доступа к информации. Банк данных – это система специальным образом организованных данных баз данных программных технических языковых организационнометодических средств предназначенных для обеспечения централизованного накопления и коллективного многоцелевого использования данных. Банк данных является сложной системой включающей в себя все обеспечивающие...
46556. Затратный подход к оценке предприятия 20.02 KB
  Суть данного подхода заключается в том что сначала оцениваются и суммируются все активы предприятия нематериальные активы здания машины оборудование запасы дебиторская задолженность финансовые вложения и т. Далее из полученной суммы вычитают текущую стоимость обязательств предприятия. Итоговая величина показывает стоимость собственного капитала предприятия.
46557. Природопользование 20.05 KB
  Предусмотренная лесным законодательством система мер направленных на организацию рационального использования и воспроизводство лесов их охрану от загрязнения истощения и уничтожения защиту от пожаров вредителей и болезней образует понятие правовой охраны лесов. Охрана и защита лесов осуществляется лесхозами государственной лесной охраной базами авиационной охраны лесов и другими организациями лесного хозяйства. Экологические требования и меры входящие в содержание правовой охраны лесов адресованы всем субъектам: организациям ведущим...
46558. Реструктуризация и реорганизация предприятия 20.06 KB
  Виды реструктуризации Реструктуризация зависящая от целевых установок и стратегии предприятия может быть оперативной или стратегической. Частичная реструктуризация вносит изменения лишь в один или несколько элементов предприятия. Направления реструктуризации предприятия Выбор конкретных видов реструктурирования зависит от конкретных внутренних возможностей и интересов самого предприятия а также от внешних условий характеризующих данную ситуацию.
46559. Стратегии социально – экономического развития экономики: процессы модернизации и инновационного развития 20.08 KB
  Базой успешной экономической стратегии государств и ключевым ресурсом общества становятся знания и интеллект информация и инновации человеческий и интеллектуальный потенциал формируемые главным образом через систему подготовки кадров. Инновации могут быть признаны таковыми если они прямо или косвенно становится фактором экономического роста. Прямо – когда инновации становятся торгуемыми товарами и услугами. Косвенно – когда инновации воплощены в конструкции товаров технологии их изготовления квалификации работников факторы роста – труд...
46560. Прогнозирование пожарной обстановки и ее оценка 20.13 KB
  Такая обстановка может возникнуть при ЯВ изза воздействия СИ техногенных пожарах на объектах экономики и природных пожарах в лесах и на торфяниках. В процессе прогнозирования определяют площадь и периметр возможного пожара характер пожара отдельный или сплошной пожар огненный шторм или массовый пожар вероятные направления и скорость его распространения а также вероятный характер воздействия пожара на людей и объекты в различные временные отрезки с учетом изменения метеоусловий. При этом берут самый неблагоприятный вариант: ось пожара...