Главная

Категории:

ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника






Задача: найти безусловный минимум функции f(x), заданной на всем пространстве En.


(Многие алгоритмы решения задач с ограничениями включают данную задачу как некоторый этап.)

2 подхода к решению задач:

1. задача нахождения экстремума заменяется задачей поиска решений уравнений вида f '(x)=0.

2. нахождение такой последовательности точек х1, х2, х3..., что f(х1)<f(х2)<... - прямой метод решения задач оптимизации.

Различие между этими методами - несущественное, т.к. метод 1 также приводит к построению последовательности {xk}.

Последовательности векторов {xk}, при которых f(х0)>f(х1)>...>f(хn) называется релаксационными, а методы их построения называются методами спуска.

Методы спуска различаются выбором направления спуска и длины шага вдоль этого направления. Точки {xk} вычисляются по формуле

хk+1 = xk + akpk,

где pk - направление спуска

ak - длина шага.

Скорость сходимости методов спуска - важнейшая их характеристика.

Линейная сходимость (сходимость со скоростью геометрической прогрессии)

|| хk+1- x*||<=q||xk - x*||,

где x* - точка минимума f(x)

q - константа 0<q<1

Сверхлинейная скорость сходимости

||хk+1- x*||<=qk||xk - x*|| если qk →0 при k→∞.

Квадратичная сходимость

||хk+1- x*||<=с||xk - x*||2, с>=0.

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

а) Методы нулевого порядка (методы поиска) - используют только значения самой целевой функции;

б) методы первого порядка - требуют кроме того вычисления первых производных минимизируемой функции.

Наименьшего числа итераций требуют методы второго порядка (общее число машинных операций при этом не всегда минимально!)

II Градиентные методы - методы 1-ого порядка

Градиент скалярной функции f(x) в некоторой точке xk направлен в сторону наискорейшего возрастания функции и ортогонален линии уровня (поверхности постоянного значения f(x), проходящей через заданную точку).

Антиградиент - вектор, противоположный градиенту f '(xk) направлен в сторону наискорейшего убывания функции. Выбрав в качестве направления спуска pk в

хk+1 = xk + akpk т.е. pk= -f '(xk)

антиградиент в точке xk, получим итерационный процесс

хk+1 = xk - akf '(xk) ak >0, k=1, 2, ... (1)

В координатной форме (1) запишется как

= ak (xk ) i=1,2,...n (2)

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

Отличаются градиентные методы выбором шага ak.

Часто в (1) вместо градиента f '(xk)=▼f(xk) используют нормированный (единичный) градиент ▼f(xk) / ||▼f(xk)||.

Наиболее распространенные 2 способа выбора шага:

Метод с дроблением шага

2. Метод наискорейшего спуска. (минимизируется на каждом функция f(xk-af '(xk)) от a).

II.1. Градиентные методы с дроблением шага. Методы с постоянным шагом

В выражении (1) хk+1= xk - akf '(xk) выбрав достаточно малый шаг ak получим

(3) f(xk-af '(xk))< f(xk), т.е. f(хk+1)< f(xk).

Проблема: при малом ak - слишком много шагов

при большом ak - может нарушиться неравенство (3)

Пример: необходимо минимизировать функцию f(x)=ax2; a>0

Формула (1) принимает вид [ = xk - akf '(x)]

хk+1=(1 - 2aka)xk

Если ak=const, то процесс сходится, при 0<ak< и расходится при ak> . (В данном случае х*=0, и процесс будет сходиться, если | хk+1|<| xk|, т.е. |1 - 2aka |<1

, т.к. а>0, то >0, , )

Если ak = , то x1 = - x0; x2 = x0; x3 = - x0; и т.д., т.е. происходит зацикливание.

Если ak> , процесс расходится: пусть a = > . Тогда хk+1=(1-4)xk= -3xk. Пусть x0=1, тогда x1=-3; x2=9; x3=-27 и т.д.

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

(4) f(xk-af '(xk)) - f(xk)<= -eak|| f '(xk)||,

т.е. f(хk+1) - f(xk)<= -eak|| f '(xk)||,

где 0<e<1

Требование (4) на выбор шага более жесткое, чем требование (3). В (3) необходимо только, чтобы f(хk+1)<f(xk).

Алгоритм, реализующий метод с дроблением шага:

1. Выбирается a>0.

На k-ом шаге (на каждом шаге) проверяем выполнение условия (4). Если условие выполняется, переходим к следующей итерации. В противном случае дробим a до тех пор, пока условие (4) не выполнится.



Последнее изменение этой страницы: 2016-06-10

headinsider.info. Все права принадлежат авторам данных материалов.