9895

Градиентные методы

Реферат

Математика и математический анализ

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

Русский

2013-03-18

87.5 KB

161 чел.

Градиентные методы

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

На k-м этапе градиентных методов переход из точки Xk в точку Xk+1 описывается соотношением:

  Xk+1 = Xk + kSk,     (1.2)

где k - величина шага, k - вектор в направлении Xk+1-Xk.

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

Впервые такой метод рассмотрел и применил еще О. Коши в XVIII в. Идея его проста: градиент целевой функции f(X) в любой точке есть вектор в направлении наибольшего возрастания значения функции. Следовательно, антиградиент будет направлен в сторону наибольшего убывания функции и является направлением наискорейшего спуска. Антиградиент (и градиент) ортогонален поверхности уровня f(X) в точке X. Если в (1.2) ввести направление

 ,

то это будет направление наискорейшего спуска в точке Xk.

Получаем формулу перехода из Xk в Xk+1:

.

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

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

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

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

Но самое главное - очень медленная сходимость наискорейшего спуска в общем случае. Дело в том, что спуск является "наискорейшим" в локальном смысле. Если гиперпространство поиска сильно вытянуто ("овраг"), то антиградиент направлен почти ортогонально дну "оврага", т.е. наилучшему направлению достижения минимума. В этом смысле прямой перевод английского термина "steepest descent", т.е. спуск по наиболее крутому склону более соответствует положению дел, чем термин "наискорейший", принятый в русскоязычной специальной литературе. Одним из выходов в этой ситуации является использование информации даваемой вторыми частными производными. Другой выход - изменение масштабов переменных.

Метод сопряженного градиента Флетчера-Ривса

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

  ,

причем коэффициенты выбираются так, чтобы сделать направления поиска сопряженными. Доказано, что

   

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

Алгоритм Флетчера-Ривса.

1. В X0 вычисляется .

2. На k-ом шаге с помощь одномерного поиска в направлении находится минимум f(X), который и определяет точку Xk+1.

3. Вычисляются f(Xk+1) и .

4. Направление определяется из соотношения:

 

5. После (n+1)-й итерации (т.е. при k=n) производится рестарт: полагается X0=Xn+1 и осуществляется переход к шагу 1.

6. Алгоритм останавливается, когда , где - произвольная константа.

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

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

Ньютоновские методы

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

,

где - матрица Гессе.

Минимум правой части (если он существует) достигается там же, где и минимум квадратичной формы. Запишем формулу для определения направления поиска :

 .

Минимум достигается при .

Алгоритм оптимизации, в котором направление поиска определяется из этого соотношения, называется методом Ньютона, а направление - ньютоновским направлением.

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

Классификация Ньютоновских методов

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

Теорема 1.4. Если матрица Гессе нелинейной функции f общего вида в точке минимума X* положительно определена, начальная точка выбрана достаточно близко к X* и длины шагов подобраны верно, то метод Ньютона сходится к X* с квадратичной скоростью.

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

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

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

Залогом эффективности методов ньютоновского типа является учет информации о кривизне минимизируемой функции, содержащейся в матрице Гессе и позволяющей строить локально точные квадратичные модели целевой функции. Но ведь возможно информацию о кривизне функции собирать и накапливать на основе наблюдения за изменением градиента во время итераций спуска. Соответствующие методы, опирающиеся на возможность аппроксимации кривизны нелинейной функции без явного формирования ее матрицы Гессе, называют квази-Ньютоновскими методами.

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

Метод Ньютона-Рафсона

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

Основная итерационная формула многомерной оптимизации Xk+1 = Xk + k+1 используется в этом методе при выборе направления оптимизации из соотношения , k+1 = 1.

