jadan (1)

1.δk(x|X) < +∞ для всех x X0;

2.δk(x|X) = +∞ для всех x / X0;

Кроме того,наложим на {δk(x|X)} следующие требования:

3. limk→∞ |δk(x|X)| = 0 для всех x X0;

4. если {δk(x)} последовательность неотрицательных на X0 функций,то δk(x|X) > δk+1(x|X) для любого x X0.

Согласно этим условиям δk(¯x|X) = +∞ для всех x¯ ∂X,причем выполняется предельное равенство

lim δk(x|X) = +∞.

x→x,¯ x X0

Поэтому аппроксимация функции δ(x|X) последовательностью функций {δk(x|X)} осуществляется только с точностью до границы,так как

lim δk(x|X) = δ(x|X), x X \ X0.

k→∞

Определение17. Внутренним штрафом или барьером будем называть непрерывную функцию ψ(x) такую,что ψ(x) < +∞ тогда и только тогда,когда x X0

и limx→x,¯ x X0 ψ(x) = +∞, если x¯ ∂X.

Используя барьер,можно построить внутреннюю штрафную функцию(барьерную функцию) в виде

P (x, t) = f(x) + tψ(x),

где t > 0 коэффициент внутреннего штрафа . Обозначим теперь

X (t) = Arg min P (x, t).

x X0

Алгоритм метода внутренних штрафных функций(метода барьерных функ-

ций).Задаем монотонно убывающую последовательность коэффициентов tk → +0 и полагаем k = 1.

Шаг 1.

Решаем вспомогательную задачу

min P (x, tk)	(126)
x X0

и находим точку xk X (tk).

Шаг 2.Полагаем k := k + 1 и идем на шаг 1.

В результате работы алгоритма получаем последовательность точек {xk} X0. Если она ограничена,то имеет предельные точки x X.

66

Далее будем предполагать,что X компактное множество . Тогда точкиxk X (tk) существуют и xk X0.Считаем также для простоты,что ψ(x) ≥ 0 для всех

x X0.

Теорема12. Любая предельная точка x последовательности {xk} есть решение задачи(109)и

lim P (xk, tk) = f(x ) = f .

k→∞

Доказательство. Не ограничивая общности,считаем,что последовательность {xk} является сходящейся.Тогда xk → x . Так как X замкнутое множество,то x

X.

Если x / X , то из предположения clX0 = X следует,что найдется y X0 такое, что f(y) < f(x ) и,стало быть,

f(y) < lim f(xk).
k→∞
Поэтому можно указать такое δ > 0, что
f(y) < f(xk) − δ	(127)
для k достаточно больших.Поскольку ψ(x) ≥ 0,то из(16)вытекает
f(y) < f(xk) − ε + tkψ(xk) = P (xk, tk) − δ
для этих же k.
Но для y X0 в силу того , что
lim tkψ(y) = 0,
k→∞
имеет место равенство	(128)
lim P (y, tk) = f(y).
k→∞
Отсюда получаем,что для достаточно больших k выполняются неравенства
P (y, tk) < P (xk, tk),	(129)

что противоречит определению точки xk X (tk), поскольку y X0. Таким образом ,

x X .

Далее,опять же в силу определения точек xk X (tk)

P (xk+1, tk+1) = f(xk+1) + tk+1ψ(xk+1) ≤

≤f(xk) + tk+1ψ(xk) ≤

≤f(xk) + tkψ(xk) = P (xk, tk),

т.е.последовательность {P (xk, tk)} является монотонно невозрастающей.Но она ограничена снизу,поэтому существует предел

lim P (xk, tk) = P ≥ f .

k→∞

67

Покажем,что строгое неравенство P > f невозможно и на самом деле имеет место равенство P = f .Действительно,иначе нашлись бы такие ε > 0 и δ > 0, что

y ∆ε(X ) ∩ X0 и

P (xk, tk) > f(y) + δ

для k достаточно больших.Но согласно(128)

δ

P (y, tk) = f(y) + tkψ(y) ≤ f(y) + 2,

если k достаточно большое.Отсюда и из(129)

