jadan (1)

Приведем пример вспомогательной функции M1(x,η ),для которой выполнены условия теоремы14.Возьмем в качестве B(g) функцию g+ p, в которой 1 ≤ p ≤ +∞. Тогда приходим к следующей вспомогательной функции:

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

Для нее η = f − 1/(2 u p ).Поэтому наибольший диапазон допустимых значений η будет в том случае,когда p = 1. Тогда p принимает предельное значение p = ∞ и норма u ∞ является чебышевской,т.е.

u ∞ = max |ui |.

1≤i≤m

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

1.6.3.Методы модифицированных функций Лагранжа

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

****

Рассмотрим сначала задачу нелинейного программирования,содержащую только ограничения-равенства

x X	X = x R	n	:	g	(x) = 0, 1 ≤ i ≤ m .	(149)
min f(x),

Будем предполагать,что как целевая функция f(x), так и функции - ограничения gi(x), 1 ≤ i ≤ m,являются по крайней мере непрерывно дифференцируемыми.

Составим для задачи(149)функцию Лагранжа

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

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

	m
		t			2
M(x, u, t) = f(x) +	i=1 uigi(x) +		gi(x)		,	(150)
		2

где t > 0 -некоторый параметр.

Функцию(150)принято называть модифицированной функцией Лагранжа для за-

дачи(149).Она обладает многими свойствами,присущими обычной функции Лагран-

жа L(x, u),а именно,если вычислить производную	M(x, u, t) по x, то получаем
Mx(x, u, t) = fx(x) + gT (x)u + tgT (x)g(x).
x	x

76

Отсюда видно,что

Mx(x, u, t) = Lx(x, u),

когда x X и u Rm.Кроме того,

Mu(x, u) = Lu(x, u) = g(x)

для тех же u и произвольных x Rn.Поэтому вместо того,чтобы искать стационарные точки функции Лагранжа L(x, u), т . е . точки[x , u ],в которых

Lx(x , u ) = 0n, Lu(x , u ) = g(x ) = 0,

можно было бы искать стационарные точки модифицированной функции Лагранжа

Mx(x , u , t) = 0n, Mu(x , u ) = g(x ) = 0m.

(151)

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

y, Lxx(x , u )y > 0 y K(x ), y = 0n,

где K(x ) = {y Rn : gx(x )y = 0m}, то точка x не является точкой локального минимума функции L(x, u ) на всем пространстве Rn,она доставляет локальный минимум функции L(x, u ) по x лишь на некотором подпространстве.Это следствие того,что матрица Lxx(x , u ) не обязательно должна быть положительно полуопределенной.

В отличие от классической функции L(x, u) модифицированная функция Лагранжа M(x, u, t) в этой же самой точке [x , u ] при достаточно больших значениях параметра t уже имеет локальный минимум по x.Действительно,если функции f(x) и g(x),определяющие задачу(149),дважды непрерывно дифференцируемы,то матрица вторых производных функции Mxx(x, u, t) по x в стационарной точке [x , u ] имеет вид

Mxx(x , u , t) = L(x , u ) + tgxT (x )gx(x ).

(152)

Здесь при подсчете производной учтено,что g(x ) = 0m в стационарной точке [x , u ]. Воспользуемся далее следующим известным результатом,называемым иногда лем-

мой Финслера.

Лемма5. Пусть A и B симметричные квадратные матрицы порядка n, причем матрица B положительно полуопределенная.Пусть,кроме того,

y, Ay > 0,

когда y Rn, y = 0n. Тогда можно указать t¯ > 0 такое,что

y, Ay + t y, By > 0

77

для любого t > tø и всех y Rn.

На основании леммы5и представления(152)заключаем,что матрица Mxx x , u , t) положительно определена при t достаточно больших.Так как M(x , u , t) = 0n, то функция M(x, u , t) имеет локальный минимум по x в точке x при этих же t.В силу непрерывности это свойство сохраняется и в некоторой окрестности ∆(u ) точки u .Действительно,по теореме о неявной функции в этой окрестности существует решение уравнения Mx(x, u, t) = 0n,т.е.такая непрерывная функция x(u), что Mx(x(u)), u, t) ≡ 0n и x(u ) = x .Из положительной определенности матрицы Mxx(x, u, t) вблизи точки [x , u ] следует,что

