40842

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

Лекция

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

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

Русский

2013-10-22

302.5 KB

25 чел.

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

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

                                          


 

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

79288. Высвобождение персонала 55.85 KB
  Высвобождение персонала Высвобождение персонала это вид управленческой деятельности предусматривающий комплекс мероприятий по соблюдению правовых норм и организационно-психологической поддержки со стороны администрации при увольнении работников. Виды высвобождения персонала из организации приведены на рис. тот вид высвобождения который практически не прогнозируется администрацией и как правило происходит для нее неожиданно. Однако с точки зрения работника это наиболее мягкий вид высвобождения: работник готов покинуть организацию и...
79289. Управление социальным развитием организации 11.87 KB
  Управление социальным развитием организации Говоря об управлении социальным развитием организации можно использовать термин – Социальная политика организации которая характеризуется как часть политики управления персоналом и включающая в себя все цели и мероприятия связанные с добровольными социальными услугами организации. Социальная политика организации означает уважение признание заслуг и поощрение людей. Соответственно этому система дополнительных социальных льгот должна быть не только привлекательной для сотрудника но и...
79290. Организация обучения персонала 19.09 KB
  Организация обучения персонала. Следует различать три вида обучения. Отечественный и зарубежный опыт выработал три концепции обучения квалифицированных кадров: Концепция специализированного обучения ориентирована на сегодняшний день или ближайшее будущее и имеет отношение к соответствующему рабочему месту. Концепция многопрофильного обучения является эффективной с экономической точки зрения так как повышает внутрипроизводственную и внепроизводственную мобильность работника.
79291. Аттестация персонала 13.3 KB
  Аттестация персонала организаций основного звена управления процедура определения квалификации уровня знаний практических навыков деловых и личностных качеств работников качества труда и его результатов и установления их соответствия несоответствия занимаемой должности. Аттестация персонала служит юридической основой для переводов продвижения по службе награждения определения размера заработной платы а также понижения в должности и увольнения. Аттестация направлена на улучшение качественного состава персонала определение степени...
79292. Управление деловой карьерой, служебно-профессиональным продвижением 353.73 KB
  Деловая карьера поступательное продвижение личности в какойлибо сфере деятельности изменение навыков способностей квалификационных возможностей и размеров вознаграждения связанных с деятельностью; продвижение вперед по однажды выбранному пути деятельности достижение известности славы обогащения. Планирование и контроль деловой карьеры заключаются в том что с момента принятия работника в организацию и до предполагаемого увольнения с работы необходимо организовать планомерное горизонтальное и вертикальное продвижение работника по...
79293. Работа с кадровым резервом 17.89 KB
  Работа с кадровым резервом Принципы формирования и источники кадрового резерва Формирование кадрового резерва основывается на следующих принципах: актуальность резерва потребность в замещении должностей должна быть реальной; соответствие кандидата должности и типу резерва требования к квалификации кандидата при работе в определенной должности; перспективность кандидата ориентация на профессиональный рост требования к образованию возрастной ценз стаж работы в должности и динамичность карьеры в целом состояние здоровья. Источниками...
79294. Теории мотивации трудовой деятельности 43.01 KB
  Различают первичные и вторичные потребности. Потребности можно удовлетворить вознаграждениями. Маслоу существует пять основных типов потребностей: физиологические потребности уровень 1; потребность в безопасности уровень 2; социальные потребности уровень 3; потребность в уважении и самоутверждении уровень 4; потребность в самовыражении уровень 5. Маслоу Эти потребности образуют иерархическую структуру которая определяет поведение человека причем потребности высшего уровня не мотивируют человека пока хотя бы частично не...
79295. Мотивация и стимулирование трудовой деятельности персонала 45.96 KB
  Мотивация и стимулирование трудовой деятельности персонала Система стимулирования труда персонала: общие положения и составные части. Система материального стиулирования труда и ее элементы. Основным компонентом материального стимулирования труда является система его оплаты которая осуществляется в двух формах – повременной и сдельной рис. Формы оплаты труда Система оплаты труда комплекс взаимосвязанных принципов и методов определления уровня оплаты труда персонала на основе учета количественных и или качественных характеристик...
79296. Оценка результатов труда персонала организации 16.86 KB
  Оценка результатов труда персонала организации Оценка результатов труда одна из функций по управлению персоналом направленная на определение уровня эффективности выполнения работы. Оценка результатов труда является составной частью деловой оценки персонала наряду с оценкой его профессионального поведения и личностных качеств и состоит в определении соответствия результатов труда работника поставленным целям запланированным показателям нормативным требованиям. Оценка труда мероприятия по определению соответствия количества и качества...