Численные методы на основе метода штрафных функций

При этом методе задача (4.2.1) заменяется на задачу

F(X, r_s)=f(X)+P(X, r_s) ® min, (4.3.2)

где

P(X, r_s)= ,

=max{0, }= ,

r_s - так называемый параметр штрафа. Функция P(X, r_s) называется штрафной функцией. К полученной задаче применяются численные методы безусловной оптимизации (нулевого, первого или второго порядков). При этом начальная точка поиска задаётся обычно вне множества допустимых решений X. На каждой s-й итерации ищется точка X^*(r_s) минимума вспомогательной функции F(X, r_s) при заданном параметре r_s с помощью одного из методов безусловной минимизации. Полученная точка X^*(r_s) используется в качестве начальной на следующей итерации, выполняемой при возрастающем значении параметра штрафа. При неограниченном возрастании r_s последовательность точек X^*(r_s) стремится к точке условного минимума X^*.

Более подробно:

1. Задать: начальную точку X₀ внутри области X; начальное значение параметра r_s³0; число C>1 для уменьшения параметра штрафа; малое число e³0 для остановки алгоритма. Положить s=0.

2. Составить вспомогательную функцию

F(X, r_s)=f(X)+ .

3. Найти точку X^*(r_s) безусловного экстремума функции F(X, r_s) по X с помощью какого-либо метода (нулевого, первого или второго порядка):

F(X^*(r_s), r_s)= F(X, r_s).

При этом задать все требуемые выбранным методом параметры. В качестве начальной точки взять X_s. Вычислить P(X^*(r_s), r_s).

4. Проверить условие окончания:

а) если P(X^*(r_s), r_s)£e, то процесс поиска закончить:

X^*=X^*(r_s), f(X^*)=f(X^*(r_s));

б) если P(X^*(r_s), r_s)<e, то положить: r_s+1=Cr_s, X_s+1=X^*(r_s), s=s+1 и перейти к шагу 2.

Обычно выбирается r₀Î{0,01; 0,1; 1}, а CÎ[4, 10].

Пример I. Исследовать на условный экстремум функцию:

f(X)= ® min

3x₁-2x₂-5=0.

Решение. Нам потребуется вспомогательная функция F(X, r_s) при различных значениях параметра r_s и её градиент. Поэтому предварительно выпишем эти элементы задачи в общем виде:

F(X, r_s)= + (3x₁-2x₂-5)²,

=4x₁+3r_s(3x₁-2x₂-5), =8x₂-2r_s(3x₁-2x₂-5),

ÑF(X, r_s)=(4x₁+3r_s(3x₁-2x₂-5), 8x₂-2r_s(3x₁-2x₂-5)).

Далее действуем пошагово согласно вышеописанной схеме.

Шаг 1. Зададим: начальную точку X₀=(1, -1) внутри области X; начальное значение параметра r_s=0,1; число C=4 для уменьшения параметра штрафа; малое число e=0,1 для остановки алгоритма. Положить s=0.

Шаг 2. Составим вспомогательную функцию

F(X; 0,1)= +0,05×(3x₁-2x₂-5)².

Шаг 3. Найдём точку X^*(0,1) безусловного минимума функции F(X, 0,1) по X с помощью метода градиетного спуска:

F(X^*(0,1), 0,1)= +0,05×(3x₁-2x₂-5)² ® min (4.3.3)

1. Зададим X₀=(1, -1), e₁=0,1, e₂=0,1, k₀=10, найдём градиент

ÑF(X; 0,1)=(4x₁+0,3×(3x₁-2x₂-5), 8x₂-0,2×(3x₁-2x₂-5)).

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

3.0. Вычислим ÑF(X₀; 0,1)=(4; -8).

4.0. Вычислим |ÑF(X₀; 0,1)| и проверим критерий окончания: |ÑF(X₀; 0,1)|= »8,9443>0,1. Переходим к шагу 5.

5.0. Проверим условие k>k₀: k=0<10=k₀. Переходим к шагу 6.

6.0. Зададим h₀=0,1.

7.0. Вычислим X₁=X₀-0,1×F(X₁; 0,1)=(1; -1)-0,1×(4; -8)=(0,6; -0,2).

8.0. Проверим выполнение условия F(X₁; 0,1)-F(X₀; 0,1)<0. Так как F(X₁; 0,1)=1,272, F(X₀; 0,1)=7, то условие выполняется. Переходим к шагу 9.

