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

С огласно этому методу надо сделать сразу такой шаг t_* из начальной точки 0 в направлении антиградиента –G₀ , чтобы функция F перестала убывать. То есть мы должны найти минимум целевой функции F на данном направлении (точка I). Слева и справа на выбранной прямой от точки I функция F возрастает.

В точке I наше направление касается линии уровня. Направление градиента в этой точке касательной, т.е. нашей прямой, по которой мы пришли из точки 0 в точку I.

А нтиградиент -G₁ определяет следующее направление движения до точки касания другой изолинии (точка 2), градиент в которой второму нашему направлению. Продолжая процесс, придем в точку минимума F₀.

Достоинство метода наискорейшего спуска: знаем, какой выбрать шаг, и не боимся проскочить минимум.

К ак вычислить шаг t_* ?

t

t

Условие минимума функции F на данном направлении

.

Из этого уравнения мы и будем искать шаг. Здесь одно нелинейное уравнение и можно найти его корень методом Ньютона.

Напишем параметрическое уравнение прямой в матричном виде:

где - это вектор переменных

- это вектор производных .

Функция F зависит от переменных х, которые в свою очередь зависят от шага t, т.е. . Возьмем производную от функции , скалярное произведение двух векторов, из которых

первый вектор

второй вектор: .

Возьмем производную по параметрическим уравнениям

;

- это компоненты вектора - градиента

Следовательно: .

Определим шаг t^* методом Ньютона. Имеем одно нелинейное уравнение (см. рис.), необходимо найти его корень t^*.

Вспомним алгоритм вычисления методом Ньютона:

1. Задание начального значения t.

2. Вычисление функции .

3. Вычисление производных .

4. Вычисление ньютоновского шага .

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

.

Известно, что методом Ньютона самый значительный шаг от начального приближения к корню осуществляется на первой итерации. Поэтому для того, чтобы сократить время расчетов, ограничиваются только одним шагом метода Ньютона к корню нелинейного уравнения , то есть за его решение принимают первое приближение ∆t_н, считая, что оно достаточно близко к действительному корню t^*, но не больше его.

Отметим, что в том случае, когда векторы – G⁽¹⁾ и G⁽⁰⁾ будут перпендикулярными векторами, этому условию и соответствует шаг t^*.

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

(ε = 0,10).

0 шаг

1. ; ; .

2. ; .

3. и .

4. .

5. t_п = 0,1 (из эксперимента).

6.

7. ; .

8.

9. .

10. .

1 шаг

1. ; .

2. ; .

3. Нет !

4. .

5. t_п = 0,1.

6. ; .

7. ; .

8. .

9. .

10. .

y – вектор независимых переменных (его порядок равен числу степеней свободы n - m)

z = x, y.

Разделение переменных вектора z на зависимые и независимые переменные, то есть на x и y , в каждой конкретной задаче осуществляется с учетом удобства и целей расчета. В процессе спуска к минимуму функции можно перемещать переменные между векторами x и y оставляя порядок векторов неизменным, за счет чего удается уменьшить число шагов.

Зависимые переменные вектора x с помощью систем уравнений (2) исключаются из целевой функции (1) в результате задача (1) – (2) сводится к нахождению минимума функции вектора y без ограничений.

Поясним этот метод подробнее. Итак, решаем задачу

min F( x, y )

при W( x, y ) = 0 (6)

Задаем y = y⁽⁰⁾ и подставляем его в систему уравнений. Получим систему W( x, y⁽⁰⁾ ) = 0, в которой число переменных х равно числу уравнений. Решив эту систему любым известным методом найдем корни х⁽⁰⁾.

Поскольку значение х зависит от задаваемого значения y, то вектор х является неявной функцией вектора y

х = х( y ).

Поэтому можно записать

F( x, y ) = F( x ( y ), y ) = F( y ) (7)

W [ x ( y ), y ] = 0 . (8)

Градиент функции (7)

, (9)

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

- матрица частных производных зависимых переменных по независимым.

Матрица может быть получена из (8) по правилу вычисления частных и производных неявной функции

,

где и - матрицы частных производных уравнений связи соответственно по зависимым и независимым переменным.

Д альнейшая процедура определения минимума функции (7) ничем не отличается от процедуры, осуществляемой по методу наискорейшего спуска.

Пример: найти минимум функции

при условиях связи

( n – m ) = ( 3 – 2 ) = 1

Решение: примем Y = Р₃, Х = Р₁, Р₂;

при

0 шаг

1. Пусть у = 20, тогда х₁ = 0, х₂ = 50

2. .

3. .

а) ;

б) ;

в )

G_у < ε

3. Нет !

4. .

5. t_п = 0,01.

6.

.

7. .

8.

9. .

10. .

1 шаг

1.

2. .

3. .

К онец расчета.

Пример: найти минимум функции

при условиях связи

методом Лагранжа

Решение:

1			х		=	50
2						20

		х		=	-50	х 1,5
					-20