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

Рассмотрим задачу максимизации функции f(X). Пусть Х° - начальная точка, с которой начинается реализация метода, УДХ*) - градиент функции f в k-й точке X*. Идея метода сводится к определению в данной точке направления р, вдоль которого производная по направлению df/dp достигает своего максимума. Это происходит в том случае, когда последовательные точки X* и Х*+1 связаны соотношением

где г* - параметр, называемый длиной шага в точке X*.

Обычно значение параметра г* выбирается из условия, чтобы в точке Х*1 наблюдалось максимальное увеличение значения целевой функции /. Другими словами, если функция Л(г) определяется соотношением

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

Описанная процедура заканчивается, когда две последовательные точки X* и X**1 близки. Это эквивалентно тому, что rVf(Xk) = 0. Поскольку г * 0, последнее соотношение означает, что в точке X* выполняется необходимое условие экстремума УДХ*) = 0.

Пример 21.1.2

Рассмотрим задачу максимизации функции

/(х х2) = 4х, + 6х2 -2х] -2хххг -2х22.

Функция Дх х2) является квадратичной, и нам известно, что ее абсолютный мак-

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

k+l

X + rkVf(Xk),

h(r) = f(Xk + rVf(Xk)),

УДХ) = (4 - 4x, - 2x2, 6 - 2x, - 4x2). Пусть начальной точкой является Х° = (1, 1).

X = (l, l) + r(-2, 0) = (l-2r, 1).

ДХ) = 4х, + 6х2 - 2xf- 2ххх2 - 2х22

1 1 3 2 х1

Рис. 21.3. Последовательность точек, ведущая к оптимуму функции

Отсюда получаем выражение для функции 1г(г):

h(r) =Д1 - 2r, 1) = -2(1 - 2rf + 2(1 - 2г) + 4.

Оптимальная длина шага г, при которой функция h(r) достигает максимума, равна 1/4. Таким образом, мы нашли, что X1 = (1/2, 1).

Итерация 2.

УДХ) = (0, 1).

Теперь следующая точка X2 определяется выражением

Х = (1,1) + К0,1) = (,1+/-).

Следовательно,

h(r) = -2(1 + rf + 5(1 + г) + .

Отсюда получаем г = 1/4 и X2 = (1/2, 5/4). Итерация 3.

УДХ2) = (-1,0). Точка X3 определяется выражением

Следовательно,

/i(r) = --(l-r)2+ -а-г)+ - 2 4 8

Отсюда получаем г = 1/4 и X = (3/8, 5/4). Итерация 4.

V/(X3) = (0, -).

Точка X4 определяется выражением

x=VWan Г35+Г

,8 4J I. А) 1,8 4 Поэтому

*(0 = -(5 + r)s+g(5 + r) + g.

Отсюда имеем г = 1/4 и X4 = (3/8, 21/16). Итерация 5.

УДХ4) = (-1,0).

Точка X5 определяется выражением

3 21 V-i,oi=fc:

Следовательно,

Х ,8l6j Л & ) { 8 16

Л(Н =--(3-г) +- (3-Н+-.

v 32v ; 64v 128

Отсюда получаем г = 1/4 и Xй = (11/32, 21/16). Итерация 6.

УДХ6) = (0, -).

Так как V/(X°) = 0, вычисления можно закончить. Получена приближенная точка максимума X5 = (0,3437, 1,3125). Точный максимум достигается в точке Х* = (0,3333, 1,3333).

УПРАЖНЕНИЯ 21.1.2

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

/(X) = 4,v, + 6х2 - 2.x2 - 2х,х, - 2х\.