Реальная длина шага скрыта в ненормализованном Ньютоновском направлении . Так как этот метод не требует значения целевой функции в текущей точке, то его иногда называют непрямым или аналитическим методом оптимизации. Его способность определять минимум квадратичной функции за одно вычисление выглядит на первый взгляд исключительно привлекательно. Однако это "одно вычисление" требует значительных затрат. Прежде всего, необходимо вычислить n частных производных первого порядка и n(n+1)/2 - второго. Кроме того, матрица Гессе должна быть инвертирована. Это требует уже порядка n3 вычислительных операций. С теми же самыми затратами методы сопряженных направлений или методы сопряженного градиента могут сделать порядка n шагов, т.е. достичь практически того же результата. Таким образом, итерация метода Ньютона-Рафсона не дает преимуществ в случае квадратичной функции.

Если же функция не квадратична, то

- начальное направление уже, вообще говоря, не указывает действительную точку минимума, а значит, итерации должны повторяться неоднократно;

- шаг единичной длины может привести в точку с худшим значением целевой функции, а поиск может выдать неправильное направление, если, например, гессиан не является положительно определенным;

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

Сама по себе стратегия не различает, к какой именно стационарной точке (минимума, максимума, седловой) приближается поиск, а вычисления значений целевой функции, по которым можно было бы отследить, не возрастает ли функция, не делаются. Значит, все зависит от того, в зоне притяжения какой стационарной точки оказывается стартовая точка поиска. Стратегия Ньютона-Рафсона редко используется сама по себе без модификации того или иного рода.

Методы Пирсона

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

Алгоритм Пирсона № 2.

В этом алгоритме обратный гессиан аппроксимируется матрицей Hk, вычисляемой на каждом шаге по формуле

Hk+1 = Hk + .

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

Данный алгоритм Пирсона часто приводит к ситуациям, когда матрица Hk становится плохо обусловленной, а именно - она начинает осцилировать, колеблясь между положительно определенной и не положительно определенной, при этом определитель матрицы близок к нулю. Для избежания этой ситуации необходимо через каждые n шагов перезадавать матрицу, приравнивая ее к H0.

Алгоритм Пирсона № 3.

В этом алгоритме матрица Hk+1 определяется из формулы

Hk+1 = Hk + [Xk+1-Xk-Hk (f(Xk+1)- f(Xk))]

 

Траектория спуска, порождаемая алгоритмом, аналогична поведению алгоритма Дэвидона-Флетчера-Пауэлла, но шаги немного короче. Пирсон также предложил разновидность этого алгоритма с циклическим перезаданием матрицы.

Проективный алгоритм Ньютона-Рафсона

Пирсон предложил идею алгоритма, в котором матрица рассчитывается из соотношения

Hk+1 = Hk + ,

H0=R0, где матрица R0 такая же как и начальные матрицы в предыдущих алгоритмах.

Когда k кратно числу независимых переменных n, матрица Hk заменяется на матрицу Rk+1, вычисляемую как сумма

Rk +.

Величина Hk(f(Xk+1) - f(Xk)) является проекцией вектора приращения градиента (f(Xk+1)-f(Xk)), ортогональной ко всем векторам приращения градиента на предыдущих шагах. После каждых n шагов Rk  является аппроксимацией обратного гессиана H-1(Xk), так что в сущности осуществляется (приближенно) поиск Ньютона.  

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

Этот метод имеет и другие названия - метод переменной метрики, квазиньютоновский метод, т.к. он использует оба эти подхода.

Метод Дэвидона-Флетчера-Пауэла (ДФП) основан на использовании ньютоновских направлений, но не требует вычисления обратного гессиана на каждом шаге. Направление поиска на шаге k является направлением , где Hi - положительно определенная симметричная матрица, которая обновляется на каждом шаге и в пределе становится равной обратному гессиану. В качестве начальной матрицы H обычно выбирают единичную. Итерационная процедура ДФП может быть представлена следующим образом:

1. На шаге k имеются точка Xk и положительно определенная матрица Hk.

2. В качестве нового направления поиска выбирается

  

