Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

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






Градиентный метод с постоянным шагом






Основная проблема в градиентных методах – это выбор шага ak. Достаточно малый шаг ak обеспечивает убывание функции, то есть выполнение неравенства: f(xk - akf `(xk))) < f(xk),

 
 

но может привести к неприемлемо большому количеству итераций, необходимых для достижения точки минимума. С другой стороны, слишком большой шаг может вызвать неожиданный рост функции (невыполнение условия убывания) либо привести к колебаниям около точки минимума. Однако проверка усл–я убывания на каждой итерации является довольно трудоемкой, поэтому в методе град–го спуска с постоянным шагом задают a=ak пост–м и дост–но малым, чтобы можно было использовать этот шаг на любой итерации. При этом приходится мириться с возможно большим кол–вом итераций. Утешением является лишь то, что трудоемкость каждой итерации, в этом случае, минимальна (нужно вычислять только градиент f`(xk).

Схема алгоритма

Шаг 1. Задаются начальное приближение х0, постоянный шаг a, условия останова алгоритма e3. Вычисляется значение градиента f`(xk) – направление поиска. Присваивается к=0.

Шаг 2. Определяется точка очередного эксперимента:

хк+1 = хк - af’(xk),

или, в координатной форме:

 
 

Шаг 3. Вычисляется значение градиента в точке хк+1:

,

или, в координатной форме:

Шаг 4. Если || f ` (xk+1) ||£ e3, то поиск заканчивается, при этом:

Иначе к=к+1 и переходим к шагу 2.

Градиентный метод с дроблением шага

В методе градиентного спуска с дроблением шага величина шага aк выбирается так, чтобы было выполнено неравенство:

f(xk-ak )-f(xk)£ -dak|| f ` (xk) ||2, где 0< d< 1 – произвольно выбранная постоянная (одна и та же для всех итераций). Это требование на выбор шага aк более жесткое, чем условие убывания, но имеет тот же смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства.

 
 

Процесс выбора шага протекает следующим образом. Выбираем число a> 0, одно и то же для всех итераций. На к-й итерации проверяем вып–е нер–ва при aк=a. Если оно выполнено, полагаем aк=a и переходим к след–ей итерации. Если нет, то шаг aк дробим, напр–р уменьшаем каждый раз в два раза, до тех пор, пока оно не выполнится.

Схема алгоритма

Шаг 1. Задаются х0, e3, d и начальное значение шага a. Вычисляется значение градиента f`(x 0) – направление поиска. Присваивается к=0.

Шаг 2. Проверяется условие: f(xk-a )£ -da|| ||2. Если выполняется, то переходим к шагу 3, иначе дробим значение a (a=a/2) и повторяем шаг 2.

Шаг 3. Определяется точка очередного эксперимента: хк+1 = хк - a f`(xk).

Шаг 4. Вычисляется значение градиента в точке хк+1: f `(хк+1).

Шаг 5. Если || f`(xk+1) ||£ e3, то поиск заканчивается, при этом:

Иначе к=к+1 и переходим к шагу 2.


Поделиться с друзьями:

mylektsii.su - Мои Лекции - 2015-2024 год. (0.006 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал