Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Численные методы безусловной оптимизации первого порядка




Читайте также:
  1. B-дерево порядка 2.
  2. Cоциологический анализ электорального процесса: проблемы и методы исследования, сферы применения результатов
  3. I. Невербальные методы оценки.
  4. II. Аксиомы порядка
  5. II. Влияние начальной концентрации Н2О2 на период полупревращения. Определение порядка реакции.
  6. III.3.3. Основные методы количественного анализа
  7. V. ПОНЯТИЕ ЛЕГИТИМНОГО ПОРЯДКА
  8. V6:» тема: Методы таксации насаждений
  9. VI. ТИПЫ ЛЕГИТИМНОГО ПОРЯДКА: УСЛОВНОСТЬ И ПРАВО
  10. VII В зависимости от порядка исчисления налога на прибыль

Основные положения. Градиентом дифференцируемой функции f(x) в точке х[0] называется n-мерный вектор f(x[0]), компоненты которого являются частными производными функции f(х), вычисленными в точке х[0], т. е.

f'(x[0]) = (дf(х[0])/дх1, …, дf(х[0])/дхn)T.

Этот вектор перпендикулярен к плоскости, проведенной через точку х[0] , и касательной к поверхности уровня функции f(x), проходящей через точку х[0] .В каждой точке такой поверхности функция f(x) принимает одинаковое значение. Приравнивая функцию различным постоянным величинам С0, С1, ... , получим серию поверхностей равного уровня, характеризующих ее топологию. Если переменных две, то получаем серию линий равного уровня в плоскости координат (рис. 1.4). Вектор-градиент направлен в сторону наискорейшего возрастания функции в данной точке (рис. 1.14). Вектор, противоположный градиенту (-f’(х[0])), называется антиградиентом и направлен в сторону наискорейшего убывания функции. В точке минимума градиент функции равен нулю. На свойствах градиента основаны методы первого порядка, называемые также градиентным и методами минимизации. Использование этих методов в общем случае позволяет определить точку локального минимума функции.

Рис. 1.14. Вектор градиента и вектор антиградиента функции цели

Очевидно, что если нет дополнительной информации, то из начальной точки х[0] разумно перейти в точку х [1], лежащую в направлении антиградиента - наискорейшего убывания функции. Выбирая в качестве направления спуска р[k] антиградиент -f’(х[k]) в точке х[k], получаем итерационный процесс вида

х[k+1] = x[k]-akf'(x[k]), аk > 0; k=0, 1, 2, ...

В координатной форме этот процесс записывается следующим образом:

xi[k+1]=хi[k] - ak f(x[k])/ xi, где i = 1, ..., n; k= 0, 1, 2,...

В качестве критерия останова итерационного процесса используют либо выполнение условия малости приращения аргумента || x[k+l] - x[k] || <= ε, либо выполнение условия малости градиента || f’(x[k+l]) || <= ξ., где ε и ξ - заданные малые величины.

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

При методе с постоянным шагом для всех итераций выбирается некоторая постоянная величина шага. Схема сходимости приведена на рис. 1.15. Достаточно малый шаг аk обеспечит убывание функции, т. е. выполнение неравенства



f(х[k+1]) = f(x[k] – akf’(x[k])) < f(x[k]).

Рис. 1.15. Геометрическая интерпретация градиентного метода спуска с постоянным шагом

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

Более экономичны в смысле количества итераций и надежности градиентные методы с переменным шагом, когда в зависимости от результатов вычислений величина шага некоторым образом меняется (рис. 1.16).

Рис. 1.16. Геометрическая интерпретация градиентного метода спуска с переменным шагом


Дата добавления: 2015-07-26; просмотров: 12; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.009 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты