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

Пусть дана функция f (X), ограниченная снизу на множестве и имеющая непрерывные частные производные во всех его точках.

Требуется найти безусловный минимум функции f (X) на множестве допустимых решений, то есть найти такую точку , что

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

Разложим функцию f (X) в окрестности точки в ряд Тейлора:

, (4.2)

где — градиент функции f (X) в точке X^k; — вектор приращения переменных функции f (X); — члены ряда, имеющие второй порядок и выше.

Ограничимся в выражении (4.2) членами не выше первого порядка, тогда выражение (4.2) примет вид:

. (4.3)

Приращение вектора переменных должно выбираться таким образом, чтобы выполнялось неравенство . Уменьшение значения функции в точке может быть осуществлено за счет выбора 2-го слагаемого, а именно, . В этом случае направление поиска минимума функции будет совпадать с направлением, противоположным градиенту . Тогда формула (4.1) примет окончательный вид [4,5]:

. (4.4)

Замечания

1. Величина шага α вдоль выбранного направления в выражении (4.4) может быть:

- постоянной α =const, и не зависящей от выбора точки X^k и номера итерации; в этом случае реализуется градиентный метод с постоянным шагом;

- может определяться на каждой итерации, и α^k вычисляется путем решения задачи минимизации функции f (X) вдоль выбранного направления на основе методов однопараметрической оптимизации [6]; в этом случае реализуется метод Коши.

Рисунок 6 — Приближение к точке минимума функции на основе метода наискорейшего спуска (Коши).

Алгоритм

Шаг 1. Задать начальную точку X ⁰, ε ₁>0, ε ₂>0, предельное число итераций M. Найти градиент функции в произвольной точке.

Шаг 2. Положить k =0.

Шаг 3. Вычислить

Шаг 4. Проверить выполнение критерия окончания :

а) если критерий выполнен, то X ^*= X^k;

б) иначе перейти к шагу 5.

Шаг 5. Проверить выполнение равенства k ≥ M:

а) если неравенство выполнено, то X ^*= X^k;

б) иначе перейти к шагу 6.

Шаг 6. Вычислить величину α^k в соотношении на основе метода квадратичной аппроксимации [6], положив α^k ₁=0, Δ α =0,1.

Шаг 7. Вычислить .

Шаг 8. Проверить выполнение условий:

а) если оба условия выполнены, то расчет окончен и X ^*= X^k⁺ ¹;

б) если хотя бы одно из неравенств не выполнено, то положить k = k +1 и перейти к шагу 3.

Пример 4. Выполнить приближение к локальному минимуму функции f (X)=2 x ₁²+ x ₁ x ₂+ x ₂² на основе двух итераций в соответствии с методом наискорейшего спуска (Коши).

1. Зададим X ⁰= , ε ₁=0,1, ε ₂=0,15, М =1. Градиент функции в произвольной точке равен .

2. Положим k =0.

3 ⁰. Вычислим .

4 ⁰. Вычислим . Перейти к шагу 5.

5 ⁰. Проверим условие k =0<1, перейти к шагу 6.

6 ⁰. Вычислим величину шага вдоль выбранного направления α ⁰ на основе метода квадратичной аппроксимации [6]. Для этого выполним следующие действия.

1) α ⁰₁=0; ; Значение функции в вычисленной точке равно ;

2) α ⁰₂= α ⁰₁+ Δ α =0,1;

Значение функции в вычисленной точке равно ;

3) Так как f ¹> f ², то α ⁰₃= α ⁰₁+ 2Δ α =0,2;

Значение функции в вычисленной точке равно ;

По имеющимся значениям α ⁰₁, α ⁰₂ и α ⁰₃ и значениям функций f ¹, f ² и f ³ вычисляем значение , минимизирующее функцию вдоль выбранного направления .