Задача безусловной оптимизации

Задача безусловной оптимизации - задача оптимизации , допустимой множеством которой является весь евклидово пространство ( R N ):

$f (x) \ to \ min, \ qquad x \ in \ mathbf R ^ n$

Методы решения

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

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

Геометрическое представление метода в R 2 . Синим цветом показаны линии уровня функции.

Метод заключается в построении последовательности { X K } по формуле:

$x ^ {k +1} = x ^ k - t (x ^ k) \ cdot \ nabla f (x ^ k)$ . (1)

где ? F ( X K ) - градиент функции f ( x ) в точке X K , а t ( X K ) выбирается исходя из условия:

$\ Min_t f \ left (x ^ k - t \ nabla f (x ^ k) \ right) = f \ left (x ^ k - t (x ^ k) \ nabla f (x ^ k) \ right)$ . (2)

Впервые метод был предложен французским математиком Огюстен Коши . Широкое применение этого метода обусловлено тем, что в направления антиградиенту - ? F ( x ) производная функции по направлению достигает наименьшего значения.

Если градиент ? F ( x ) непрерывен по x а f ( x ) ? ? при X ? ?, то при произвольном начальном приближении ?F ( X K ) ? 0 при K ? ?. Если при этом x * - единственная стационарная точка, то X K ? X * , где f ( x * ) = Min X F( x ).

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

Пусть существует матрица Гессе

$H (x) = \ left \ {\ frac {\ partial ^ 2F} {\ partial x_i \ partial x_j} \ right \} ^ n_ {i, j = 1}$ ,

положительно определена в каждой точке x . Тогда для последовательности (1) X K ? X * , и, начиная с некоторого номера N , выполняется неравенство

$\ Sum_ {i = 1} ^ n (x_i ^ {k +1} - x_i ^ *) \ leq q \ sum_ {i = 1} ^ n (x_i ^ k - x_i ^ *) ^ 2$ при K ? N ,

где

$q = \ frac {M (x ^ *) - m (x ^*)}{ M (x ^ *) + m (x ^ *)} <1$ ,

X K и - i -я координата X K , M ( x * ) и m ( x * ) - соответственно наибольшее и наименьшее собственные значения матрицы H ( x * ).

Существует модификация метода, когда t ( X K ) = ?> 0 - const, то есть

$x ^ {k +1} = x ^ k - \ tau \ nabla f (x ^ k)$ . (3)

Если градиент ? F ( x ) удовлетворяет условию Липшица , то для последовательности (3) при выполнении перечисленных предположений верны соответствующие свойства последовательности (1).