Методы оптимизации (стр. 7 из 11)

х₃=(0,04; 0,08)^T - 0,24 (0,24; 0,2)^T = (-0,0176; 0,032)^T.

8² . Вычислим

и :

= 0,0749 < 0,15; = 0,0116 < 0,15.

Полагаем k =3 и переходим к шагу 3.

3³. Вычислим

: = (-0,012;-0,0816)^T.

4³. Вычислим

: = 0,082 < 0,1. Расчет окончен. Найденаточка х₃=(-0,0176;0,032)^T, f(х₃) = 0,00127.

II. Анализ точки х₃.

В примере 1.1 (гл.2 §1) было показано, что функция f(x) является строго выпуклой и, следовательно, точка х₃ является найденным приближением точки глобального минимума х_*. ■

1.3 Метод покоординатного спуска

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

Стратегия решения задачи состоит в построении последовательности точек {х_k}, k = 0,1,..., таких, что

k= 0,1,... . Точки последовательности {х_k}вычисляются по циклам в соответствии с правилом

. (4)

где j- номер цикла вычислений; j = 0,1,2,...; k- номер итерации внутри цикла, k= 0,1,...,n-1; е_k+1, k = 0,l,..., n- 1 -единичный вектор, (k+1) -я проекция которого равна 1; точка х₀₀ задается пользователем, величина шага

выбирается из условия

или .

Если выбранное условие при текущем

не выполняется, шаг уменьшается вдвое и точка вычисляется заново. Легко видеть, чтопри фиксированном jза одну итерацию с номером kизменяется только одна проекция точки х_jk, имеющая номер k +1, а в течение всего цикла с номером j , т.е. начиная с k= 0 и кончая k= п -1, изменяются все п проекций точки х_j0. После этого точке х_jпприсваивается номер х_{j + 0,1}, и она берется за начальную точку для вычислений в j + 1 цикле. Расчет заканчивается в точке х_jkпри выполнении по крайней мере одного из трех критериев окончания счета: , или , или двукратного выполнения неравенств , .

Полученные в результате вычислений точки могут быть записаны как элементы последовательности {х_l}, где

- порядковый номер точки, т.е.

Геометрическая интерпретация метода для п = 2 приведена на рис. 5.

Рис. 5

Пример 1.3. Найти локальный минимум функции

.

□ I. Определение точки x_jk, в которой выполнен по крайней мере один из критериев окончания расчетов.

1. Зададим х₀₀,

М: х₀₀ = (0,5; 1)^Т, ; М=10. Найдем градиент функции в произвольной точке

2. Зададим j= 0.

3⁰. Проверим выполнение условия

: j = 0<10 = М.

4⁰. Зададим k= 0.

5⁰. Проверим выполнение условия

: k = 0<1 = n-1.

6⁰. Вычислим

: = (3; 2,5)^T.

7⁰. Проверим условие

: = 3,8 > 0,1.

8⁰. Зададим

= 0,5 .

9⁰. Вычислим

, где

, .

Отсюда х₀₁ = (-1;1)^T.

10⁰. Проверим условие

: = 2-2 = 0. Вывод: полагаем = 0,25 и переходим к шагу 9.

9⁰¹. Вычислим х₀₁ с шагом

= 0,25: х₀₁ = (-0,25; 1)^T.

10⁰¹. Проверим условие

:

= 0,875 - 2 = -1,125 < 0.

11⁰. Проверим условия

, :

= 0,75 > 0,15; = 1,125 > 0,15.

Полагаем k=1 и переходим к шагу 5.

5¹. Проверим условие

: k = 1 = n-1.

6¹. Вычислим

: = (0; 1,75)^T.

7¹. Проверим условие

: = 1,75 > 0,1.

8¹. Зададим

=0,5.

9¹. Вычислим

, где ;

.

Отсюда х₀₂ = (-0,25; 0,125)^Т .

10¹. Проверим условие

:

= 0,109 - 0,875 = - 0,766 < 0.

11¹. Проверим условия

, :

= 0,875 > 0,15, = 0,766 > 0,15.

Полагаем k= 2, переходим к шагу 5.

5². Проверим условие

: k = 2 > n -1. Зададим j= 1, х₁₀ = х₀₂, переходим к шагу 3.

3¹. Проверим условие

: j= 1 < 10 = М.

4¹. Зададим k= 0.

5². Проверим условие

: k = 0 <1 = п-1.

6². Вычислим

: = = (-0,875; 0,00)^T .

7². Проверим условие

: = 0,875 > 0,1.