M(x(u), u, t) = min M(x, u, t),

x ∆(x )

где ∆(x ) Rn некоторая окрестность точки x .Чтобы найти точку [x , u ] теперь следует просто решить уравнение

Mu(x(u), u, t) = g(x(u)) = 0m.

(153)

Указанное свойство позволяет построить алгоритм решения задачи(149),основанный на отыскании соответствующей точки Каруша-Куна-Таккера [x , u ] путем решения уравнения(153)методом простой итерации.Пусть задано начальное

u0 Rm и выбрано и зафиксировано достаточно большое значение параметра t, ко - торое гарантировало бы существование решений соответствующих задач безусловной минимизации функции M(x, u, t) по первой переменной x.Итерации в методе проводятся по следующей рекуррентной схеме

xk	=	argminx RnM(x, uk, t),	(154)
uk+1	=	uk + tg(xk),

причем для отыскания точки xk в(154)могут применяться различные известные методы безусловной минимизации.

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

x X	X = x R	n	:	h (x) ≤ 0, 1 ≤ i ≤ l	,	(155)
min f(x),

где по-прежнему предполагается,что все функции,определяющие задачу по крайней мере непрерывно дифференцируемы.

Задача с ограничениями-неравенствами сводится к задаче с ограничениями-равенствами путем введения дополнительных переменных

hj(x) + (σj)2 = 0, j = 1, 2, . . . , l.

Тогда,применяя тот же принцип,что и при построении функции(151),приходим к

78

соответствующей модифицированной функции Лагранжа

l
			t			2
M(x,σ, v, t ) = f(x) + j=1 vj	hj (x) + (σj )2	+		hj (x) + (σj )2		,	(156)
			2

где v Rl.

Теперь при построении аналога метода(154)минимизацию придется проводить как по основной переменной x, так и по дополнительной переменной σ = [σ1, . . . , σl]. Но минимум функции M(x,σ, u, t ) по σ при фиксированных x и v легко вычисляется. В самом деле , дифференцируя функцию (156) поσj и приравнивая производную к

нулю,получаем

(157)

σj

vj + t

hj (x) + (σj )2

= 0.

является корень

σj = 0

, а также корни квадратичного

Решением уравнения(157)

уравнения

vj

(σj )2 + hj (x) +

(158)

= 0.

t

Данное уравнение имеет действительный положительный корень,если

vj

hj (x) +

< 0.

При этом

t

σj =

− hj (x) +

vj

.

t

Таким образом,

hi(x) + (σj )2 =

hj (x),

hj (x) + vj /t ≥ 0,

1

≤

j

≤

l,

−vj /t,

hj (x) + vj /t < 0,

что можно записать также,как

hj (x), −

,

hi(x) + (σj )2 = max

vj

1 ≤ j ≤ l.

(159)

t

Подставляя(159)в(156),после несложных преобразований приходим к модифицированной функции Лагранжа для задачи с неравенствами(155),уже избавленную от дополнительных переменных σ,

		l						− (vj )2 ,
M(x, v, t) = f(x) +	1				vj + thj (x)		2		(160)
							+
	2t j=1

где,как обычно,знак + внизу означает положительную срезку.

Обратимся теперь к общей задачи нелинейного программирования,в которой

79

присутствуют как ограничения-равенства,так и ограничения-неравенства,

x X

{

R

n : g(x) = 0

m

≤

l}

(161)

min, X =

x

, h(x)

0

.

Тогда объединяя функции(150)и(160),приходим к модифицированной функции

Лагранжа для этой задачи:

m

t

2

1

l

2

M(x, u, v, t) = f(x)+ i=1 uigi(x) +

2

gi(x)

+

2t j=1

vj + thj(x)

+

− (vj)2

. (162)

Пусть функции f(x), g(x) и h(x), определяющие задачу (161), дважды непре - рывно дифференцируемы и пусть x есть решение этой задачи.В том случае,когда

