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

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

А.Г.Трифонов. Методы линейного поиска.

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

Кубический полиномиальный метод.

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

(3-15)

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

(3-16)

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

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

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

Процедура кубического полиномиального линейного поиска

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

Для каждого случая:

  • Левая точка на графе представляет данную точку .

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

  • Правая точка представляет собой точку , куда попадаешь после шага в направлении d.

    Вариант 1:

    где:

    Reduce step length - уменьшение длины шага;

    otherwise - иначе.

    Вариант 2:

    где:

    Reduce step length - уменьшение длины шага;

    Update H. Reset d - корректировка H. установка d

    Вариант 3:

    где:

    Update H. Reset d - корректировка H. установка d;

    Change to steepest descent method temporarily - Временный переход к методу наискорейшего спуска.

    Варіант 4: где

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

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

    Условное обозначение относится к наименьшим значениям набора .

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

    Кроме того, в данном случае также подключены определенные стабилизирующие меры, такие как, при введении ложной информации о градиенте снижения значений функций f(x), можно получать отрицательные значениях величины шага. Это может быть преодолено при установке в ситуации, когда снижается ниже некого определенного порогового значения (например, 1e-8). В случае применения чрезмерно высоких требований к точности, такой подход дает определенные преимущества, чем при использовании только конечно-разностных градиентов.

    Смешанный кубический/квадратичный полиномиальный метод.

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

    Отсюда следует, что используемый в программах fminunc, lsqnonlin и fsolve метод оптимизации должен использовать три точки для охвата минимума функции, а также кубическую интерполяцию для поиска минимума на каждом этапе линейного поиска. Такая процедура оценки величины шага на каждой внутренней итерации, по j, приведена ниже на графах для ряда сочетаний анализируемых точек. Самая левая точка на графике отображает получаемые после последней корректировки значения функций и одномерного градиента . Оставшиеся точки отображает точки после применения внутренних итераций в методе линейного поиска.

    Члены и относятся к минимальным значениям, полученным из соответствующих методов квадратичной и кубической интерполяции или экстраполяции. Для высоко нелинейных функций значения и могут быть отрицательными и в этом случае они устанавливаются в и, таким образом, поддерживается их положительное значение. В вариантах 1 и 2 используется квадратичная интерполяция для двух точек и одно значение градиента для расчета третьей точки с целью охвата минимума. В случае неудачи такого подхода варианты 3 и 4 представляют возможности для изменения размера шага в ситуации когда доступны, по крайней мере, три точки.

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

    Приводимые ниже графы отображают процедуру линейного поиска для вариантов с 1 по 4 при наличии некоего градиента для первой точки.

    Вариант 1:

    где Reduce step length - Уменьшение длины шага

    Вариант 2:

    где Increase step length - Увеличение длины шага

    Вариант 3:

    Вариант 4:


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

    Система Orphus

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