δ

P (xk, tk) > P (y, tk) + 2

для этих k, что невозможно в силу определения точек xk.

Встает вопрос,как строить внутренние штрафы ψ(x)? Будем поступать аналогич - но,тому,как это делалось в методе внешних штрафных функций,используя аппарат свертывающих функций.

Пусть Rm−− обозначает внутренность ортанта Rm− .Пусть,кроме того, Rø обозначает расширенную прямую,т.е.прямую R, пополненную элементами ±∞.

Определение18. Функция B(g) : Rm → Rø называется внутренней свертываю-

щей функцией,если она непрерывна на Rm и B(g) < +∞ при g Rm−− и B(g) = +∞ при g / Rm−−.

В качестве примера внутренних свертывающих функций приведем следующую функцию

1	g− pp, g R−−m ,	(130)
B(g) = −p

где −∞ < p < 0 и g− отрицательная срезка вектора g Rm, т . еgi. = min[gi, 0]

−

для всех 1 ≤ i ≤ m.Когда g / Rm−−, полагаем :B(g) = +∞. Разумеется функция g p при p < 0 уже нормой не является,однако для однообразия обозначений знак нормы здесь сохранен.

Если воспользоваться функцией g 0, определенной как

	= √			m	|gi|	1/m
g 0						, g Rm,	(131)
		m		=1
				i

то приходим к внутренней свертывающей функции,дополняющей семейство функции(130)при значении параметра p = 0:

B(g) = −ln ( g− 0) − 12, g Rm−−.

Здесь опять же считается,что B(g) = +∞ при g / Rm−−.

68

Использую внутренние свертывающие функции,строим внутренние штрафные функции в виде

P (x, t) = f(x) + tB(g(x)).

В частном случае,беря внутреннюю свертывающую функцию(130)при значении параметра p = −1, приходим к внутренней штрафной функции

m	−
i		1		, x X0,
P (x, t) = f(x) + t		g(x)
=1

которая носит название обратной барьерной функции.

Аналогичным образом,используя внутреннюю свертывающую функцию(131),то получаем другую внутреннюю штрафную функцию

	t	m				t	1
		i								(132)
P (x, t) = f(x) −	m	=1	ln −gi(x)		−	2	ln m −	2	, x X0.

Если опустить константы,которые не влияют на решение вспомогательных задач мининимизации(126),то функция(132)перепишется как

m
i
P (x, t) = f(x) − t	ln −gi(x) , x X0.
=1
Данную функцию принято называть логарифмической барьерной функцией.
Получим оценки оптимального значения		вспомогательной функции M(x, y)

в задаче минимизации (126) в предположении , что в задаче нелинейного программи - рования(109)существует седловая точка [x , u ] функции Лагранжа.Вновь применяя неравенство Юнга-Фенхеля,как и в(122)приходим к оценке

min P (x, t)		≥	f	−			(B mt)(u			) = q(t).
x X0								R−
Пусть функция B(g) имеет вид(130),где								−∞ < p < 0. Тогда имеем
	t		u			p			t1−p		p
q(t) = f +					p			= f +			u p ,
	p		t						p

(133)

(134)

где p−1 + p−1 = 1. Так как p < 0, то 0 < p < 1.Поэтому,в силу(134),нижняя оценка превышает f и стремится к f при p → 0. В частном случае при p = −1 для обратной барьерной функции P (x, t) получаем,что

m
q(t) = f + 2√t ui .	(135)

i=1

В случае , когдаp = 0, для общей логарифмической барьерной функции (132)

69

имеем соответственно

				m
x X0				i			−		(136)
				=1
min q(t) = f	+ t	(ln m + 1) /2 +			ln ui	/m		ln t

и,следовательно,нижняя оценка q(t) опять стремится к f при t → +0. Оценка (136) в отличие от (135) справедлива только если u > 0m, т . е . если в решении задачи (109)

точке x все ограничения активны.

Восновном методы внутренних штрафных функций применяются в тех случаях, когда целевая функция f(x) не определена за пределами допустимого множества X. В последнее время идеи методов внутренних штрафных функций нашли широкое применение в так называемых методах внутренних точек,разработанных для решения задач линейного программирования,а также для решения более общих задач выпуклой минимизации.

