УМ_Пособие_09

k , еслиf(X k 1 ) f(Xk )

где 0< <1 – произвольно выбранная постоянная (одна и та же для всех итераций).

Это требование на выбор шага к имеет следующий смысл: функция должна убывать от итерации к итерации. Однако при выполнении неравенства функция будет уменьшаться на гарантированную величину, определяемую правой частью неравенства.

Схема алгоритма Шаг 1. Задаются х0, 3, и начальное значение шага .

Вычисляется значение градиента f’(x0) – направление поиска. Присваивается к=0.

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

xi k 1 xi k k f ( X k )

xi

Шаг 3. Проверяется условие f(Xk 1 ) f(Xk ) . Если оно выполняется, то переходим к шагу 4, иначе дробим значение

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

Теоретически точное значение экстремума за конечное число шагов найти невозможно. Однако, учитывая монотонность уменьшения приращений k+1 = f(Xk+l) - f(Xk) на каждом шаге, процесс вычислений можно остановить, как

только k+1 0 заранее заданной.

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

52

выполняется в направлении наискорейшего возрастания функции в соответствующей точке.

Пример. Пусть требуется найти max f(X)=-2x12+2x1x2- x22-9x1+6x2. Эту задачу легко решить с помощью классических методов, приравнивая к нулю частные производные

Метод наискорейшего подъема (спуска)

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

Метод наискорейшего спуска (подъема) объединяет основные идеи метода релаксации и метода градиента. После того, как в начальной точке найден градиент оптимизируемой функции, в направлении градиента осуществляется продвижение до тех пор, пока функция f(X) не перестанет

возрастать. Таким образом, получаем: Xk+1=Xk+ αк f(Xk),

где αк - частый максимум функции одной переменной f[X(α)]=f(α)на направлении f(Xk), когда

xik 1 xik f ( X k ) .

xi

53

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

где xjA, xjB - координаты начальной и конечной точек подъема. Пример. Найти методом наискорейшего спуска

минимум функции f(X)=x12+x22+l.2x1x2.

Пусть X0=(1,2), тогда f(X0)=7.4 и

r10=4.4, r20=5.2.

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

x2

Причем α растет, начиная от 0. Подставим эти выражения в формулу для f(X):

f[х1(α), х2 (α)]= (1 - 4.4 )2 + (2 - 5.2α)2 + 1.2(1 - 4.4α)(2 - 5.2α) = F0 (α)

Таким образом, f(x1,x2) превратилась в функцию от α, так как движение происходит по уже выбранной прямой. Минимум f(X) по этому направлению и есть min F0(α) среди всех положительных α, т.е. F0 (α) = 82.9α2 - 46.4α + 7.4.

Так α находим из условия: F0(α) = 2 . 82.9α - 46.4 = 0 ; αmax = 0.28 , и тем самым определяем наилучшее значение α на исходном шаге. Полагая α0=αmax=0.28, находим координаты следующей точки остановки:

= 0.502 2 0.628 0.487 ;

1 max 0.627 ;

x1(2)=x1(2)(α)=-0.230-0.192.0.625=-0.35; x2(2)=0.038,

f(x(2))=0.074.

Методы оврагов

Градиентные методы медленно сходятся в тех случаях, когда поверхности уровня целевой функции f(x) сильно вытянуты. Этот факт известен в литературе как «эффект оврагов».

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

– эта группа переменных характеризует «склон оврага», а по остальным переменным, задающим направление «дно оврага», функция меняется незначительно.

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

Существуют различные подходы для определения точки минимума функции f(x) в овражной ситуации.

55

х*

Х(1)

Рис.

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

Другую эвристическую схему предложил И.М.Гельфанд.

Основная идея овражных методов.

совершают обычный градиентный спуск с постоянным шагом и

