Методы оптимизации (стр. 8 из 11)

8² . Зададим

= 0,25.

9². Вычислим

: x₁₁ = (-0,03;0,125)^T

10². Проверим условие

:

= 0,01-0,109 = -0,099 < 0.

11². Проверим условия

, :

= 0,22 > 0,15, = 0,099 < 0,15.

Полагаем k=1 и переходим к шагу 5.

5³. Проверим условие

: k = 1 = n -1.

6³. Вычислим

: = (0,005; 0,22)^T .

7³. Проверим условия

: = 0,22 > 0,1.

8³. Зададим

=0,25.

9³. Вычислим

: x₁₂ =(-0,03; 0,07)^T.

10³. Проверим условие

:

= 0,0046 -0,01 = -0,0054 < 0.

11³. Проверим условия

, :

= 0,055 < 0,15, = 0,0054 < 0,15.

Зададим k= 2 и переходим к шагу 5.

5⁴. Проверим условие

: k = 2 > п-1.

Полагаем j = 2, х₂₀ = х₁₂ и переходим к шагу 3.

3² . Проверим условие

: j= 2 < 10 = М.

4². Зададим k=0.

5⁴. Проверим условие

:k = 0 <1 = n-1.

6⁴. Вычислим

: = = (-0,05; 0,11)^T.

7⁴. Проверим условие

: = 0,12 > 0,1.

8⁴ . Зададим

= 0,25.

9⁴. Вычислим

: х₂₁= (- 0,02; 0,07)^Т.

10⁴. Проверим условие

: 0,0043-0,046 = -0,0003 < 0, перейдем к шагу 11.

11⁴. Проверим условия

, :

= 0,01 < 0,15 , = 0,0003 < 0,15.

Условия

, выполнены в двух последовательных циклах с номерами j= 2 и j-1 = 1. Расчет окончен, найдена точка х₂₁= (- 0,02; 0,07)^Т; f(х₂₁) = 0,0043 .

На рис. 6 полученные точки соединены пунктирной линией.

В методе покоординатного спуска мы спускаемся по ломаной, состоящей из отрезков прямых, параллельных координатным осям.

Рис. 6

II. Анализ точки х₂₁.

В примере 1.1 (гл.2 §1) было показано, что функция f(х) строго выпукла, имеет единственный минимум и, следовательно, точка х₂₁ = = (-0,02; 0,07)^Т является найденным приближением точки глобального минимума. ■

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

Теорема. Если функция f(x) ограничена снизу, ее градиент удовлетворяет условию Липшица (

)и выбор значения

производится одним из описанных выше способов, то, какова бы ни была начальная точка х₀:

при .

При практической реализации схемы

k=1, 2, …n.

итерации прекращаются, если для всех i, i = 1, 2, ..., n, выполнены условия типа

,

где

- некоторое заданное число, характеризующее точность нахождения минимума.

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

(если функция f(х) не имеет минимума; рис. 7), либо к значению функции в некоторой стационарной точке, являющейся пределом последовательности {х_к}. Нетрудно придумать примеры, когда в этой точке реализуется седло, а не минимум. На практике методы градиентного спуска уверенно обходят седловые точки и находят минимумы целевой функции (в общем случае — локальные).

Рис. 7

§ 2. Методы второго порядка

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

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

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

Стратегия поиска

Стратегия метода Ньютона [ NewtonI. ] состоит в построении последовательности точек {х_k}, k = 0,1,..., таких, что

k= 0,1,.... Точки последовательности вычисляются по правилу

(5)

где х₀задается пользователем; величина шага

определяется для каждого значения kпо формуле

.(6)

Выбор

по формуле (6) гарантирует выполнение требования при условии, что . Формула (6) получена из следующих соображений:

1. Функция f(х) аппроксимируется в каждой точке последовательности {х^k} квадратичной функцией

.

2. Направление

определяется из необходимого условия экстремума первого порядка: Таким образом, при выполнении требования последовательность является последовательностью точек минимумов квадратичных функций F_k, k= 0,1,... (рис. 8). Чтобы обеспечить выполнение требования , k = 0,1,..., даже в тех случаях, когда для каких-либо значений матрица Гессе не окажется положительно определенной, рекомендуется для соответствующих значений kвычислить точку по методу градиентного спуска с выбором величины шага из условия .