9.0. Проверим условия r(X₁, X₀)<0,1 и |F(X₁; 0,1)-F(X₀; 0,1)|<0,1. Второе условие не выполняется: |F(X₁; 0,1)-F(X₀; 0,1)|=4,728>0,1. Полагаем k=1 и переходим к шагу 3.

3.1. Вычислим ÑF(X₁; 0,1)=(1,56; -1,04).

4.1. Вычислим |ÑF(X₁; 0,1)| и проверим критерий окончания: |ÑF(X₁; 0,1)|= »1,8749>0,1. Переходим к шагу 5.

5.1. Проверим условие k>k₀: k=1<10=k₀. Переходим к шагу 6.

6.1. Зададим h₁=0,1.

7.1. Вычислим X₂:

X₂=X₁-0,1×ÑF(X₁; 0,1)=(0,6; -0,2)-0,1×(1,56; -1,04)=(0,444; -0,096).

8.1. Проверим выполнение условия F(X₂; 0,1)-F(X₁; 0,1)<0. Так как F(X₂; 0,1)=1,0353, F(X₁; 0,1)=1,272, то условие выполняется: F(X₂; 0,1)-F(X₁; 0,1)=1,0353-1,272=-0,2367. Переходим к шагу 9.

9.1. Проверим условия r(X₂, X₁)<0,1 и |F(X₂; 0,1)-F(X₁; 0,1)|<0,1. Второе условие не выполняется: |F(X₂; 0,1)-F(X₁; 0,1)|=0,2367>0,1. Полагаем k=2 и переходим к шагу 3.

3.2. Вычислим ÑF(X₂; 0,1)=(0,7332; -0,0728).

4.2. Вычислим |ÑF(X₂; 0,1)| и проверим критерий окончания: |ÑF(X₂; 0,1)|= =0,7368>0,1. Переходим к шагу 5.

5.2. Проверим условие k>k₀: k=2<10=k₀. Переходим к шагу 6.

6.2. Зададим h₂=0,1.

7.2. Вычислим X₃:

X₃=X₂-0,1×ÑF(X₂; 0,1)=(0,444; -0,096)-0,1×(0,7332; -0,0728)=(0,3707;-0,0887).

8.2. Проверим выполнение условия F(X₃; 0,1)-F(X₂; 0,1)<0. Так как F(X₃; 0,1)=0,9947, F(X₂; 0,1)=1,0353, то условие выполняется: F(X₃; 0,1)-F(X₂; 0,1)=-0,0406. Переходим к шагу 9.

9.2. Проверим условия r(X₃, X₂)<0,1 и |F(X₃; 0,1)-F(X₂; 0,1)|<0,1. Оба условия выполняются:

r(X₃, X₂)= =0,0737<0,1,

|F(X₃; 0,1)-F(X₂; 0,1)|=0,0406<0,1.

Это значит, X^*(0,1)=(0,3707; -0,0887) - решение задачи (4.3.3).

Вычислим P(X^*(0,1), 0,1)=0,05×(3×0,3707-2×(-0,0887)-5)²=0,6941.

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

а) если P(X^*(r_s), r_s)£e, то процесс поиска закончить:

X^*=X^*(r_s), f(X^*)=f(X^*(r_s));

б) если P(X^*(r_s), r_s)>e, то положить: r_s+1=Cr_s, X_s+1=X^*(r_s), s=s+1 и перейти к шагу 2.

Имеем P(X^*(0,1), 0,1)=0,6941>0,1. Поэтому полагаем r₁=C×r₀=4×0,1=0,4, X₀=X^*(0,1)=(0,3707; -0,0887), и перейти к шагу 2, то есть решаем задачу

F(X^*(0,4), 0,4)= +0,2×(3x₁-2x₂-5)² ® min (4.3.4)

Ниже приводим только результаты пунктов алгоритма без комментариев:

1. X₀=(0,3707; -0,0887), e₁=0,1, e₂=0,1, k₀=10,

ÑF(X; 0,4)=(4x₁+1,2×(3x₁-2x₂-5), 8x₂-0,8×(3x₁-2x₂-5)).

2. k=0.

3.0. ÑF(X₀; 0,4)=(-2,9698; 2,2588).

4.0. |ÑF(X₀; 0,4)|»3,7312>0,1.

5.0. k>k₀? k=0<10=k₀. ® 6.

6.0. h₀=0,1.

7.0. X₁=(0,6677; -0,3146).

8.0. F(X₁; 0,1)-F(X₀; 0,1)=-0,6511<0. ® 9.

9.0. |F(X₁; 0,1)-F(X₀; 0,1)|= 0,6511>0,1. k=1 и ® 3.