перемещаясь «вдоль дна оврага» (шаг называют овражным

u0дноu01

оврага

x(1)

Рис.

57

Пусть х0 и х1 – две произвольные близкие точки. Как и в предыдущем случае, из каждой точки осуществим градиентные спуски с постоянным шагом . Получим точки u0 и u1, лежащие в окрестности «дна оврага». Соединяя их прямой, делаем «большой шаг» в полученном направлении. В результате получим точку х2. Из этой точки осуществим градиентный спуск и получим точку u2. А вот далее, для того чтобы осуществить «овражный шаг», берем предпоследнюю точку u1. Соединяя прямой точки u2 и u1, делаем шаг в полученном направлении и определяем х3. Дальше аналогичным образом вычисляются х4,

х5, … .

x(2)

xk+2

uk+2

Рис.

Схема овражного метода 2 Шаг 1. Задаются начальное приближение х0, точность

решения 1 и 3, шаг для градиентного спуска, начальное значение для овражного шага.

Из точки х0 осуществляется градиентный спуск с постоянным шагом на «дно оврага». В результате получается точка u’0.

В окрестности х0 берется точка х1, из которой тоже осуществляется градиентный спуск на «дно оврага». В результате получается точка u’1. Полагается к=1. Если f(u’0)<f(u’1), то полагаем u0=u’1, u1=u’0. Если f(u’0)>f(u’1), то u0=u’0, u1=u’1.

вычисляется точка x'k+1. Из нее осуществляется градиентный

спуск и мы получаем точку u / . Если f( u / )<f(uk), то полагаем

k 1 k 1

xk+1= х / и uk+1= u / . k 1 k 1

Иначе уменьшаем овражный шаг (например в 2 раза

и поиск минимума на этом заканчивается, иначе к=к+1 и переходим к шагу 2.

Методы Ньютона

Методы Ньютона относятся к методам второго порядка, использующих вторые частные производные целевой функции f(x). Все они являются прямым обобщением известного метода Ньютона отыскания корня уравнения:

Этот метод ещѐ называют методом касательных для решения уравнения φ(x) = 0.

Пусть теперь φ(x) – n-мерная вектор-функция векторного аргумента Х той же размерности. Тогда для решения системы уравнений φ(Х) = 0 мы можем использовать итерационный процесс, аналогичный:

59

Рассмотрим теперь случай, когда вектор-функция φ(x) является градиентом некоторой скалярной функции f(x), т.е.

φ(x) = f'(x).

Приравнивая еѐ нулю, приходим к системе уравнений, определяющей координаты стационарных точек функции f(x). Формула метода Ньютона для решения этой системы выглядит следующим образом:

xk+1 = xk – (f''(x)) –1·f'(x), (4)

и получается заменой в (3) φ(xk) на f'(x).

Итерационный процесс (4) строит последовательность точек {xk}, которая при определѐнных предположениях сходится к некоторой стационарной точке x функции f(x), т.е. к точке, в которой f'(x ) = 0. Если матрица вторых производных f''(x ) положительно определена, эта точка будет точкой локального минимума функции f(x).

Основная идея метода Ньютона.

В методе Ньютона последовательность точек спуска определяется формулой (4). Для текущей точки xk направление и величина спуска определяется вектором pk = – (f''(xk)) –1·f'(xk). Хотя в определении вектора pk фигурирует обратная к f''(xk) матрица (f''(xk)) –1, на практике нет необходимости вычислять последнюю, так как направление спуска pk можно найти как решение системы линейных уравнений

градиент f'(x0) и матрица f''(x0).

Шаг 2. Определяется направление спуска pk, как решение системы линейных уравнений f''(xk)·pk = – f'(xk) (например, методом исключений Гаусса).

Шаг 3. Определяется следующая точка спуска:

xk+1 = xk + pk.

Шаг 4. В точке xk+1 вычисляются градиент f'(xk+1) и матрица f''(xk+1).

60

Шаг 5. Если ||f'(xk+1)|| ε3, то поиск заканчивается и

полагается x = xk+1 и y = f(xk+1).

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

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

В общем случае, когда минимизируемая функция не квадратична, вектор pk = – (f''(xk)) –1·f'(xk) не указывает в точку еѐ минимума, однако имеет большую составляющую вдоль оси оврага и значительно ближе к направлению на минимум, чем антиградиент. Этим и объясняется более высокая сходимость метода Ньютона по сравнению с градиентными методами при минимизации овражных целевых функций.

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

Модификации метода Ньютона.

Значительные трудности, возникающие при практической реализации метода Ньютона, связаны с необходимостью вычислить матрицу f ''(x). Мы рассмотрим две модификации метода Ньютона, которые используют не точные значения, а некоторые приближѐнные аналоги матрицы вторых производных. В результате уменьшается трудоѐмкость методов, но, конечно, ухудшается их сходимость.

В качестве первой модификации метода Ньютона рассмотрим следующий алгоритм:

xk+1 = xk – k(f''(xk)) –1·f'(xk), k ≥ 0. (8)

здесь для построения направления спуска используется один раз вычисленная и обращѐнная матрица вторых производных f''(x0).

Схема модификации I метода Ньютона.

Шаг 1. При k = 0, вводятся x0, ε3. Вычисляются f'(x0) и

f''(x0).

Шшаг 2. Определяется обратная матрица (f''(x0))–1. Шаг 3. Определяется направление спуска pk: