Категории: ДомЗдоровьеЗоологияИнформатикаИскусствоИскусствоКомпьютерыКулинарияМаркетингМатематикаМедицинаМенеджментОбразованиеПедагогикаПитомцыПрограммированиеПроизводствоПромышленностьПсихологияРазноеРелигияСоциологияСпортСтатистикаТранспортФизикаФилософияФинансыХимияХоббиЭкологияЭкономикаЭлектроника |
Задача: найти безусловный минимум функции 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 lectmania.ru. Все права принадлежат авторам данных материалов. В случае нарушения авторского права напишите нам сюда... |