1.6.2.Метод параметризации целевой функции

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

f = x X	X = {x R	n	: g(x) ≤ 0n} .	(137)
min f(x),

Считаем,что задача имеет решение и обозначим через X множество ее решений. Пусть η оценка снизу оптимального значения целевой функции f .Если η < f ,

то система неравенств

f(x) − η ≤ 0, g(x) ≤ 0m

не имеет решения.Поэтому,беря произвольный внешний штраф ψ(x), например , ψ(x) = B(g(x)), где B(g) внешняя свертывающая функция,а также квадратичный внешний штраф для первого неравенства (f(x) −η)2+, приходим к тому , что функция

M1(x,η ) = (f(x) − η)+2 + B(g(x))

(138)

принимает для всех x Rn только положительный значения как,впрочем,и функция

M2(x,η ) = (f(x) − η)2+ + B+2 (g(x)) > 0.

Введем сначала в рассмотрение вспомогательную функцию
M(x,η ) = (f(x) − η)+2 + B+2 (g(x)),	(139)

где x Rn и η R.Для данной вспомогательной функции поставим задачу без-

70

условной минимизации

(140)

φ(η) = min M(x,η ).

x Rn

Предполагаем,что задача(140)имеет решение для всех

η R.

n

, если η < f .

Из сказанного выше следует,что M(x,η ) > 0 для любого x R

φ(η) > 0

η

η

≥

f

получаем φ(η) = 0.

Поэтому

для всех таких

.С другой стороны,беря

,

n

.Но,взяв точку

Действительно,функция M(x,η ) ≥ 0 неотрицательна для всех x R

x X X, имеем

(f(x ) − η)2+ = 0, B+(g(x )) = 0, M(x , η ) = 0.

На основании приведенных рассуждений можно поставить задачу поиска наименьшего корня уравнения

φ(η) = min M(x,η ) = 0.

x Rn

Минимальный корень очевидно равен f .Любая точка x Rn, которая решает задачу(16)при η = f , такова , чтоx X .

Встает вопрос,как искать этот минимальный корень?Приведем сначала вариант метода,который основан по существу на использовании метода простой итерации для решения уравнения φ(η) = 0. Обозначим через X (η) множество решений задачи (140)при фиксированном значении оценки η, т . е . множество

X	(η) = Arg min M(x,η ).
	x Rn	η R, то
Так как мы предположили,что задача(140)имеет решение при всех
множество X (η) всегда не пусто.

Алгоритм метода параметризации целевой функции. Задаемся начальной оцен -

кой η0 ≤ f и полагаем k = 1.

Шаг 1.Находим точку xk X (ηk).

Шаг 2.Если M(xk, ηk) = 0,то останавливаемся.В противном случае вычисляем

ηk+1 = ηk + M(xk, ηk).

(141)

Шаг 3.Полагаем k := k + 1 и идем на шаг 1.

В общем случае получаем бесконечную последовательность точек {xk} и беско - нечную монотонно возрастающую последовательность оценок {ηk}.Имеет место следующий результат.

Лемма4. Пусть ηk ≤ f . Тогда ηk+1 ≤ f .

Доказательство. Возьмем произвольную точку x X . Так как xk X (ηk) и

71

B(g(x )) = 0, то

M(xk, ηk) ≤ M(x , ηk) = (f(x ) − ηk)2+ = f(x ) − ηk = f − ηk.

Поэтому

ηk+1 = ηk + M(xk, ηk) ≤ f .

Таким образом,действительно получаем монотонно возрастающую последовательность оценок ηk,которая ограничена сверху.Следовательно,существует предел

limk→∞ ηk = η ≤ f .

Теорема13. Пусть последовательность {xk}, порождаемая алгоритмом ме - тода параметризации целевой функции,принадлежит компактному множеству W. Тогда любая ее предельная точка есть решение задачи . При этом

lim f(xk) = lim ηk = f .		(142)
k→∞	k→∞