3.1. ÑF(X₁; 0,1)=(-0,1704; -0,6226).

4.1. |ÑF(X₁; 0,1)|»0,6456>0,1. ® 5.

5.1. k>k₀? k=1<10=k₀. ® 6.

6.1. h₁=0,1.

7.1. X₂=(0,6847; -0,2523).

8.1. F(X₂; 0,1)-F(X₁; 0,1)=-0,0245. ® 9.

9.1. r(X₂, X₁)=0,0646<0,1 и |F(X₂; 0,1)-F(X₁; 0,1)|=0,0245<0,1.

Значит, X^*(0,4)=(0,6847; -0,2523) - решение задачи (4.3.4).

Вычислим P(X^*(0,4), 0,4)=1,1212.

Шаг 4. Проверим условие окончания: P(X^*(0,4), 0,4)=1,1212>0,1. Поэтому полагаем r₂=C×r₁=4×0,4=1,6, X₀=X^*(0,4)=(0,6847; -0,2523), и переходим к шагу 2, то есть решаем задачу

F(X^*(1,6), 1,6)= +0,8×(3x₁-2x₂-5)² ® min (4.3.5)

Ниже в таблице приведены результаты вычислений. В таблице применяются следующие сокращённые обозначения: ÑF_k=ÑF(X_k; 1,6), F_k=F(X_k; 1,6), DF_k=F(X_k+1; 1,6)-F(X_k; 1,6), r_k+1=r(X_k+1, X_k).

Таким образом, X^*(1,6)=(1,087; -0,4195) - решение задачи (4.3.5). При этом P(X^*(1,6), 1,6)=0,9562>0,1. Полагаем r₃=C×r₂=4×1,6=6,4, X₀=X^*(1,6)= =(1,087; -0,4195), и переходим к шагу 2 - решаем задачу

F(X^*(6,4), 6,4)= +3,2×(3x₁-2x₂-5)² ® min. (4.3.6)

Решение получается за одну итерацию: X^*(6,4)=(1,0856; -0,3957). При этом P(X^*(6,4), 6,4)=0,648>0,1.

Шаг 4. Так как P(X^*(6,4), 6,4)=0,648>0,1, то полагаем r₄=C×r₃=4×6,4=25,4, X₀=X^*(6,4)=(1,0856; -0,3957), и переходим к шагу 2 - решаем задачу

F(X^*(6,4), 6,4)= +12,8×(3x₁-2x₂-5)² ® min (4.3.7)

На последних двух шагах получаем r(X_k+1, X_k)<0,1 и |f(X_k+1)-f(X_k)|<0,1, а в последнем шаге - P(X^*(25,4), 25,4)=0,0005<0,1. Процесс поиска закончен.

Ответ: точкой условного локального минимума является точка X^*=(1,2911; -0,5049), f(X^*)=4,5284 - условный локальный минимум.

Метод проекции градиента.

Метод применяется в задачах поиска условного экстремума с ограничениями типа равенство и неравенств. Мы ограничимся рассмотрением поиска экстремума с ограничениями типа равенства.

Требуется решить задачу

(4.4.1)

где функции f(X), j_i(X) - выпуклые дифференцируемые функции.

Поиск решения состоит в построении последовательности точек {X_k}, вычисляемых по правилу

X_k+1=X_k+dX_k (k=0, 1, …), (4.4.2)

где dX_k - вектор, вычисляемый для каждого значения k из условия проекции вектора -Ñf(X_k), k=0, 1, …, на аппроксимирующую плоскость, задаваемую уравнением

A_kdX_k =T_k, (4.4.3)

которая аппроксимирует в точке X_k (k=0, 1, …) поверхность П, задаваемую уравнениями j_i(X)=0 (i=1, …, m). Здесь A_k - матрица

A(X)= ,

вычисленная в точке X=X_k, T_k=-(j₁(X_k), …, j_m(X_k))^T.

Вектор dX_k определяется по формуле

dX_k=d₁X_k+d₂X_k (4.4.4)

где

d₁X_k=-h_k[E- (A_k ) A_k]Ñf(X_k)=-h_kDX_k (4.4.5)

- градиентная составляющая приращения, d₂X_k= (A_k ) T_k - компенсационная составляющая приращения.

Величина h_k шага может выбираться как из условия убывания функции f(X) при переходе из точки X_k в точку X_k-h_k[E- (A_k ) A_k]Ñf(X_k), так и из условия

y(h_k)=f(X_k-h_k[E- (A_k ) A_k]Ñf(X_k))® (4.4.6)

