Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

Скачать файл (14,79Мб)

Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 15.10.2024

Просмотров: 144

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

76	ГЛ. 1. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
1.1.2.	Выпуклые	задачи. Теорема	Куна — Таккера.
Пусть X — линейное		пространство, /0,	fn — конечные
функции на X и А — подмножество пространства X. Рас
смотрим	задачу	foM -> in f;		(9)

	М * ) < 0 .........fn( x ) < 0,			(10)
		х е Л		(11)
Соотношения (10)называются ограничениями				типа

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

циональной	форме,скажем, в	виде неравенства
б(л ;\|Л )^0.)	Если функции /0......... fn и множество А
выпуклы, то	задачу (9)'— (11)	называют задачей вы
пуклого программирования.
Из-за того, что ограничения в нашей задаче разде
лены на две	группы — ограничения типа неравенств и

ограничения (11), мы можем по-разному составлять функцию Лагранжа задачи (9) — (11). Главным обра зом, мы будем иметь дело с функцией Лагранжа, в ко

торую не включены ограничения			(11):
			П
3? (х, А0, . . . , Я„) =			2 ^tfi (х).
			t=о
Однако можно	рассмотреть	и «удлиненную» функцию
Лагранжа
<?, (*,	Я„, . . . , К) =	2 hft (х) + Ь(х I А).
		*=i

Условия экстремума в задачах выпуклого програм мирования можно записывать в двух почти эквивалент ных формах: в нелокальной форме (см. ниже теорему Куна — Таккера) и в локальной форме, с помощью субдифференциалов. Это связано с тем фактом, что в таких задачах всякий локальный экстремум является и

абсолютным.	2	(теорема	Куна — Таккера).	Пусть
Т е о р е м а
функции fo, . . . ,	fn и множество А выпуклы. Предполо
жим, что вектор		х * удовлетворяет ограничениям		(10),
(И). Тогда, если		х * — решение задачи (9) — (11), то
существуют такие не равные			одновременно нулю	мно

§ 1.1. ПОСТАНОВКИ ЗАДАЧ

жители Лагранжа Яо ^					О, . . . ,	An	^	О, что
	9? (xt,		Я0.........А„)		= min SE (х,			Я0, . . . .	Я„)	(12)
U					х е	А
		hfi (-О — 0			пРЧ	г =	1,	. . . . п.		(13)

Если	же, кроме того, существует такой вектор х е А,
что / г- (л:) с		0	при	всех	i — 1,		п (условие Слейте
ра),	то Яо ф		0 и можно считать,				что Яо =		1. В послед
нем	случае соотношения (12), (13) достаточны для
того,	чтобы точка х*, удовлетворяющая условиям									(10),
(11),	была решением задачи (9) — (11).
Соотношение (12) называется условием Куна — Тан
кера,	а равенства			(13) — условиями дополняющей						не-
жесткости.		Условие Куна — Танкера показывает, что для

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

х ч, т. е. таким,	которые в этой точке обращаются	в ра
венства.	2' (субдифференциальная форма	усло
Т е о р е м а
вий экстремума в выпуклом программировании).		Пусть

X — отделимое локально выпуклое пространство и все функции U, •••> fn непрерывны в некоторой точке мно жества А (хотя они могут и не быть всюду конечными). Пусть далее точка х* удовлетворяет условиям (10) — (11). Если х * — решение задачи (9) — (11), то найдут ся такие не равные одновременно нулю множители Ла