Доказательство. Имеем на основании утверждения леммы4

klim (ηk+1	− ηk) = klim M(xk, ηk) = 0.
→∞	→∞

Поэтому существует предел

lim B(g(xk)) = 0.

k→∞

Возьмем теперь произвольную сходящуюся к точке x последовательность {xks }. В силу непрерывности получаем B(g(x )) = 0, следовательно ,x X.Кроме того,

M(x , η ) = (f(x ) − η )+ = 0.

Так как x X, имеет место неравенство f(x ) ≥ f .Но строгое неравенство f(x ) >

f не может иметь места,поскольку иначе с учетом того,что	η ≤ f ,получили бы:
M(x , η ) > 0.	(143)

Поэтому обязательно f(x ) = f . Отсюда заключаем , чтоx X .

Из вышесказанного следует также,что выполняются предельные равенства(142). Действительно,случай,когда η < f , невозможен , так как из него опять следует неравенство(143).

Способ пересчета оценок(141)допускает наглядную геометрическую интерпре-

тацию.Обозначим через G(f, B) функцию

G(f, B) = f2	+ B2 .
+	+

72

Тогда вспомогательная функция M(x,η ) может быть записана как

M(x,η ) = G (f(x) − η, B(g(x))) .

Введем также в рассмотрение множество

W = [f, B] R2 : f = f(x), B = B(g(x)), x Rn .

Множество W есть образ задачи(137)в пространстве двух переменных,а именно,значения целевой функции и внешнего штрафа,соответствующих каждой точке пространства Rn.Наряду с множеством W рассмотрим также множество

W+ = W + R2+.

Если задача(137)является задачей выпуклого программирования,а B(g) неубывающей выпуклой функцией,то множество W+ оказывается выпуклым.На рис. ***

показаны множество W (вместе с W+),а также и линии уровня функции G(f −ηk, B). Решение вспомогательной задачи минимизации есть не что иное,как нахождение такой линии уровня функции G(f − ηk, B), которая соответствовала бы минимальному значению этой функции и при этом касалась бы множества W.Последующее значение ηk+1 получается путем пересечения данной линии уровня с вертикальной осью.

Предположим,что в задаче(137)существует седловая точка функции Лагранжа

L(x, u) = f(x) + g(x), u , u Rm+ ,

т.е.выполняются неравенства
L(x , u) ≤ L(x , u ) ≤ L(x, u ) x Rn,	u R+m.	(144)
Тогда точка x является решением задачи(137)и,поскольку	f = L(x , u ), из право -

го неравенства(144),применяя дважды неравенства Минковского-Малера,получаем для всех x Rn и любого η ≤ f :

f − η ≤ f(x) − η + g(x), u 0≤
≤ f(x) − η + B(g(x))B (u ) =							≤	0
	B(g(x))			B0(u 0)
=	f(x) − η	,		1
≤ G (f(x) − η, B(g(x))) G (w ) = M(x,η )G (w ),
где w = [1, B0(u )]T .
Поэтому					f − η
	M(x,η )					.
			≥ G0(w )

Так как правая часть не зависит от x, то отсюда , а также из неравенстваφ(η) ≤ M(x , η) = f η, где x X , приходим к двусторонней оценке

f	−	η	≥	φ(η)	f − η	.	(145)
					≥ G0(w )

73

Если в качестве M(x,η ) берется функия

					m