Задача (4.4.6) может решаться либо с использованием необходимых и достаточных условий минимума, либо с использованием численных методов.

Расчёт заканчивается в точке X_k, в которой |DX_k|£e, |d₂X_k|£e, где e - заданное число. В полученной точке обязательна проверка выполнения достаточных условий минимума функции в исходной задаче (4.4.1). Если будет выполнено точное равенство d₁X_k=-h_k[E- (A_k ) A_k]Ñf(X_k)= , то это означает, что выполнены точные необходимые условия экстремума. При этом вектор L_k множителей Лагранжа определяется по формуле

L_k=-(A_k ) A_kÑf(X_k) (4.4.7)

Если в задаче (4.4.1) ограничения линейны, то матрица A постоянна. При этом начальная точка X₀ попадает в ОДР за одну итерацию. В дальнейшем требуется вычисление только d₁X_k.

Таким образом, алгоритм решения задачи - следующий:

1. Задать X₀, e³0, k₀ - число итераций.

2. Найти A(X), Ñf(X), DX=-[E- (A ) A]Ñf(X), d₂X=A^T(AA^T) T(X) где T(X)=-(j₁(X_k), …, j_m(X_k))^T.

3. Положить k=0.

4. Проверить выполнение условия k³k₀:

а) если неравенство выполнено, то расчёт окончен. Вычислить L_k=-(A_k ) A_kÑf(X_k), проверить необходимое условие минимума, оценить результаты;

б) если неравенство не выполнено, то перейти к шагу 5.

5. Вычислить матрицу A_k=A(X_k).

6. Вычислить d₂X_k.

7. Вычислить |d₂X_k|.

8. Вычислить DX_k.

9. Вычислить |DX_k|.

10. Проверить выполнение условий |DX_k|£e и |d₂X_k|£e:

а) если условия выполняются, то расчёт окончен. Вычислить L_k и проверить достаточные условия минимума;

б) если |DX_k|>e, |d₂X_k|£e, то положить d₂X_k=0 и перейти к шагу 11;

в) если |DX_k|£e и |d₂X_k|>e, то положить DX_k=0 и перейти к шагу 13;

г) если |DX_k|>e, |d₂X_k|>e, то перейти к шагу 11.

11. Получить выражение для точки X_k+ DX_k.

12. Определить из условия f(X_k+h_kDX_k)® .

13. Вычислить X_k+1=X_k+ DX_k+d₂X_k. Положить k=k+1 и перейти к шагу 4.

Если ограничения в задаче линейны, то при k³1 на шаге 4 переходим к шагу 8. При этом на шаге 10 полагаем |d₂X_k|=0.

Пример II. Найти условный экстремум функции:

f(X)= ® min

3x₁-2x₂-5=0.

Решение. 1. Задаём X₀=(1, -1) e=0,1, k₀=10 - число итераций.

2. Найдём A(X)= =(3; -2), Ñf(X)=(4x₁, 8x₂)^Т,

DX=-[E- (A ) A]Ñf(X)=- =

=- =- =

=- =- = ,

то есть DX» ,

T(X)=-j₁(X_k)=-3x₁+2x₂+5,

d₂X=A^T(AA^T) T(X)= (-3x₁+2x₂+5)=

= (-3x₁+2x₂+5)= = ,

то есть d₂X» .

3. Полагаем k=0.

4.0. Проверим выполнение условия k³k₀: k=0<10=k₀ - неравенство не выполнено. Поэтому идём к пункту 5.

5.0. Вычисляем матрицу A₀=A(X₀)=(3; -2).

6.0. Вычисляем d₂X₀= = .

7.0. Вычисляем |d₂X₀|= =0.

8.0. Вычисляем DX₀= » .

9.0. Вычисляем |DX₀|= »0,832.

10.0. Проверяем выполнение условий |DX₀|£0,1 и |d₂X₀|£0,1. Имеем |DX₀|>0,1 и |d₂X₀|£0,1. Поэтому полагаем d₂X₀=0 и переходим к шагу 11.

11.0. Получим выражение для точки X₀+h₀DX₀:

X₀+h₀DX₀=(1; -1)+h₀(2,462; 3,692)=(1+2,462h₀; -1+3,692h₀).

12.0. Определяем h₀ из условия f(X₀+h₀DX₀)® . Имеем

f(X₀+h₀DX₀)=2×(1+2,462h₀)²+4×(-1+3,692h₀)²=

=2×(1+4,924h₀+6,061 )+4×(1-7,384h₀+13,631 )=

=66,646 -19,688h₀+6.