в соответствующей точке Каруша-Куна-Таккера [x , u , v ] выполнены достаточные условия второго порядка для(161),матрица вторых производных Mxx(x, u, v, t) модифицированной функции Лагранжа(162)в данной точке,также оказывается положительно определенной для t достаточно больших(превышающих некоторое пороговое

значение t).Поэтому,как и в задаче с равенствами,вблизи точки	[u , v ] существует
¯
непрерывное решение x(u, v) задачи минимизации
x(u, v) = arg min M(x, u, v, t),	(163)
x Rn

причем такое,что x(u , v ) = x . Таким образом , чтобы найти точкуx , достаточно решить систему уравнений,

Mu(x(u, v), u, v, t) = g(x(u, v)) = 0m,					(164)
Mv(x(u, v), u, v, t) =	1			(v + th(x(u, v)))+ − v = 0l.	(165)
		t

Опишем алгоритм решения задачи задачи нелинейного программирования(161), основанный на использовании метода простой итерации для решения системы(164), (164).

Выбираем достаточно большое t, чтобы существовали решения задач безусловной

минимизации(166).Выбираем также начальные u0 Rm и v0 Rl.Полагаем		k = 0.
Шаг1).	Решаем задачу безусловной минимизации
	xk = arg min M(x, uk, vk, t).	(166)
	x Rn
Шаг2).	Полагаем
	uk+1 = uk + tg(xk), vk+1 = (vk + th(xk))+ .	(167)

Шаг2). Увеличиваем k := k + 1 и идем на шаг 1.

Имеет место следующий результат,касающийся сходимости метода(166), (167), который приведем без доказательства.

80

Теорема15. Пусть функции f(x), g(x) и h(x) дважды непрерывно дифференцируемы и пусть точка x X является решением задачи(161).Предположим также,что x вместо с u Rm и v Rl+ образует точку Каруша-Куна-Таккера, в которой выполнены достаточные условия второго порядка теоремы ***. Тогда можно указать достаточно большое число t¯ > 0 такое,что для всех t > t¯ и всех достаточно близких к [u , v ] начальных точек [u0, v0] для последовательностей {uk} и {uk}, вырабатываемых итеративным процессом (167), имеют место предельные равенства

lim u		= u	,	lim v		= v	.
k→∞	k			k→∞	k

При этом последовательность {xk} также оказывается сходящейся и

lim xk = x .

k→∞

Сделаем несколько замечаний,касающихся метода модифицированных функций Лагранжа(166), (167).

1.Метод прост в реализации и не требует выпуклости функций f(x) и h(x), хотя сходимость здесь в случае общих невыпуклых задач лишь локальная.

2.Так как значение параметра t конечно,то овражность функции M(x, uk, vk, t) не увеличивается катастрофически с ростом числа итерации,как это происходит в методе внешних штрафных функций.Поэтому решение задач безусловной минимизации(166)в методе модифицированных функций Лагранжа оказывается более простой простой процедурой по сравнению с методом внешних штрафных функций.

3.Для ограничений-неравенств hj(x) ≤ 0,которые являются неактивными в ре-

шении,т.е, hj(x ) < 0 для достаточно больших k выполняется thj(xk) < 0. Согласно второй из формул пересчета это приводит к тому,что на некоторой

итерации соответствующий множитель vkj обнуляется и далее остается равным нулю.Фактически данное ограничение перестает влиять на вычислительный процесс.

4. Минимизацию модифицированной функции Лагранжа(162)по x можно проводить,отбрасывая слогаемые (−vj)2, 1 ≤ j ≤ l.На точки минимума данные слогаемые влияния не оказывают.

81

1.7.Задачи многокритериальной оптимизации

Предположим,что у нас имеется r > 1 критериев f1(x), f2(x), . . . , fr(x),

которые нам хотелось бы проминимизировать одновременно на некотором допустимом множестве X Rn.Формально данная задача может быть записана как

x X	≤		≤		(168)
min fi(x), 1		i		r.

Вектор-функцию f(x) = [f1(x), . . . , fr(x)] принято называть векторным критерием,

а саму задачу (168) задачей многокритериальной минимизации.

Понятно,что в большинстве случаев найти такую точку x X, в которой все критерии f1(x), . . ., fr(x) достигали бы на X своего минимального значения,не представляется возможным.Поэтому приходится изменять само понятие оптимальности для задач вида(168).Сделать надо это таким образом,чтобы отбросить заведомо неприемлемые решения.

	Определение19.	Точка x X называется оптимальной по Слейтеру или
	слабо оптимальной по Парето,если
		max	i		i
			f (x)		− f (x ) ≥ 0 x X.
		1≤i≤r
	Определение20.	Точка x X называется оптимальной по Парето,если
	max	i		i
		f (x) − f (x ) > 0 x X, f(x) = f(x ).
	1≤i≤r