3. Одномерным поиском (обычно кубической интерполяцией) вдоль направления определяется k, минимизирующее функцию .

4. Полагается .

5. Полагается .

6. Определяется и . Если Vk или  достаточно малы, процедура завершается.

7. Полагается Uk = f(Xk+1) - f(Xk).

8. Матрица Hk обновляется по формуле

 

9. Увеличить k на единицу и вернуться на шаг 2.

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

Матрица Ak обеспечивает сходимость Hk к G-1, матрица Bk обеспечивает положительную определенность Hk+1 на всех этапах и в пределе исключает H0.

 

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

Таким образом, метод ДФП использует как идеи ньютоновского подхода, так и свойства сопряженных направлений, и при минимизации квадратичной функции сходится не более чем за n итераций. Если оптимизируемая функция имеет вид, близкий к квадратичной функции, то метод ДФП эффективен за счет хорошей аппроксимации G-1(метод Ньютона). Если же целевая функция имеет общий вид, то метод ДФП эффективен за счет использования сопряженных направлений.

На практике оказалось, что метод ДФП может давать отрицательные шаги или окончиться в нестационарной точке. Это возможно, когда Hk+1 становится плохо обусловленной. Этого можно избежать путем увеличения числа получаемых значимых цифр или перезаданием матрицы Hk+1 в виде специальной диагональной матрицы H, где

   .

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

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

Практическая проверка эффективности алгоритма показала, что он столь же эффективен, как и метод Флетчера-Ривса.


 

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

58462. Наші зелені друзі 274.5 KB
  Мета: удосконалювати читацькі навички, вчити виділяти головне з прочитаного, робити власні висновки та аргументувати їх; розвивати прагнення до розуміння краси природи; учити дітей бути спостережливими, уважними, виробляти звичку планувати власні дії, самостійно контролювати результати своєї праці...
58463. Степень с целым показателем и ее свойства 6.32 MB
  Оборудование: презентация Степень; раздаточный материал для Математического лото; портреты ученых математиков. И соберём по капельке всё что учили по теме: Степень в младших класах. Степенью числа а с натуральным показателем п большим за 1 называется произведение п множителей каждый из которых равен а. аn = аа а n раз Как называется число которое...
58464. Визначні місця Лондона 63.5 KB
  Today I invite you to London. We are going to visit famous sights there. I think we’ll travel there by plane, because it is the fastest way. Get your tickets and fill in some information about yourself for registration.
58465. Appearance. Вивчення граматичної структури This is та These are 54.5 KB
  Ви вже знаєте потрібні слова для опису зовнішність людини. Та він є неповним без опису її одягу. Одяг – це частина самовираження людини, її прикраса. Тож вам необхідно знати як називати предмети гардеробу англійською.
58466. The Environmental Protection 106 KB
  This is the season when fruit is sweet. This is the season when school friend meet. This is the season when mornings are dark. And birds do not sing in wood and the park. The summer is over, the trees are all bare, This is the mist in the garden and frost in the air.
58467. At the Post-Office 121.5 KB
  Today at the lesson you will learn from the text about the main functions of the post-office. This knowledge you can use in your everyday life. And also you will write a test work in listening comprehension.
58468. Тварини. Прикметники 3.05 MB
  It teaches subject/verb agreement for the most important verb in English, making plurals by adding -s, dropping the article a in the plural, and that adjectives are not inflected.
58469. Шкільне приладдя 2.29 MB
  There are two cats on the picture. There are two flowers on the picture. There are two dogs on the picture. There are two girls on the picture. There are two boys on the picture. There are two books on the picture.
58470. Sport. Повторить грамматический материал Do/Does 69.5 KB
  Sport is fun for girls and boys, It’s much better than toys. You can sledge and ski and skate And throw snowballs with Kate. You can swim and play football, Hockey, tennis, and basketball. You can jump and you can run, You can have a lot of fun.