Материал: Методы оптимизации в примерах и задачах. Медведь Н.А., Фокин А.А

y k

f (x k ) .

Как известно, в малой окрестности точки xk антиградиент

обеспечивает наискорейшее убывание

функции. Приведем два

варианта методов градиентного спуска

(отличающиеся способом

отыскания величины α).

Шаг 0.

Задать параметр точности , начальный шаг

0,

выбрать x0 Rn , вычислить f(x0).

Шаг 1.

Найти f (x0 ) и проверить критерий останова:

Шаг 3. Положить

и перейти к шагу 2.

2

Пример. Решить задачу

Итерация 1

0.

Зададим x0=(0.5,1), f(x0)=1.5. Выберем =0.01,

1 .

1.

f (x 0 ) = (2, 2), || f (x 0 ) ||> .

3. Положим

= 1/2 и перейдем к шагу 2.

2

1

0

1

0

1

х

= х

-

f (x

) = (0.5-1,1-1) = (-0.5,0), f(x

) = 0.5.

2

Так как f(x1)<f(x0),

то полагаем

х0 = х1 = (-0.5,0), f(x0) = f(x1) = 0.5 и переходим к шагу 1.

Итерация 2

5.

f (x 0 ) =(-2,0), ||

f (x 0 ) ||>

1

0

1

0

1

х

= х

-

f (x

) = (-0.5+1,0) = (0.5,0), f(x ) = 0.5,

2

7. Положим

= 1/4 и перейдем к шагу 2.

2

1

f (x 0 ) = (-0.5 +0.5, 0) = (0,0), f(x1) = 0,

х1 = х0- 4

f(x1) < f(x0).

Полагаем

х0 = х1 = (0,0) , f(x0) = f(x1) = 0 и переходим к шагу 1.

9.

f (x0 ) = (0,0), ||

f (x 0 ) || = 0< - останов, найдено

точное решение.

Ответ: x1*

0; x*2

0; f min

0.

2.3.2.2. Метод наискорейшего спуска

Пусть

f(x) имеет минимум в

точке x* (x1* , x*2 ,..., x*n ) ,

координатами.

x ik 1

x ik

k f x

' (x k );

k

0, k

1,2,... (2.3.1)

i

В методе наискорейшего спуска величина

k

определяется

из условия минимума функции одной переменной.

Ôk ( ) f {xk

f '

(xk ), xk

f ' (xk ),..., xk

f

'

(xk )} . (2.3.2)

1

x

2

x

n

x

i

2

n

последовательность точек xk, (k=1,2,…) сходится к х*, т.е.

lim xk x*.

(2.3.3)

k

На практике процесс итераций по (2.3.1) заканчивается при

k=n, если выполняется условие

max

f x' (x n )

,

(2.3.4)

i

i

где - заданная точность нахождения минимума.

следующих шагов.

Шаг 0.

Задать параметр точности

, выбрать х0 Rn .

Шаг 1.

Найти

f (x 0 ) и проверить критерий останова:

||

f (x 0 ) ||< .

(2.3.5)

Если он выполнен, то вычисления завершить, полагая

x* = x0, f* = f(x0) .

Шаг 2.

Решить задачу одномерной оптимизации

Ф(α) = f(х0- α f (x 0 ) )

min ,

f (x)

{f '

, f '

}

{2x

1

2x

2

- 6; 2x

1

4x

2

- 8},

x1

x

2

имеем

f (x 0 )

{-2;-2}.

Значение шага

0

получим из условия минимума функции,

Ф0 (

)

f(1

2

,1

2

)

20

2

8

3,

0.

Решая одномерную задачу минимизации, получим

0 = 0,2.

Поэтому

x11

1

2

1,4;

x 12

1 2

1,4.

Найдем второе приближение, для чего вычислим

координаты

f (x) в точке х1(1,4;1,4):

f x' (1,4;1,4)

- 0,4,

f x'

(1,4;1,4)

- 0,4.

1

2

Точка х2( x12 , x 22 )

лежит на луче

x1

1,4

0,4

;

x 2

1,4

0,4

,

0.

Минимизируя функцию

Ф (

)

f(1,4

0,4

;1,4

0,4

)

0,16

2

0,32

14,2,

1

получаем

1

1; x12

1,8; x 22

1.

Аналогично найдем

x13

1,88; x 32

1,08; x14

1,96; x 24

1.

Проверим условие (2.3.5) или (2.3.4), для чего вычислим

значение производных функции f(x) в точке x 4 (x14 , x 24 )

f ' 4 (1,96;1)

- 0,08; f '

4

(1,96;1)

- 0,08.

x

x

2

1

0,1,

Так как

0,08

то процесс итераций заканчиваем.

Ответ:

x1*

1,96; x*2

1; fmin

2,0016.

Замечание: Классическим методами математического

анализа можно найти точное решение:

x1

2, x 2

1, fmin

2.

Пример 2. Решить задачу

f (x)

x12

x 22

4x1

2x 2

min

методом наискорейшего спуска.

Решение:

f (x) (2x1

4,2x2

2)