M(x,η ) =			η)+2	+	(gi(x))+2
	(f(x)	−
					i=1

то B(g) = g+ 2, B0(u ) = u 2 и оценка (145) принимает вид :

f	η M(x,η )	→				f − η				.
	→					−			(ui )2
− ≥		≥				1 +	m
Отсюда видно,что M(xk, ηk)	0 при ηk						i=1
				f		0.
Возможен также другой способ пересчета оценок ηk.Согласно нему
	ηk+1 = ηk +		(M(xk, ηk))2					.	(146)
			f(xk) − ηk

Данный способ соответствует использованию метода Ньютона для решения уравнения φ(η) = 0.Он применяется,когда(137)является задачей выпуклого программирования,т.е.функция f(x) и все функции gi(x), 1 ≤ i ≤ m,выпуклы.Если снова обратиться к рис. **,то точка ηk+1 из(146)получается путем пересечения касательной к соответствующей линии уровня функции G(f − ηk, B) с вертикальной осью . Разумеется,она лежит выше,чем та оценка ηk+1, которая получается по по способу (141),но опять же ниже,чем точка f .

Метод может также применяться и для решения задач нелинейного программирования,содержащих ограничения типа равенства.В этом случае,аналогично тому,как это делается в методе внешней штрафной функции,добавляется штраф

за нарушение ограничений-равенств.Например,для задачи(125)функция									M(x,η )
преобразуется следующим образом
	(f(x)					m	l
M(x,η ) =			−	η)+2	+	(gi(x))2 +	(hj(x))+2 .
						i=1	j=1

Заметим также,что при численном решении вспомогательных задач(139)целесообразно минимизировать не саму функцию M(x,η k),а ее квадрат,что обычно и делают.

Обратимся в заключение к вспомогательной функции M1(x,η ) вида(138).Данная функция при определенных предположениях обладает свойством быть точной, т . е . существует целый интервал значений оценки η, для любого значения η из которого множество решений вспомогательной задачи безусловной минимизации

x Rn	−	+
min (f(x)		η)2	+ B(g(x))
совпадает с множеством решением X	исходной задачи(137).По прежнему через

74

X (η) будем обозначать множество решений задачи(137).

Теорема14. Пусть в задаче (137) существует седловая точка [x , u ] функции Лагранжа на множестве Rn × Rm+ . Пусть , кроме того , внешняя свертывающая

функция B(g) такова,что 0 < B0(u ) < +∞. Тогда X (η) = X для любого η < η ≤ f , где η = f − (2B0(u ))−1.

Доказательство. Покажем,что для всех x Rn и любого η (η , f ] имеет место неравенство

(f(x) − η)+2 + B(g(x)) ≥ (f − η)2.

(147)

Оно очевидно,если f(x) ≥ f .Убедимся в его справедливости для остальных x, когда

f(x) < f .

Из наличия у функции Лагранжа седловой точки и из неравенства МинковскогоМалера следует,что

f ≤ f(x) + g(x), u ≤ f(x) + B(g(x))B0(u ),
откуда получаем
B(g(x)) ≥ (f − f(x))/B0(u ).
Учтем теперь,что (B0(u ))−1 = 2(f − η ). Тогда для тех x Rn,для которых
f(x) ≤ η, имеем
(f(x) − η)+2 + B(g(x)) = B(g(x)) ≥ (f − f(x))/B0(u ) =	2	≥ (f −	2	.
= 2(f − f(x))(f − η ) ≥ 2(f − η)			η)
Таким образом,неравенство(147)оказывается справедливым и для данных				x.

Осталось рассмотреть последний случай,когда η < f(x) < f . Оценивая последо - вательно разность ∆ = (f(x) −η)2+ + B(g(x)) −(f −η)2 между левой и правой частью (147),получаем

∆

≥

(f(x)

η)2

(f

−

η)2 + (f

−

f(x))/B0

(u

) =

−2

2−

0

(u ) = 0

=

(f(x))

− f + 2η(f − f(x)) + (f − f(x))/B

(u

) =

(148)

= (f(x)

−

f

)(f(x) + f

) + 2η(f

f(x)) + (f

−

f(x))/B

− 0

(u )].

= (f − f(x))[2η − f(x) − f + 1/B

Но η > η = f − 1/(2B0(u )).Поэтому

2η − f(x) − f + 1/B0(u ) > f − f(x) > 0.

Отсюда и из(148)делаем вывод,что неравенство(147)имеет место,когда

η

<

< f(x) < f .

x X ,то неравенство(147)переходит в равенство.Это

Если подставить в(147)

означает,что

X X(η)

для всех η Y . Более того ,

проводя рассуждения ,

ана -

логичные тем,которые делались при доказательстве теоремы10,можно убедиться, что на самом деле X(η) = X .

75