гранжа Яо 0, . . . . Я„	^	0,	что
О е Я 0df0 (х,) + . . .		+	К dfn (х,) + ЛГ (х,\| А), (12')
hfi (x,) =	0,		i = l , . . . , n ,

где ЛГ(х,|Л) = д6(х,|Л) — нормальный конус к множе ству А в точке х *. Если, кроме того, выполнено условие Слейтера, то КоФО и можно считать, что Ко= 1. В по следнем случае написанные соотношения не только не обходимы, но и достаточны для того, чтобы вектор х , был решением задачи.

78	ГЛ. 1. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
Соотношение (12') мы также будем называть урав
нением	Эйлера — Лагранжа.		Оно	означает,	что	0 ен
^ д х2? 1	и может	рассматриваться		как естественное
распространение		уравнения	Эйлера — Лагранжа			(3)
на выпуклые задачи.			все	функции	f0, . . . , fn
В гладком случае, когда

дифференцируемы, X — Rm и выполнено условие Слей тера, уравнение Эйлера — Лагранжа совместно с усло виями дополняющей нежесткости образуют систему из ш -j- п уравнений с т + п неизвестными, т. е. мы снова приходим к замкнутой системе, где число уравнений совпадает с числом неизвестных. Этот факт отражает алгоритмическую сущность теоремы Куна — Таккера.

В конце параграфа мы снова вернемся к задачам выпуклого программирования и сформулируем теорему Куна — Таккера в форме теоремы о седловой точке, ко


торая позволит взглянуть с новых позиций				и	на сам
принцип Лагранжа.
1.1.3.	Гладко-выпуклые задачи. Экстремальный прин
цип в гладко-выпуклых задачах. Пусть X и У—
банаховы	пространства, U — произвольное			множество,
fo, •••, fn — функции на х X		и	и F: X X U		У — ото
бражение произведения X X		U в У. Рассмотрим задачу
	f0(x, и) -»• inf;					(14)
	F{x,u) =		0,			(15)
	fi(x, « X 0.........fn(x, и ) < 0 ,					(16)
	и £= U .					(17)
Задачи такого типа мы будем называть гладко-выпук
лыми, если функции f0, . . . , fn			и отображение		F	удов
летворяют	некоторым условиям		гладкости	по	х	и вы

пуклости по и, точно формулируемым ниже.

Нас будут интересовать необходимые условия ло кального минимума в задаче (14) — (17). Однако в данном случае содержание термина «локальный мини мум» требует уточнения, поскольку множество U не предполагается топологизированным. Мы скажем, что

пара	(х, «), удовлетворяющая ограничениям	(15) —
(17),	есть точка локального минимума в задаче	(14) —
(17),	если для всякого х из некоторой окрестности точ

§ 1.1.

ПОСТАНОВКИ

ЗАДАЧ

ки л", и всякого и из U, удовлетворяющих тем же огра

ничениям,

выполняется неравенство

Ы *.. « .)< /(* >

и).

Рассмотрим,

как

в предыдущих

случаях,

функцию

Лагранжа

задачи

(14) —

(17),

включив

нее

только

функциональные ограничения:

(■х, и,

Я0.........Я„,

у ) — S hfi (х,

и) +

(у *,

F(x,

и)),

1=0

где, как обычно,

Яо,

. . . ,

Яп — действительные

числа,

г/* <= У*.

(экстремальный принцип в гладко

Т е о р е м а

выпуклых задачах).

Пусть точка

(х*, и,) удовлетворяет

условиям

(15) —

(17). Предположим далее,

что точка

х* обладает такой окрестностью V а

X, что

а)

при

всяком

u ^ U

отображение

x —*F(x,u)

функции x - * f i { x , u ) ,

i =

0, . . . ,

п,

принадлежат клас

су Ci в точке х»;

х е У

б)

при

всяком

отображение

u - * F ( x , u )

функции u-*fi(x,

и),

i =

0, .. .,

п,

удовлетворяют

сле

дующему

условию

выпуклости:

для

всяких

Ui е

« 2 G t / и 0 <

а <

найдется

такое « е ! / ,

что

F (х,

и) — aF (х,

Ui) -j- ( 1 — a) F (х, и2),

fi (х, и) < afi (х,

и{) - f (1 — а) / , (х, и2),

1 =

0.........п.

Допустим, кроме того, что

в)

множество

значений

линейного

оператора

F*(x*, «*):

X —* У имеет конечную

коразмерность

У.

Тогда,

если (х*, «*)— точка локального минимума

задаче (14) —

(17),

то найдутся такие не равные одно

временно

нулю

множители

Лагранжа

Яо ^

0, . . .

. . . , Я„ ^

у* е

У*,

что

SEх (х„

ut, Яд,

.. •,

Я„,

у ) = 2]

^iftx (•*■*> u.) +

'=°

+ F 'x (xt, ы.) у* =

(18)

С*-*»

w*» Яд,

Яп,

у ) === min

(^*>

и, Яо,

Я^, у ),

(Ю)

и е [/

Я*/г (*,. «,) = 0 ярм / = 1, . . . . п.

(20)

Если же в дополнение к сформулированным условиям

Смотрите также файлы

Картирование шельфов сборник статей..pdf

Квитко, М. П. Кислородно-конвертерный процесс.pdf

КМА набирает высоту сборник статей, очерков об освоении Курской магнитной аномалии..pdf

Коган, З. А. Консервация и упаковка машиностроительной продукции.pdf

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

Файл: Иоффе, А. Д. Теория экстремальных задач [учеб. пособие].pdf

Смотрите также файлы

Информация

Списки файлов

Дополнительно