Согласно приведенным определениям любая оптимальная по Парето точка является одновременно оптимальной и по Слейтеру,но не наоборот.

Обозначим через F Rr образ задачи (168)в пространстве критериев

F = {f Rr : f = f(x), x X} .

Если допустимое множество X выпукло и все функции f1(x), . . ., fr(x) также выпуклы,то множество F оказывается эффективно выпуклым,что означает выпуклость множества F+ = F +Rr+.На рис. *и**показаны множества F и F+ как в общем случае,так и в случае выпуклых критериев.Пространство Rr, которому принадлежит множество F называется критериальным пространством или пространством оце-

нок, а сами векторы f(x) F называют также векторными оценками допустимого решения x X.

Пусть XS множество точек из X,оптимальных по Слейтеру,и пусть XP мно - жество точек из X,оптимальных по Парето.Этим двум множествам соответствуют

82

пара подмножеств в F, а именно ,FS = f(XS) и FP = f(XP ).Множество FS яв-

ляется множеством значений критериев,оптимальных по Слейтеру . Аналогично ,

FP является множеством значений критериев,оптимальных по Парето . Векто -
		при этом называют					P
ры f		FP	f		парето-оптимальным критериями или парето-
оптимальной оценками.Если						F	, то не	существует такой векторной оценки
									S
f F, что f = f и f ≤ f .Соответственно,если									f F , то не существует оценки

f F такой,что f < f .Часто эти неравенства используются в качестве определений оптимальных оценок(по Парето или по Слейтеру).На рис. ***показаны множества

FP и FS. Оба эти множества , находясь вF, принадлежат " юго - западной " границе F+.Имеет место включение FP FS.

Для решения задач многокритериальной оптимизации разработано много подходов и способов.В основном их можно разбить на два главных направления.В рамках одного из этих направлений главное внимание уделяется нахождению одного подходящего решения из множества оптимальных оценок FP или FS.При этом считается,что выбор конкретной оценки осуществляется лицом принимающим решение (ЛПР),у которого на самом деле имеются некоторые"скрытые"предпочтения среди критериев,например,их относительная важность.Руководствуясь данными предпочтениями ЛПР и принимает решение.Формально это описывается наличием некоторого бинарного отношения предпочтения и нахождением решений,которые являются недоминируемыми с точки зрения этих отношений,т.е.неулучшаемыми. Для выявления этих отношений предпочтения могут применяться в частности ин-

терактивные подходы.

Конкретные решения из множества оптимальных оценок могут быть получены также и с применением метода целевой точки или метода главного критерия.Со-

гласно методу целевой точки выделяется некоторая точка в критериальном пространстве,не принадлежащая множеству F+, и ищется точка из F, ближайшая к выделенной точке в заданной метрике.В методе главного критерия все критерии ранжируются по степени важности и далее ищется множество точек,которые доставляют оптимум наиболее важному критерию,далее на найденном множестве ищется его подмножество,доставляющее минимум по второму критерию и т.д.

Другое направление в решении задач многокритериальной оптимизации заключается в предъявлении ЛПР всего множества оптимальных оценок и далее ЛПР сам решает,какая из этих оценок его более устраивает.Имеются разные подходы к нахождению множеств оптимальных оценок или,по крайней мере,их аппроксимации конечным количеством точек.Одним из наиболее простых является подход, основанный на сведении задачи многокритериальной оптимизации к параметрической задаче нелинейного программирования.Осуществляется подобный переход путем скаляризации векторного критерия,т.е.свертывания всех частных критериев в единый критерий.Однако,возможно и непосредственное обобщение рассмотрен-

83

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

Ниже в качестве примеров указанных обобщений рассматриваются обобщения методов параметризации целевой функции,метода возможных направлений и метода модифицированной функции Лагранжа.Разумеется все эти обобщения проводятся таким путем,чтобы в частном случае,когда в задаче имеется один критерий,они переходили в известные численные схемы.В этих обобщениях также присутствуют оценки оптимальных значений критериев,но они не зафиксированы,а меняются в ходе вычислительного процесса.Поэтому условно данные обобщения можно назвать

