4.4. Метод проекции градиента.
Метод применяется в задачах поиска условного экстремума с ограничениями типа равенство и неравенств. Мы ограничимся рассмотрением поиска экстремума с ограничениями типа равенства.
Требуется решить задачу
(4.4.1)
где функции f(X), i(X) выпуклые дифференцируемые функции.
Поиск решения состоит в построении последовательности точек {Xk}, вычисляемых по правилу
Xk+1=Xk+Xk (k=0, 1, …), (4.4.2)
где Xk вектор, вычисляемый для каждого значения k из условия проекции вектора f(Xk), k=0, 1, …, на аппроксимирующую плоскость, задаваемую уравнением
AkXk =Tk, (4.4.3)
которая аппроксимирует в точке Xk (k=0, 1, …) поверхность П, задаваемую уравнениями i(X)=0 (i=1, …, m). Здесь Ak матрица
A(X)=
,
вычисленная в точке X=Xk, Tk=(1(Xk), …, m(Xk))T.
Вектор Xk определяется по формуле
Xk=1Xk+2Xk (4.4.4)
где
1Xk=hk[E
(Ak
)
Ak]f(Xk)=hkXk
(4.4.5)
градиентная составляющая приращения, 2Xk= (Ak ) Tk компенсационная составляющая приращения.
Величина hk шага может выбираться как из условия убывания функции f(X) при переходе из точки Xk в точку Xkhk[E (Ak ) Ak]f(Xk), так и из условия
(hk)=f(Xkhk[E (Ak ) Ak]f(Xk)) (4.4.6)
Задача (4.4.6) может решаться либо с использованием необходимых и достаточных условий минимума, либо с использованием численных методов.
Расчёт
заканчивается в точке Xk,
в которой |Xk|,
|2Xk|,
где
заданное число. В полученной точке
обязательна проверка выполнения
достаточных условий минимума функции
в исходной задаче (4.4.1). Если будет
выполнено точное равенство
1Xk=hk[E
(Ak
)
Ak]f(Xk)=
,
то это означает, что выполнены точные
необходимые условия экстремума. При
этом вектор k
множителей Лагранжа определяется по
формуле
k=(Ak ) Akf(Xk) (4.4.7)
Если в задаче (4.4.1) ограничения линейны, то матрица A постоянна. При этом начальная точка X0 попадает в ОДР за одну итерацию. В дальнейшем требуется вычисление только 1Xk.
Таким образом, алгоритм решения задачи следующий:
1. Задать X0, 0, k0 число итераций.
2.
Найти
A(X),
f(X),
X=[E
(A
)
A]f(X),
2X=AT(AAT)
T(X)
где
T(X)=(1(Xk),
…, m(Xk))T.
3. Положить k=0.
4. Проверить выполнение условия kk0:
а) если неравенство выполнено, то расчёт окончен. Вычислить k=(Ak ) Akf(Xk), проверить необходимое условие минимума, оценить результаты;
б) если неравенство не выполнено, то перейти к шагу 5.
5. Вычислить матрицу Ak=A(Xk).
6. Вычислить 2Xk.
7. Вычислить |2Xk|.
8. Вычислить Xk.
9. Вычислить |Xk|.
10. Проверить выполнение условий |Xk| и |2Xk|:
а) если условия выполняются, то расчёт окончен. Вычислить k и проверить достаточные условия минимума;
б) если |Xk|>, |2Xk|, то положить 2Xk=0 и перейти к шагу 11;
в) если |Xk| и |2Xk|>, то положить Xk=0 и перейти к шагу 13;
г) если |Xk|>, |2Xk|>, то перейти к шагу 11.
11.
Получить выражение для точки Xk+
Xk.
12. Определить из условия f(Xk+hkXk) .
13. Вычислить Xk+1=Xk+ Xk+2Xk. Положить k=k+1 и перейти к шагу 4.
Если ограничения в задаче линейны, то при k1 на шаге 4 переходим к шагу 8. При этом на шаге 10 полагаем |2Xk|=0.
Пример II. Найти условный экстремум функции:
f(X)= min
3x12x25=0.
Решение. 1. Задаём X0=(1, 1) =0,1, k0=10 число итераций.
2.
Найдём
A(X)=
=(3;
2),
f(X)=(4x1,
8x2)Т,
X=[E
(A
)
A]f(X)=
=
=
=
=
=
=
=
,
то
есть
X
,
T(X)=1(Xk)=3x1+2x2+5,
2X=AT(AAT)
T(X)=
(3x1+2x2+5)=
=
(3x1+2x2+5)=
=
,
то
есть 2X
.
3. Полагаем k=0.
4.0. Проверим выполнение условия kk0: k=0<10=k0 неравенство не выполнено. Поэтому идём к пункту 5.
5.0. Вычисляем матрицу A0=A(X0)=(3; 2).
6.0.
Вычисляем 2X0=
=
.
7.0.
Вычисляем |2X0|=
=0.
8.0.
Вычисляем X0=
.
9.0.
Вычисляем |X0|=
0,832.
10.0. Проверяем выполнение условий |X0|0,1 и |2X0|0,1. Имеем |X0|>0,1 и |2X0|0,1. Поэтому полагаем 2X0=0 и переходим к шагу 11.
11.0. Получим выражение для точки X0+h0X0:
X0+h0X0=(1; 1)+h0(2,462; 3,692)=(1+2,462h0; 1+3,692h0).
12.0.
Определяем h0
из условия f(X0+h0X0)
.
Имеем
f(X0+h0X0)=2(1+2,462h0)2+4(1+3,692h0)2=
=2(1+4,924h0+6,061
)+4(17,384h0+13,631
)=
=66,646 19,688h0+6.
Так
как f(X0+h0X0)
квадратный трёхчлен относительно h0
с положительным коэффициентом при
,
то минимум f(X0+h0X0)
достигается при h0,
удовлетворяющем уравнению
(X0+h0X0)=0.
Имеем
(X0+h0X0)=133,292h019,688=0 h00,15.
13.0. Вычисляем X1:
X1=X0+h0X0+2X0=X0+h0X0=(1+2,4620,15; 1+3,6920,15)=(1,3693; 0,4462).
Положим k=1 и перейдём к шагу 4.
4.1. Проверим выполнение условия kk0: k=1<10=k0 неравенство не выполнено. Поэтому идём к пункту 5.
5.1. Вычисляем матрицу A1=A(X1)=(3; 2).
6.1.
Вычисляем 2X1=
=
.
7.1.
Вычисляем |2X1|=
0.
8.1.
Вычисляем X1=
.
9.1.
Вычисляем |X1|=
0,0677.
10.1. Проверяем выполнение условий |X1|0,1 и |2X1|0,1. Имеем |X1|0,1 и |2X1|0,1. Поэтому расчёт окончен. Вычисляем 1 для проверки необходимых и достаточных условий экстремума в найденной точке X1=(1,3693; 0,4462):
1=(A1
)
A1f(X1)=
=1,8135.
Выпишем необходимые условия экстремума с учётом функции Лагранжа: L(X, )= +1(3x12x25):
=4x1+31, =8x221,
(4.4.6)
Будем считать, что необходимые условия выполнены, если уравнения системы (4.4.6) выполняются с точностью до 0,1. Подставляем X1=(1,3693; 0,4462) и 1=1,8135 в систему (4.4.6):
Следовательно, необходимые условия экстремума в точке X1 выполнены. Проверим достаточные условия экстремума. Имеем
=4, =8, = =0, d2L=4d +8d >0,
то есть достаточное условие минимума выполняется. Таким образом,
Ответ: точкой условного локального минимума является точка X*(1,3693; 0,4462), f(X*)4,5447 условный локальный минимум.
Приложения