MATLAB.Exponenta
MATLAB и Simulink на русском
Технологии разработки и отладки
		сложных технических систем

Optimization Toolbox 2.2 Руководство пользователя

А.Г.Трифонов. Квазиньютоновские методы.

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

(3-3)

Где H - симметричная и положительно определенная матрица второго порядка частных и смешанных производных (матрица Гессе, или Гессиан), с - постоянный вектор, b - константа.

Оптимальное решение приведенной задачи соответствует нулевым значениям первых производных, то есть

(3-4)

Точка оптимального решения может быть представлена как

(3-5)

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

Среди подобных алгоритмов одним из наиболее популярных и используемых в пакете Optimization Tooldox является так называемый BFGS алгоритм, получивший свое название по фамилиям предложивших его авторов (Broyden [3], Fletcher [14], Goldfarb [22], and Shanno [39]), в котором аппроксимация H производится итерационно по формуле

,

(3-6)

где

В качестве стартовой точки может быть установлена некая положительно определенная матрица, например, тождественная матрица I. Отметим, что более удобно иметь аппроксимацию не матрицы H, а обратной к ней матрицы , приведенное рекуррентное соотношение подобную замену допускает, при этом сам алгоритм становится практически идентичным хорошо известному методу Давидона [9] - Флетчера -Пауэлла [16], зе тем исключением, что в последнем (3-6) векторы заменены на векторы и наоборот.

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

Для каждой основной итерации линейный поиск осуществляется в направлении:

 

(3-7)  

Применение квазиньютоновского метода можно проиллюстрировать с помощью анализа пути поиска для функции Розенброка (3-2), как это представлено на Рис. 3-2. Иллюстрация метода BFGS для функции Розенброка.

Рис. 3-2. Иллюстрация метода BFGS для функции Розенброка

Линейный поиск

Большинство методов поиска, как в случае наличия ограничений так и без, основаны на решении некой подзадачи, определяющей направление поиска в сторону искомого решения. Процесс минимизации среди направлений такого поиска как правило проводится с помощью процедуры поиска (например Fibonacci, Golden Section) или с помощью метода полиномов, включаюший в себя интерполяцию или экстраполяцию (например квадратичную или кубическую). В методе полиномов проводится аппроксимация некого числа точек для неизменного полинома, чей минимум может быть легко вычислен. Интерполяция используется в случае, когда минимум находится в интервале поиска (т.е. минимум лежит в области, охватываемой имеющимися точками), в то время как интерполяция относится к случаю, когда минимум локализован вне доступных точек. Методы экстраполяции как правило считаются ненадежными в случае оценки минимума нелинейеых функций. Однако эти методы весьма полезны для оцнеки длины шага в случае попыток локализации минимума, как это буде показано в разделе Методы линейного поиска. Методы полиминальной интерполяции обычно высоко эффективны, когда подлежащая интерполяции функция является непрерывной. Проблема заключается в том, что бы найти новую итерацию в форме

(3-8)

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

Квадратичная интерполяция

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

(3-9)

Когда экстремум должен находиться на расстоянии шага

(3-10)

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

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

  ,

(3-11)

где

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

и

Кубическая интерполяция

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

(3-12)

Где локальные экстренумы являются корнями квадратичного уравнения:

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

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

(3-13)

где

Реализация квазиньютоновского метода

Квазиньютоновский метод используется для команды fminunc. Данный метод состоит из двух частей:

  • Определение направления поиска (Корректировка Гессиана);

  • Методы линейного поиска.

    Детали реализации этих двух этапов приводятся ниже

    Корректировка Гессиана

    Направление поиска определяется после выбора метода решения. Это может быть или метод BFGS (3-6) или метод DFP, как это приведенно в разделе Квазиньютоновские методы (при установке опционного параметра HessUpdate как 'dfp' выбирается метод DFP). Гессиан всегда, согласно определению, поддерживается положительным, так что направление поиска, d, всегда направлено по направлению спуска. Это означает, что для некого произвольного малого шага в направлении d, отмечается уменьшение по величине целевой функции. После достижения положительных значений H, согласно определению матнрицы Гессе H, устанавливается и положительное значение величины (согласно 3-14). Член является произведением параметра длины шага линейного поиска и сочетания направления поиска d с прошедшим или текущим расчетным значением градиента.

     

    (3-14)

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

     

  • Поиск по сайту:

    Система Orphus

    Яндекс.Метрика