Так как f(X₀+h₀DX₀) - квадратный трёхчлен относительно h₀ с положительным коэффициентом при , то минимум f(X₀+h₀DX₀) достигается при h₀, удовлетворяющем уравнению (X₀+h₀DX₀)=0. Имеем

(X₀+h₀DX₀)=133,292h₀-19,688=0 Û h₀»0,15.

13.0. Вычисляем X₁:

X₁=X₀+h₀DX₀+d₂X₀=X₀+h₀DX₀=(1+2,462×0,15; -1+3,692×0,15)=(1,3693; -0,4462).

Положим k=1 и перейдём к шагу 4.

4.1. Проверим выполнение условия k³k₀: k=1<10=k₀ - неравенство не выполнено. Поэтому идём к пункту 5.

5.1. Вычисляем матрицу A₁=A(X₁)=(3; -2).

6.1. Вычисляем d₂X₁= = .

7.1. Вычисляем |d₂X₁|= »0.

8.1. Вычисляем DX₁= » .

9.1. Вычисляем |DX₁|= »0,0677.

10.1. Проверяем выполнение условий |DX₁|£0,1 и |d₂X₁|£0,1. Имеем |DX₁|£0,1 и |d₂X₁|£0,1. Поэтому расчёт окончен. Вычисляем L₁ для проверки необходимых и достаточных условий экстремума в найденной точке X₁=(1,3693; -0,4462):

L₁=-(A₁ ) A₁Ñf(X₁)= =-1,8135.

Выпишем необходимые условия экстремума с учётом функции Лагранжа: L(X, L)= +l₁(3x₁-2x₂-5):

=4x₁+3l₁, =8x₂-2l₁,

Û (4.4.6)

Будем считать, что необходимые условия выполнены, если уравнения системы (4.4.6) выполняются с точностью до 0,1. Подставляем X₁=(1,3693; -0,4462) и l₁=-1,8135 в систему (4.4.6):

Следовательно, необходимые условия экстремума в точке X₁ выполнены. Проверим достаточные условия экстремума. Имеем

=4, =8, = =0, d²L=4d +8d >0,

то есть достаточное условие минимума выполняется. Таким образом,

Ответ: точкой условного локального минимума является точка X^*»(1,3693; -0,4462), f(X^*)»4,5447 - условный локальный минимум.

Приложения

Приложение 1. Варианты индивидуальных заданий

Задания 1 - 5решить с использованием необходимых и достаточных условий

Задание НП-1

Дана функция y=f(x) (таблица). Найти:

а) Безусловные экстремумы функции y=f(x).

б) Условные экстремумы функции y=f(x) на отрезке [a, b]:

Вар-т	Функция	[a, b]		Вариант	Функция	[a, b]
	y=ln(x2-2x+2)	[0; 3]			y=	[1; 3]
	y=3x/(x2+1)	[0; 5]			y=(x5-8)/x4	[-3; -1]
	y=(2x-1)/(x-1)2	[-1/2; 0]			y=(e2x+1)e-x	[-1; 2]
	y=(x+2)e1-x	[-2; 2]			y=xlnx	[1/e2; 1]
	y=ln(x2-2x+4)	[-1; 3/2]			y=x3ex+1	[-4; 0]
	y=x3/(x2-x+1)	[-1; 1]			y=x2-2x+2/(x-1)	[-1; 3]
	y=((x+1)/x)3	[1; 2]			y=(x+1)	[-4/5; 3]
	y=	[-2; 2]			y=	[-3; 3]
	y=4-	[0; 1]			y=(lnx)/x	[1; 4]
	y=(x3+4)/x2	[1; 2]			y=3x4-16x3+2	[-3; 1]
	y=xex	[-2; 0]			y=x5-5x4+5x3+1	[-1; 2]
	y=(x-2)ex	[-2; 1]			y=(3-x)e-x	[0; 5]
	y=(x-1)e-x	[0; 3]			y= +cosx	[0; p/2]
	y=x/(9-x2)	[-2; 2]			y=108x-x4	[-1; 4]
	y=(1+lnx)/x	[1/e; e]			y=x4/4-6x3	[14; 20]

Задание НП-2

Исследовать на безусловный экстремум функцию:

а) f(x, y)=ax²+2xy+by²-2x-3y:

б) f(x, y)=ax³+ax²y+bx+ y³+cy:

в) f(X)=a +b +c -2x₁x₂-x₁+3x₂:

г) f(X)=a +b +c +3x₁x₃-4x₁+2x₃:

д) f(X)=a +b +c -x₂x₃+2x₂-3x₃: