§4. Элементы численных методов задачи условной оптимизации выпуклого программирования

4.1. Общие замечания к численным методам условной оптимизации. Численные методы условной оптимизации делятся на две группы:

1. Методы, основанные на сведении задачи условной оптимизации к задаче безусловной оптимизации, и применении численных методов безусловной оптимизации.

2. Методы непосредственного решения задачи условной оптимизации, основанные на движении из одной допустимой точки, где выполнены все ограничения, к другой допустимой точке с лучшим значением целевой функции. Это  методы возможных направлений.

Основная идея методов первой группы состоит в том, чтобы заменить исходную задачу условной оптимизации задачей безусловной оптимизации, например, методом штрафных функций, и применить к ней численные методы безусловной оптимизации.

Методы второй группы аналогичны итерационным методам безусловной оптимизации.

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

4.2. Постановка задачи выпуклого программирования.

Задача условной оптимизации называется задачей выпуклого программирования, если целевая функция f(X) является либо выпуклой, либо вогнутой, а функции _i(X) из системы ограничений  выпуклые.

Таким образом, данный класс задач относится к задачам условной оптимизации. Мы ограничимся рассмотрением некоторых численных методов именно этого класса задач. При этом для определённости рассматриваем задачу условной минимизации:

f(X)  min

(4.2.1)

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

При этом методе задача (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 для уменьшения параметра штрафа; малое число 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), то процесс поиска закончить:

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

б) если P(X^*(r_s), r_s)<, то положить: 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 для уменьшения параметра штрафа; малое число =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), ₁=0,1, ₂=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. Проверим условия (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. Проверим условия (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. Проверим условия (X₃, X₂)<0,1 и |F(X₃; 0,1)F(X₂; 0,1)|<0,1. Оба условия выполняются:

(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), то процесс поиска закончить:

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

б) если P(X^*(r_s), r_s)>, то положить: 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), ₁=0,1, ₂=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. (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), F_k=F(X_k+1; 1,6)F(X_k; 1,6), _k+1=(X_k+1, X_k).

k	Xk	Fk	|Fk|	Xk+1	Fk+1	Fk	k+1	Pk+1
0	(0,6847; 0,2523)	(8,9794; 5,9738)	10,6864	(1,5826; 0,8317)	9,3696	9,3696>0	h0=0,05
				(1,1337; 0,542)	3,9576	2,0026	0,5343
1	(1,1337; 0,542)	(2,0633; 2,6883)	3,3888	(1,0305; 0,4076)	3,7446	0,2131	0,1694	1,1212
2	(1,0305; 0,4076)	(1,1258; 0,2378)	1,1507	(1,087; 0,4195)	3,7151	0,0296	0,0575	0,9562

Таким образом, 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)

k	Xk	Fk	|Fk|	Xk+1		Fk+1		Fk		k+1		Pk+1
0	(1,0856; 0,3957)	(68,7558; 45,5666)	82,4844	(4,5234; 2,674)		2549,104		2534, 525>0		h0=0,025
					(2,8045; 1,5349)		536,1644		548, 5852>0		h0=0,01
					(1,7732; 0,8514)		61,5308		46,9516>0		h0=0,005
					(1,7294; 0,6235)		9,3079		5,2713		0,4124
1	(1,4294; 0,6235)	(42,821; 32,3902)	56,9327	(1,1953; 0,4616)		6,7956		2,5122		0,2847
2	(1,1953; 0,4616)	(32,9199; 21,4413)	39,2868	(1,3599; 0,5688)		5,5973		1,1971		0,1964
3	(1,3599; 0,5688)	(22,1282; 15,6762)	27,1183	(1,2493; 0,4904)		5,0261		0,5711		0,1356
4	(1,2493; 0,4904)	(15,8386; 9,9674)	18,7139	(1,3285; 0,5402)		4,7529		0,2727		0,0936
5	(1,3285; 0,5402)	(10,3751; 7,6957)	12,9177	(1,2766; 0,5017)		4,6221		0,1306		0,0646
6	(1,2799; 0,5017)	(7,7038; 4,5266)	8,9353	(1,3151; 0,5243)		4,5592		0,0631		0,0447		0,3561
7	(1,3151; 0,5243)	(4,7919; 3,8821)	6,1671	(1,2911; 0,5049)		4,5284		0,0307		0,0308		0,0005

На последних двух шагах получаем (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  условный локальный минимум.