методами подвижной целевой точки.

1.7.1.Обобщение метода параметризации целевой функции

Рассмотрим обобщение этого метода на примере задачи многокритериальной минимизации(168),в которой допустимое множество X задается с помощью ограничений типа неравенства

i X

≤

≤

R

r

≤

≤

≤

(169)

min fi(x), 1

i

r, X = x

n : gj(x)

0, 1

j

m .

Предположим,что нам известен вектор

η R ,который не принадлежит мно-

жеству F+. Вектор η по смыслу полностью аналогичен оценке снизу оптимального значения,которая использовалась в методе параметризации целевой функции с одним критерием.Составим вспомогательную функцию

	r
M(x,η ) =		(fi(x)		ηi)+2	+ (B(g(x)))+2 ,
			−
	i=1

где B(g) внешняя свертывающая функция.Обозначим через X (η) множество минимумов функции M(x,η ) на всем пространстве Rn при фиксированном значении вектора η, т . е . множество решений задачи

min M(x,η ).	(170)
x Rn

Опишем теперь сам алгоритм метода параметризации целевой функции, обоб -

щенный для решения задачи многокритериальной минимизации.Пусть задан вектор η0 / F+ и направление e R такое,что e > 0r и e 2 = 1.Полагаем k = 1.

Общая k-я итерация.

Шаг1) . Решаем задачу (170) при η = ηk и находим точку xk X (ηk).Если M(xk, ηk) = 0,то останавливаемся.Если нет,то идем на шаг2.

84

Шаг2) .Пересчитываем вектор ηk,
ηk+1 = ηk + λke,	(171)

где λk = M(xk, ηk).Полагаем k := k + 1 и идем на шаг 1.

Убедимся,что при таком способе пересчете векторов ηk ни один из них не попадет в множество intF+.

Лемма6. Пусть ηk / F+. Тогда ηk+1 / intF+.

Доказательство. Предположим противное,что ηk+1 intF+. Тогда обязательно

найдется точка x¯ X такая,что для векторной оценки								f¯ = f(¯x) выполняется f¯ <
ηk+1.Имеем для данной точки				x¯ в силу ее допустимости и правила пересчета (171):
				r	i	−	i 2
M(¯x,η	k	) =		r	(fi(¯x)		ηi )2 + (B(g(¯x)))2 =
				i=1			k +	+
					(f (¯x) − ηk)+ = (f(¯x) − ηk)+ 2 =
		=	i=1

= (f(¯x) − ηk+1 + M(xk, ηk)e)+ 2 <

< M(xk, ηk)e 2 = M(xk, ηk) e = M(xk, ηk).

Мы пришли к противоречию с тем,что xk X (ηk). Таким образом ,ηk+1 / intF+. Так как на каждой итерации M(xk, ηk) ≥ 0 и все компоненты вектора e строго положительны,то {ηk} является последовательностью векторов со все увеличивающимися компонентами,расположенными на луче,выходящим из точки η0 / F+ и имеющим направление e.Из-за того,что ни один из векторов ηk не принадлежит

intF+,следует ограниченность этой последовательности сверху и,стало быть,существование предела limk→∞ ηk = η / intF+.Очевидно,что данный предельный вектор η также принадлежит указанному лучу.

Убедимся теперь,что в результате работы алгоритма мы получаются точки оптимальные по Слейтеру.

Теорема16. Пусть последовательность {xk}, порождаемая алгоритмом обоб - щения метода параметризации целевой функции,принадлежит компактному множеству W . Тогда любая ее предельная точка является оптимальной по Слейтеру , а предельный вектор η принадлежит границе множества F+.

Доказательство. Обозначим λ = inf{λ ≥ 0 : η0 + λ e F+}.Какое бы η0 / F+ и направление e ни взять луч {η = η0 + λ e: λ ≥} обязательно пересечет множество F+, поэтому величина λ конечна.Имеет место представление

k
s	(172)
ηk+1 = η0 + λke,λ k = M(xk, ηk) ≥ 0.
=0

85