Эта процедура вполне оправдывает название метода. С ее помощью мы построим последовательность точек M0,M1,M2,... которой соответствует монотонная последовательность значений функции f(M^0) \ge f(M^1) \ge f(M^2) \ldotsОбрывая ее на некотором шаге k, можно приближенно принять значение функции f(Mk) за ее наименьшее значение в рассматриваемой области (рис. 10).

Отметим, что данный метод сводит задачу поиска наименьшего значения функции нескольких переменных к многократному решению одномерных задач оптимизации. Если целевая функция f(x1,x2,\ldots,xn задана явной формулой и является дифференцируемой, то мы можем вычислить ее частные производные и использовать их для определения направления убывания функции по каждой переменной и поиска соответствующих одномерных минимумов.

На рис. 10 изображены линии уровня некоторой функции двух переменных u=f(x, y). Вдоль этих линий функция сохраняет постоянные значения, равные 1, 3, 5, 7, 9. Показана траектория поиска ее наименьшего значения, которое достигается в точке O, с помощью метода покоординатного спуска.

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


Рис. 10.

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

НЕ нашли? Не то? Что вы ищете?

Функция Розенброка:

f(x_1, x_2) = 100(x_2 - x_1^2)^2 + (1-x_1)^2; \quad x^* = (1; 1).

(11)

Функция Пауэлла:

\begin{aligned} & f(x)=(x_1+10x_2)^2+5(x_3-x_4)^2+(x_2-2X_3)^4+10(x_1-x_4)^4; \\ & x^*=(0;0;0;0). \end{aligned}

(12)

Двумерная экспоненциальная функция:

\begin{aligned} & f(x_1,x_2)=\sum_a [(e^{-ax_1}-e^{-ax_2})-(e^{-a}-e^{-10a})]^2, \\ & \text{где} \; a=0,1(0,1)1^*; \; x^*=(1;10). \end{aligned}

(13)

6.8. Методы оптимизации первого порядка

6.8.1. Спуск по координатам

Все методы минимизации сводятся к построению траектории спуска { Мk } вдоль которой целевая флнкция убывает:

f(Мk+1)<f(Мk)

(или возрастает).

Опишем координатный спуск. Выберем нулевое приближение М0(, .... ) и зафик­сируем все значения координат, кроме первой, тогда f ()

f (х1, , .... , )≡φ1(х1)

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

Используя методы минимизации функции одного переменного, найдем точку ее минимума и совершим шаг из М0 в М0(1)( , , ...., ).

На k-м шаге спуска: Из точки М0(k-1)( ,…, ,, .... , ).

спускаемся по xk минимизируя

φk(xk)≡f( ,…, , xk, , .... , ),

:φ( )=φk(xk) (1)

в точку

М0(k)( ,…, ,, .... , ).

И так до тех пор, пока не выполним один цикл спуска по координатам

Последнюю точку спуска назовем

М1≡ М0(п) ( ,…, )≡ М1 ( ,…, ).

Траектория { Мk} - траектория спуска, поскольку

f(Мk) ≤f(Мk-1).

В силу ограниченности снизу значений f(х) значением f(x*)≡ f* (мы предполагаем, что экстремум существует), то

fk ≥f* fk=≥f*

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

Рассмотрим трактовку координатного спуска на примере функции двух переменных:

Двигаясь по прямой АВ мы пересекаем линии уровня (х,у) = cons, при этом f (х, y) либо возрастает, либо убывает в зависимости oт направления движения. Только в одной точке В, где данная прямая касается линии уровня, функция f(х, у) имеет минимальное значение в данном на­правлении (экстремум по х или по у). Найдя такую точку, завершаем спуск по данному направлению.

Заметим, что в координатном спукске соответствующие направления взаимно ортогональны.

Если в рельефе наличествует «истинный», то спуск (в данном случае первый же спуск в точку В) приводит к попаданию на ''дно" оврага. А поскольку он ориентирован достаточно произвольно, то дальнейший спуск может оказаться невоз­можным. Хотя минимум еще и не достигнут.

Если же f () достаточно гладкая функция и минимум невырожден, hess f (*) > 0, то в окрестности * рельеф котловинный и координатный спуск ведет нас к локальному минимуму при произвольном начальном приближении 0 в этой окрестности.

Рассмотрим достаточные условия сходимости координатного спуска на примере функции двух переменных:

Теорема 1. Пусть D – множество уровня, ограниченное линией уровня f(х, у) = f0, т. е.

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

(2)

(G(х, у)≥d>0 в D. Используя критерий Сильвестра можно сформулировать многомерный аналог этого условия.)

Тогда траектория координатного спуска {Мk} (1) из произвольной точки М0 D сходится к локальному минимуму х* в области D.

Доказательство. Докажем сходимость grad f(Мk) на траектории спуска { Мk }. Проследим за изменением | fх | и | fу | на траектории спуска {Mk}. Поскольку f(х, у) вдоль траектории спуска не возрастает, то все точки Мk D0. Пусть предыдущий цикл спусков закончился в точке A, тогда

fy (А) = 0. | fх(A) | = U≠0.

Попав в точку экстремума В на прямой AB получим следующие компоненты градиета

|fy (В) | =V≠ 0 fx(А) = 0.

Теперь нетрудно получить, что

Спустившись далее по направлению ВС в точку экстремума С, найдём

Окончательно, за один цикл спуска, получаем

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97