Необходимые условия экстремума - Пшеничный Б.Н.

Автор: Пшеничный Б.Н.
Теги: математика
Год: 1969
Похожие
Необходимые условия экстремума
Что такое высшая математика: чем она отличается от школьной, зачем она нужна
Лекции по аналитической геометрии, пополненные необходимыми сведениями из алгебры
Численные методы в экстремальных задачах
Текст
                    ОПТИМИЗАЦИЯ
И ИССЛЕДОВАНИЕ
ОПЕРАЦИЙ
Б. Н. ПШЕНИЧНЫЙ
Необходимые
условия
экстремума

ОПТИМИЗАЦИЯ
И ИССЛЕДОВАНИЕ
ОПЕРАЦИЙ
Редактор серии
И. Н. МОИСЕЕВ
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ ФИЗИКО-МАТЕМАТИЧЕСКОЙ
ЛИТЕРАТУРЫ
МОСКВА 1969
Б. Н. ПШЕНИЧНЫЙ
НЕОБХОДИМЫЕ
УСЛОВИЯ
ЭКСТРЕМУМА
ИЗДАТЕЛЬСТВО «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
МОСКВА 1 У 6 9
519
П 93
УДК 519.9
Необходимые условия экстремума.
Пшеничный Б. Н., Изд-во «Наука»,
Главная редакция физико-математиче-
ской литературы, 1969.
Настоящая книга представляет обзор совре-
менного состояния теории необходимых условий
экстремума.
Она содержит как общий математический ап-
парат, так и применение этого аппарата к реше-
нию таких важных задач, как математическое
программирование, теория игр, проблема момен-
тов, дискретный принцип максимума и т. п.
Библ. — 69 назв.
2-2-8
95-69
СОДЕРЖАНИЕ
От редактора серии ..................................... 6
Предисловие .	............. .	.............. 7
Введение. Элементы функционального анализа и выпук-
лые множества................. ................. .	13
1.	Основные положения функционального анализа .	. 13
2.	Выпуклые множества	.	................28
3.	Выпуклые функционалы	.	................37
§ 1.	Свойства выпуклых функционалов .	..............39
§ 2.	Выпуклое программирование в пространстве Банаха .	49
§ 3.	Квазидифференцируемые функционалы ...	57
§ 4.	Необходимые условия экстремума в общих задачах ма-
тематического программирования..........................66
§ 5.	Необходимые условия экстремума в конкретных зада-
чах ....................................................91
1.	Классическая задача математического программиро-
вания ..............................................91
2.	Математическое программирование с континуумом
ограничений ......................................  92
3.	Теоремы	о минимаксе...................... 94
4.	Задачи	чебышевского приближения.................97
5.	Задача линейного оптимального управления с фазо-
выми ограничениями................................ 105
6.	Принцип двойственности в выпуклом программиро-
вании	............................ 111
7.	Системы	выпуклых неравенств.	Теорема Хелли .	116
8.	Проблема моментов................... . .	121
9.	Дискретный принцип максимума.................. .	133
Краткая библиография .	............144
Литература.............................................148
ОТ РЕДАКТОРА СЕРИИ
В 1964 году Отделение математики АН СССР приняло ре-
шение проводить один раз в два года Всесоюзную математиче-
скую школу, посвященную общим вопросам оптимизации, тео-
рии принятия решения и управления. Первая из этих школ была
проведена в Черновицах. Она была первым шагом в процессе
адаптации к потребностям лиц, активно занимающихся созданием
и приложением математических методов оптимизации к теории
управления. Лекционные циклы носили характер лаконичных об-
зоров, причем часто довольно элементарных вопросов.
Вторая школа была проведена в 1967 году в окрестности
г. Шемаха в поселке астрофизической обсерватории АН Аз.ССР.
Лекционные курсы этой школы состояли из пяти циклов общим
объемом в 80 академических часов:
Введение в исследование операций (Ю. Б. Гермейер).
Необходимые условия экстремума (Б. Н. Пшеничный).
Последовательный анализ вариантов в сетевых задачах
(В. В. Шкурба).
Задачи оптимальной остановки (А. Н. Ширяев).
Дискретный принцип максимума (А. И. Пропой).
Эти курсы готовились авторами на протяжении длительного
времени и представляли систематическое изложение обширного
материала. Поэтому они были предложены для публикации в
издательство «Наука» и было принято решение на их базе на-
чать издавать серию «Оптимизация и исследование операций».
Монография Б. Н. Пшеничного открывает серию. Она по-
священа общим вопросам отыскания экстремума функций, за-
данных в нормированных пространствах и содержит вопросы,
которые ныне стали уже почти классическими. Книга Б. Н. Пше-
ничного основывается главным образом на собственных резуль-
татах автора, сделавшего большой вклад в развитие того напра-
вления в функциональном анализе и теории экстремумов функ-
ций, возникновение которого связано с именами А. Я. Дубовиц-
кого и А. А. Милютина. Книга, предлагаемая читателям, пред-
ставляет собой систематическое изложение предмета.
И. Н. Моисеев
ПРЕДИСЛОВИЕ
Последние 10—12 лет были периодом исключи-
тельно бурного развития теории экстремальных за-
дач и методов их решения. Большое количество
интересных в теоретическом отношении и важных в
практическом отношении проблем привлекло внима-
ние широких кругов математиков и инженеров. И это
не удивительно. Сейчас трудно назвать какую-либо
область знаний, где в той или иной форме не воз-
никали бы экстремальные задачи и решение которых
не было бы существенным для развития этих обла-
стей. Это и теория автоматического управления, и
проблема экономики, и даже биология. Все эти науки
выдвигают свои экстремальные задачи и ждут отве-
тов на два вопроса: каков качественный характер
решения и как его найти?
Первый из этих вопросов — каков качественный
характер решения — побуждает математиков искать
наиболее полные необходимые условия экстремума,
ибо именно эти условия позволяют предсказать об-
щую структуру решения. Лавинообразный характер
потока возникающих задач ясно стал показывать, что
необходимы именно общие условия экстремума, т. е.
такие условия, которые были бы применимы к широ-
кому классу задач, чтобы избавиться от необходимо-
сти в каждом конкретном случае строить новую тео-
рию. С другой стороны, уже решенные частные
задачи давали основание быть уверенными, что та-
кие условия можно сформулировать. Более того, они
показывали, что такие условия не будут слишком
далекими от конкретных задач, так что их примене-
ние для данной задачи будет скорее похоже на за-
нятие заранее подготовленных позиций, чем на штурм
крепости.
7
Задачи на экстремум — не новость для матема-
тики. Они встречались и решались на протяжении
всей истории математики. Однако интенсивное и по-
следовательное их изучение началось сравнительно
недавно, когда, с одной стороны, запросы экономики
и автоматического управления сделали решение этих
задач неотложным делом, а, с другой стороны, по-
явление электронных вычислительных машин дало
в руки исследователей мощное средство, с помощью
которого решение может быть доведено до конечного
итога — численного результата. Если не говорить
сейчас о вариационном исчислении и задачах мини-
мизации функций при ограничениях типа равенств,
задачах, в которых необходимые условия экстремума
были получены давно, то начало нового этапа раз-
вития теории экстремальных задач можно датиро-
вать 1939 годом. В этом году советским математиком
Л. В. Канторовичем были созданы методы решения
нового типа задач —задач линейного программиро-
вания. В дальнейшем теория линейного программиро-
вания получила широкое развитие в работах Г. Дан-
цига и многих других авторов как за рубежом, так
и в СССР.
Следующим этапом в развитии необходимых ус-
ловий экстремума явилась разработка теории выпук-
лого программирования. Центральным местом в этой
теории является теорема Куна—Таккера, дающая
необходимые условия экстремума и послужившая
источником целого ряда алгоритмов. Дифференциаль-
ная форма теоремы Куна—Таккера применима также
к задачам невыпуклого программирования в конеч-
номерном пространстве и позволяет сформулировать
для этих задач необходимые условия экстремума.
При разработке небходимых условий для задач
линейного и выпуклого программирования был вы-
яснен принцип, лежащий в основе всех построений.
Этот принцип был резюмирован Г. Зойтендейком в
его монографии «Методы возможных направлений».
Сущность этого принципа составляет тот совершенно
очевидный факт, что если в данной точке существует
направление, которое не выводит из допустимой об-
ласти и функция вдоль него убывает, то такая точка
не может быть точкой минимума. На основе этого
8
принципа были построены необходимые условия экс-
тремума для широкого класса задач в конечномер-
ном пространстве с гладкими ограничениями.
Параллельно с теорией конечномерных экстремаль-
ных задач — математическим программированием —
шло исследование другого класса задач — задач оп-
тимального управления. Решающую роль во всей этой
теории сыграла формулировка необходимых условий
экстремума в форме принципа максимума Л. С. Пон-
трягина. Нет нужды подробно останавливаться на
том, какое значение имела формулировка этого прин-
ципа для всей теории автоматического управления и
какое огромное количество работ она вызвала. Учи-
тывая направленность настоящей книги, необходимо
в первую очередь отметить, что доказательство прин-
ципа максимума, данное В. Г. Болтянским, было в
какой-то мере сенсационным, поскольку оно исполь-
зовало методы, которым трудно было найти анало-
гию в рамках уже развитой теории математического
программирования. В связи с этим на повестку дня
стал вопрос о выяснении возможности доказатель-
ства принципа максимума с помощью идей и методов,
используемых в классическом вариационном исчис-
лении и математическом, программировании. Помимо
чисто эстетического значения, поставленный вопрос
имел и другую, практическую сторону, ибо его ре-
шение позволило бы применить численные методы,
разработанные в математическом программировании,
для задач оптимального управления.
Вложение теории оптимального управления в об-
щую теорию необходимых условий было впервые
осуществлено А. А. Милютиным и А. Я. Дубовицким.
Большое значение их работ состоит в том, что им
удалось в рафинированной форме сформулировать
необходимые условия экстремума, пригодные для
применения к широкому классу задач. При этом было
выяснено, какая часть результатов по доказатель-
ству принципа максимума укладывается в общие
рамки, а какая обусловлена спецификой задачи оп-
тимального управления, т. е. наличием связей в виде
обыкновенных дифференциальных уравнений. Наи-
более полное отражение специфика связей в виде
дифференциальных уравнений нашла в работах
9
Р. В. Гамкрелидзе, который сформулировал понятие
скользящих режимов и понятие квазивыпуклых мно-
жеств. На основе понятия квазивыпуклого множества
Р. В. Гамкрелидзе дал новое доказательство прин-
ципа максимума Л. С. Понтрягина, которое четко
разделяет общую вариационную задачу и специфику
дифференциальных связей.
Работы по теории оптимального управления ока-
зали чрезвычайно плодотворное влияние на общую
теорию необходимых условий экстремума. Они по-
зволили выявить основные принципы, развить тех-
нику построения необходимых условий и посмотреть
с единой точки зрения на широкий класс задач. При
этом углубленное и последовательное изучение по-
зволило построить необходимые условия в задачах,
в которых участвуют уже недифференцируемые в
обычном смысле функции. Оказалось достаточным
рассматривать лишь функции, дифференцируемые по
направлению. В терминах функций, дифференцируе-
мых по направлению, X. ХалкиниЛ. Нейштадт сфор-
мулировали весьма общую теорему о необходимых
условиях, которая применима при решении широкого
класса задач, в том числе и задач оптимального уп-
равления.
Интересно отметить, что как основные теоремы
А. А. Милютина и А. Я. Дубовицкого, так и теоремы
X. Халкина и Л. Нейштадта, требуют для своего до-
казательства средств, достаточно давно известных
математике. И то, что эти результаты были получены
лишь в последние пять-шесть лет, показывает, какая
большая работа была проделана по осмысливанию
основных принципов, по выработке основных по-
нятий.
Настоящая книга посвящена изложению теории
необходимых условий экстремума. В основу положен
дедуктивный принцип изложения, т. е. сначала изла-
гаются общие результаты, а потом показывается, как
эти результаты могут быть конкретизованы в частных
задачах. Такой способ изложения в данный момент
представляется оправданным, поскольку имеется
очень большое число работ, посвященных выводу не-
обходимых условий в конкретных задачах, которые
вполне подготовили переход на абстрактный уровень
Ю
изложения. Далее, в теории необходимых условий
можно выделить две части, которые несколько услов-
но можно назвать следующим образом: формальные
условия экстремума и техника вычислений.
Формальные условия экстремума в настоящей
книге изложены в § 4. Это некоторый набор теорем,
утверждающих, что если выполнены определенные
условия на минимизируемую функцию и область, в
которой происходит минимизация, то в точке мини-
мума выполняется некоторое соотношение. Однако
как конкретно записать это соотношение в данной
задаче, указанные теоремы не говорят. Для эффек-
тивного построения необходим развитый аппарат тех-
ники вычислений. Чтобы сделать понятными сказан-
ные общие фразы, поясним их на примере • задачи
о минимуме функции одной переменной.
Для того чтобы в некоторой точке достигался
минимум, необходимо, чтобы в этой точке производ-
ная от функции равнялась нулю. Это в приведенной
терминологии формальное условие экстремума. Но
если бы не была развита техника вычислений произ-
водных от достаточно сложных функций, то приве-
денное условие невозможно было бы эффективно
записать для сколько-нибудь реальной задачи. Пер-
вые три параграфа книги посвящены исследованию
техники вычислений. Только после того, как эта тех-
ника достаточно развита, приводятся формальные
условия экстремума.
Всякая общая теория ценна лишь постольку, по-
скольку она позволяет охватить единой точкой зре-
ния достаточно широкий класс задач. Поэтому срав-
нительно большой § 5 посвящен иллюстрации того,
как можно применить построенную теорию для кон-
кретных задач. Каждая из рассмотренных задач да-
леко не тривиальна и ее исследованию было, посвя-
щено достаточно большое количество работ. Некото-
рые из рассмотренных задач, например теория
чебышевского приближения и проблема моментов,
сами носят весьма общий характер и имеют много-
численные приложения в экономике и теории опти-
мального управления.
Из задач оптимального управления в § 5 рассмат-
риваются лишь такие, в которых результат может
11
быть получен без исследования специфики, вносимой
связями в виде дифференциальных уравнений, так
как рассмотрение таких связей увело бы несколько
в сторону от общего направления книги.
Чтобы сделать изложение замкнутым, во введе-
нии приведены основные факты из функционального
анализа и теории выпуклых множеств, используемые
в ходе изложения. Отказываться от изложения ма-
териала с использованием более общих пространств,
чем конечномерные, не хотелось, так как такой отказ
повел бы к значительному обеднению материала и
ряд задач, ради которых собственно и строилась
сложная теория, оказался бы вне рассмотрения.
Таким образом, читатель, мало знакомый в функ-
циональным анализом, сможет ознакомиться со все-
ми фактами, необходимыми для понимания даль-
нейшего, во введении, тем более, что таких фактов
очень немного. Читатель, знакомый с основами функ-
ционального анализа, может приступать к чтению
сразу с первого параграфа.
Необходимо сделать также замечание о способе
ссылок на литературу, принятом в книге. В ходе из-
ложения делаются только самые необходимые ссыл-
ки на те результаты, которые используются в книге,
но в ней не доказаны.
Ссылки же, указывающие, в какой работе дока-
зана та или иная теорема, в каком отношении данный
результат находится с другими результатами и т. п.,
приведены в конце книги в краткой библиографии.
Настоящая книга написана на основе цикла лек-
ций, которые автор прочел во Второй Всесоюзной
школе по методам оптимизации, г. Шемаха, 6—26 ию-
ля 1967 г. Автор искренне признателен председателю
оргкомитета школы чл.-кор. АН СССР Н. Н. Моисе-
еву за приглашение прочитать эти лекции, а также
за многочисленные плодотворные дискуссии и вни-
мание к данной работе.
Считаю также своей приятной обязанностью вы-
разить признательность моим сотрудникам по Инсти-
туту кибернетики АН УССР, помощь которых в ра-
боте над этой книгой трудно переоценить.
Б. Пшеничный
ВВЕДЕНИЕ
ЭЛЕМЕНТЫ ФУНКЦИОНАЛЬНОГО АНАЛИЗА
И ВЫПУКЛЫЕ МНОЖЕСТВА
Математическим аппаратом, на котором основано
построение теории необходимых условий в задачах
минимизации, является функциональный анализ.
В сущности при построении теории используется
лишь несколько основных понятий и несколько тео-
рем. Это в первую очередь понятия слабой сходимо-
сти, бикомпактности и теорема отделимости выпук-
лых множеств. Для удобства читателей мы кратко
без доказательств изложим необходимые для пони-
мания дальнейшего основные факты функционально-
го анализа, заимствуя их из книги [1]. Впрочем, боль-
шинство приводимых ниже теорем, за исключением
некоторых основных, являются непосредственными
следствиями определений и их доказательство мо-
жет быть проведено самим читателем, желающим
проверить правильность понимания вводимых опре-
делений.
1. Основные положения функционального анализа.
Определение 1. Семейство т подмножеств
множества X образует его топологию, если оно со-
держит пустое множество 0, само X, каждое объе-
динение любого числа и каждое пересечение конеч-
ного числа своих подмножеств. Пара (X, т) назы-
вается топологическим пространством. Множества
из т называются открытыми множествами. Окрест-
ностью точки р называется каждое открытое множе-
ство, содержащее р, окрестностью множества А —
13
любое открытое множество, содержащее А. Точка
р е А называется внутренней точкой Д, если суще-
ствует такая окрестность р, которая целиком содер-
жится в А.
Очевидным следствием определения 1 является
следующая
Лемма 1. Для того чтобы множество в тополо-
гическом пространстве было открытым, необходимо
и достаточно, чтобы оно содержало некоторую окрест-
ность каждой своей точки.
Определение 2. Семейство (3 подмножеств
из X называется базисом топологии т, если любое
множество из семейства р содержится в семействе т
и каждое множество из т есть объединение множеств
из семейства р.
Для того чтобы система р служила базисом не-
которой топологии, необходимо и достаточно, чтобы
для каждой пары множеств U, V е р и x^UCW
нашлось такое W е р, что x^W^UCW, и объеди-
нение всех множеств из р совпадало со всем множе-
ством X.
Если задан базис р, то топология т задается
всеми множествами, образованными с помощью опе-
рации объединения некоторого количества множеств
из р. Например, обычная топология в n-мерном про-
странстве может быть задана с помощью семейства
Р, состоящего из множеств, определяемых неравен-
ствами
i = I
где y = {yi, ... ,уп} и R — произвольные вектор и чис-
ло, причем /?>0.
Определение 3. Множество Y cz X называется
замкнутым, если дополнительное к нему множество
Х\У открыто. Пересечение всех замкнутых мно-
жеств, содержащих некоторое множество А, назы-
вается замыканием А и обозначается А.
Задание топологии т на некотором множестве X
позволяет определить понятие сходимости последо-
вательности.
Определение 4. Последовательность хп,
ц—>оо, сходится к точке Xq, хп^Х, xQ^X, если для
14
любой окрестности точки х0 найдется такой номер V,
что все точки хп,	принадлежат этой окрест-
ности.
В дальнейшем мы будем рассматривать только
так называемые хаусдорфовы топологические про-
странства, т. е. такие топологические пространства
(X, т), в которых множества, состоящие из одной
точки, замкнуты и у любых двух несовпадающих
точек х и у существуют непересекающиеся окрестно-
сти. В таких пространствах каждая сходящаяся по-
следовательность имеет единственную предельную
точку х0, и можно написать
lim хп = х0.
П->оо
Введенное выше понятие сходимости вполне экви-
валентно в случае n-мерного пространства обычному
понятию сходимости, приводимому в курсе матема-
тического анализа [44]: последовательность векторов
xh сходится к вектору х°, если для любого е>0 най-
дется такое W, что для fe > Л/
— х°)2<е2.
Пусть теперь заданы два топологических простран-
ства (Xi, Ti) и (Х2, тг). Говорят, что задано отобра-
жение f: %!—>Х2 (%] в Х2), если каждому xgXj
однозначным образом поставлен в соответствие эле-
мент у е Х2. Этот элемент у обозначают через f(x).
Если t/czXi, то через f(U) обозначается множество
всех точек f(x), которые получаются, когда х пробе-
гает U. Если VczX2, то есть множество тех
точек х, для которых /(x)eV. f(U) называется об-
разом множества U, a —прообразом множе-
ства V.
Определение 5. Отображение f: Х{—>Х2 на-
зывается непрерывным в точке х0, если для каждого
открытого множества V cz Х2, f(xo)eV найдется та-
кая окрестность U точки х0, что /(C/)cz V. Отображе-
ние f: Xi —> Х2 называется непрерывным, если оно
непрерывно в каждой точке хеХр
Отображение f непрерывно тогда и только тогда,
когда для любого открытого множества V cz Х2 его
15
прообраз f-1(V) есть также открытое множество.
В самом деле, пусть V — открытое множество в %2
и	По определению непрерывности в точ-
ке х и тому, что f(x) е V, найдется такая окрест-
ность Ux, что f((7x)cz V. Тогда очевидно, что
г‘(ю= U
х^Г1 (V)
и правая часть этого равенства есть открытое мно-
жество, поскольку она является объединением откры-
тых множеств.
Если перейти к более близкому для обычного
курса математического анализа определению непре-
рывности через последовательности, то легко дока-
зать, что если f(x) непрерывна в точке х0, то из
хп-+х0 следует, что f(xn) -+f(x0).
Точно так же, если А— замкнутое по определе-
нию 3 множество, то из того, что хп-+х0, хп^А
следует, что хоеЛ.
Существует важный класс пространств — метриче-
ские пространства, для которых введенные понятия
непрерывности функции и замкнутого множества экви-
валентны соответствующим понятиям, заданным
на языке последовательностей. В таких пространст-
вах функция непрерывна в точке х0 тогда и только
тогда, когда из хп-+х0 следует, что f(хп) -+f(х0), а
множество А замкнуто тогда и только тогда, когда
из хп-+хо, хп^А следует, что Хо<=А.
Определение 6. Множество X называется
метрическим пространством, если для любых х,
у <= X определена функция р(х, у), обладающая свой-
ствами:
О р(*> и р(х, //) =0, только если х = у\
2) р(х, у)=р(у,х);
3) р(х, z)<p(x,£/)+p(t/,z).
Топология в таком пространстве задается с по-
мощью базиса, состоящего из множеств
5(х0, г)={х: х<=Х, р(х,х0)<г}.
В частности, обычное пространство ц-мерных век-
торов является метрическим. Метрика в нем задается
16
с помощью формулы
/ п	\1/2
Р (х, у) = s (х, - у(у .
\i=l	/
Одну из важнейших ролей в дальнейшем изло-
жении играет понятие бикомпактности и связанное
с ним понятие компактности.
Определение 7. Покрытие множества А в то-
пологическом пространстве X есть семейство откры-
тых множеств, объединение которых содержит А.
Множество А называется бикомпактным, если из
всякого его покрытия можно извлечь конечное. Мно-
жество А называется компактным, если из всякой
последовательности {хп}, хп^А, можно выбрать схо-
дящуюся подпоследовательность, пределом которой
есть элемент того же множества А.
Укажем на некоторые свойства бикомпактных
множеств.
Лемма 2. а) Если отображение f\ Х{-+Х2 не-
прерывно, то образ f(U) бикомпактного множества U
бикомпактен.
б) Бикомпактное множество хаусдорфова про-
странства замкнуто.
в) В метрическом пространстве понятия компакт-
ности и бикомпактности совпадают.
По известной из анализа теореме Вейерштрасса,
для того чтобы в n-мерном пространстве множество
было компактным, необходимо и достаточно, чтобы
оно было замкнутым и ограниченным.
Пусть Xi и Х2— Два топологических пространства
С ТОПОЛОГИЯМИ Т1 И Т2- Чтобы иметь возможность
обращаться с функциями вида /(xi,x2), где хх^Х\,
а х2 Х2, введем понятие прямого произведения то-
пологических пространств Xi и Х2, которое обозна-
чается через Xi X Х2. Топологическое пространство
Х[\Х2 состоит из всевозможных пар вида (хьх2),
XieXb х2 е Х2, а топология на нем задается сле-
дующим образом: если — множество из системы п,
a U2 — из системы т2, то множество вида (J\ X U2,
принадлежность к которому точки х= (хьх2) озна-
чает, что Xi е U\, x2^U2, входит в систему т мно-
жеств, задающих топологию в Xi X Х2, и т состоит
из таких и только таких множеств. Таким образом,
2 Б. Н. Пшеничный
17
все открытые множества в Х\ X Х2 состоят из точек
(-Vi,x2), где Xi е [Д, х2е(/2 и LG, И2— открытые
множества в Х} и Х2 соответственно. Согласно этому
определению, если топологию на прямой — одномер-
ном пространстве — задать с помощью базиса, со-
стоящего из открытых интервалов, —г < Xi—х0 < г,
то базис в n-мерном пространстве будут образовы-
вать системы векторов x = {xi, хп}, удовлетво-
ряющих неравенствам
— г < х. — х° < г, i = 1, ..., п.
Таким образом, если рассматривать n-мерное про-
странство как прямое произведение п одномерных
пространств, то базис в нем задается с помощью
всевозможных открытых параллелепипедов.
Теперь ясно, что понимать под непрерывной функ-
цией /: XiXX2—* У, т. е. функцией /(хьх2), опреде-
ленной для Xi е Xi, х2 е Х2 и принимающей свои зна-
чения в У. f(x\,x2) будет непрерывной, если она
непрерывна как функция, отображающая топологи-
ческое пространство X Х2 в топологическое про-
странство У.
В дальнейшем мы будем иметь дело с тополо-
гическими пространствами, которые наделены струк-
турой линейного пространства.
Определение 8. Пространство L называется
линейным, если для любых х е L, у е L определены
операция сложения x + y^L и операция умножения
на вещественное число Хх е L, так что
1.	(х + у) + z = х +'\у + г).
2.	х4-# = г/4-х.
3.	Существует такой элемент 0еА, что для всех
xeL х + 0 = х и Ох = 0.
4.	(Х + ц)х = А,х+'цх.
5.	X (х + у) = Хх + Ху.
6.	(Л,ц)х = Х(цх).
7.	1 *х=х.
Элемент 0 играет роль «нуля» в этой системе, и
его часто обозначают знаком «нуля», если это не
ведет к недоразумениям,
18
В качестве примера линейного пространства мож-
но указать пространство Еп /г-мерных векторов, в ко-
тором операция сложения векторов и умножения на
число определена обычным образом.
В линейном пространстве L может быть задана
некоторая топология. Тогда пространство L стано-
вится линейным топологическим пространством, если
эта топология такова, что функции g(x, у)=х + у и
f(X, х)=Кх, отображающие LXL-+L и E[XL —* Lt
непрерывны.
Е[ — это пространство действительных чисел, то-
пология в котором задана с помощью базиса, со-
стоящего из множеств
5 (Ло, т) = {2i.‘ | К — Хо | <С г}.
Линейное пространство называется нормирован-
ным, если каждому элементу х поставлено в соот-
ветствие число ||х||, называемое нормой элемента,
которое удовлетворяет следующим условиям:
1)	IWI> 0 и равенство ||х||=0 эквивалентно ра-
венству х = 0;
2)	||U||= Щ ||х||;
3)	llx+f/IKM + llf/ll.
Задание в линейном пространстве нормы позво-
ляет определить в нем топологию, базисом которой
служат множества
S(x0, г)={х: ||х — x0||<r}.	(1)
В такой топологии последовательность хп сходится
к х0 тогда и только тогда, когда
Цхп — Xoll —0.
Нормированное пространство является метрическим
пространством, поскольку метрика в нем может быть
задана с помощью формулы
р (х, у) = ||х— 1/||.
В силу сделанного выше замечания в нормирован-
ном пространстве понятия компактности и бикомпак-
тности совпадают, а понятия непрерывной функции и
замкнутого множества могут быть сформулированы на
языке последовательностей. Например, множество А
2*
19
замкнуто тогда и только тогда, когда из
хп —► .г0, хп^А следует, что х0(=А.
Функция ц(х), определенная на нормированном
пространстве и принимающая свои значения в про-
странстве Е1 (т. е. ц(х) есть вещественное число),
непрерывна в точке х0 тогда и только тогда, когда
для каждого е > 0 найдется такое б > О, что
IhW — н(*о) I < е,
как только ||х— Xoll < б. Если учесть, что базис то-
пологии в Е1 задается с помощью интервалов
IА — %о| < е, а базис топологии нормированного про-
странства задан формулой (1), то легко видеть, что
приведенное определение непрерывности полностью
согласуется с определением 5.
Функции ц(х), принимающие свои значения в
множестве действительных чисел, обычно называются
функционалами.
Функции 4(х), задающие отображение А: В-*ВХ
одного нормированного пространства в другое, на-
зываются операторами.
В дальнейшем нормированное пространство будет
обозначаться буквой В. Особую роль при изучении
нормированного пространства В играет сопряженное
ему пространство непрерывных линейных функцио-
налов В*. Напомним, что функционал называется
линейным, если
ц(х +//) = ц(х) + |л(у)
и
ц(Лх) = Хц(х).
Элементы пространства В* будем обозначать с
помощью латинских букв со звездочкой вверху: на-
пример, х*, у* и т. п.
Пространство В* есть линейное пространство, по-
скольку операция сложения функционалов и умно-
жения на число может быть определена следующим
образом:
(х + /) (х) = х* (х) + у (х),
(Лх’)(х) = Кх (х).
20
Очевидно, что если х*, е В*, то функционалы
x* + f/* и Хх* также являются линейными непрерыв-
ными функционалами.
Так же легко проверяется, что если В = В{ X В2,
то В = Bi X Во, так что если х €= В , то
х*(х) = x*(Xj) + х*(х2)
для некоторых х* е В*, х*еВ* и любого х={хр х2].
Топология в пространстве В* может быть опреде-
лена двумя различными способами. Первая, так на-
зываемая сильная топология задается с помощью
базиса, состоящего из всех множеств
V (X, г, х*) = {/: sup | х (х) - х*(х) | < г},
где X — произвольное ограниченное подмножество В,
т. е. такое множество, что ||х|| 4^ R для некоторого R
и всех х<=Х. В такой топологии В* само оказы-
вается нормированным пространством, если норму
функционала определить формулой
|| х* |1 = sup х* (х),
а в качестве базиса взять систему множеств
S’(4 ') -(*•:
Уместно заметить, что справедлива двойственная
формула
|| х||= max х*(х),
х*е=$*
где
S* = {x*: || х*||< 1}.
То, что базисы V (X, г, xj) и S*(xJ, г) порождают
одну и ту же топологию, следует из того, что S*(xJ, г)
совпадает с V (X, г, х*), если
X = S = {x: ||х||<1},
и легко проверить, что множество V (X, г, xj) может
быть образовано как объединение множеств типа
S’(x*o> О-
21
Вторая, слабая* топология пространства В*, об-
разуется с помощью базиса, состоящего из множеств
IF(X, г, x*)={x*: | х* (х) — х* (л?) | < г для х^Х],
где X — подмножество В, состоящее из конечного
числа элементов х^еВ, f=l, ..., k.
В соответствии с наличием двух топологий каж-
дый из таких терминов, как компактность, биком-
пактность, замкнутость, сходимость, получает двой-
ное звучание в зависимости от того, сильная или
слабая * топология имеется в виду. Например, схо-
димость может быть сильной и может быть слабой *.
Заметим, что семейство открытых множеств, об-
разующее сильную топологию, шире семейства мно-
жеств, образующих слабую* топологию, как это не-
посредственно видно из определений V (X, г, и
W (X, г, Xq). Поэтому (см. определение сходимости
в топологическом пространстве) из сильной сходимо-
сти последовательности функционалов х* к x*Q сле-
дует слабая* сходимость, однако обратное неверно,
так как х* сильно сходится к х*, если
В то же время х* слабо* сходится к xj, если для
любого х е В
Точно так же, из бикомпактности множества X* cz В*
в сильной топологии следует его бикомпактность в
слабой* топологии, однако обратное опять-таки не-
верно.
По-другому обстоит дело с понятием замкнутости.
Если множество замкнуто в сильной топологии, то
оно может оказаться не замкнутым в слабой* топо-
логии. Действительно, замкнутое множество есть до-
полнение некоторого открытого множества. Класс
открытых множеств в сильной топологии шире, чем
класс открытых множеств в слабой * топологии. По-
этому, если дополнения к некоторому множеству есть
открытое множество в сильной топологии, то оно
может не оказаться открытым в слабой* топологии.
22
Наоборот, если множество слабо* замкнуто, то оно
и сильно замкнуто.
Рассмотрим теперь функционалы специального
вида, определенные на пространстве В*. Пусть х0 е В.
Тогда величина х*(х0) есть линейный функционал
на В*, ибо каждому х* ставится в соответствие число
х*(х0), причем
(х‘ + у*) (х0) = X* (х0) + У* (х0),
(Л.х’)(х0) = Лх*(х0).
Покажем, что построенный функционал непреры-
вен в обеих топологиях. Для этого надо показать,
что для любого x*Q множество тех х*, для которых
|х (хо) “ хо (хо) | < 8»
открыто, т. е. образует некоторую окрестность точ-
ки x*Q. Но это множество совпадает с множеством
v (*о> е> О = W (хо> е> хо)-
которое по определению открыто в обеих топологиях.
С понятием сходимости в нормированном про-
странстве тесно связано понятие фундаментальной
последовательности.
Последовательность называется фундаментальной,
если для всякого е > 0 существует такой номер /V,
что
Цхп — хт|| < е,
как только п, m> N. Легко показать, что если
хп -*х0, то последовательность хп, п=1, ..., фунда-
ментальна. Действительно, так как
11хп —х0|| ->0
при п —*оо, то для данного 8 найдется такой номер N,
что
8
II Хп Xq II < ~2~
для всех п> N, Пусть теперь т> N. Тогда
II Хп Хт II = II ^хп ^о) (*0 Хт) II
< II Хп ~ Хо || + || Х0 ~ Хт || < 8.
23
Здесь использовано третье свойство нормы, указан-
ное в ее определении.
Пусть теперь нормированное пространство В та-
ково, что для всякой фундаментальной последова-
тельности хп найдется такой элемент хоеВ, что
хп~*х0. Такое пространство называется полным. Пол-
ное нормированное пространство называется про-
странством Банаха или банаховым пространством.
Имеет место следующая теорема [1].
Теорема 1. Если В — пространство Банаха, то
для того, чтобы подмножество X* пространства В*
было слабо* бикомпактным, необходимо и достаточ-
но, чтобы оно было слабо* замкнутым и существо-
вала такая константа R, что
||х*||-</? для всех
Во всяком линейном пространстве можно опреде-
лить сумму двух множеств Хх и Х2 следующим об-
разом: Xi+X2 есть множество, состоящее из элемен-
тов xi + x2, где XieXb х2 е Х2. Пусть рассматривае-
мое пространство есть пространство В*, а X* и X* —
его подмножества.
Теорема 2. Если X*, X* слабо* замкнуты и
Х2 — слабо* бикомпактно, то множество X* + Х2
слабо* замкнуто.
Можно также определить произведение множества
в линейном пространстве на число. Если X cz L, то
XX есть множество, состоящее из элементов Хх,
хеХ. Через эти две операции уже определяется сум-
ма вида XiXi + X2X2, которая очевидным образом со-
стоит из элементов XiXi + X2x2, х\^Х\, х2еХ2.
Приведем два примера банаховых пространств,
которые чаще всего встречаются в экстремальных
задачах.
Пространство Еп. Это пространство всех ц-мерных
векторов x = {xi, ..., хп}, в котором сложение и ум-
ножение на число определено обычным образом:
х + У = {х{ + уь • • хп + уп},
Кх = {Ххь ...» Ххц}.
24
Норма в Еп задается формулой
Любой линейный функционал из (£п)* задается фор-
мулой
п
х* (*) = 2
z=i
где а = {аь ..., ап} — также некоторый вектор п-мер-
ного пространства. Таким образом, любому х*е(Еп)*
соответствует однозначным образом некоторый век-
тор а. Обратно, предыдущая формула показывает,
что любому а е Еп соответствует некоторый непре-
рывный функционал х*. Более того, сумме функцио-
налов соответствует, как легко проверить, сумма
соответствующих векторов, а произведению функцио-
нала на число — произведение вектора на число. По-
этому пространство (£п)* можно отождествить с
n-мерным векторным пространством.
Сильная топология в (£п)* определяется нормой
II X* II = sup 2	= 1/ ij = IIЯII-
||Х||<1 4 = 1	Г 4 = 1
Таким образом, (£n)* не только есть простран-
ство /г-мерных векторов, но и норма функционала
оказывается совпадающей с нормой соответствую-
щего ему вектора. Значит, сильная топология в (Еп)*
совпадает с топологией Еп и (£’n)*=£n.
Нетрудно показать, что в конечномерном прост-
ранстве слабая* топология и сильная топология сов-
падают, так как они определяют одинаковые системы
открытых множеств. Поэтому в сопряженном к Еп
пространстве нет различия между сильной и слабой*
сходимостью, замкнутостью, понятие компактности
совпадает с понятием бикомпактности.
При оперировании с конечномерным простран-
ством удобно ввести понятие скалярного произведе-
ния одного вектора на другой, которое обозначается
25
как (а, х):
п
(а, х) = 2 ai^b
Г = 1
В этих обозначениях
х*(х) = (а, х),
II х И = /(х, х).
Пространство С [0, 1]. Это пространство состоит
из всех непрерывных на отрезке [0, 1] функций, при-
чем норма определена формулой
II х|| = max | х(/) |.
с 1
Сходимость в этом пространстве совпадает с равно-
мерной сходимостью последовательности функций
хп(/) к х0(/). Пространство непрерывных функцио-
налов С* состоит из функционалов вида
1
х(х(0)= J x(t)dg(t), g(0) = 0,
О
где g(t)—функция ограниченной вариации. Норма
||х*|| определяется выражением
||х ||= Var g(0,
где
k
Var g(0 = sup 3l£(M-£&-i)l
/ = ]
и верхняя грань берется по всем разбиениям tit
i = 0, ..., k, /о = О, th= 1.
В заключение этого беглого изложения элементов
функционального анализа введем еще понятия про-
изводной оператора. Пусть оператор А (х) отобража-
ет пространство В в В}. Говорят, что оператор Д(х)
дифференцируем по Фреше в точке х0 е В, если су-
ществует такой линейный оператор /Г(х0): В—>ВЬ
что
А (х) — А (х0) =А' (х0) (х — х0) +у Uo, х — х0),
26
где r(x^z) такова, что
Оператор А (х) дифференцируем по Гато, если
A (xq + А/б) — А (х0) ~АД7 (хо) е + г (хо, Аб?),
где г(х0, Ае) такова, что
lim 1|Г(ХО Ле)Ц =0
Х->0 Л
Оператор-Д'(%о) называется в первом случае про-
изводной Фреше, а во втором — производной Гато.
Из того, что Д7(х0) есть производная Фреше, сле-
дует, что он является и производной Гато, однако
обратное верно не всегда.
Напомним, что оператор А называется линейным,
если он непрерывен и
А (х + у) = А (х) + А (у),
Д (А,х) = АД(х).
Для линейного оператора можно определить сопря-
женный к нему оператор, . обозначаемый Д*. Если
А—линейный оператор, то для всякого xj е В*
' р (х) = х* (Дх), х^в, х>в;
есть, очевидно, линейный непрерывный функционал
на В.
Таким образом, каждому х* В* можно поста-
вить в соответствие некоторый функционал х* е В*
так, что
х*(х) = х*(Дх)
для всех х^В. Если обозначить этот функционал
через Д*Х1, то оказывается, что Д* есть линейный
оператор из В* в В*. Таким образом, сопряженный
оператор определен следующими соотношениями:
Д*: в;->в*,
Д*х*(х) = х*(Дх).
27
2. Выпуклые множества. Понятие выпуклого мно-
жества играет важнейшую роль в исследовании экс-
тремальных задач. В сущности вся теория необхо-
димых условий есть развернутое следствие теоремы
отделимости выпуклых множеств.
Определение 9. Множество X в линейном
пространстве L называется выпуклом, если из
Xi е X, х2 X следует, что и
Х1%1 + Л-2-^2 X
для всех
Х1, Х2 О, Л1+%2=1«
Иными словами, множество выпукло тогда и
только тогда, когда вместе с двумя точками оно со-
держит и весь отрезок, их соединяющий.
Из определения выпуклости сразу же следует
такое свойство. Если множество X выпукло, то вме-
сте с точками Xi, 1=1, п, оно содержит и точку
п
X =
Z = 1
(2)
где
2^ = i,
Z = 1
Xz>0.
Доказательство этого факта проводится по индук-
ции. Для п = 2 он следует из определения. Пусть он
установлен для n = k—\. Пусть в (2) n = k и все
Xi > 0, 1=1, ..., k. Если некоторое Хг = 0, то дело
сводится уже к рассмотренному случаю n = k— 1.
Положим
X/ —	, i — 2, ..., k, К — Х^ + ... + Х^
Тогда
k
Sx' = i
i=2
и точка
k.	k
X = ^ \xl = Y 2 Xtx. e= X
i~2
28
по предположению индукции. Тогда
х=\\х{ + Кх,	*1 е X, х X,
и так как Х| > О, X > 0 и
k
A,t + X =	1,
1 = 1
то по определению выпуклого множества х е X, что
и требовалось доказать.
Пусть теперь В есть пространство Банаха. Ос-
новное свойство выпуклых множеств, которое делает
эти множества таким ценным орудием при исследо-
вании экстремальных задач, дается следующей тео-
ремой — теоремой об отделимости выпуклых мно-
жеств.
Теорема 3. Любые два непересекающихся вы-
пуклых множества X и Y в банаховом пространстве,
одно из которых содержит внутреннюю точку,
могут быть разделены некоторым ненулевым линей-
ным функционалом, т. е. найдется такой ненулевой
функционал х* е В*, что
х*(х) <х*(у)
для всех х е X, у е У.
Примечание 1. Точка х0 е А называется внут-
ренней точкой подмножества А, лежащего в неко-
тором топологическом пространстве, если найдется
такая окрестность Q этой точки, что ficz/1. В рас-
сматриваемом случае пространства Банаха точка х0
есть внутренняя точка множества X, если для неко-
торого г все точки, удовлетворяющие неравенству
Их —Xoll < Г,
принадлежат множеству X.
Примечание 2. Если пространство конечно-
мерно, требование о наличии в одном из множеств
внутренней точки, которое содержится в формули-
ровке теоремы 3, можно опустить.
В случае, когда множества X и Y замкнутые, тео-
рема 3 допускает уточнение.
Теорема 4. Если Хи Y — непересекающиеся
замкнутые выпуклые множества из В, причем Y
29
бикомпактно, то существует такой непрерывный ли-
нейный функционал х* В* и также константы с и
е > О, что
х* (х)	с — е < с х* (г/)
для всех х е X, у е Y.
Следствие. Если X замкнутое выпуклое мно-
жество из В и х0 е X, то существует такой функцио-
нал Xq В*, что для всех х е X
х* (х) С Хо(х0) - е, Vx X
где е — некоторое положительное число.
В самом деле, множество, состоящее из одной
точки, очевидно, бикомпактно.
Нам придется рассматривать выпуклые множества
В пространстве В*, сопряженном к данному простран-
ству Банаха В. В этом пространстве особо важными
будут так называемые регулярно выпуклые множе-
ства.
Определение 10. Множество Х*сВ* назы-
вается регулярно выпуклым, если для каждого функ-
ционала х^ ё= X* найдется такой элемент Хо е В, что
х (хо) < хо (хо) ~~ е
для всех х* еХ* и некоторого 8 > 0.
Определение 10 задает регулярно выпуклое мно-
жество через свойство отделимости. Следующая тео-
рема [52] показывает, как может быть охарактеризо-
вано это множество через свойство выпуклости и
слабой* замкнутости.
Теорема 5. Множество X* регулярно выпукло
тогда и только тогда, когда оно выпукло и слабо*
замкнуто.
Таким образом, если множество X* выпукло и
слабо* замкнуто, то любой функционал х*, не при-
надлежащий ему, может быть отделен с помощью
некоторого элемента х0 В.
Если множество X не является выпуклым, то мож-
но образовать наименьшее выпуклое множество, со-
держащее X, которое называется его выпуклой обо-
лочкой и обозначается через соХ или [X]. Данное
определение выпуклой оболочки годится для мно-
го
жества X из любого линейного пространства. Если
к тому же рассматриваемое пространство L есть ли-
нейное топологическое пространство, то можно вве-
сти понятие замкнутой выпуклой оболочки соХ, ко-
торая определяется как наименьшее выпуклое зам-
кнутое множество, содержащее X.
Легко видеть, что со X состоит из всех точек х,
представимых в виде выпуклой комбинации точек
из X, т. е. из точек х, представимых в виде
х =	Л^х^, X/ X, 2i = 1,	0.
i=1	t=l
Это непосредственно следует из того, что множество
всех точек, образованных как выпуклая комбинация
точек из X, выпукло и любое выпуклое множество,
как это было показано выше, должно содержать все
выпуклые комбинации своих точек.
Приведем некоторые свойства выпуклых оболочек.
Лемма 3. Для произвольных подмножеств X
и Y линейного пространства L:
1) со(аХ)=асоХ, со (Х+ У) =со Х + со У.
Если L есть линейное топологическое простран-
ство, то
2) со (X) ==_со (Х)-__	_
3)£сли _соХ и со У бикомпактны, то co(XU У)=
= co(coX U со У).
В частности, если X и У бикомпактны и выпуклы,
то co(XUK) = co(XUF).
Примечание. Черта над множеством означает замыкание.
В конечномерном пространстве выпуклая оболочка
множества обладает одним специфическим свойст-
вом, которое оказывается чрезвычайно полезным и
из которого следует ряд тонких результатов в тео-
рии чебышевских приближений и теории моментов.
Теорема 6. Если X — подмножество п-мерного
пространства Еп, то любая точка из со X предста-
вима в виде выпуклой комбинации не более чем
(п+Л)-й точки из X.
31
Доказательство. Как уже указывалось
выше, любая точка со X представима в виде
k
X = 2 %l X.
i = 1
Допустим, что k > n +1 и все %г- > 0. (Если не-
которое 2ч = 0, то число k может быть уменьшено.)
Введем векторы Уг (n +1)-мерного пространства,
образованные так:
И71
Поскольку k > п+1, то число векторов Уг больше,
чем размерность пространства, в котором они лежат,
и поэтому они линейно зависимы, т. е. найдутся та-
кие не все равные нулю числа аг-, что
k
5 a.i/i = 0
1	= 1
или в покомпонентном виде
k	k
2	= 0,	5 а, = 0.
i	= 1	i = 1
Поскольку аг- не все равны нулю, а их сумма равна
нулю, то среди аг- найдутся положительные. Положим
теперь
Me) = ^-saf.
Тогда
k	k	k
2	М8) = 2 К -8 2 щ = 1-
г=1	i=l	i=1
Кроме того, так как Хг>0, то при малых еХг(е)>0.
Будем теперь увеличивать 8 от нуля до тех пор,
пока какое-либо Хг(е) не обратится в нуль. Посколь-
ку среди аг есть положительные, то это обязательно
произойдет при некотором е = 8о, 8о > 0. Тогда

причем хоть одно из Л/ равно нулю.
32
Теперь
k
х = 2 ^ixr
t=i
Действительно,
k	k	k	k
2 ^ixi = 2	- eoa;) xf = 2	- eQ 2 atxt = x.
i = l	r = l	z = l	i = l
Итак, точка x представлена в виде выпуклой ком-
бинации k точек Xi е X, причем хотя бы один коэф-
фициент обращается в нуль. Это значит, что
если х представима в виде выпуклой комбинации k
точек Xi е X и k> п + 1, то она представима в виде
выпуклой комбинации (k—1)-й точки.
Отсюда, собственно, и следует теорема, так как
с помощью описанной процедуры число k можно
уменьшать до тех пор, пока оно не станет равным
п+ 1.
Обратимся теперь к специальному классу выпук-
лых множеств — выпуклым конусам.
Определение 11. Множество К линейного
пространства называется выпуклым конусом, если
оно выпукло, и из того, что хе К, следует, что
Не К при любом А, > 0.
Нетрудно проверить, что К есть выпуклый конус
тогда и только тогда, когда из х, у е К следует
x + z/еЛ и ИеК для любого К > 0.
Если исходное пространство В есть пространство
Банаха, то каждый выпуклый конус /С cz В поро-
ждает некоторый другой конус К* в В*, который назы-
вается двойственным или сопряженным к конусу К.
По определению
К* = {х* : х* е В*, х* (х) > 0 для всех х е Л].
Так как из х*еК* и у* е К*, К > 0 следует, что
х* (х) + г/* (х) > 0,	Хх* (х)	0
для всех хеК, то /<* также представляет собой вы-
пуклый конус.
Приведем некоторые свойства конуса К*. Ясно,
что нулевой функционал х_* = 0 всегда принадлежит
К*. Если КФ В, т. е. К не совпадает со всем
3 В. Н. Пшеничный
33
пространством, то /<♦ содержит отличные от нуля эле-
менты. В самом деле, если К 4= В, то найдется такой
элемент Хо, который не принадлежит замкнутому вы-
пуклому множеству К, Тогда по следствию теоремы 4
найдется такой функционал xj, что
*0 (%) *о (хо) ”’е
для всех хеК, или, если обозначить xj =—х0,
х*(х)^х*(х0) + е.
Покажем, что
х*(х)>0
для всех хе К. Действительно, если х*(х.)<0 для
некоторого Xi е К, то, так как Xxi е Л для всех К > О,
X* (AxJ = Лх* (Xj) — ОО
при X—> +оо. В то же время из Кх\ е К должно сле-
довать по построению х*, что
X* (^х1)>х1 (хо) + е-
Полученное противоречие показывает, что
х?(х)>0
для всех х е К и х* есть ненулевой функционал, при-
надлежащий конусу_К*.
Лемма_ 4. 1) (#)* = №“.
2) х е К тогда и только тогда, когда
х* (х) > 0 для всех х* е К*.
3) Если х — внутренний элемент К, то
х*(х)>0 для всех х*<=К*, х* =# 0.
Доказательство. 1) Поскольку В — нормиро-
ванное пространство, то замыкание К конуса /< со-
стоит из точек самого К и из таких точек х0, для
которых существует последовательность хп е
хп —► х0. Поэтому, если х* е Д'*, то
х*(хп) >0
34
и в силу непрерывности %*
х* (х0) > О
для любой точки %о ^_К. Отсюда следует, что
(А")*. Ита^ X* cz (К)*. С другой стороны, так
как множество К шире множества К, то_в силу опре-
деления двойственного конуса Д*о(А)*. Поэтому
2) Если х^К, то по определению (А)*
х*(х) >0 для всех (К)*.
Но, как только что показано, Д*=(А)*. Поэтому ис-
следуемое неравенство выполняется, если х<=К.
Пусть теперь точка xQ такова, что
х* (*о) > 0
для всех х* е К*. Допустим, что х0 К. Тогда, как
показано при доказательстве_того, что К* содержит
ненулевые элементы, если КФ В, найдется такой
функционал х* е Д*, что
х* (*)	** (х0) + е, 8 > 0,
для всех х е К. Но так как Хх е К для любого
хе К и А > 0, то, устремляя X к нулю, получим, что
Подставляя 0 в предыдущее неравенство, по-
лучаем
-е>х,(х0).
Это противоречит тому, что х* е Д* и х* (х0) больше
нуля для всех х* е Д*.
3) Пусть х0 — внутренний элемент Д, т. е. най-
дется такое г > 0, что все х, удовлетворяющие не-
равенству
Их —х0|| <г,	(3)
также принадлежат Д. Для любого х* е Д*, х* Ф 0,
х*(х) > 0
при всех х е Д и, в частности, при всех х, удовлет-
воряющих (3).
По определению нормы функционала
|| х* || = sup х* (х)
11х|| <1
3*
35
найдется такой элемент е, Це|| 1, что
II X’II >**(*)> у 1Ю
Рассмотрим точку
Х1 = х0 - у е.
Xi удовлетворяет (3), ибо
IIX] - х0 || = || у е || = у II е II < г.
Поэтому X] е К и
х* (Х1) = х’ (х0) - у х* (е) > О,
или
№)> у *’(*)> у ПЛ >0,
(4)
что и требовалось доказать.
Лемма 5. Если К — выпуклый конус, то ко-
нус К* слабо* замкнут.
Доказательство. Необходимо показать по
определению замкнутого множества, что множество
всех х*, не принадлежащих К*, открыто. Для этого
достаточно показать, что если х^ К*, то найдется
такое открытое в слабой* топологии пространства в*
множество, которое содержит x*Q и не имеет общих
точек с К*. Тогда множество всех х*ё= К* будет от-
крыто как объединение всех таких открытых мно-
жеств, построенных для каждого х* ё= К*.
Пусть х* е /С*. Тогда по определению К* найдется
такое х0 е К, что
хо(хо) = а<°-
Определим множество
М = {х*: 2а<х*(х0)<0}.
Очевидно, что x*Q и М не имеет общих точек с
К*. Покажем, что М — открытое множество. Дейст-
вительно,
M = W(x0, | а |, х*)=(х*: |х*(х0)-х£(х0)| <| а |],
36
которое по определению является открытым множе-
ством в слабой* топологии пространства В*.
Лемма доказана.
3. Выпуклые функционалы. Более подробному изу-
чению выпуклых функционалов будет посвящен бли-
жайший параграф. Здесь мы остановимся лишь на
определении выпуклого функционала и на несколь-
ких его простейших свойствах.
Определение 12. Функционал р(х), опреде-
ленный для всех x<=L, где L — линейное простран-
ство, называется выпуклым, если для любых Аь
Х2 > 0, Х1+Хг=1 и любых Xi, x2^L выполняется
неравенство
+ Х2Х2) Xi Ц (%1) + А,2|1(Х2).
Если обозначить Л=ХЬ 1—А,=А,2, то последнее не-
равенство переписывается в несколько ином, часто
употребляемом виде
Хц(Х1) 4-(1 — А,) Ц (*2) ц(ХХ1+ (1 — Х)хг)
для всех X, О А, 1.
Пусть ц(х)—выпуклый функционал. Обозначим
для фиксированных х <= L и е <= L
ф(/) = р(х + te)\
ф(/)—выпуклая функция одномерного аргумента t,
— 00	t +оо.
Действительно,
Ф (Xj/j 4- А,2/2) — р- (х 4- (^1^1 4* А^2) в) = ц (Aq (х 4- t^e) 4-
4- А.2(х 4- /2^)) А^ц 4" t\e) 4" А,2ц (х 4" /2^)=
= А,1ф(#1)4-А,2ф(/2).
Итак, для ф(0 выполняется неравенство
Ф(Wi 4- W2)-С А,1ф(/1) 4- ^2ф(/2)«	(о)
Пусть to < /1 < t2 и
1 __ Л ~ ^0	\	_ 1	~ ^0
Л1 ~	/ __ /	> Л2	~ 1	~	_ /	•
42 — /-0	12 — 10
Заметим, что
Aq/2 4" Wo = 71—^2 + (1 “ тт_'72 Vo =
37
Поэтому неравенство (5) можно переписать в виде
ИЛИ
<pUi)-<pUo)	ф (*г) - ф Go)	(gj
t\ — ^0	^2 — ^0
Далее, пусть t_\ <tQ< t.
ср (Xi/+ Хг^-i) ^А1ф(/) + Х2ф (t-1).	(7)
Положим
Тогда легко видеть, что Xi, Х2 > О, М + Х2 = 1 и
М + W-i= /о-
Теперь неравенство (7) переписывается в виде
Ф Go) < ^т^Г1 <Р & + Т^Г~ Ч
ИЛИ
(/0 - t-1) Ф (/о) + (* - М Ф (<о) < (*о -1-1) Ф (0 + (t - to) ф (t-1),
ср(/о)-ф(/1)	ф(0-ф(М	/пх
/о — t-х	t — to
Доказанные неравенства (6) и (8) позволяют сде-
лать вывод, который мы сформулируем в виде леммы.
Лемма 6. Если ср(/)—выпуклая функция чис-
лового аргумента /, то функция
Y = <р(О-ф(М
t — ^0
определенная при t > /0, не убывает с ростом t и
ограничена снизу.
Следствие. Пусть
ф(0 =ц(х+/е),
где ц(х)—выпуклый функционал. Положим to = Of
i = k. Тогда отношение
у	+	(х)
Л *
определенное при К > 0, не убывает с ростом X и
ограничено снизу.
38
Лемма 7. Если ц(х)—выпуклый функционал,
то в каждой точке х для любого направления е су-
ществует производная по направлению
дц (х) = цт ц (х + Хе) - р, (х)
х->+о
Доказательство. Так как отношение
ц (х + Хе) - ц (х)
X
убывает при Х-* + 0 и ограничено снизу, то по из-
вестной теореме анализа оно имеет предел при
X—►+0. Но существование этого предела и означает
существование производной по направлению.
§ 1. СВОЙСТВА ВЫПУКЛЫХ ФУНКЦИОНАЛОВ
Пусть ц(х)—произвольный выпуклый функцио-
нал. Всюду в дальнейшем мы будем предполагать,
что если X cz В и
\\x\\<k
для всех х<=Х, то найдется такое число С, что
для всех х<=Х. Такие выпуклые функцио-
налы мы будем называть ограниченными.
Введем следующее
Определение 1.1. Множеством опорных функ-
ционалов к ц(х) в точке х0 называется множество
Af(x0)czB*, удовлетворяющее условию
Л1(.Го) = {х*: /ей*, jli(x) —
х*(х — Xq) всех х е В}.
Существование такого множества для любой точки
Xq^B устанавливает следующая
Теорема 1.1. 7И (х0) — не пусто, выпукло, сла-
бо* замкнуто и ограничено.
Доказательство. Положим Во = £'1 X В и рас-
смотрим в этом пространстве множество
Z = {{a, х}: а>ц(х)}.
Это множество выпукло, так как из того, что
> ц(%1), а2>н(%2), следует, что для любых Хь
39
Z.2	0; X]+X2=l
Aqcq + Z2a2 > Z, (xj + Л2ц (x2) p (XjXj + Л2х2)
в силу выпуклости ц(х). Кроме того, множество Z
содержит внутренние точки. В самом деле, по пред-
положению, найдется такое Со, что
ц(х) <с0
для всех х таких, что ||х— х0||1. Положим а0=
= Со+1. Очевидно, что точка {ао, ^о} Z. Тогда все
точки {а, х}, удовлетворяющие условиям
|a-aol<4’ Их-хо1К Г (1-1)
также принадлежат Z, ибо для таких {а, х}
1 । 1 \
« > «о - у = £о + ^-> Ц(х)
по определению с0.
По определению Z это множество не имеет общих
точек с лучом L
£ = {{а, х0}: а<н(х0)}.
Поэтому существует такое число с и функционал
у*^.В* [1], не равные одновременно нулю, что
са + //*(х) > сц(х0) +//*(х0)	(1.2)
для всех {а, х}е2. Полагая здесь х=х0, получим
с (а — ц (х0)) >0
для всех а>ц(х0). Отсюда следует, что с>0. Од-
нако если с = 0, то (1.2) показывает, что
г/*(х — х0) > 0
для всех хеВ, что невозможно, так как при с = 0
г/* =# о.
Таким образом, с > 0. Полагая в (1.2) а = р(х),
получаем
р. (х) - р. (х0)> - - у* (х - х0),
т. е. х* =у* принадлежит множеству Af(x0). Тем
самым доказано, что Л4(х0) не пусто. Выпуклость и
40
слабая* замкнутость Л4(х0) проверяются элемен-
тарно.
Покажем, что М (х0) ограничено. Допустим про-
тивное. Тогда найдется такая последовательность
х* (х0), что || х* || -> + оо. Пусть уп е S, где S —
единичный шар в В, таковы, что
Положив xn = xQ+yn, получим, что
ц (х„) - Н (х0) > х*п (Уп) > || х* || - е,
откуда следует стремление ц(хп) к бесконечности
при п —► оо. Но ||хп — XoIKl, и мы приходим к про-
тиворечию с ограниченностью ц(х) на ограниченном
множестве.
Роль множества М (х0). при исследовании экстре-
мальных задач, в которых участвуют выпуклые функ-
ционалы, выясняет
Теорема 1.2. Производная по направлению
дц _ ц (х^ + Ле) - ц (х0)
~^о	*
существует при любых х0 и е, и справедлива фор-
мула
max х’(е).	(1.3)
06	х*<^М (Хо)
Доказательство. Существование производ-
нои по направлению следует из результатов, по-
лученных во введении. Там же доказано, что
ц (х0 + Ле) - ц (х0)
=--------Л-------
есть неубывающая функция Л.
Докажем формулу (1.3). Для любого х* е М (х0)
по определению имеем
ц (х0 + Ле) — ц (х0) > Лх* (е),
т. е.
ц (хр + Ле)- |л (хр) > * / ч
41
для всех х* s М (х0) и X > 0. Поэтому
др,	♦ , ч
~дГ> .™х х
х*^М
Предположим, что для некоторого е0
^-> шах х’(е0).	(1.4)
иеЧ Х*^М (х0)
Рассмотрим в В0=Е{ X В луч
L = j(a, х}: а = р(х0) + Л-^-, х = х0 + А.е0, Л>о|.
Так как <р(Л.) не убывает при возрастании X, то
-^-<<р(Л.) и
ц (х0 + Хе0) > ц (х0) + X .	(1.5)
Отсюда следует, что определенное выше множе-
ство Z и луч L не имеют общих точек. Действитель-
но, допустим противное. Это значит, что для некото-
рого Л > 0 точка {ai, xj, где
«1 = И (хо) + %0	,
Х1 = Хо + Л0в0,
принадлежит множеству Z и является его внутрен-
ней точкой, т. е.
ои > Ц(Х1)
и для достаточно малых б > 0
ai — б p(xi).
Но по определению оц и Xi из последнего неравен-
ства следует
/?||
Н (х0) + А»о — б ц (х0 + Хоео),
а это противоречит (1.5).
Итак, Z и L не имеют общих внутренних точек,
и поэтому (теорема 3 Введения) существует такое
число с и функционал у* В*, что
са + у* (х) > с (н(х0) +	+ у” (х0 + ^е0) (1.6)
42
для всех а, х и X таких, что а>ц(х), При
этом с и у* не равны одновременно нулю. Анало-
гично тому, как это делалось при доказательстве тео-
ремы 1.1, можно показать, что с > 0. Полагая в (1.6)
а = ц(х), Х=0, получим
Н(х)-м.(хо)>-7^(х-хо),
т. е. х* = — у / ее Л1 (х0). Далее из (1.6) следует,
неравенство
|Х (х) - ц (х0) > х* (х - Х0) + Л - X* (во)] .
Положив здесь х = хо, получаем с учетом того, что
% > 0,
что противоречит (1.4).
Теорема доказана.
Замечание 1. Формула (1.3) является обоб-
щением хорошо известной формулы
которая справедлива в случае, когда функционал
ц(х) дифференцируем по Фреше [7] в точке х0.
Множества Л4(х0) для выпуклых функционалов
играют такую же роль, какую играют обычные про-
изводные в конечномерном случае. И так же, как
правила вычисления производных в конечномерном
пространстве значительно облегчают построение
условий экстремума, нижеследующие правила по-
строения множеств Л4(х0) для функционалов, полу-
ченных в результате некоторых операций над дру-
гими выпуклыми функционалами, позволяют строить
условия экстремума для сложных функционалов.
Прежде чем переходить к исследованию операций
над множествами Л4(х0), докажем лемму.
Лемма 1.1. Если и М2— выпуклые слабо*
замкнутые множества в В* и для всех е В
sup х*(е)= sup х*(е),
то М[ = М2.
43
Доказательство. Допустим, что найдется
такое	что х* ё= М2. Множество М2 — регу-
лярно выпукло. Поэтому найдется такое во, что
Но это противоречит условиям леммы. Таким обра-
зом, М2^> М\. Аналогично доказывается, что M2czMi,
откуда следует утверждение леммы.
Теорема 1.3. Если ц(х) =в]|Ы1 (х)+с2ц2(х),
Ci 0, с2^0 и pi(x), ц2(х)— выпуклые ограничен-
ные функционалы, то ц(х)—выпуклый ограничен-
ный функционал и
М(х0) =с1Л41(х0) +с2Л42(х0),	(1.7)
где М(х0), MJxo), М2(х0)—множества опорных
функционалов для р(х), щ (х) и ц2(х) соответственно.
Доказательство. Имеем
г	др,2 _
де 1 де ' 2 де
= £j max х* (в) + вг max х*(в) =
X* G (%0)	х* €= М2 (X)
= max х* (в).	(1.8)
v*G=clMl(Xo)+*M2 (Хо)
Нетрудно проверить, что ц(х) —выпуклый ограничен-
ный функционал.
Поэтому
4£ = шах х*(е).	(1.9)
ое х* е М (Хо)
Множество Л4(х0) выпукло и слабо* замкнуто в силу
теоремы 1.1. Так как множества Mi(x0) и Л42(х0) сла-
бо* замкнуты и ограничены, то (теорема 1 Введения)
они слабо* бикомпактны, и поэтому множество
с2Л42(хо) +’с2Л42(хо) слабо* замкнуто (теорема 2 Вве-
дения). Из соотношений (1.8), (1.9) и леммы 1.1 те-
перь следует требуемый результат.
Теорема 1.4. Пусть I — конечное множество ин-
дексов и для всех i^I рДх) —выпуклый ограничен-
ный функционал.
44
Тогда множество M(xq) для функционала
н(х) = тахцДх),
i «= I
который также является выпуклым и ограниченным,
дается формулой
М(хо) =
= |х*:3\>0, 2 Л.= 1, х* = 2 Л.хТ.хТеМДхо)!
I	i(=I (Xf)	’
где
I(.xo) = {i: it=l, и(х0) = ц/(х0)},
a Mi (xQ) — множества опорных функционалов в точ-
ке xq для функционалов цДх).
Доказательство. Докажем, что ц(х) — вы-
пуклый функционал.
В самом деле,
И (AqXj + Х2х2) = max Hz (^1*1 + Х2х2)
iez
max [AqHi (*i) + X2hz (x2)] Xq maxpf(xi) + X2 max (x2) =
i £ /	i G /	i e I
= (xi) +	(,x2).
Кроме того, если каждый из функционалов цДх)
ограничен в ограниченной области, то легко видеть,
что ц(х) обладает этим свойством.
Докажем в первую очередь, что множество
Л7=1х*: ЗЛ,>0, teZ, 2 \ = 1,
I	i е I (х0)
Х = . 2 Xi
I I (Х0)	J
выпукло и слабо* замкнуто.
Пусть
и
i / (Хс)
Тогда Л7 = со Д, где со Д обозначает выпуклую обо-
лочку множества Д. Далее, множества МДх0) вы-
пуклы, слабо* замкнуты и ограничены. Поэтому они
бикомпактны в слабой* топологии и со Л4Дх0) =
= Л4г(х0), где со (В) означает замкнутую выпуклую
оболочку множества В. На основании леммы 3 можно
45
написать
соЛ = со( (J со МДх0)) == со ( (J Mz(x0)) = со А.
i ее / (х0)	i / (х0)
Отсюда следует, что М = со А замкнуто в слабой *
топологии, ибо со А есть слабо* замкнутое множе-
ство.
Обозначим для каждого Х>0 через какой-либо
индекс из множества /(х0 + Хе). Так как множество /
конечно, то найдется такая последовательность
Xj —> 0, X; > 0, что = /° для всех /, / —► оо. Покажем,
что (° е I (х0) •
В самом деле, если Z°g=/(x0), то ц.о(х0)<ц(х0) и
в силу непрерывности ц(х0 + Хе) и цДхо + Хе) по X
при достаточно малых Xj выполняется соотношение
Мхо + М<(Л(хо +V)’
что противоречит тому, что t° <= / (х0 + ^е).
Далее из соотношения
р,(хо + Л/е)--м,(Хо) = HZo(x0 + A7g)--l4o(x0)
Л/	Л/
следует, что	Для любого fe/(x0)
ц (х0 + Хе) - ц (*о)	(*о + Хе) - ц/ (х0)
X	X
по определению ц(х) и /(х0), и поэтому
для всех ie/(x0). Отсюда можно сделать вывод, что
Но
4^-= шах х*(е)= шах
ое х*^м (хо)	---
i <= I (хо) де
шах
z е I (Хо)
де
шах у
/е/(хо) 1	1	i^I(x0)
дщ.
де
max X max xj(e) =
*- с= i V&O'
max max V X;x*(e)= max x’(e),
ie/(x0)X‘=l
46
Таким образом,
max х*(е)= max х" (е).
х* М (х0)	х* s= М
Применение леммы 1.1 теперь завершает доказатель-
ство теоремы.
Пусть теперь В и — два пространства Банаха,
а А—ограниченный линейный оператор, определен-
ный на В и отображающий В в Вь Пусть ц0(у)—вы’
пуклый ограниченный функционал, определенный
на Bi. Тогда легко видеть, что функционал
ц(х) =р,0(Ях)
есть выпуклый функционал, определенный на В.
Теорема 1.5. Если
ц(х) =ц0(Лх),
то множество опорных к р, (х) функционалов дается
формулой
М(х0) =Л*Мо((/о),
где уъ=Ахъ.
Доказательство. Во-первых, отметим, что
функционал ц(х) ограничен в ограниченной области,
так как ограничены цо(у) и оператор А. Так что
формула (1.3) для ц(х) справедлива:
Во-вторых,
ц(х0 + Хе) -ц (х0)
%
__ ц0 (Дх0 + %Ле) - ц0 (Дх0)	дц0 (Дх0) __
К	^-> + 0	<5 (Ле)
= max у*(Ае).
У*^М0 (г/о)
Таким образом,
= max А*у*(е)= max х*(е).
08	х*^А*Мо(Уо)
Отсюда после применения леммы 1.1 следует требуе-
мый результат.
Теорема 1.6. Пусть М — ограниченное выпук-
лое слабо* замкнутое множество в В* и
u(x) = max %*(%).
х* ем
47
Тогда
M(x0) = (x‘: х*^М, х*(х0) = р(х0)}.
Доказательство. Пусть х*0 таково, что
хг'еЛ1и х*(х0) = р.(х0). Тогда по определению ц(х)
Н (х) - р (х0) > х‘ (х) - х* (х0) = X* (х - х0),
т. е. х*0 <= М (х0).
Обратно, пусть М (х0), т. е.
р(х)-р(х0)>х*(х-х0).	(1.10)
Докажем, что x*Q^A4. Допустим противное. Так
как М выпукло и слабо* замкнуто, то оно регулярно
выпукло, и поэтому найдется такой элемент е, что
supx*(e)<x*(e).	(1.11)
х*^М
С другой стороны, так как максимум разности не
меньше, чем разность максимумов, то
max х* (х - х0) > р (х) - р (х0) > х* (х - х0).
х* е М
Положив здесь х — х0 = е, получим
max х* (е) х„ (е).
х* М
Но это противоречит (1.11). Таким образом, x*Q е М.
Докажем, что х* (х0) = Ц (х0). Допустим противное.
Так какх*^Л4, то это значит, что
хо (хо) < I1 (хо).
Из (1.10) тогда следует, что
ц (х) - х*(х) > ц(х0) - х* (х) = д > 0
для любого х. Положив х = 0, приходим к противо-
речию. Это полностью завершает доказательство тео-
ремы.
48
§ 2. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
В ПРОСТРАНСТВЕ БАНАХА
Основываясь на свойствах выпуклых функциона-
лов, изученных в предыдущем параграфе, мы по-
строим в этом параграфе теорию необходимых и до-
статочных условий для задачи выпуклого програм-
мирования.
Рассмотрим сначала следующую задачу. Пусть
в пространстве Банаха В задан выпуклый ограни-
ченный функционал р,(х) и выпуклое множество Q.
Выясним, при каких условиях точка х0 е Q дает ми-
нимум ц(х) на Q.
Пусть
ГХа={е: е<=В, + для некоторого X > 0}. (2.1)
Нетрудно проверить, что ГХо— выпуклый конус.
В самом деле, если е^ГХг, то найдется такое
% > 0, что	Если е\ = ае, а > 0, то х04-
+Л1в1 е Q при Xi = ~. Поэтому 61ЕГХо) откуда
следует, что ГХо — конус. Покажем, что ГХо — выпук-
лый конус. Для этого надо показать, что если
61ЕДО и е2ЕД0, то ei + e2^rX0. Из того, что
ei е ГХо и е2 е ГХо, следует существование таких Xi
и Х2, больших нуля, что
Xo + M^l	Q,	й.
Пусть теперь а, р>0, а + р=1. Так как множество й
выпукло, то
+ +Р(X0 + W2) €= S2.
Положим теперь
п —	R =
А] + Лг ’ Р Xi + Хг *
Тогда
а (хо + Ai6i) + р (хо + Х2в2) =
откуда и следует, что ех + е2 е ГХо.
Выпуклый конус ГХо определяет множество на-
правлений, исходящих из точки xQi при малом сдвиге
вдоль которых точка х0 + Хе остается принадлежащей
4 Б. Н. Пшеничный
49
множеству Q. В самом деле, если А:0+^ей, то из
выпуклости множества Й следует, что
ссхо + Р (хо + Лв) ее Q
при всех а, р^О, а + р=1. Поэтому точка
Хо + РА,£ ЕЕ Q
при всех р, 0 р 4И, т. е. точка
Хо + б£ е= Q
при всех 6,
Докажем теперь теорему, которая дает необхо-
димые и достаточные условия минимума р(х) на
множестве Q.
Теорема 2.1. Для того чтобы выпуклый огра-
ниченный функционал р(х) достигал минимума в
точке х0 е Q, где Q — выпуклое множество, необхо-
димо и достаточно выполнение условия
ехаПМ(хо)^0.	(2.2)
Замечание. Здесь М (х0) — множество опорных
функционалов в точке х0 для р (х), а Г*о—конус,
двойственный к ГХо, т. е.
Г* = (х*: х* е В, х* (е)	0 для всех е е Г 1.
*0 I	' '	XoJ
Известно (лемма 5 Введения), что Г*о—выпуклый
слабо* замкнутый конус в В*.
Доказательство. Необходимость.
Пусть
р(х0)	р(х), хей,
но условие (2.2) не выполняется. Множество
Г*о — Л4(х0) выпукло и слабо* замкнуто. Действитель-
но, Г*о слабо* замкнуто, а Л4(х0) по теореме 1.1
слабо * замкнуто и ограничено в метрической тополо-
гии. Поэтому (теорема 1 Введения) Л4(х0) слабо*
бикомпактно и по теореме 2 Введения множество
Г*г —М(х0) слабо* замкнуто. Из выпуклости и сла-
бой* замкнутости F*Xq — Л4(х0) следует, что это мно-
жество регулярно выпукло.
В силу нашего предположения нулевой функцио-
нал не принадлежит множеству Г*о~ Л1(х0). Поэтому
50
найдется такой е0 е В, что
inf х* (е0) 6 > О
х* е Г'х<~М (Хо)
ИЛИ
inf x*(e0)^d + max х*(е0).	(2.3)
х*еЛФо)
Но так как Г*о— конус, то левая часть последнего
неравенства равна нулю. В самом деле, если
inf х* (е0) < О,
* ♦
X (= Г
Хо
то найдется такой функционал х* е Г*о, что
xi (ео) <
Так как — конус, то ах^ Г*Хо для всех а > 0.
Поэтому
.inf. х*(е0)<а<(е0)
Х ГХ0
для всех а > 0, откуда следует, что inf х(е0) =
х*^4о
= —оо.Но это противоречит неравенству (2.3), пра-
вая часть которого ограничена. Итак
inf х*(ео) = О.	(2.4)
* *
Отсюда следует, что еоеГТа (лемма 4 Введения),
где черта сверху обозначает замыкание в сильной
топологии пространства В. Кроме того, из формул
(1.3), (2.3) и (2.4) вытекает, что
дц (хр) <__§
де0
Так как еоЕГХо, то в ГХо найдется такое направле-
ние е, что
II е - е0|К-| ( sup ||х" ИГ1.
Z v X* €= М (Хо> J
4!
51
Поэтому
—= max х* (е) шах х* (е0) +
06 X* G= М (Х0)	X* €Е М (Хо)
+ шах х*(е — е0) =^ —6 +1| е —е0II sup ||х*|К~4.
х*е ,М (хо)	х* <= м (Хо)	z
Таким образом, для достаточно малых X х0+
Э-ХееЙ и р, (х0 + ^е)^ц(х0) — Л — , что противоречит
тому, что х0 — точка минимума р(х) в Й.
Достаточность. Пусть условие (2.2) вы-
полнено. Тогда найдется такой функционал х*, что
х0еЛ4(х0) и х*^Г*о, т. е.
ц(х) - Н (х0) > xj (х - х0)	(2.5)
для всех х и хо(е)^О для всех е е ГХо. Но если
хей, то легко проверить, что направление е=х — х0
принадлежит конусу ГХо, и поэтому
х* (х — х0)	0 для всех х g Q.
Сопоставление этого неравенства с (2.5) доказывает
достаточность условий теоремы.
Следствие. Для того чтобы точка х0 достав-
ляла минимум выпуклому ограниченному функциона-
лу |ш (х) в йч необходимо и достаточно, чтобы на-
шелся такой функционал х* е М (х0), что
%о (я) %о (х0)	(2*6)
для всех х Й.
Доказательство. В самом деле, если (2.6)
выполнено, то
и (х) - ц (х0) > х*0(х - х0) > О
для всех хей.
Обратно, если х0 — точка минимума, то по пре-
дыдущей теореме найдется такой функционал
x*Q е М (х0), что Xq <= Г*о. Это значит, что
xj(x — хе)>0
для всех хе й, откуда следует (2.6),
52
Если рассматривать теорему 2.1 как средство
эффективного построения необходимых и достаточ-
ных условий минимума, то легко заметить, что ми-
нимизируемый функционал и множество Q исполь-
зуются при ее формулировке не вполне равноценно.
Для построения множества М (х0) мы имеем раз-
витый аппарат, в то время как конус задан лишь
своим определением.
Следующая теорема в значительной мере устра-
няет этот недостаток и делает возможным применять
аппарат, развитый для построения М(х0), для ис-
следования г*о.
Теорема 2.2. Пусть множество Q задается не-
равенством
Q = {х: р, (х) < 0},
где ц (х) — выпуклый ограниченный функционал, при-
чем для некоторого Xj p(xi) <0. Тогда Г*о={О},
если р(хо)<О. Если ц(хо)=О, то
ГХо ~ {х * х = Y-^о» V 0, х0 М
Доказательство. Рассмотрим вначале случай
р(х0) <0. Тогда для любого е при достаточно малом
X в силу формулы (1.3)
р(хо + Ле) = |1(хо) + Л шах х* (е) + о (X) < 0.
X* G М (Х0)
Поэтому конус TXt совпадает со всем пространством
В, а С0 = {0}.
Пусть теперь р (х0) = 0. В этом случае конус Гжо
задается условием
/\0 = {е: р (х0 + Ке) 0 = р (х0) для некоторого X > 0}.
Отсюда следует, что если е е ГХо, то
0 > р (хо + Хе) — р (хо) > Хх* (е)
для любого х*е/И(х0). Поэтому ух*(е)>0 при
у-<0 для всех е^Гх>. Но это значит, что ух*
Докажем теперь обратное включение, т. е. что для
любого х* е Г’о найдется такое у<0 и XgeAl(x0),
что х* = YXq .
53
Допустим противное. Тогда найдется такой функ-
ционал х* е Г*о, что ах*ёМ(х0) при любом а < 0.
Более того, ax*eAf(x0) и при а = 0, ибо
0 > |л(%1) — ц(х0) > Х*(Х] — %о)
для х*еЛ4(х0), откуда следует, что М(х0) не содер-
жит нулевого функционала.
Рассмотрим множество ах* — М (х0) для всех а
•<0. Оно выпукло, слабо* замкнуто (ибо Л4(х0) слабо
замкнуто и бикомпактно) и не содержит, согласно
предыдущему, нулевого функционала. Поэтому най-
дется такое е В, что
ах*(е) > 0 > х*(е)
для всех а40 и х*еМ(х0). Но тогда
дн (*о)
де
= шах х*(е)<0,
X* €= М (Хо)
и поэтому е е ГХо. Более того, легко видеть, что е
есть внутренний элемент ГХо и поэтому. [4] х*(е) > 0
для всех х*еГ, а значит, х*(е) >0. Но это проти-
воречит тому, что ах*(е)>0 для всех а<^0.
Полученное противоречие показывает, что любой
функционал х" е Г*о представим в виде х* = ух*, где
уС 0 и Xq^M(xq). Ранее было показано, что ух*е Г*
при любом у<0 и xj е М (х0). Отсюда следует до-
казательство теоремы.
Приступим теперь к выводу необходимых и доста-
точных условий оптимальности для случая, когда об-
ласть Q задается различными наборами равенств и
неравенств.
Теорема 2.3. Для того чтобы выпуклый ограни-
ченный функционал ц(х) достигал своего минимума
на всем пространстве В в точке х0, необходимо и до-
статочно выполнение условия
0 g= М(х0).
Доказательство. Так как множество Q в дан-
ном случае совпадает со всем пространством, то ГХо =
= В, Г*Хо = {0}, и результат непосредственно следует из
теоремы 2.1.
54
Теорема 2.4. Пусть множество й задается систе-
мой неравенств
Цг(х) ^0, 1=1,..., п,
где Цг (%)—выпуклые ограниченные функционалы и
найдется такая точка хь что рг(%1)<0 для всех
i = 1, ..., п. Тогда, для того чтобы выпуклый ограни-
ченный функционал ро(%) достигал своего минимума
на Й в точке х0, необходимо и достаточно существо-
вание таких х* е Mi (х0), i = 0, 1, ..., п, и чисел
что
п
х0 = Xzxz, Xzpiz (х0) = 0, Xz 0, i = 1, ..., п.
Доказательство. Введем функционал
ц(х) = шах цДх).
1 < i < п.
Тогда область й может быть задана в виде одного
неравенства
й = {х: ц(х) С 0}.
Если х0 таково, что ц(х0) <0, то доказательство сле-
дует из теорем 2.1 и 2.2, ибо в этом случае Г*о = {О},
М(х0) должно содержать нулевой функционал Xq = 0,
и требования теоремы будут удовлетворены, если по-
ложить Xi = 0, i = 1, ..., п.
Допустим, что ц(х0) = 0. Тогда по теореме 2.2 Г*о
состоит из функционалов, представимых в виде ух*,
где у40и х*еМ(х0). С другой стороны, на основа-
нии теоремы 1.4 х*еЛ4(х0) тогда и только тогда,
когда для него справедливо представление
X* = 2 Ъх*,,
i е= I (х0)
Где X. 0, S Xz = 1, х* (х) и множество
i г I (х0)
/ (х0) СОСТОИТ ИЗ тех индексов I, ДЛЯ которых Цг(х0) =
= ц(х0) = о.
Таким образом, функционал х* принадлежит
тогда и только тогда, когда он представим в виде
х = у 2 Xzx’, у 'С 0.
i / (Хо)
55
На основании теоремы 2.1 в точке х0 s Q минимум
достигается только тогда, когда в Л4о(^о) найдется та-
кой функционал что x*q е Г*о. Но из предыдущего
следует, что этот функционал представим в виде
Положим =yKi для (х0) и Ki = 0 для I^I(Xq).
Тогда имеет место представление
Х0 = 2 hjXr
1 = 1
При этом Кг^.0, ибо у<0, а Хг>0. Кроме того, со-
отношение кгщ(хо) =0 выполняется для всех г, ибо
если (х0), то цДхо) =0, если же ie/(x0), то
Ki = 0.
Теорема доказана.
Теорема 2.4 дает необходимые и достаточные ус-
ловия минимума в задаче выпуклого программирова-
ния, когда область Q задана системой неравенств.
Для того чтобы получить условия минимума в том
случае, когда область Й определяется рядом равенств
и неравенств, удобнее всего воспользоваться теоре-
мой Куна — Таккера. Доказательство этой теоремы
можно найти в [11]. Здесь она приводится для пол-
ноты изложения. Кроме того, далее будет показано,
как эта теорема может быть получена как следствие
более общей теоремы 4.1 § 4.
Теорема 2.5. (Куна — Таккера). Пусть цг-(%),
i = —m, ..., — 1, 0, 1, ..., п, — фукнционалы над не-
которым линейным пространством Е, причем цДх)
выпуклы для 1 = —пг, ..., —1, 0 и линейны для
i = 1, ..., п. Тогда, для того чтобы точка xQ(=E до-
ставляла минимальное значение функционалу ц0(х)
при ограничениях
(х)	0, i = — m, ...» — 1,
н, (%) = о, * = I, • • •, Я,
хеХ,
56
где X — некоторое выпуклое множество в Е, необхо-
димо существование таких Хг-, i = —гпу ..., п, что
2	2 Мч(х)
для всех х е X. Кроме того, Ki 0 для всех i =
= —m, ..., О и KiЦг (х0) = О для i = —m, ..., п, i =# О.
Если Хо > О, то условия и достаточны.
Теорема Куна — Таккера носит глобальный харак-
тер. Следующая теорема дает необходимые и доста-
точные условия в дифференциальной форме. Такая
форма часто на практике является наиболее удобной.
Теорема 2.6. Пусть В — пространство Банаха.
Для того чтобы точка х0* была решением задачи ми-
нимизации
min Но(Д
Hi (х) О, — rn i — 1,
Hi (х) = 0, 1 п,
хеХ,
где цг(х) выпуклы для и линейны для f > О, а
X — выпуклое подмножество пространства В, необхо-
димо существование таких констант Кг и функциона-
лов х* е Mt (х0), что
Ktx\ (х) для всех х е X,
Ki 0, ХгЦг (х0) = 0 для i <0, Хо > 0.
Если Хо > 0, то условия являются и достаточными.
Доказательство. Теорема является непосред-
ственным следствием теорем 2.5, следствия теоремы
2.1 и теоремы 1.3.
§ 3. КВАЗИДИФФЕРЕНЦИРУЕМЫЕ
ФУНКЦИОНАЛЫ
Нетрудно заметить, что при доказательстве почти
всех результатов § 1 относительно техники вычис-
лений производных по направлению выпуклость
57
рассматриваемого функционала в явной форме не ис-
пользовалась. Основой всех рассуждений служила
формула
= шах х(е).	(1.3)
ое	(хо) •
Целесообразно ввести следующее определение.
Определение 3.1. Функционал называется ква-
зидифференцируемым в точке х0, если существует та-
кое выпуклое слабо* замкнутое множество Л4(х0), что
имеет место формула (1.3).
Обсудим, насколько широк класс квазидифферен-
цируемых функционалов. Во-первых, ясно, что в него
входят все дифференцируемые по Гато функционалы,
ибо в этом случае в качестве Л4(х0) может быть вы-
брано множество, состоящее из единственного функ-
ционала xj, являющегося производной Гато от ц(х),
в точке х0. Во-вторых, результаты § 1 показывают, что
квазидифференцируемыми являются все выпуклые
функционалы.
Далее, теоремы 1.3 и 1.4 остаются справедливыми,
если в их формулировках заменить слова «выпуклый
функционал» на «квазидифференцируемый функцио-
нал». Поэтому сумма с положительными коэффициен-
тами и операция взятия максимума от конечного чис-
ла функционалов не выводят нас из класса квази
дифференцируемых функционалов.
Следующая теорема является обобщением тео-
ремы 1.5.
Теорема 3.1. Пусть Во и Вх—пространства Ба-
наха, [i(y) —квазидифференцируемый функционал
над Bi, удовлетворяющий условию Липшица, а
А (х): Во Bi — дифференцируемый по Гато опера-
тор. Тогда
цо(х) = ц(Л (х))
есть квазидифференцируемый функционал над BQt
причем
ЛМ*о) = (<М(Л(хо)),
где Аз— производная Гато от А (х) в точке х0.
58
Доказательство.
Но (х0 + Хе) - Цо (*о) __ р(Л(х0 + Хв))-ц(Л (х0)) _
X	X
[н (Л (х0) + ХЛде + г (Л)) - н (Л (х0) + ХЛ^е)] (
~	X	+
И (л (х0) + ХЛ^е) - |Х (Л (х0))
'Ь	X
lim -Ц^- = О.
Х->0 л
При X—>+0 правая часть этого равенства стремится
к величине
= тах у" (ло4
д(Лое) р*еМ(А(х0)) V 7
Отсюда следует теорема.
Покажем теперь, что в широком классе случаев
операция взятия максимума по параметру не выво-
дит из класса квазидифференцируемых функциона-
лов. Мы начнем с доказательства нескольких вспомо-
гательных утверждений.
Пусть ф(х, а)—непрерывный функционал пара-
метров х и а, где х принадлежит нормированному
пространству В, а а — элемент компактного тополо-
гического пространства Z. Образуем функционал
р(х) = шахф(х, а)
а е z
и обозначим
Z(x) = {a: aeZ, ф(х, a) = p(x)}.
Лемма 3.1. ц (х) — непрерывный функционал.
Доказательство. Имеем
ф’(х, а) = р(х)^ф(х, а0),
ф(х0, а)<И(х0) = Ф(х0, а0),
ае Z(х), aos Z(х0).
Вычитая эти неравенства, получаем
ф(х, а)-ф(х0, а)>ц(х)-р(х0)>ф(х, а0)-ф(х0, а0). (3.1)
59
При х —•> х0 правая часть стремится к нулю. В силу
компактности Z и непрерывности ф(х, а) по аргумен-
там левая часть также стремится к нулю.
Действительно, допустим, что разность
ф(х, а)—ф(хо, а), aeZ(x)
не стремится к нулю, когда х —>х0. Это значит, что
найдется такая последовательность х^ —>х0, аг е
е Z(x;), что
IФ(*й «г) — Ф(*о, аг) | > д > 0.
Поскольку Z компактно, то из последовательности
ai можно выбрать сходящуюся. Не ограничивая
общности, будем считать, что сама исходная после-
довательность аг сходится к ао е Z.
Переходя в последнем неравенстве к пределу, по-
лучаем в силу непрерывности ф(х, а)
0>б>0.
Полученное противоречие показывает, что левая
часть (3.1) стремится к нулю, что завершает дока-
зательство леммы.
Лемма 3.2. Для любой окрестности acZ мно-
жества Z(x0) существует такое б, что
Z(x) cz со,
как только ||х— ХоН-^Сб.
Доказательство поведем от противного. Пусть для
некоторой окрестности со0 существует такая последо-
вательность хг-—> Хо, а в множествах Z(xJ такие точ-
ки а^ что aiе (Оо- Так как Z—компактно, то мож-
но считать, что аг -+ а0.
По определению
|l(Xi) = ф(хй а0.
Переходя к пределу, получаем, что
|ы(хо) = ф(х0, а0),
т. е. ao^Z(xo). Но это невозможно, ибо а^—>ао и
а, е= too, и если мы допустим, что aoeZ(xo) с: со, то
в силу открытости множества ооо аг (оо Для доста-
точно больших /, что приводит к противоречию.
60
Исследуем теперь дифференциальные свойства
функционала ц(х). Пусть х(Х) = х0 + Хе. Подставляя
в (3.1) и деля это неравенство на X > О, получим
ф(х (X), а)-ф(х0> а) ц (х (X)) - р, (х0)
%	X
<р(х(Х). а0) Ф(хо,а<>) aeZ(x(x)). (3.2)
Л
Из левой части неравенства получаем, что если
<р(х, а) дифференцируема по направлению е, то
lim ц (х (X)) - ц (х0) dgp (х0, а0)
или, так как ао — произвольный элемент Z(x0),
X
1.	ц (х (X)) - ц (хр)	дф (х0> а)
ПГП	а	оИр
хТ+О	Л	aezw	06
(3.3)
Допустим теперь, что ф(х, а) дифференцируема по
направлению е в точке х0, т. е. для X > О
ф(х0 + Хе, а) = ф(х0, а) 4- Л	4~ Ху U, а)
и при этом у(Х, а) —>0 при X —> + 0 равномерно по а.
Тогда производная — непрерывна по а как
равномерный предел непрерывных функций
Ф (х0 4- Хе, а) — ф (х0, а)
X
и inf sup	°),ю
со => Z (Хо) а <= со с'е
sup	°)
aeZW де
В силу леммы 3.2 получаем из (3.2)
ц(х(Х))-ц(х0) Г<?ф(х0> а) . J
*	aS^ Г де	+ V (Л, а)]
при любом a>=>Z(xo) и достаточно малых к Переход
к пределу по X—» + 0 дает
77— ц (х (Л)) - ц (х0)	-11Г/ Oq (х0> а)
1 И И	А	''5^. о И р	,
Л->+0	Л	аесо
61
Учитывая, что со — произвольная окрестность, содер-
жащая Z(x0), окончательно получаем
ПЫ Mx W)-H(xo) с inf sup г>ф(х0,а) =
Л->+0	Л	cozdZ(xc) аеш
= sup 2*^1. (3.4)
a е= Z (х0)	ое
Сопоставление (3.3) и (3.4) приводит нас к следую-
щей теореме.
Теорема 3.2. Пусть ф(х, а)—непрерывный
функционал аргументов х и а, где х^ В, а а G Z
(Z— компактное топологическое пространство).
Кроме того, пусть
<р(хо + ^е, а) = ф(х0, а) + X	+ Ху (*, а) для Х>0,
причем у(Х, а)—>0 равномерно по а при X—>+0.
Тогда в точке х0 функционал
ц(х) = шах ср (х, а)
aez
дифференцируем по направлению е и
(5p,Uo)__ С11П дф(х0, а)	, _
де ••	<3’5)
Замечание 1. Нетрудно видеть, что условие
непрерывности по х и а может быть без всякого
ущерба заменено на условие непрерывности функции
Ф (х0 4- Хе, a) по X и а.
Замечание 2. Если ф(х, а)—выпуклые по х
,	д® (х0, а)
функционалы, то теорема выполняется, если ~~~^е	•
непрерывно зависит от а.
В самом деле, выпуклый функционал всегда диф-
ференцируем по направлению и отношение
Ф (х0 + Хе, а) — ф (х0, а)
X
стремится к а~ при фиксированном а, монотон-
но убывая [6] (см. также Введение, лемма 6). Но
тогда по теореме Дини [45] у(Х, а) стремится к нулю
равномерно по а.
62
Теорема 3.3. Если ср(х0 + Хе, а)—непрерывный
по к и а функционал, причем существует непрерыв-
ная для [0,1] и a^Z производная 	,
то имеет место формула
d[i(xQ) _ __ дф(х, а)
5	— 111 а. X	ч
де asz (хо) де
(3.6)
Доказательство аналогично доказательству пре-
дыдущей теоремы, за тем исключением, что при вы-
воде неравенства (3.4) необходимо воспользоваться
формулой Лагранжа
Ф (х0 + ке, а) - ф (х0, а) _ дф (х0 + I (к) е, а)
к	~ дк >
где 0 4^£(А,) и заметить, что
дф (х0 + ке, а) I _ дф (х0, а)
дЛ к=о~ де
Теорема 3.4. Если ср(х, а)—квазидифференци-
руемые в точке х0 функционалы, для которых выпол-
нены условия теоремы 3.2 при любом е, то р,(х)—
также квазидифференцируемый в х0 функционал,
причем
М (х0) = со U М (х0, а),	(3.7)
а £ Z (х0)
где Л4(х0, а)—множество функционалов в точке х0
для функционала ф(х, а), Л4(х0)—для функционала
ц(х), а со А означает слабое* замыкание выпуклой
оболочки множества А.
Доказательство. На основании теоремы 3.2
и определения квазидифференцируемого функциона-
ла получаем
sup	sup sup	(3.8)
ое a^Z (Хо) ие	а е z (Хо) х* ем (х0, а)
Но, как легко видеть, максимум в правой части равен
максимуму величины х*(е), когда х* меняется в опре-
деленном формулой (3.7) множестве 2И(х0). В самом
деле, М(х0) есть слабое* замыкание множества
63
точек вида
х-‘ = 3
где х’еМ(х0> а(.), 2jAz = 1, \>0.
Поэтому
**(е)= S \-Ч(е)^=тахЧ(е)^ sup sup х’(е),
i	a^Z (х0) х* е= м (х0, а)
и значит, в силу того, что верхние грани непрерывной
функции х*(е) аргумента х* по некоторому множе-
ству и по его замыканию совпадают,
sup х*(е)< sup sup х*(е).
х* е=М (х0)	a^Z (х0) х*^М (Хо, а)
Но, с другой стороны, М (х0) =>Л1(хо, а) для любого
a^Z(x0), и поэтому
sup х*(е)^ sup sup х*(е).
х* €= м (Хо)	af=Z (Хо) х*<^М (Хо, а)
Итак, указанные максимумы совпадают, и мы можем
написать
Для завершения доказательства теоремы осталось
заметить, что М(х0) выпукло и слабо* замкнуто по
самому определению.
Представление множества М (х0) в виде (3.7) не
всегда является эффективным. Мы сейчас укажем
частный случай, когда множество Л4(х0) можно опи-
сать более эффективно.
Теорема 3.5. Пусть ф(х, а)—дифференцируе-
мые относительно х по Гато и непрерывные по а
функционалы, причем производная х* о слабо * не-
прерывно зависит от х и а, где а изменяется в ком-
пактном топологическом пространстве Z. Тогда
ц(х) = max ср (х, а)
aeZ
есть квазидифференцируемый функционал, причем
множество М(х0) состоит из таких функционалов х*,
64
которые представимы в виде
х’(е)= Г х* (e)v(da),
Z (Хо)
(3.9)
где v — неотрицательная мера, полная вариация ко-
торой по Z(x0) равна единице.
Доказательство. Так как функция ф(х0 +
+ Ае, а) имеет производную по Л, равную
-^51 = г* (М
дх лх0+Ке,аЛс)>
которая в силу предположений теоремы непрерывна
по Л и а, то на основании теоремы 3.3 мы можем за-
ключить, что для любого е
др (х0)
де
= шах
а <= Z (х0)
dqp(x0, а)
де
= max х*(е),
а €= z (хо)
где х* =	— производная Гато от ф(х, а) в точ-
ке х0.
Из определения и свойств интеграла по мере сле-
дует, что для любого е
max
a g z (х0)
Хд(е) = тах
v *
Z (х0)
x*(e)v(da),
где максимум берется по всем мерам, описанным в
условиях теоремы.
Таким образом,
°" = maX J ха(еМ^“)-
V Z (ХР)
Для завершения доказательства осталось убе-
диться, что множество функционалов, представимых
в виде (3.9), выпукло, слабо* замкнуто и ограничено.
Но выпуклость очевидна.
Покажем слабую* замкнутость этого множества.
Для этого заметим, что каждую из рассматриваемых
мер можно рассматривать как элемент единичного
шара (полная вариация v равна единице) простран-
ства С*(Z) — пространства, сопряженного к про-
странству непрерывных на Z функций. Поскольку Z
компактно, то пространство C(Z) сепарабельно. Но
5 Б. Н. Пшеничный
65
в таком случае слабая* топология в С* может быть
задана некоторой метрикой (см. [1], стр. 461).
Так как для метрических пространств понятия
компактности и бикомпактности совпадают, то, по-
скольку единичный шар в C*(Z) слабо* бикомпактен
(теорема 1 Ввведения), то он и слабо* компактен.
Пусть теперь последовательность функционалов
<(е) = J ^e)vn(da)	(3.10)
Z(Xo)
слабо* сходится к %*. Выберем из последовательно-
сти уп слабо* сходящуюся подпоследовательность (в
смысле пространства непрерывных функций C(Z)).
Без ограничения общности можно считать, что сама
последовательность уп слабо* сходится к v0. Тогда
из того, что для любого множества Е из борелевской
о-алгебры множества Z
v0(£)= I v0(da)= lim | vrt(da)= lim vn (£),
£	П-+00 J	n-^oo
С	C.
следует, что vo—неотрицательная мера и vo(Z(xo)) =
= 1.
Переходя к пределу в (3.10), получаем, что
х’(е)= J x;(e)v0(da),
Z(x„)
что доказывает слабую* замкнутость рассматривае-
мого множества.
§ 4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
В ОБЩИХ ЗАДАЧАХ МАТЕМАТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
В этом параграфе мы выведем необходимые ус-
ловия экстремума, обобщающие обычное правило
множителей Лагранжа на широкий класс задач.
Пусть L — линейное пространство, ср;, 1 =—т, ...
..., 0, ..., k, функционалы на нем, а М — некоторое
66
множество. Рассмотрим задачу:
min ф0(х),
Ф/ М < О, i < О,
Фг (х) = 0, I > О,
хе М.
(4.1)
Поскольку в такой постановке задача имеет весьма
общий вид, для получения эффективных условий экс-
тремума необходимо сделать некоторые основные
предположения.
Пусть xQ — решение задачи.
1.	Существует выпуклый конус Км такой, что если
е (= Км> то
ь
х(Л) = Xq + Ле + S (Л) ei	(4-2)
принадлежит множеству М для любых векторов
е^е£и любых функций (X), удовлетворяющих ус-
ловию
lim гДЛ)Л-1=О,
Л,->+0
как только Л > 0 достаточно мало.
2.	Для i 4^0
lim	<А (е)
Л->+0	Л
где х(А,) определено с помощью (4.2), a h{(e)— вы-
пуклый по е функционал.
3.	Для i > 0
Um
х-»+о	Л
где hi(e) —линейный функционал.
Теорема 4.1. Если х0 — решение задачи (4.1) и
выполнены условия 1—3, то найдутся такие числа Л;,
не все равные нулю, что
k
2 М<(е)>0
m
для всех
е е Км, (4.5)
X,- > 0 для i -С 0 и Хгф4 (хо) = 0 для I < 0.
5*
67
Прежде чем приступить к доказательству, уста-
новим следующую лемму.
Лемма 4.1. Пусть функционалы i = 1, ..., А,
линейно независимы. Тогда, для того чтобы Хо было
решением задачи 4.1, необходимо, чтобы выпуклая
оболочка множества
К = {1- ge£|/<Xo)l, = е<=Км, /е=/(хо)}
и множество
P = {g: ^<0, Ze=Z(x0), /<0, ^ = 0, />0}
не пересекались. Множество /(х0) определяется фор-
мулой
/(х0) = {/: фЛх) = 0, /<0 или
а 11 (х0) | есть число элементов в /(х0).
Доказательство леммы. Допустим, что
лемма неверна. Тогда существует такой вектор
е со R, что
go<Q. fe/(4 j<0,
|? = 0, z > 0.
Так как ^есо^, то найдутся такие g’ е К, что
причем %3 >0 и = Далее, так как	то
для некоторых е* Км
где h(e)—вектор с компонентами ЛДе), /е/(х0).
Пусть е°=2^/£у- Так как Км — выпуклый ко-
нус, то е°^Км- В силу сделанных предположений
М^С2Ше/)=2ЦН?<°-	/е/(х0).
ht (е°) = 2 ЯД И = 2	= % = 0, I > 0.
/ / ---
68
Рассмотрим теперь систему уравнений
/	k \
фг(А,, П, Г2,	гк) = ф^хо +Ае°+ 5r/aJ = O, (4.6)
i — 1, ..., k,
где а1 <= L выбраны так, что /г,(аО = Ьц. Такой вы-
бор векторов а’ всегда возможен, поскольку /г,- ли-
нейно независимы.
Легко видеть, что
^ = Лг(а«) = О,
где производные взяты в точке А = 0, rj = 0, / = 1, ...
Из теоремы о неявных функциях, доказанной
в конце этого параграфа, следует, что система (4.6)
имеет решение г/(А), причем
lim г ДА) А"1 = 0.
Х->+0
Рассмотрим теперь точки
*
х (А) = Хо 4- Ае° + 2 / (A) aj.
/=i
Во-первых, х(А) е М при достаточно малых А. Это
следует из того, что eQ е Км, и условия I основных
предположений.
Во-вторых,
ф/ U (А)) < ф/ Uo) +	(е°) + о (А) < Khi (е°) + о (А) < (L
для всех достаточно малых А, если i<0, ie/(x0),
так как hi(e°) <0. Если же i<0 и *ё=/(х0), то
Фг(х(А)) меньше нуля при малых А, так как фДх0) <
<0.
В-третьих, для i = 0
Фо U W) < Фо (^о) + АЛ0 (е°) + о (А) < фо (х0),
ибо йо(е°) < 0»
69
Наконец, по построению ri(ky)
фг(х(Х)) = О
для i = 1, ..., k.
Таким образом, при малых X точка х(Х) удовлет-
воряет всем ограничениям и значение функционала
фо(х) в ней также меньше, чем фо(хо). Это противо-
речит предположению о том, что х0— решение зада-
чи (4.1).
Лемма доказана.
Обратимся теперь к доказательству тео-
ремы.
Если hi, i = 1, ..., k, линейно зависимы, то доста-
точно положить все Хг-= 0, /^0, а в качестве Хь
i > 0, взять те коэффициенты, для которых
k
i	= 1
Если же hi, i = 1, ..., k, линейно независимы, то на
основании леммы множества соК и Р не пересекают-
ся. Поскольку это выпуклые множества в конечно-
мерном пространстве, то их можно разделить. Это
значит, что найдется такой вектор А с компонентами
Ki, i е / (х0), что
2	М<>о> 2 Ш (4.7)
i е I (хо)	i <= I (хо)
для всех % е R, £^Р. Так как все представи-
мы в виде
g = h(e), et=KM,
то мы получаем 2	для всех е^Км-
i е I (хо)
Правая часть неравенства (4.7), как легко видеть,
дает Хг- > 0 для i (= I (х0) Л -С 0. Но при i I (х0), i < 0
ф2 (Х0) = 0. Поэтому Лгфг (х0) = 0, i < 0, i <= I (х0).
Если теперь положить X; = 0 для /е/(х0), то мы
получаем все утверждения теоремы.
Следствие. Если ограничения типа равенства
отсутствуют или фДх) для i>0 линейны, то в основ-
ных предположениях 1—3 можно положить
х(Х) = х0 + 1е,	1\ = 0, i > 0.
70
Действительно, в этом случае <рг- = hi и система
(4.6) приобретает вид
/	k	\	k
фЛ Хо + Ле° + 2	= Фх(*о) +	(е°) + S rjhj (ау) = 0.
\	/=1	/	7=0
Но поскольку (рДхо)=О по предположению, а
/гДе°) = 0 по построению вектора е°, то для удовлет-
ворения полученной системы уравнений достаточно
ПОЛОЖИТЬ rj; = 0, / = 1, . . . , k.
Конкретизуем теперь теорему 4.1 для случая, ко-
гда рассматриваемое пространство есть пространство
Банаха, а функционалы фДх), квазидифферен-
цируемы. По определению квазидифференцируемого
функционала
ф (Хо + %<?) -	(х0)
lim	y= sup	х (е).
Л->+0	Л	x*^Mi(xo)
Если предположить еще, что фДх) удовлетворяет
условию Липшица, то легко проверяется справедли-
вость формулы (4.3) с
/ц(е) = sup х*(е),
x^^i (*о)
причем в (4.3) вместо знака неравенства надо поста-
вить знак равенства.
Пусть теперь фДх) для />0 таковы, что выпол-
няется (4.4), где hi совпадает с некоторым функцио-
налом х*. е В*. Тогда выполнены все условия теоре-
мы 4.1 и значит, для точки xQl являющейся решением
задачи 4.1, найдутся такие числа X;, что
о	k
2\ sup хЦе) + 2	0 (4-8)
1—т	х>М,.(х0)
для всех е Км-
Лемма 4.2. Если множества Mi(xQ) ограничены,
то для выполнения условия (4.8) необходимо и доста-
точно, чтобы нашлись такие функционалы х\^
что
k
2	и-9)
i = -/n
71
Доказательство. Рассмотрим множество
I
N’ = х*: х = 2 \х*, х’е=М(.(х0), /СО
I	i = — т
Это множество, очевидно, выпукло, так как выпуклы
множества Мг(х0). Более того, оно слабо* замкнуто
и слабо* бикомпактно, ибо Л4г-(хо), по предположе-
нию (см. определение 3.1), слабо* замкнуто и огра-
ничено, а значит, слабо* бикомпактно. Допустим в
противоположность (4.9), что N* и К*м не пересе-
каются. Тогда множество —регулярно вы-
пукло, ибо множество К* слабо* замкнуто, a W* сла-
бо* замкнуто и бикомпактно, а значит /Q —АГ так-
же слабо* замкнуто. Так как К*м и N* не пересека-
ются, то К*м — N* не содержит нулевого функционала.
Поэтому найдется такой элемент ее В, что
г/*(е) —х*(е) > б > О	(4.10)
для всех у s К*м и х* е №*. Из полученного неравен-
ства видно, что величина г/* (е) ограничена для всех
у* s /Q. Но так как fCM — конус, то
inf z/*(e) = O.	(4.11)
у^*м
Отсюда следует, что е^Км, где — замыкание
конуса Км.
Далее, сопоставление (4.10) и (4.11) показывает,
что х* (е)	—б^ для всех W*.
Но из е<=Км и (4.8) следует, что найдется такое
х* е N*, для которого
/еЛГ.
Таким образом, мы пришли к противоречию. Это
означает, что N* и /Q пересекаются, и поэтому вы--
полнено (4.9). Этим доказана необходимость условия
(4.9). Его достаточность очевидна.
Лемма доказана.
Теорема 4.2. Пусть фДх)— функционалы в про-
странстве Банаха. Если фДх) удовлетворяют усло-
вию Липшица и квазидифференцируемы при i-<0, а
72
Ф; (x) для i > 0 удовлетворяют условию Липшица и
имеют производную Гато х*, то для того, чтобы
точка х0 была решением задачи (4.1), необходимо
существование таких чисел Ki (X; не все равны нулю)
и функционалов х*еЛ4Дх0), z^O, что
k
/ =—m
Ki О, I 0, Х4-ф/ (хо) = 0, i У= 0.
Доказательство теоремы фактически следует из
предыдущих рассуждений. Необходимо доказать
только некоторые детали.
Во-первых, если фДх), i > 0, удовлетворяют усло-
вию Липшица, то
lim Ъ UW)-cp.(x0)

где х(Х) дается формулой (4.2).
Доказательство этого факта тривиально. Из него
следует выполнение условия 3 основных предполо-
жений.
Во-вторых, покажем, что Мг-(х0) ограничено, что
требуется в лемме 4.2. .Но если допустить противное,
то для каждого целого п > 0 найдется такой элемент
еп, Iknll = 1, и такой функционал х* еЛ4.(х0), что
х* —е,
п \ nJ —	’
где е — произвольное положительное число. Тогда
Ф/(х0 + Кеп) - (рДхо) =
= Х sup x*(^n) + o(X)>X(n — е) + о(Х).
x*^Mz(x0)
С другой стороны, в силу условия Липшица
| фг (*0 + Хвп) — фг (Х0) | LK.
Поэтому
LK К(п — б) + о (X).
Но если п — е > L, то последнее неравенство невоз-
можно при достаточно малых X. Полученное проти-
воречие показывает, что Мг(х0) ограничено. Это за-
вершает доказательство теоремы.
73
Теорема 4.3 (Куна — Таккера). Пусть
ф7(х)— выпуклые ограниченные функционалы в R,
причем для i > 0 срг- (х) линейны. Пусть также множе-
ство М — выпукло. Тогда, для того чтобы точка х0
была решением задачи минимизации (4.1), необходи-
мо существование таких Х7, Х7 О для i 0, что
k	k
Zj	2 Xzqpz(x0) для всех x^M. (4.12)
i = —m	i = —m
Кроме того,
Х7фг‘(Х0) = О ДЛЯ I 0.	(4.13)
Если Хо > 0, то условия теоремы являются достаточ-
ными.
Доказательство. Определим конус Км'
Км = {е- е = К(х — xQ) для х^М, х =^= х0, X>0}.
Легко видеть, что если е е Км, то
х(Х) = Хо + Хе е М
при малых X. Далее,
. Ф, (ХО + Хе) - Ф (Хо) _ дф (Хо)
Х->+0	Л	де
< <рг (х0 + е) - <р (х0) = hi (е).
Для i > 0 неравенство превращается очевидным об-
разом в равенство. При 1^0 оно следует из того, что
выражение
ф.(Хо + Хе)-ф(хо)
К
монотонно убывает с уменьшением X (см. Введение,
лемма 6). Если учесть следствие теоремы 4.1, то вид-
но, что все условия теоремы 4.1 выполнены. Поэтому
найдутся такие Х7, Х7 <>0, для f^O, что
k	k
2 АД (е)= 2 К [<Pi (хо + e) - <p (xo)] > 0
i = -m	i =—m
для всех e Км-
lb
Взяв здесь е = х — х0, х Mf получим
k	k
2	s MUo)
Z =—m	i = —m
для всех XG M.
Пусть теперь (4.12), (4.13) выполнены и Хо > 0.
Тогда х0 — решение задачи 4.1. В самом деле, для
любой точки х, удовлетворяющей всем ограничениям,
мы имеем в силу (4.12) и (4.13)
k	k
Мо(*о) = 5 MzUoX 2 M(*XMoW
i = — tn	i — — m
ибо фг(х)-<10 для f<0 и фг(х) =0 при I > 0. Итак,
Фо(*о) <Фо(х),
откуда следует, что х0 — решение задачи (4.1). Уста-
новим теперь взаимоотношение между изложенными
результатами и теорией Милютина — Дубовицкого
[Ю].
Допустим, что задан некоторый функционал ф(х)
в В и необходимо найти его минимум при ограниче-
ниях xeQn /=1, ..., п, и х е L. Пусть х0 — точка
минимума. Предположим, что в точке х0 существует
для каждого такой выпуклый конус Ki, что как
только е е Ki
х(Х) = х0 + Хе'е	(4.14)
для всех достаточно малых X > 0 и всех е', удовлет-
воряющих неравенству ||е'— е||^ее, где ее — завися-
щее от е положительное число. Кроме того, в точке
х0 существует касательное к L подпространство Z,
т. е. для всякого e^L найдется такое г(Х), что
х(Х) = х0 + Хе + г(Х) е L (4.15)
как только X достаточно мало. При этом ||r (X) ||Х-1-*
—►0 при X—► +0.
Далее, предположим, что ф(х)—такой функцио-
нал, что существует конус запрещенных вариаций, т. е.
такой выпуклый конус Ко, что выполняется (4.14)
для Qo, где
й0 = {х: ф(х)<ф(х0)}-
75
Теперь почти очевидна первая теорема Милю-
тина — Дубовицкого.
Теорема 4.4. Для того чтобы точка х0 была
решением задачи
min ф(х),
х е i= 1, ..., n,
xgL
необходимо, чтобы конусы Ко, К\, Кп и Z не пе-
ресекались.
Доказательство. Пусть конусы Ki, 1 = 0, ...
..., п, и Z пересекаются. Тогда найдется такое е9
что ее/ и е е К{. По определению Z найдется та-
кая функция г(Х), что
х = Хо + Х£-Ьг(Х)
и
Л-»0 Л
Далее, так как е е Ki, то
х=х0 + Хе' е Qi
как только X достаточно мало и
\\е' — е|| <8*.
Положим
/	, г (К)
е =е + -г--
Но
а эта величина стремится к нулю. Поэтому для до-
статочно малых X ||ех — е|| менше 8е и, значит,
х=xg-f-Ке + r(X) е Qi.
Итак, при достаточно малых X точка хе L и
хе Qi, Z = 0, 1, ..., п. Это значит, что х удовлетво-
ряет всем ограничениям и, кроме того,
ф(х) < ф(Х0),
так как xeQ0. Последнее неравенство противоречит
тому, что в точке Хо достигается минимум ф(х).
76
Теорема доказана.
Для того чтобы теорему 4.4 можно было исполь-
зовать, необходимо дать эффективное условие не-
пересечения конусов. Ответ на этот вопрос дает вто-
рая теорема Милютина — Дубовицкого.
Теорема 4.5. Для того чтобы конусы Ко, К\, ...
..., Кп и Z не пересекались, необходимо и достаточ-
но существование таких функционалов х\ е /(*,
i = 0, 1, ..., п, и %* е Z*, что
+	... +<+/=0	(4.16)
(К] — двойственный конус к Ki), причем х\, х* не все
равны нулю.
Доказательство. Существует весьма изящ-
ное доказательство этой теоремы, принадлежащее ее
авторам. Здесь мы дадим доказательство, основанное
на вышеизложенных результатах. Отметим сразу же,
что конусы Ki, 1 = 0,..., п, по своему построению
открытые. Рассмотрим их пересечение. Не уменьшая
общности, можно считать, что оно не пусто. Тогда,
по предположению теоремы,
(ПмП/=0.
ч=о /
п
Но конус Р) Ki есть открытый выпуклый конус, а
i = 0
L — выпуклое множество. На основании теоремы от-
делимости найдется такой функционал е В*, что
i/*(e)>0 для
1=0
г/*(е)<0 для eeZ.
Положим
(х) = max х* (х), z = 0, 1, ..., п,
X* е=
(4.17)
где = — К* П S‘, S* — единичная сфера в В*, т. е.
S*={x*: ||x*||jC 1}. Нетрудно видеть, что область,
77
определяемая неравенством
|ii(x) <0,
совпадает с Ki, где Ki — замыкание /Q.	_
В самом деле, это следует из того, что x^Ki
тогда и только тогда, когда
х* (х)	0 для всех х* е /<*.
Теперь ясно, что область
Q = {x: цДх)<Д, * = 0,
совпадает с пересечением всех К^ Из (4.17) следует,
что функционал р,0(*) достигает своего минимума в
области Q при хо = О.
Заметим теперь следующее. Во-первых, так как
все конусы Ki открыты, то их пересечение также от-
крыто и найдется такая точка хь что Xi есть внутрен-
няя точка Q Кь
i = 0
Но тогда цг (Х1) < 0 для всех i = 0, ..., п.
Во-вторых, в силу теоремы 1.6 § 1 множество опор-
ных функционалов Л4г(0) к цг (х) (i > 0) в точке
х0 = 0 совпадает с Л4г-.
На основании теоремы 2.4 мы можем теперь утвер-
ждать, что найдутся такие что
п
где у* е Мг Положим теперь х* = — у*0, х\ = Kty\. То-
гда предыдущее равенство переходит в равенство
х* + Xj + ... "Т х* + х = 0.
Но х*е2* в силу (4.17). Далее х*е/(*, ибо
Необходимость условий теоремы доказана.
Достаточность условия (4.16) легко доказать от
противного.
Действительно, пусть (4.16) выполнено, но най-
дется такая точка е0, что е0 Ki, i = 0, ..., п, и
78
eQ^Z. Тогда
xi (eo) 0» x (eo) 0
по определению двойственного конуса, причем среди
х](е^ хоть одна величина строго больше нуля, ибо
е0 Кг и конус Кг открытый (а значит, eQ — внутрен-
няя точка для всех Ki) и, кроме того, не все х*. рав-
ны нулю.
Отсюда
W + <(e0)+ ... +<(ео) + х‘(ео)>О,
что противоречит (4.16).
Итак, мы видим, что из предыдущих результатов
следует основная теорема Милютина — Дубовицкого.
Эта теорема дает весьма общие условия экстремума.
В частности, она является более общей в некотором
отношении, чем теорема 4.1, поскольку она не тре-
бует, чтобы ограничения типа равенства, роль кото-
рых играет множество L, были заданы в виде конеч-
ной системы равенств нулю функционалов. С другой
стороны, сами по себе теоремы 4.4 и 4.5 еще не позво-
ляют строить в общем случае необходимых условий,
так как оставляют открытым вопрос об эффективном
построении конусов и подпространства Z.
Форма изложения, принятая в настоящей работе,
построена так, чтобы развить сначала технику вычис-
ления производных по направлению, что эквивалентно
построению конусов Ki, а потом уже сформулировать
такие необходимые условия, которые в пределах раз-
витой техники позволяют немедленно в конкретном
виде записать эти условия.
Рассмотрим теперь некоторое обобщение задачи,
изученной в начале этого параграфа. Это обобщение
позволяет получить в некоторых задачах, например
таких, как задача дискретного оптимального управ-
ления, более тонкие условия минимума, чем те, кото-
рые дает теорема 4.1.
Пусть L — линейное пространство, X — подмноже-
ство L, a U — множество произвольной природы. На
X X U заданы функционалы ф; (х, и), I = —т,..., — 1,
0, 1, ..., k. Требуется сформулировать необходимые
условия того, что точки х0, Uq являются решением
79
задачи
min(po(x, w),
фДх, u)^0, Z < О,
фДх, и) = 0, i > 0,
х^Х, u^U.
(4.18)
Сформулируем основные предположения, при ко-
торых будет решаться задача.
1.	Еслиср(х, и) = [(р__пг(ху и), ..ф0(х, и),... ,фДх, «)},
то при каждом фиксированном х множество ф(х, (7),
которое пробегает вектор ф(х, и), когда и меняется в
U, выпукло.
2.	В точке xQ существует выпуклый конус Кх та-
кой, что из е е Кх следует
k
X (А-) = Xq +	+ 2 / (М	(4.1 9)
при достаточно малом К > 0 для любых е L и лю-
бых функций гДХ), удовлетворяющих условию
Г/ W
lim —Ц— = 0.
Х->+0 л
3.	Для и любого ugU
фДх(Л), и) -ф (х0, и)
lim —----а——L^hi(uy е),
-X J-П	Л
где х(Х) дается выражением (4.19), а И{(и, е)—вы-
пуклый по е функционал, причем hi(u,Ke')=lkhi(u,e).
4.	Для i > 0 существуют такие линейные по е функ-
ционалы hi(u, е), что
k
фДх(Х), «) —qp/(xo, и) — Kht(u, е) — гjh^u, a.j) =
где х(Х) дается выражением
k
(^) = -^о “Ь “Ь /»	(4.20)
/=1
80
a r(z) —такая функция, что
lim = 0.
2->0 Z
/	k	\
Кроме того, фДх0 + Л,е + 5 riab u / —непрерывные
функции X И Гу
Условие 4 можно иначе проинтерпретировать сле-
дующим образом. Если в ср (%, и) подставить выраже-
ние (4.20), то функционал ф(х, и) становится функ-
цией конечного числа переменных X и Гу Условие 4
тогда означает, что эта функция дифференцируема в
точке хо, т. е. может быть в некоторой окрестности
точки х0 аппроксимирована линейной функцией X и г$
с точностью до членов более высокого порядка мало-
сти, чем X и Гу
Обсудим теперь, что дает условие 1. Из него сле-
дует, что если Uj^U, j = 1, п, и числа yj удов-
летворяют условию
п
то существует такое и е U, что
п
ф(х, й)=2у/ф(х, U/).	(4.21)
Далее, если uQ^U, то найдется такое и(хД),
что
ф(х, и(х, Х)) = ф(х, и0) + Л[ф(х, и) — ф(х, w0)] (4.22)
при	1.
Пусть теперь точка хо, w0— решение задачи (4.18)
и функционалы hi(u0, е), / = 1,.й, линейно неза-
висимы. Кроме того, без ограничения общности мы
можем считать, что для всех /<0 фг(х0, и0) = 0.
Рассмотрим множество
К = & l = е) +
+ [ф (х0, и) - ф (х0, w0)], е е 7<х, и е [/},
где £ — (т + k + 1)-мерный вектор, a h (u0, е) =
= {h_fn(iiQ, е),	/z/,(w0, е)}, и множество
Р =	^<0 для Z<0, ^ = 0, Z>0}.
81
6 Б. Н. Пшеничный
Покажем, что выпуклая оболочка множества К и мно-
жество Р не пересекаются.
Допустим противное. Тогда найдется такой вектор
£° е со К, что
£? < О для i < О,
= 0 для i > 0.
(4.23)
По определению выпуклой оболочки множества и
определению множества К найдутся такие неотрица-
тельные числа yj, /= 1, ..., /г, сумма которых равна
единице, и такие е Кх и и, е [7, что
п
£° = S Y/ [Л («о, в/) + [<р (х0, М/) - ф (х0, Ио)] ]•
7=1
Положим теперь
п
- S v/б/,
а и определим из условия
п
ф(*о> й)= 2 У/ф(*о, «/)•
7=1
Так как Кх— выпуклый конус и е^Кх, то е0(=Кх-
Из выпуклости hi(uQ,e) по е для и их линейно-
сти при i > 0, а также соотношений (4.23) следует
Mw0> ео) + [ф/(хо- «)-ф/(хо. «о)]<^<° Для г’<0,
hi («о> ео) + [ф< (*о> “) - ф/ (хо- мо)] = = 0 для z' > °- .
(4.24)
Так как функционалы /ii(u0, е), /= 1, k, ли-
нейно независимы, то найдутся такие aj е Z, что
hi(uQi aj) =	i, j = 1, ..., k,
где Sij = 0, если i 4= j и дц = 1, i = /.
Рассмотрим нелинейную систему уравнений
фг(Х, Г1, ..., rh) = 0, i = 1, ..., k, (4.25)
где
фг(^> ГЬ ..rk)=	ь
= ф; х0 + Ле0 + 2 rjah и (Л., гь ..., гк) ,
\	/=1	/
82
a u(X, rb rh) для 0-041 определено из условия
! k \
ФИ х0 + Ле0 + 2 Г/а/, и (Л, rb	г J =
/	k	\	г	/	k	\
= Фх( %q + ^о ~Ь 1 riab )• + Л ф/( Xq 4- Лв0 + 2 гiab )—
\	/-=1	/	L	\	7=1	/
/	k	\ I
— Ф/ *о + Ле0+ 2 Uq , Z = — m, ..(4.26)
\	/=i	/J
Таким образом, функция фг(Х, rb ..., rh) совпа-
дает с правой частью формулы (4.26). Если восполь-
зоваться теперь условием 4 предположений, при ко-
торых решается задача и выделить в правой части
(4.26) линейную часть, то получим
k
•фДА., Г]...г*) = ЛЛг(и0, е0)+ 2 rjhj. (и0, а;) +
k
+ А.[ф/(х0, «) — ф>(хо. м0)]+ ... =^rjhl(uQ, ai)+ ...,
7 = 1
где многоточием обозначены члены, оценивающиеся
величиной
и при выводе использовано второе из соотношений
(4.24).
На основании теоремы 4.7, приводимой в конце па-
раграфа, мы можем утверждать, что система (4.25)
разрешима относительно ..., гк, т. е. определяет
для достаточно малых X функции гДХ), причем вы-
полнено условие
Пусть теперь
п
X (Л) = Xq + KCq +2^7 (М /,
7 = 1
и(Л) = и(Л, Г1(Л),
Тогда на основании приведенных выше определений
функций xpi и и (К, гх, rk) получим
фг(*(М, 7/(Х)=0, i= 1, ..., k.
6!
83
Далее, на основании предположения 2 х(Х)еХ
при достаточно малом X > 0. Кроме того, для 1^.0
Фг(х(Х), и(Х)) = ф,(х(Х), м0) + Х[фДх(Х), й)-фг(х(Х), и0)]>
<р (х (X), и (X)) - ф, (х0, Uo)
lim ----------.-------------
х->+о	Л
= iim ^(xW’“o) -<P<(*Q’»o) j
Л->+0
+ lim [ф/ (х (X), й) - фг (х (X), «о)] <
Л-> +о
< hl (u0, е0) + [ф/ (х0, и) — фг- (х0, н0)]
Но из (4.24) следует, что правая часть в последней
формуле строго меньше нуля. Поэтому
фг(*(М> u(X)) < ф;(х0, U0) ДЛЯ i < 0.
Полученные результаты противоречат тому, что
х0, и0— решение задачи (4.18). В самом деле, точка
х(Х), и(Х) удовлетворяет всем ограничениям, ибо
х(Х)еХ при достаточно малых X, и(Л)е(7 по опре-
делению,
фДх(Х), и(Л))=0 для />0,
фг (х (X) , U (А/) ) <фг (х0, U0)=0 ДЛЯ 1<0
и фо(х(Х), и(Х)) < фо(хо, Uo), т. е. х0, и0 не есть ми-
нимальное значение ф0(х, и) при данных ограничениях.
Полученное противоречие показывает, что coR и Р
не пересекаются. Но coR и Р — выпуклые множества
в (m + k + 1)-мерном пространстве. Поэтому найдутся
такие не все равные нулю константы Хг-, i = —т, ...
..., k, что
k	k
2 X&>0> s Ш £есоК,
i = — т	i ——m
Из правой части этого неравенства следует, что
> 0 для i^O. Левая же часть по определению дает
2 Хг [hi («о, е) + [ф, (х0, и) - фг (х0, «о)] ] > 0
г = — т
для всех е е и и е U.
84
Но так как е и и меняются независимо, то полу-
ченное неравенство эквивалентно двум следующим:
k
(w0,
k
S A/Pz (*o,
ё) 0 для e <= Kx>
k
Ио) = min s Mi (*o, «)•
и e U i =—m
(4.27)
Нами доказана
Теорема 4.6. Пусть выполнены предположения
1—4 и функционалы ht(u0,e), i = 1, ..., k, линейно
независимы. Тогда, для того чтобы х0, w0 было реше-
нием задачи (4.18), необходимо существование таких
Лг, i = —m, ..., k, которые не все равны нулю, что вы-
полнены соотношения (4.27) и
Х/>0 для i-^О, 21гфг(хо, wo)=O для t<0.	(4.28)
В утверждающей части теоремы требуют разъяс-
нения лишь соотношения
А-гфг (Хо, W0) = 0 ДЛЯ I < 0.
В предположениях, при которых доказывалась тео-
рема, т. е. фг- (*о, Wo) = 0 для i < 0, они очевидны. Если
же для некоторых i
фг (*0, Wo) < 0,
то такие ограничения при построении точки х(Х)', и (К)
можно было игнорировать, поскольку для такого i
ф/ (х (Л), и (Л)) = ф; (х (Л), и0) +
+ Л[фг(х(Л), й)-фДх(Х), и0)]<фДх0, uQ) +
+	(х0, е0) + [фг (х0, и) - ф (х0, uQ)] ] + о (X).
Правая часть последнего неравенства следует из пред-
положения 3 и становится отрицательной при доста-
точно малом X независимо от выбора вектора е0 и и.
Поэтому, если для некоторых /<0 фг(х0, uQ) отрица-
тельны, то можно повторить все доказательство тео-
ремы так, как будто этих ограничений нет. При вы-
воде же соотношений (4.27) следует положить Хг- = 0
для таких i, что автоматически поведет к выполнению
условий (4.28),
85
При доказательстве теорем 4.1 и 4.6 ограничения,
накладываемые на условия типа равенства, т. е. усло-
вия 3 для теорем 4.1 и условия 4 для теоремы 4.6,
имели различную форму. Покажем, что на самом
деле сделанные ограничения эквивалентны.
Действительно, если выполнено условие 4 для тео-
ремы 4.6, то для
k
к (X) = Xg 4" Ав + 2 О (М #/	(4.29)
/=1
<р. (х (Л), и) - <р (ХО, и)	Л Г. (Л)
-----------(и, е) + 2j -5г- л< («> «/) +
/=|
+1 г [ 1/ Л2 + 2 w) - hi (и, е), (4.30)
X	/=1	/
если гДХ)Х-1—>0 при Л->0. Таким образом, из вы-
полнения условия 4 для теоремы 4.6 следует выпол-
нение условия 3 для теоремы 4.1.
Обратно, пусть выполнено условие 3. Покажем,
что выполнено условие 4 теоремы 4.6. Для доказа-
тельства допустим противное, т. е. найдутся такие
и г", ф что Лп->0, г?->0, при п—>оо, однако
k
~<Р/(*о>	e„)-Sr7^(U’ al)
7=1
к нулю не стремится, | еп | > 6 для всех п. Положим
Поскольку по определению
|/ Y2+ 2(®У)2=1,
86
то из последовательности векторов со^, ...,
можно выбрать сходящуюся. Поэтому будем считать,
что
и положим
Vn Vo,
(О? -> (Оу,
k
е' = уое + 5 ®°аг
(4.31)
Теперь величину гп можно записать в следующем
виде:
8„ = {ф,- (*о + Ч6' + 4 (Уп - Vo) 6 +
+ 5 4 (®/«)-ф,(*о> ы)}(4)-'-
k
-ht(u, е') + (у„ - уо) (и, e)+a/)«
Из предположения 3 теоремы 4.1 и (4.31) следует,
что при п —>оо, т. е. при Л,'->0, первый член в вы-
ражении для еп стремится к hi(u,e'), а само 8П стре-
мится к нулю. Но это противоречит предположению
о том, что |еп|^б. Тем самым доказано, что из
условия 3 теоремы 4.1 следует условие 4 теоре-
мы 4.6.
В заключение этого параграфа приведем доказа-
тельство теоремы о разрешимости системы нелиней-
ных уравнений, на которую неоднократно делались
ссылки *).
Теорема 4.7. Пусть х k-мерный вектор, а непре-
рывные функции фг (Х, %) удовлетворяют следующим
условиям:
а)	фг (0, 0) = 0, 4=1, ...» k\
♦) Если предположить, что гр/(X, х) непрерывно дифферен-
цируемы в некоторой окрестности точки Л=0, х=0, то тео-
рема 4.7 совпадает с обычной теоремой о неявных функциях [45].
87
б)	фДХ, х) дифференцируемы в точке X = О, х = О,
т. е.
<9ib. (О, 0) dib. (О, О)
Ф/ (*, х) ~ Фг (О, 0) - К —--------— х>
/-«
/ k \'/2
где || х || = 2%- , а г (г) г”1-* О при г->0;
\/=i 7
f дф. 1
г) матрица дхф = ~g^ J > * = 1, ..., j = I, ..., k,
не вырождена.
Тогда система уравнений
фг (X, х) = О, i = 1, ..., kt
разрешима при достаточно малых X и существует ре-
шение х(Л), обладающее свойством
г II X (%) II л
lim 21—= 0.
Х->0 Л
Доказательство. Рассуждения удобно прово-
дить в векторных обозначениях. Поэтому обозначим
ф(^> х)={ф1(^ х), .... фй(Х, х)).
Из условий теоремы следует, что
ф (Л, х) = дуфх + г (Л, х), 1
IIГ(X, х)||<г(УХ2 + ||х|р). J (4‘32)
Рассмотрим отображение
g (X, х) = х — (<ЭД>)~' i|s (%, х).
Используя (4.32), получаем
g (Л, х) = - («Эд-ф)-1 г (%, х),
IIg(Л, х)II<г(]А2 + ||х|НII(МГ*II•	(4.33)
Заметим теперь, что без ограничения общности мы
можем считать r(z) неубывающей функцией г. В са-
88
мом деле, если это не так, то г (г) можно заменить на
со(г)= sup г(/),
О t г
так что со(г)>г(г). При этом со(г) уже, очевидно,
неубывающая функция и
Z
Действительно, так как r(t)t 1—>0, то для всякого
е > 0 найдется такое 6, что
7
как только t S.
со (г) _ 1
Z ~~ Z
Если теперь z < 6, то
- / п	г (/)
sup	sup —
Пусть теперь
T(X) = inf{r: 7<г(‘|Л^2 + т2)^т},
где К = ||(д/ф) !||. Так как при достаточно малых К
выполняется неравенство
Кг (]Л,2 + Л2) = Кг (Л /У) < К
то при достаточно малых %	Кроме того, по
определению нижней грани для каждого такого X су-
ществует такое т*(%), что
т(Х)<т*(^)<т(л) + Z2,
и
Яг(]Л2 + (т*(М)2)<т‘(М-
(4.34)
Покажем, что
т(Л) >Q
В самом деле, по определению
-г (Л) - Л2 < Кг (/Л2 + (т(Л.)-А,2)2) < Кг (Л +1 т (Л) — Л21),
(4.35)
где мы воспользовались тем, что r(z)— неубывающая
функция и	______
У К2 + со2 К + <о
89
для X и со положительных. Далее, так как для малых
т(Х) А, то правую часть (4.35) можно оценить сле-
дующим образом:
Кг (X + | т (Л) - Л21X Кг (Л + Л) = Кг (2Л).
Итак, мы получаем
т(Л)-Л2<Я7(2М
или
Л
т. е.
тЩ ? 0
Л
при Л->0. Но тогда и
Л
Итак, для достаточно малых X выполнено неравен-
ство (4.34).
Если теперь
1|х|| <т*(Х),
то, согласно (4.33),
||	х) ||<Кг (/Л2 + II х IP)< Кг (]А2 + (т‘ (Л,) )2) <т’ (X).
Отсюда следует, что непрерывное отображение g (К, х)
отображает шар
\\х\\ <т*(Х)
в себя. На основании теоремы Брауэра [1] теперь мо-
жно утверждать, что отображение g(2i, х) обладает
неподвижной точкой, т. е. найдется такая точка х(Х),
что
x(A.) = g(X, х(Л)),
|| х (Л) || < т* (Л).
Но из определения g(X, х) следует, что
4>(Х, х(Х)) = 0,
т. е. исследуемая нелинейная система уравнений раз^
решима,
90
При этом
II X (Л) ||	, т*(Х)
X	л
откуда следует, что
II X (Л) || п
Л
при X—>0.
Теорема полностью доказана.
§ 5.	НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
В КОНКРЕТНЫХ ЗАДАЧАХ
В этом параграфе мы проиллюстрируем примене-
ние развитой в предыдущих параграфах общей тео-
рии к различным экстремальным задачам. Сила вся-
кой общей теории состоит в том, что она позволяет
рассмотреть единообразным способом различные ча-
стные задачи и получить полные результаты единым
методом.
Многие из исследуемых ниже задач рассматрива-
лись раньше и им посвящено большое количество ра-
бот. Как правило, для изучения каждой задачи при-
влекались свои специфические методы, пригодные для
решения именно данной узкой задачи. Мы покажем,
что применение развитой общей теории в каждой из
исследуемых ниже задач сразу же, без привлечения
каких-либо дополнительных длинных рассуждений,
дает полные результаты, зачастую даже более общие,
чем те, которые были получены специальными мето-
дами.
1.	Классическая задача математического програм-
мирования. Пусть заданы в ^-мерном пространстве
дифференцируемые функции f;(x), i = —т, ..., k. Не-
обходимо найти условия, которым удовлетворяет точ-
ка Хо, являющаяся решением следующей задачи:
minfo(x),
А(х)<0,	1= — т, ...» —1,
Л(х) = 0,	/=1,	k.
Предполагается, что функции ^(х) непрерывно диф-
ференцируемы.
91
Так как функции fi(x) дифференцируемы, то они
входят в класс квазидифференцируемых функций, при-
чем для них множество Мг-(х0) состоит из одного-
единственного вектора, совпадающего с градиентом
fi(x) в точке х, который мы обозначим через dxfi(x).
В самом деле, по известной теореме анализа [44]
=	е).
Легко видеть, что мы находимся в условиях при-
менимости теоремы 4.2, где в качестве множества М
надо взять все пространство. Поэтому Км — также все
пространство и Км = {0}.
Из теоремы 4.2 теперь следует, что найдутся такие
числа Хь для что
k
/SmWiUo) = o,
^ifi (*о) =	0.
Мы получили известное правило множителей Лаг-
ранжа.
2.	Математическое программирование с контину-
умом ограничений. Требуется найти минумум непре-
рывно дифференцируемой функции ц(х) п-мерного
аргумента х при ограничениях
ц(а, х)<С0, аей,
где р(а, х) — непрерывная по а и х функция, обла-
дающая непрерывным градиентом дхц(а, х), а Й —
компактное множество.
Введем функцию
H-i(x) = тахр(а, х).
ае Q
Тогда поставленная выше задача эквивалентна за-
даче
min ц (х).
Согласно теореме 3.3 p_i(x) есть квазидиффе-
ренцируемая функция, причем, согласно теореме 3.4,
92
множество Л4_1(хо) для нее дается формулой
M-i(x0) = co/ (J M(xQ, a)V
\as й (х0)	/
гдей(х0)={а: asQ, p(a, Xo) = H-i(*o)}- Таккакфунк-
ция ц(а, х) непрерывно дифференцируема по х, то
M(xq, а) = {<5хц(а, х0)}, и мы можем написать
M_t(xo) = co/ (J djx(a, х0Й,
\a g Q (хо)	/
причем знак замыкания убран, поскольку выпуклая
оболочка замкнутого множества в конечномерном про-
странстве замкнута, а множество
U ^(а, Хо)
а 6 Q (хо)
замкнуто, так как замкнуто множество Q(x0), а
дхц(а, %о) непрерывно зависит от а.
На основании теоремы 4.2 можно утверждать, что
найдутся такие неотрицательные константы Хо, Х-ь не
равные нулю одновременно, что
Xo3x|i(xo) + k1c = O, Х^|Ц_1(хо) = О,
где сеЛк^Хо). Но Л4-1(х0) есть выпуклая оболочка
n-мерных векторов dxp(a, х0), a^Q(x0). Отсюда сле-
дует, что вектор с представим в виде
п+1
с = S ktdx}x (az, Хо),
/ = 1
п+1
где az е Q(xo), XZJ> О, 3 К = !• Таким образом, окон-
t«l
чательно получаем
п+1
МжН (*о) + 2 Y Ан («/> Хо) = о, (5.1)
Z = 1
п + 1
где уг = Х1Х10, причем 2yz = ^-i* Сформулируем
полученный результат.
Теорема 5.1. Для того чтобы точка х0 была ре-
шением задачи математического программирования с
континуумом ограничений, необходимо, чтобы нашлись
93
такие не все равные нулю константы Ло О и > О
и точки а:-ей(хо), / = 1, ...» п + 1, что выполнено
соотношение (5.1) и все уг = О, если ц_1(хо)<О.
Допустим теперь, что ц(х) и все ц(а, х) выпуклые
по х функции, причем найдется такая точка х, что
ц_! (xi) <0. Тогда исследуемая задача становится за-
дачей выпуклого программирования.
Применяя теорему 2.4 для случая одного ограни-
чения, получим, что найдется такое неотрицательное
число Л-i и такой вектор ceM-i(x0), что
дхц(х0) = —Л-iC,
причем это условие является необходимым и доста-
точным.
Рассуждая теперь аналогично предыдущему, мы
получим
Следствие 1. Если ц(х) и ц(а, х)—выпуклые
функционалы и ц_1(Х1)< 0 для некоторой точки хь то
для того, чтобы точка х0 была решением задачи с кон-
тинуумом ограничений, необходимо и достаточно, что-
бы нашлись такие числа у?^>0 и a^^Q(x0), что вы-
полняется условие (5.1) с Ло = 1.
Следствие 2. При предположениях следствия 1,
для того чтобы точка х0 была решением задачи с кон-
тинуумом ограничений, необходимо и достаточно, что-
бы нашлись такие oii е Q(x0), что точка х0 есть реше-
ние задачи
min ц (х),
p(az, х)^0, i = 1, ..., п 4- 1.
В самом деле, соотношение (5.1) (Ло=1) есть
одновременно необходимое и достаточное в силу тео-
ремы 2.4 условие, для того чтобы точка х0 была ре-
шением задачи (5.2).
Таким образом, следствие 2 показывает, что в вы-
пуклом случае решение задачи с континуумом огра-
ничений может быть сведено к решению специально
подобранной задачи с числом ограничений, не боль-
шим чем п + 1.
3.	Теоремы о минимаксе. Пусть в простанстве В
задано выпуклое компактное множество М, а в про-
94
(5.2)
странстве В* — выпуклое ограниченное слабо* замк-
нутое множество *. Ведем функцию qp (х) = max %* (х).
х* <= М*
Пусть %о М — точка минимума функции ср(х) на
М. Тогда по теореме 2.1 найдется такой х*еМ(х0),
где М (х0) — множество опорных функционалов в точ-
ке х0 для ф(х), что Xе е Г*о, ГХй~ конус, определяе-
мый соотношением
ГХо={е: х0 + Лее/И для малых А,>0}.
В частности, е = х — х0 для х^М принадлежит это-
му конусу.
Далее, по теореме 1.6
Л4(х0)={х*: /еМ*, х* (хо) = Ф (х0)}.
Таким образом, найдется такой функционал х^еМ (х0),
что
Xq (х — х0)	0	для всех х е= М
и
х* (х0) х* (х0) для всех х* е М\
Таким образом, из двух предыдущих неравенств сле-
дует, что
х*(х)>х;(х0)>х*(х0) для всех х М, х* е ЛГ. (5.3)
Теорема 5.2. Если М — выпуклое компактное
множество в В, а М* — выпуклое ограниченное сла-
бо* замкнутое множество в В*, то
min max х*(х)= max min х*(х).	(5.4)
х е М х* е М*	X* Е ЛГ х £ М
Доказательство. Утверждение теоремы есть
непосредственное следствие (5.3), поскольку (5.3)
(см. [5]) эквивалентно (5.4).
Следствие 1. Если X и Y — компактные мно-
жества, К (х, у) — непрерывная функция х е X и
у Y, а X* и Y* — множества всех мер соответствен-
но на X и Y таких, что p(X) = v(T)= 1, то
min max [ k(x, y)p(dx)v(dy) =
цех* veZ*
= max min k (x, z/)p- (dx) v (dy).
vey* цех* ‘
95
Доказательство. Рассмотрим в качестве В
пространство всех непрерывных функций на У. Возь-
мем в качестве М множество всех функций с (у),
представимых в виде
С (у) = j k (х, у) р (dx),
а в качестве М* — множество У*. Тогда доказатель-
ство следствия полностью совпадает с утверждением
(5.4) теоремы 5.2.
Следствие 2. Если X и У — компактные мно-
жества, а функция k(x,y), непрерывная по совокуп-
ности аргументов х е X и у G У, вдобавок выпукла
по х и вогнута по у, то
min max£(x, z/) = max min/s(x, у).
x^X y^Y	y^Y х^Х
Доказательство. На основании предыдущего
следствия теоремы 5.2 мы можем утверждать, что
найдутся такие меры ц0 и v0, цо(А') = vo(T) = 1, что
/ k(x, y)y(dx)v0(dy)^ J k(x, y)ii0(dx)v()(dy)^
> J k(x, y)n0(dx)v(dy). (5.5)
Пусть теперь
xg= J xp(dx), yv = j yv(dy).
Тогда, поскольку k(x, у) выпукла по х и вогнута по у,
j k(x, y)n0(dx)v(dy)^ j fc(xg„ y)v(dy), (5.6)
j k(x, y)[i(dx)v0(dy)^. J k(x, yVt)n(dx). (5.7)
Покажем, что
J k (x, y) Po (dx) v0 (dy) = j k (xg„ y) v0 (dy). (5.8)
В самом деле, на основании неравенства (5.6) пра-
вая часть может быть только меньше, чем левая.
Допустим, что она строго меньше, так что
J k(x, y)y0(dx)v0(dy)> J fc(xg„ y)v0(dy).
96
Взяв теперь в левой части (5.5) в качестве меры ц
меру, сосредоточенную в точке хЦо, мы придем к про-
тиворечию.
Точно так же показывается, что
J k (V> У) vo Ш = k Уъ) •	(5-9)
Действительно, из вогнутости й(х, у) по у следует,
что
J k(xM y)^dy)^k(x^ yv).
Допустим, что выполняется строгое неравенство. Из
(5.5), (5.6) и (5.8) следует, что
/ k (Хщ, у) v0 (dy) > [ k (Х|ХО) у) V (dy).
Выбрав v сосредоточенной в yVz, получим противоре-
чие с предположением.
Теперь на основании (5.5) — (5.9) получаем, что
J fe(x- y^<dx»k{x^ J k(x^ yY^dy)-
Если взять меры ц и v сосредоточенными соот-
ветственно в точках х и у, то получаем
k(x> yv,)>k(.x^ yv.)>k(.x^ у)
для всех х е X и у е У, что завершает доказатель-
ство теоремы.
4.	Задачи чебышевского приближения. Пусть за-
дана функция ц(х, а), где х меняется в некотором
множестве й, а а — в множестве 21. Будем предпола-
гать, что Q — подмножество а 21— компактное
множество в Es. Функция ц(х, а) непрерывна по сво-
им аргументам и имеет непрерывный градиент
dx|i(*, а) по х- Рассмотрим задачу минимизации
функции
р(х) = шахр(х, а)
на множестве й, которое в каждой точке х обладает
непустым выпуклым конусом Кх'
Кх = {е: x+he<=Q для достаточно малых Х>0}.
7 Б. Н. Пшеничный
97
По доказанному в § 3 функция |ы(х) квазидифферен-
цируема, причем множество Л4(х) для нее опреде-
ляется соотношением
М (х) = со / (J d (%, аУ),
\а е 21 (х)	/
91 (%) = [а: ае 21, ц(х, а) = ц(х)}.
На основании следствия теоремы 4.1 и теоре-
мы 4.2 можно утверждать, что если ц(х) достигает
минимума на Й в точке х0, то выполняется следую-
щее условие: существует такой вектор с0 е /<* что
с0^Л4(х0). Но поскольку мы имеем дело с п-мерным
пространством, то любой элемент выпуклой оболочки
некоторого множества представим в виде выпуклой
линейной комбинации векторов из самого множества.
Таким образом, найдутся такие %г-, / = 1, ..., п+1
и аг 91 (х0), что
п + 1	п+1
Со = 2 МхНUo> аД 5^=1. А,г>о. (5.10)
i=l	i=1
Теорема 5.3. Для того чтобы определенная
выше функция ц(х) достигала своего минимума в
точке х0 <= Й, необходимо, чтобы нашлись такие кон-
станты X/ > 0 и точки at е 91 (х0), i = 1, ..., п +- 1, что
п+1	п +1
Если ц(х, а) выпукла по х для всех а и множество
X выпукло, то приведенные условия достаточны.
Доказательство. (5.11) есть непосредствен-
ное следствие соотношений с0 е /Q и (5.10). Если
же выполнены дополнительные предположения о вы-
пуклости, то достаточность следует из того факта,
что функция ц(х) выпукла и к ней применима тео-
рема 2.1, которая в данном случае вполне эквива-
лентна в части необходимых условий теореме 4.2,
однако показывает дополнительно, что в выпуклом
случае необходимые условия одновременно являются
и достаточными.
Следствие. Если Q совпадает со всем про-
странством, то условие (5.11) в теореме 5.3 может
98
быть записано в виде
п + 1
2 W (-Vo, аг) = о.
/=1
В самом деле, если Q — все пространство, то и
конус /(Хо совпадает с £п, а поэтому конус КХй со-
держит единственный элемент 0.
Полученные выше результаты, сформулированные
в теореме 5.3 и ее следствии, можно рассматривать
как необходимые условия в нелинейной задаче чебы-
шевского приближения. Действительно, мы сейчас
покажем, что из них можно получить обычные усло-
вия для классической задачи о чебышевском при-
ближении.
Пусть на компактном множестве Е т-мерного
пространства заданы непрерывные функции ф&(а),
&=1, ..., п, и непрерывная функция f(a). Ее тре-
буется приблизить обобщенным полиномом
п
F (а) = 2 xk^k (а),
^=1
коэффициенты которого хг- меняются в замкнутой вы-
пуклой области Q. Это приближение должно быть
наилучшим в том смысле, что величина
п
ц (х) = max f (а) - 2 xkqk (а)
k=l
должна быть минимальной.
Представим функцию |ы(х) в несколько ином, бо-
лее удобном для исследования виде
/	п	\
ц(х)= шах Щ(а)-2 ЗДрЦа) .
(5.12)
Легко видеть, что ц(х) есть выпуклая функция х,
причем она образована как максимум по компактно-
му множеству семейства функций
(п
f(a)- 2 Xi<fi(a)
i = l
7*
99
Эти последние очевидным образом непрерывно диф-
ференцируемы по х и
a, g)= - Ucpja), gq>2(«), •••• 1фп(«)Ь
На основании теоремы
x°(=Q доставляла ц(х)
статочно существование
5.3, для того чтобы точка
минимум, необходимо и до-
таких	и {a2, gj, что
Ф1 (а<)
Фп (а/)
п + 1
2^ = 1,	(5.13)
1=1
причем все пары {аг, таковы, что на них дости-
гается максимум в (5.12) при х = х°. Отсюда следует,
что
ц(х)= Ж)” 3 x°q>fc (az) ,
k= 1
(п	\
f (az)~ 2 х»фА(аг) .
k= 1	/
(5.14)
Этот результат резюмирует следующая теорема.
Теорема 5.4. Для того чтобы коэффициенты
х®, k=\, ..., п, были решением поставленной выше
задачи чебышевского приближения, необходимо и до-
статочно, чтобы нашлись такие числа и точки
оц^Е, что выполняются соотношения (5.14), (5.13),
где ДХо есть двойственный конус к конусу допустимых
направлений в точке х° области Q.
Следствие. Если Q — все пространство, то
условие (5.13) может быть записано в виде
(5.15)
Применим теперь полученный результат для слу-
чая, когда Е—множество на числовой оси, а срл(а) —
100
= а/г-1. Пусть ссг- — точки, в которых
а^Е
f («;) - 2
(5.16)
Ь = sign f (а,) - 2 х^а*-1 ,
\	k=\	/
причем ai аг . ^Сал+1, существование которых
гарантируется теоремой 5.4. Тогда на основании
(5.15) найдутся такие числа Хг^>0, сумма которых
равна единице, что
2*&
i=i
= о.
(5.17)
Заметим теперь, что если среди а* имеются рав-
ные, то им соответствуют одинаковые векторы
£. (а9, аЬ •••» а?-1)- Собирая при них коэффициенты
в (5.17), мы получим, что найдутся такие аг-,
аг < аг-+1, и числа	что выполнено (5.16) и
2^ы :	=о, 2^=1,
где г^/г+1 и г есть число различных а^ Но так как
при различных а; векторы g. (а9, aj, ..., а?”1) ли"
нейно независимы, если	то отсюда следует,
что г = п+;1, т. е. найдется в точности /г+1 точка аг-,
для которой выполняется (5.16), и при этом все
hi — hi > 0
Таким образом, можно считать, что все аг-, вхо-
дящие в (5.17), различны.
Ю1
Рассмотрим теперь (5.17) как систему уравнений
относительно неизвестных Перенося столбец, со-
ответствующий i = n+\, в правую часть, получаем
систему уравнений
Z = 1
относительно неизвестных Xigz, /=1, ..., п. По пра-
вилу Крамера решение этой системы можно записать
в виде
a t _ _ 1 t Р(аь az-i, ая+ь az+i, • aJ
Mz~ iSn+i	D(ai, а„)
где
D (ab an) =
a? «2	••• an
a] a> ... a;
a?~1	a2~"1 * * * an"1
D(ai, ..., an) есть определитель Вандермонда, ко-
торый, как известно, положителен, если ai < аг < ...
... < ап. Далее, так как каждая перестановка столб-
цов определителя ведет к изменению его знака, то
D (ab .... a,_b a„+b a/+b ..., a„) =
= (-l)“"‘D(a1, ..., a(_b a(+b ...» an, a„+1).
Поэтому
At __ a t /	1	(cti, . . CCZ—1, aZ+b • • • , CCn, an+l)
Azfez- “	/)(«!, an)-----------•
Так как Xz, Xn+i и оба определителя положительны,
то из последней формулы следует, что
^ = - (—l)re-4n+l.
т. е. в
п
f(a)-2
k=\
точках ai, аг, ...» an+i,
достигает своего
в которых
максимального
значения, знаки уклонения чередуются,
102
Таким образом, показано, что для того, чтобы
полином
F (а) = 2 х°ак~1
k=\
был наилучшим приближением непрерывной функции
f(a) на компактном множестве £, лежащем на дей-
ствительной оси, необходимо и достаточно, чтобы
уклонение
f(a) - 2 4afc-'
k=l
достигало своего максимума не менее чем в п+1
точке ai < аг < ... <an+i, аг- е £, причем знаки укло-
нения в точках cd чередуются. Это есть классический
результат теории чебышевского приближения.
Возвратимся теперь снова к случаю, когда множе-
ство Е есть компактное множество s-мерного про-
странства Es.
Теорема 5.4 и ее следствие утверждают, что для
того, чтобы обобщенный полином
F0 (а) = 2 x°kcf>k (а)
k=l
был наилучшим приближением непрерывной функции
f(a), необходимо и достаточно выполнения условий
(5.14) и (5.15), т. е. чтобы уклонение |/(сс)—f°(a) |
достигало своего максимума в точках а2-, г=1, ..., г,
г n + 1, и было выполнено (5.15). Но если мы рас-
смотрим вместо Е множество ЁУ состоящее из точек
аг, i=l, •.., г, то условия (5.14), (5.15) будут также
необходимыми и достаточными условиями того, что
полином F°(a) наилучшим образом приближает f(a)
на множестве Ё. Таким образом доказана
Основная теорема теории чебышев-
ского приближения. Полином наилучшего при-
ближения к непрерывной функции f(a) на компакт-
ном множестве Е является одновременно полиномом
наилучшего приближения для функции f(a) на мно-
жестве I? = {ai, ..., ar}, r-^n+1. Другими словами,
существуют такие точки сц^Е, i=l, ..., г, г^п+1,
что один из полиномов наилучшего приближения для
103
f(a) на множестве Ё одновременно является поли-
номом наилучшего приближения на всем множе-
стве Е,
Рассмотрим теперь общую задачу теории чебы-
шевского приближения в пространстве Банаха В.
Пусть й— произвольное выпуклое замкнутое множе-
ство в В и ц(х) = ||х||. Найдем необходимые и доста-
точные условия того, что точка х0 минимизирует ц(х)
в й.
Так как
ц (%) = || х || = шах х* (х),
х* е s*
5*={х*: х*е=В*, || х* ||< 1),
то ц(х)—выпуклый функционал и его множество
опорных функционалов в точке х состоит из тех
x*gS*, для которых х*(х)=||х|| (см. теорему 1.6).
На основании следствия теоремы 2.1 мы можем
утверждать, что точка х0 е Й тогда и только тогда
доставляет минимум ||х|| в й, когда существует такой
опорный к ||х|| в точке х0 функционал, что
х*(х0) х* (х) для всех х е й.
(5.18)
Учитывая данную выше характеристику опорных к
||х|| функционалов, мы можем сказать, что
xo(xo) = |NI и llXo|=1- <5-19)
Допустим теперь, что й состоит из элементов вида
п
X = X + 2 С1ХЬ
1	= 1
где вектор c = {ci, ..., сп} меняется в некоторой вы-
пуклой области С. Тогда минимизацию
II	х II = X + 2 С1Х1
II г-1 II
по се С можно рассматривать как наилучшую ап-
проксимацию элемента х с помощью линейной ком-
бинации элементов х^ с коэффициентами из заданной
области.
104
Теорема 5.5. Для того чтобы вектор с° <= С
минимизировал
п
X + 2 CiXi
Z=1
необходимо и достаточно существование такого функ-
ционала х*, что
*о(* + 2 |х + 2	|х’||=1 (5.20)
и
2 х*(xz)— сJ	0 для всех с^С. (5.21)
Доказательство. В рассматриваемом слу-
чае Q есть множество элементов вида х+2зд,
с е С. Утверждение теоремы есть теперь непосред-
ственное следствие (5.18) и (5.19), если подставить
в них выражения для х и х0:
п	п
X = X + 2 cixb *о = X + 2 с°;хг
i=l	Z=1
Следствие. Если С = Еп, то условие (5.21) за-
меняется на условие
x;(xz) = 0, z= 1, п.	(5.22)
Действительно, если С = Еп, то величины с{ в ле-
вой части (5.21) могут быть любыми и неравенство
(5.21) не будет нарушаться, только если справедливы
равенства (5.22).
5. Задача линейного оптимального управления с
фазовыми ограничениями. Рассмотрим объект, пове-
дение которого, описывается системой дифференци-
альных уравнений
= Ах + Вщ 0 < / < Г,	(5.23)
где х — ft-мерный вектор, А—ft X ft-матрица, а В
есть ftXr-матрица.
Управление u(t) есть измеримая функция, при-
чем для каждого t u(t) принадлежит выпуклому
105
компактному множеству U, U с. Ег. Такие управле-
ния будут называться допустимыми.
Среди всех допустимых управлений u(t) необхо-
димо найти такое, что соответствующая траектория
удовлетворяет условиям
х(0)-х° = 0,
х(Т) — х1 = О,
p_j(x(.))= max g-i(x(0X0,
ос/ст
и такое, что функционал
Ио(х( • ))= max gQ(x(t))
достигает на нем своего минимума. Здесь gi(x)t
i = 0, —1, непрерывно дифференцируемые функции х.
Изучим поведение функционалов цг-. Это функцио-
налы, определенные на пространстве n-мерных не-
прерывных функций Сп. Поскольку каждая траекто-
рия системы (5.23) зависит от соответствующего до-
пустимого управления, то через эту зависимость
становятся функционалами над пространством управ-
лений.
Нетрудно видеть, что в силу свойств интеграла
Стилтьеса
т
Н/ (х (•)) = max [ gi (х (/)) da (t),
а е М* 0J
где М*— множество всех монотонно неубывающих
функций, удовлетворяющих условию о(0) =0, а(Т) = 1.
Каждой функции x(t) можно поставить в соот-
ветствие функцию gi (х(0), которая также есть не-
прерывная функция из пространства С1. Таким об-
разом определен некоторый нелинейный оператор
®г-: О-+С'.
Если теперь определить функционал v в простран-
стве С1 как
т
v(y( • ))= max f y(f)da(t),
a e M*
то мы можем записать
щ(х(.)) = v@t-(%(•)).
I Об
Замечая теперь [2], что множество Л4* функций а
есть выпуклое слабо замкнутое ограниченное мно-
жество в пространстве, сопряженном к С1, и приме-
няя теоремы 1.6 и 3.1, получаем, что цг(х(-)) есть
квазидифференцируемый функционал, причем
(х° (•))
де
т
max I (dxgi(x°(f)), e(t))da,
аеАРЦИО)*
где М*(х°(«))—множество тех оеЛ4*, для которых
т
О
( dg.
e(t) — произвольный элемент Сп, a dxgt(х) = j »
^gj	dSj 1
дх2 ’ ’ ’ ’ ’ дхп J ‘
Покажем теперь, что (%(•)) есть квазидиффе-
ренцируемый функционал не только относительно
пространства непрерывных функций, но и относитель-
но пространства управлений. Для этого заметим, что
справедлива известная формула Коши [46], выражаю-
щая решение системы (5.23) через управление в виде
t
х(О = Ф(О^о + Ф(О/ ®~{(x)Bu(x)dx,
О
где Ф(£)—матрица, удовлетворяющая системе урав-
нений
= ДФ, Ф (0) = /,
I— единичная матрица.
В силу этой формулы каждому сдвигу управле-
ния в направлении £(/) соответствует сдвиг траек-
тории в направлении
t
Хе (Г) = ЛФ (0 J Ф“1 (т) BE (т) dx.	(5.24)
о
Если теперь рассматривать щ(%(•)) как сложный
функционал над пространством управлений, то он
107
оказывается квазидифференцируемым и
дЕ	де
Г /	t	х
= шах [| dgi(*0(^))> Ф(0 [ф”1 (т)	(т) dx lda(/).
У	\	0J	J
Далее, в силу формулы Коши ограничение х(Т) =
=хх определяет ограничение
т
Ф (Г) х0 + Ф (Г) j Ф“‘ (0 Ви (/) dt - X1 = О,
О
которое эквивалентно заданию ограничений в виде п
линейных функционалов.
Применим теперь к исследуемой задаче теоре-
му 4.2. Для этого возьмем в качестве множества М
множество допустимых управлений. Тогда в силу вы-
пуклости множества U и линейности ограничений типа
равенства в качестве конуса Км можно взять конус
Км =	£ (7) = X (и (/) — u°(Z)),
и (/) — допустимое управление, Л^О),
где 4/°(/)—оптимальное для данной задачи управ-
ление.
Далее, легко видеть в силу определения двойст-
венного конуса, что теорема 4.2 допускает в своей
утверждающей части следующую эквивалентную фор-
мулировку: найдутся такие числа Лг-, не все равные
нулю, и функционалы х*. е М (х0), что
k
S А,.х*(е)^0 для всех е^Км>
i = — m
Ki > О, i 0,	(х0) = 0 для i 0.
В исследуемой задаче множества Л4г(х0), z = 0,—1,
в силу формулы для производной по направлению
состоят из функционалов х* вида
Т /	t	X
j” <W*°m Ф(0]* Ф’'(т)В£(т)й da(f),
о \	о	/
где о (/) е Af*(x°(-)).
108
Для ограничений типа равенства в силу их ли-
нейности функционал х* имеет вид
т
Ф(Т) J Ф"‘(0 BE(f)dt.
О
Применяя теорему 4.2, мы можем утверждать:
для того чтобы управление u°(t) и соответствующая
ему траектория x°(t) были оптимальными в постав-
ленной задаче, необходимо, чтобы нашлись такие
числа Хо, Х-i > 0, вектор X = {Xi, ..., Хп} (причем
Хо, Х-i, X не все равны нулю) и неубывающие функ-
ции По (0» a-i (0» что
° Т /	t	ч
S J dSi U° (О). Ф (0 / Ф"1 (т) BE (т) dx dOi (0 +
t = —1 о \	о	/
(т	\
Л,Ф(Г) J	(5.25)
о	/
для всех E(t) Км, или, что эквивалентно, для всех
E(t)=u(t)—u°(/), где и(/)—допустимое управле-
ние. Кроме того, должны выполняться условия
<М0) = 0, пДП=1,
J гг(х0(0)^(0 = нДх0(0), i=- 1. О,
Л_1Ц_1(х<>(.)) = 0.
(5.26)
Мы не будем утомлять читателя несколько гро-
моздкими выкладками, сводящимися к замене по-
рядка интегрирования в (5.25). После таких выкла-
док неравенство (5.25) приводится к виду
т	т
| (ф(т), Ви(х)) dx^- | (ф(т), BuQ(x)) dx,
о	о
где
ф(т) = Ф”1¥(т) X
г о т
2 и J ф" (0 dxgi (х° (0) da, (t) + Ф‘ (Г) К
_j = -l X
(5.27)
(5.28)
109
и звездочка при матрице означает транспонирование.
Но из условия (5.27) следует, что оптимальное управ-
ление должно удовлетворять условию
(ф(т), Ви? (т)) = min (ф (т), Bv) (5.29)
v^U
для почти всех т,
Полученные выше результаты резюмирует следую-
щая-теорема.
Теорема 5.6. Для того чтобы допустимое управ-
ление uQ(t) было решением сформулированной в на-
чале пункта задачи, необходимо существование та-
ких чисел %2>0, i =— 1, 0, вектора К и неубываю-
щих функций что выполняются условия (5.29),
где функция ф(т) определена соотношением (5.28),
a ki, Z и удовлетворяют условиям (5.26).
Замечание 1. Легко видеть, что если g\(x)—
выпуклые функции, то рассмотренная задача есть
задача выпуклого программирования, и если Хо > О,
то условия теоремы 5.6 являются достаточными.
Замечание 2. Отметим некоторые свойства
функции ф(т). В каждой точке, где ог2(т), i = — 1, О,
дифференцируема, т. е. почти всюду (так как о2(т)—
неубывающие функции), ф(т) имеет производную, ко-
торая дается формулой
о
i = -l
получающуюся простым дифференцированием (5.28).
В точках разрыва функций о2(т) функция ф(т) также
терпит разрыв, причем в силу определения интеграла
Стилтьеса
о
ф (т — 0) — ф(т + 0) = s Д<тг (т) dgt (х° (т)).
i= — \
Здесь До2(т)—величина скачка о2 в точке т.
В заключение отметим, что различные более
сложные ограничения на правый конец траектории
и на фазовые координаты в рассмотренной задаче
могут быть учтены, подобно тому как это было сде-
лано выше, без особых трудностей.
110
6. Принцип двойственности в выпуклом програм-
мировании. Пусть В — пространство Банаха, фДх),
1 = —т, —(т—1),	—1, 0, — выпуклые функцио-
налы, фДх), i = 1, k,— линейные функционалы
и X— выпуклое множество. Требуется решить задачу
min фо(х),
ф( (х) < О,
КО,
i>0,
(5.30)
<р,(х) = О,
хеХ.
Рассмотрим множество М в пространстве размер-
ности tn+k+1, определенное следующим образом:
M = {z: z^Em+k+\	x<==X}.
В дальнейшем будем предполагать, что множество М
компактно.
Положим
k	k
p(i/) = max 2 wt^z(x) = max 2 Щ%1 (5.31)
X^X i = — m	M i = — m
и рассмотрим задачу минимизации этой функции на
множестве
Q= {и: uQ = — 1, при i <0).
p(w) есть выпуклая функция. Так как функция
k
Z)= 2 uizi
i= — m
дифференцируема по и,
dufi(u,z)=z, z={z.m, ..., z0, .... zh],
то, согласно теореме 3.4 и замечаниям 1, 2 и 3 к
теореме 3.2, множество опорных функционалов к
ц(и) в точке и° есть выпуклая оболочка векторов г,
удовлетворяющих условию
k
2	=p(u°),
Z = — m
111
или, что то же самое, есть выпуклая оболочка век-
торов ф(х) таких, что
k
S u9qp. (х) = pi (u°), х g X, (5.32)
i*= — m
<p(x)=	.... <Po(x),	<Pfe(x)}.
Таким образом, любой вектор из М(и°) предста-
вим в виде
i	i
2 /ф («^/)>	। Лу = 1, Лу О,
причем каждая из точек Xj удовлетворяет условию
(5.32).
Рассмотрим теперь конус допустимых направле-
ний к области Q в точке и0. Легко видеть, что Ги* со-
стоит из таких векторов е = {е_т, .... е0, ej, что
et произвольно, если u9<0, /<0,
et 0,	если uQ. = 0, i < 0,
6q = 0,
ei произвольно, если i > 0.
Поэтому двойственный конус состоит из векто-
ров е*, имеющих следующую структуру:
е\ = 0, если u?<0, Z<0,
если w9 = 0, Z < 0,
е* произвольно,
е* = 0, если z>0.
Согласно теореме 2.1 в точке w°gQ, в которой p,(zz)
достигает минимума на Q, должно выполняться ус-
ловие
0-
Это значит, что найдутся такие точки %у е X, / = 1, ...
..., I и числа kj 0, что вектор
I
с = 2 MU/)
112
будет принадлежать Г*о, причем дополнительно вы-
полняются условия
2 А/ = 1,
/=1
а каждая точка Xj удовлетворяет условию (5.32). Но
тот факт, что се означает в силу сказанного выше
о конусе что
если
если
ц0 = 0,
(5.33)
2 МЛх/) = °>
если
Рассмотрим теперь точку
х0= 2 ^/Х/.
Так как X выпукло, Xj е X, то и хоеХ. Далее, из
выпуклости функционалов фг(х) для и их ли-
нейности для i > 0 на основании (5.33) получаем
i
<Р/ Uo) < 2 Мр/ (•*/) < ° для z < °,
i
Ф/ (*о) = 2 М/ (*/) = 0 для i > 0.
/=1
Наконец,
i
фо(*оХ 2м>о(*/)-
Таким образом, мы показали, что точка Хо удов-
летворяет всем ограничениям исходной задачи вы-
пуклого программирования.
Покажем теперь, что точка х0 является ее реше-
нием, т. е. минимизирует фо(х).
8 Б. Н. Пшеничный
113
Так как	для а ф, (х) выпуклы для
1<С0 и линейны для i > 0, то
><	k	i
2 «W*o)> 2 «У (•*/)=
i=—m	l^—m Н
/ k	I
= 2 л, 2 «?<pz (*/) = 2 Д-/Н (и0) = и (“°)-
/=]	' i~-m	'
где использовано то, что Xj удовлетворяет (5.32). Но
так как хоеХ, то из определения ц(и) следует, что
k
2 ы°Фг(х0)<ц(ы1).
Таким образом,
k	k
2	(х0)=н («") = 2 «?ф/(•«/)•
/«»—т	i = —m
Умножая последние соотношения на Xj и складывая,
получим, учитывая, что сумма Xj равна единице и
выполнены соотношения (5.33)
k	k / i	\ i
. 2m (x0) = t 2m ь,ф£ (xf)j=«о 2 ^/Фо(*/)-
Так как ф0(х) —выпуклый функционал и и®= — 1,
то из последнего равенства получаем
k
2 «?Ф£Ы<ыоФо(хо)
г = — т
или
k
2 U«(PZ(XO)<O.	(5.34)
i = — т
Но выше уже было показано, что фг(хо) для
i < 0 и ср* (х0) =0 для i > 0.
В силу того, что	для i<0, все слагае-
мые в левой части (5.34) оказываются неотрицатель-
ными. Поэтому неравенство (5.34) возможно лишь
тогда, когда
u^i (Ло) = 0 Для 1	0-
14
Пусть теперь х—произвольная точка, удовлетво-
ряющая ограничениям (5.30). Тогда по определению
р(«°)
k
~Фо(*о) = 2 (хо) = н (и°) >
i = — tn
k
>-ф0(х) + 2	—ф0(х),
i^-tn
ибо ^<^0 для i < 0, а фг(х)<10 для z<0 и
срг(х)=О для i > 0. Таким образом, выполнено нера-
венство фо(*о) ’Сфо(^), показывающее, что точка х0
есть решение исходной задачи выпуклого програм-
мирования.
Нами доказана
Теорема 5.7. Пусть определенное выше множе-
ство М компактно и uQ — точка минимума функции
р(и) (5.31) в области Q. Тогда среди точек, удовлет-
воряющих условию
k
2	.(х) = ц(н°), хе/,
i=-m
найдется такая, которая будет решением исходной
задачи выпуклого программирования (5.30).
В чем основной смысл полученного результата?
Он показывает, что исходной задаче выпуклого про-
граммирования можно поставить в соответствие дру-
гую задачу выпуклого программирования с более
сложной функцией, но с простыми ограничениями, ре-
шение которой эквивалентно решению исходной за-
дачи. Из классической теории линейного программи-
рования известно, что двойственная задача подчас
оказывается более удобной для решения, чем ис-
ходная. Кстати, если применить полученный резуль-
тат к обычной задаче линейного программирования,
то действительно получается задача, двойственная
в смысле теории линейного программирования [32].
Наконец, отметим следующую важную особенность
двойственной задачи: она конечномерна, даже если
исходная задача не была таковой. Именно этот факт
широко используется в ряде алгоритмов для реше-
ния линейных задач оптимального управления.
8!
115
7. Системы выпуклых неравенств. Теорема Хелли.
Покажем, как полученные результаты по теории не-
обходимых условий экстремума могут быть приме-
нены к изучению условий разрешимости систем вы-
пуклых неравенств.
Пусть L — линейное пространство и фг(х), /=1, ...
..., п,— выпуклые функционалы на нем. Рассмотрим
систему неравенств
фг(х)<0,	/=1, п, х^Х, (5.35)
где X — выпуклое множество в L. Пусть
ф(х)= {<Р1(х), ..Ф„(х)},
М = [г: z^En, г = <р(х), хеХ}.
Допустим, что множество М компактно. Тогда
существует ограниченная функция
ц (X) = max (%, z) — max (Л, ф (х)).
z^M	х^Х
Рассмотрим эту функцию на множестве
Q = | X: X < О, 2 X; = - 1
I	г = 1
р(Х) —выпуклая функция на этом множестве и до-
стигает на нем своего минимального значения в не-
которой точке АЛ
Теорема 5.8. Если множество
M = {z: z<=En, г = ф(х); х^Х}
компактно, то для разрешимости системы (5.35) не-
обходимо и достаточно, чтобы функция
p(Z) = max(X, ф(х))
хе/
была неотрицательной при всех значениях й.
Доказательство. Мы уже неоднократно
имели дело с функциями типа ц(Х), в частности в
предыдущем пункте этого параграфа. Там было по-
казано, что множество опорных функционалов к этой
функции М(Х) есть выпуклая оболочка всех векто-
ров ф(х), удовлетворяющих условию
(Х,ф(х))=и(Л), хе^Х. (5.36)
116
Пусть теперь Х° е Q есть точка минимума функ-
ции ц(А,) в Q и ц(Х°) неотрицательно. На основании
следствия теоремы 2.1 в точке Л,0 должен существо-
вать такой вектор с°еЛ1(Х) (поскольку простран-
ство конечномерно), что
(АД с°)	(X, с°) для всех й,
т. е. в силу определения множества Q
(АД c°)=min(X, с°)= — шах Л (5.37)
X е Q	к i < п
Далее, согласно вышесказанному о структуре мно-
жества М(Х), найдутся такие числа и точки Xj,
удовлетворяющие (5.36), что
k	k
с°= 5 У/Ф(х/), 2y/=*1,	Y/>0.
/-1	/-1
Отсюда следует, что
(V, с°) = i Y/ (Х°, ф (Xj)) = и(Х°) > о.
С учетом (5.37) и выражения для с° это дает
k
шах 2 YzTz (Xf) < 0-	(5.38)
i
Пусть теперь
k
Так как фДх)—выпуклые функционалы, то
п	п
ф/ (х0) < 2 Y/Ф/ (х/) < max 2 Y/Ф; (х/) < 0,
/=i	i /-1
т. е. точка х0 есть решение системы (5.35).
Достаточность условий теоремы доказана. Их не-
обходимость очевидна, так как, если для некоторой
точки х0^Х, фДхоХО, то р.(Х) = тах(Л, ф(х))>
хеХ
> (X, ф (х0)) > 0 для X е Q.
Рассмотрим теперь случай, когда L конечномерно
и имеет размерность р, L = EP.
117
Теорема 5.9. Пусть X — компактное множество
в Ер. Тогда для совместности системы (5.35) необхо-
димо и достаточно, чтобы любая подсистема из
(5.35), состоящая не более чем из р+1 неравенства,
была совместна.
Доказательство. Необходимость опять оче-
видна. Покажем достаточность. Для этого рассмот-
рим задачу
гтпц(х), х<=Х,
где
р(х) = шах срДх).
1 < i < п
На основании теоремы 1.4 множество опорных к
ц(х) функционалов состоит из р-мерных векторов х*,
представимых в виде
i е / (хо)
где
/(x0)=(Z: 1 < i«С п, фг(хо) = М*о));
х] — какой-либо опорный функционал к фДх) в точ-
ке х, а
2 Л;=1,
i е / (х0)
Заметим, что, поскольку х — р-мерный вектор,
т. е. х^£р, а сопряженное пространство к Ер экви-
валентно самому Ер, то мы можем говорить о функ-
ционалах х* е (Ер)* как о р-мерных векторах.
Если теперь обозначить через Л4г(х0) множество
опорных к фг(х) функционалов в точке х0, то приве-
денный выше результат о структуре множества опор-
ных ц(х) функционалов может быть сформулирован
и таким образом:
M(x0) = col (J
\i / (х0)	/
Это выражение для множества опорных функциона-
лов, кстати, также непосредственно следует из тео-
ремы 3.4, причем черта над знаком со убрана,
поскольку множества Мг(х0) замкнуты, а значит, зам-
кнуто и их объединение, так как объединение конеч-
ного числа замкнутых множеств замкнуто и выпуклая
118
оболочка компактного множества в конечномерном
пространстве также замкнута. Поскольку рассматри-
ваемое нами пространство р-мерно, то всякий вектор
из выпуклой оболочки может быть представлен в
виде выпуклой линейной комбинации не более чем
р+1 вектора из исходного множества. Поэтому вся-
кий опорный к ц(х) функционал (вектор) может быть
записан в виде
**=.2^,	г<р+1,	(5.39)
где if /(х0), х* е (х0). Выпуклая функция
ц(х) достигает своего минимума на компактном мно-
жестве X в некоторой точке х0. Согласно следствию
теоремы 2.1 в Л4(х0) найдется такой функционал х^,
что
хо (хо) хо W для всех х X. (5.40)
Для нашей задачи это означает, что найдется такое
г^р+1, такие и такие х^еМ^(х0), что xj
в (5.40) представим в виде (5.39). При этом
ij е / (х0) и
2л-/ = 1.
/-1
Но, согласно теореме 1.4, х* есть опорный в точке х0
функционал для выпуклой функции
р-(х) = шах Ф/Дх).
Согласно следствию теоремы 2.1 (5.40) есть не-
обходимое и достаточное условие того, что функция
р, (х) в точке х0 достигает своего минимума При этом
ц(х0) = Ц(х0),
ибо	и, значит, в точке х0
<Pi,(xo) = |*(xo),	/==1, ...» г,
по определению I (х0).
По условиям теоремы система неравенств
Ф^(х) <0, /=1, ..., г, г-^р + \, х^Х,
119
совместна. Это значит, что для некоторой точки
Xj €= X
<PfyUi)<0. /=1, .... р,
а следовательно,
Д (xi) <0.
Поэтому
Ц (х0) = Д (х0) = min Д (х)< Д (xj < 0.
х е X
Но из определения ц(х0) следует, что
фг (Хо) <Ц(Хо) <0,
т. е, точка х0 есть решение системы.
Теорема доказана.
Покажем, что следствием предыдущего резуль-
тата является известная теорема Хелли (см., напри-
мер, [5], [37]). Пусть в р-мерном пространстве задана
конечная система выпуклых компактных множеств
/=1, ..., т. Положим
Wi (ф) = шах (ф, х),
х <=
Fi(x)= max [(ар, х)-ГДф)].
II Ф IK 1
Легко показать, основываясь на теореме отделимости,
что х е Xi тогда и только тогда, когда
^(х)<0,
причем Fi(x)—выпуклая функция. В самом деле,
если XqE^, то по определению ММф)
(ф, х0) — №г(ф) <0 для всех ф.
Обратно, пусть Fi(xQ) <0, т. е. для всех ф,
||ф|| = 1 выполнено последнее неравенство. Если до-
пустить, что хо Xh то по теореме отделимости най-
дется такой вектор фо, 11фо11 = 1 и 6 > 0, что
(фо, х) < (фо, Хо) — б для всех х s Xit
т. е.
б < (фо, Хо) —	(фо),
а это противоречит предположению.
120
Итак, каждой системе компактных выпуклых мно-
жеств можно сопоставить систему неравенств
Fi(x) ^0, 1 = 1, m, xsX,
с выпуклыми функциями Fi и множеством X, в каче-
стве которого можно взять шар достаточно большого
радиуса, содержащий все Х^ Очевидно, пересечение
множеств Xi не пусто тогда и только тогда, когда
система совместна. Но по теореме 5.9 такая система
совместна тогда и только тогда, когда совместна лю-
бая ее подсистема из не более чем р + 1 неравенства.
Если перевести это на язык выпуклых множеств, то
получаем теорему Хелли.
Теорема Хелли. Если выпуклые компактные
множества Xi, i = 1, ..., m, таковы, что любые р + 1
из них имеют не пустое пересечение, то и пересече-
ние всех множеств не пусто.
8. Проблема моментов. Одной из весьма важных
математических задач, которая имеет широкие при-
ложения, является проблема моментов. Она может
быть описана следующим образом. Задано пространст-
во Банаха В и конечное число элементов Xi этого про-
странства. Необходимо найти функционал х* е Я*, об-
ладающий минимальной нормой и удовлетворяющий
системе неравенств
Х*(%г)—(Xi 0,	£=1, ..., п,
где ai — заданные числа.
Чтобы связать поставленную задачу с вопросом
о разрешимости системы выпуклых неравенств, иссле-
дуем совместность следующей системы:
%*(%г)—(Zi^O, i=l, ..., п, ||х*|| ^р. (6.41)
Очевидно, что нахождение минимального р, при
котором система (5.41) совместна, эквивалентно ре-
шению проблемы моментов.
Для того чтобы была применима теорема 5.8, не-
обходимо убедиться, что множество
M = (z: z^En, Zi = х* (х^-щ, z=l, nt ||x*IKp}
компактно. Но на основании того, что выпуклое огра-
ниченное слабо* замкнутое множество в В слабо*
9 Б. Н. Пшеничный
121
бикомпактно, можно утверждать, что множество
$;={*: II* II <р)
слабо* бикомпактно.
Действительно, если ||*о||> Р’ то найдется такой
элемент х0, ||х0||	1, что
х‘о(хо)>р.
Выберем теперь е>0 таким, чтобы х* (х0)—е было
больше р. Тогда окрестность
r0={Z: |х‘(х0)-х’0(х0)|<8)
точки х*0 не пересекается с множеством S*, ибо для
х’е Wo
х’(х0)>х‘(х0)-е>р,
а значит,
11**11 = sup х* (х) > х* (х0) > р.
II х || <1
Таким образом, каждая точка множества, допол-
нительного к множеству Sp, может быть окружена
окрестностью, не пересекающейся с S*, откуда и
следует, что множество, дополнительное к S*, откры-
то, а значит, S* слабо* замкнуто. Далее, по опреде-
лению слабой* топологии отображение
zt = х* (xz) — az, i = 1, ..., n,
непрерывно. Отсюда следует, что множество М как
непрерывный образ бикомпактного множества само
бикомпактно в обычной евклидовой топологии, а зна-
чит, просто компактно, поскольку в евклидовой топо-
логии понятия компактности и бикомпактности сов-
падают. (По поводу использованных здесь понятий и
определений функционального анализа см. Введение,
а также [1], гл. I, § 5.6 и гл. V, § 4, теоремы 2.3.)
Из сказанного следует, что множество М ком-
пактно, а значит, мы находимся в условиях приме-
нимости теоремы 5.8.
122
Для системы (5.41) функция ц(Л), использован-
ная в теореме 5.8, имеет вид
п
|1(Л)= шах 2 (** U0 — az) =
II X* ||<р 1 = 1
(п	\	п	II п	|1	п
2	= р 2 ^iXt - 3
1=1	/	£=1	II i = l	II	(-1
(5.42)
Теорема 5.10. Система неравенств (5.41) совме-
стна тогда и только тогда, когда
2
Z = 1
i = 1, •. •, п
п
2
i = \
(5.43)
Поставленная выше проблема моментов разре-
шима, если правая часть (5.43) (обозначим ее че-
рез о) конечна. В этом случае минимальная норма
функционала, являющегося решением проблемы, рав-
на шах (0, о).
Доказательство. На основании теоремы 5.8
для совместности системы 5.41 необходимо и доста-
точно, чтобы функция (5.42) была неотрицательна
при всех Xf, 1=1, ..., п, удовлетворяющих условиям
лг<о, Saz=-i.
Z = 1
(5.43) есть просто другая запись этого факта, непо-
средственно следующая из (5.42). Условие того, что
сумма Хг- равна единице, при этом может быть от-
брошено, так как правая часть (5.43) при умножении
всех Кг на одну и ту же константу не меняется.
Утверждение теоремы о разрешимости проблемы
моментов следует из отмеченной уже выше связи
между этой проблемой и разрешимостью системы
(5.41), с учетом того, что норма функционала всегда
положительна.
Часто проблема моментов встречается в лите-
ратуре в несколько другой форме. А именно, тре-
буется найти функционал минимальной нормы,
9*
123
удовлетворяющий условиям
Х*(%г)—ОСг = О, Г=1,	(5.44)
Очевидно, что такая постановка эквивалентна
предыдущей, если расписать каждое из равенств в
виде двух неравенств
х* (xz) - az < О,
Х*(-xz)-(-az)<0,
i=l, ..., п.
Поэтому к такой постановке проблемы моментов при-
менима вся предыдущая теория. Если применить тео-
рему 5.10 с учетом удвоения системы неравенств, то
получим, что система (5.44) имеет решение х*,
||х*[| <^р, только если
Р>О,
где
2	)ai
СТ = sup -jj-^--------,
£-5° |2(V-^)xz
или (если ввести обозначение Л = V — V и учесть,
что когда V и V меняются в отрицательной области,
то % пробегает все пространство)
О' = sup
п
i= 1
п
Z = 1
(5.45)
Таким образом, мы можем сформулировать сле-
дующее следствие теоремы 5.10.
Следствие. Минимальная норма функционала,
удовлетворяющего ограничениям (5.44), равна а и
определяется равенством (5.45).
Замечание. Очевидно, что если не все аг- рав-
ны нулю, то
а==Т>
(5.46)
124
где нижняя грань берется по всем X, удовлетворяю-
щим ограничению
2^=1-	(5-47)
1 = 1
Если xiy i = 1, ..., п, линейно независимы, то ниж-
няя грань достигается и отлична от нуля. Действи-
тельно, применяя неравенство Буняковского — Швар-
ца к (5.47), получаем, что
п
1 = 2 М/ <1 Л I • I а|,
i 1
где
/ п \ 1/2
I а | = 2 <4
V-1	/

Таким образом, из (5.47) следует, что

Пусть теперь
II п
р => min 2 hxi
iA.i-.ih-i
Так как х{ линейно независимы, то р > 0. Тогда для
любого вектора % = {%ь ..., XnJ, отличного от нуля,

или
РI X |.
Из последнего неравенства следует, что область зна-
чений %, для которых
п
1 = 1
$Xi
п,
i = l
содержится в области
1Л|<
м
р
125
Но ясно, что минимум
надо искать именно
в этой области. А поскольку эта область компактна
и минимизируемая функция непрерывна, то минимум
достигается. Кроме того, этот минимум отличен от
нуля. Действительно, как мы видели выше, если X
удовлетворяет (5.47), то | Л |^| а]”1. Поэтому для
всех таких X
п
>pl Ь 1>.Р1 а Г’ >0.
Полученные результаты позволяют установить
связь между проблемой моментов и задачей чебы-
шевского приближения.
Пусть даны элементы х, xh ..., хп пространства
Банаха. Рассмотрим проблему моментов
min || х* ||,
х* (х)= 1,
х*(х/) = 0,	/= 1, ..п.
На основании предыдущего замечания норма функ-
ционала, являющегося решением этой задачи, равна
1
а==Т’
где
L = min |х + 2	|,	/ = 1, ..., п.
В самом деле, в рассматриваемой задаче ао= 1,
cci = 0, i = 1, ..., п, и поэтому условие (5.47), запи-
сывающееся в виде
п
2 = 1»
Z=0
эквивалентно условию Хо = 1.
Таким образом, нахождение минимальной нормы
функционала в рассматриваемой проблеме моментов
эквивалентно решению задачи наилучшего прибли-
жения элемента х с помощью линейного агрегата
п
2
i — 1
126
Обратно, если числа таковы, что
х + 2 L,
то на основании теоремы 5.5 и ее следствия найдется
такой функционал х*, что
^ixi j
х0
(5.48)
koll=1. *о(л)=0- Z=1........п-
Если L#=0 (а ясно, что только в этом случае о< + оо
и проблема моментов имеет смысл), то, положив
х =L-1Xo, получим из (5.48), что
||х*|| =а,	х*(х) = 1, x*(xz) = 0,
т. е. функционал х* является решением проблемы мо-
ментов. Таким образом, мы установили, что между
проблемой моментов и задачей чебышевского при-
ближения существует двойственная связь и решение
одной из них может быть получено при решении дру-
гой.
Рассмотрим специальный случай проблемы мо-
ментов, когда рассматриваемое пространство есть
пространство С непрерывных функций аргумента /,
меняющегося на отрезке [О, Г]. В таком пространстве
норма задается формулой
||х||= max | x(t) |.
Непрерывные функционалы в С* по известной теоре-
ме [2] имеют вид
т
х*(х) = J x{t)dg{f), g(0) = 0,
О
где g(0—функция ограниченной вариации, причем
||x* 11= Var g(/).
В связи с этим проблема моментов для пространства
С может быть сформулирована следующим образом:
127
найти функцию g(/) с минимальной вариацией на
отрезке [О, Г], удовлетворяющую соотношениям
т
J <р(- (f) dg (t) = ah i = 1, .. ., n,
0
где —непрерывные функции, a a,— заданные
числа.
Согласно замечанию к теореме 5.40 этой задаче
соответствует следующая задача:
min max
2 М» (0
г = 1
к
2	= 1.
i=l
Таким образом, необходимо найти минимум выпуклой
функции
(п	\
2	(0
Z=1	/
конечного числа аргументов на множестве
Q =! Л: 2	= 1 г •
I i=i	)
С функциями такого типа, как р(Х), мы уже неодно-
кратно встречались, например, в пп. 4 и 6 этого па-
раграфа. Если положить
2 М< (0
Z = 1

= |Л(М
то множество опорных функционалов для ц(Х) яв-
ляется выпуклой оболочкой векторов
Б(Оф(О = U(0ti(0, •••> Шфп(0),
|(0= sign [2 Mz(ol,
Далее, легко видеть, что в каждой точке Хей ко-
нус Гк допустимых направлений состоит из векторов е,
12Ь
удовлетворяющих условию
2	= 0.
1 = 1
Поэтому двойственный конус Г*к состоит из векторов
вида ха, где
а = {ai, ..., ап}, —оо < х < + оо.
В самом деле, если а е Г* то
Л
(а, е)> О
для всякого е е т. е. для е, удовлетворяющего ус-
ловию
(е, а) = 0.
Представим а в виде а = ха + &, (а, Ь) = 0. Такое
представление однозначно. Тогда
х(а, е) + (&, е)^ 0
или
(&,е)>0
для е е 1\. Но —b 1\, ибо (—&, а) = 0. Таким об-
разом,
— (&, Ь) =—||b||2 X),
т. е. b = 0.
Функция ц(Х) есть непрерывная функция своих
аргументов.
Допустим, что функции фг(/) линейно независимы,
а аг- не все равны нулю. Тогда на основании замеча-
ния к теореме 5.10 минимум ц(Х) на Q достигается и
отличен от нуля.
Пусть Х° Q — точка минимума. На основании тео-
ремы 2.1 тогда в множестве опорных в точке № к
|ы(Х) функционалов найдется такой, который принад-
лежит множеству Гм. Из данного выше описания мно-
жества опорных функционалов и следует, что най-
дутся такие Yj^O, j = 1, г, х и точки /jEK(^0),
что
2 V/№)Ф(^/) =	Y/>0, 2y;=1, rO+1. (5.49)
/=i	/-1
129
Если умножить скалярно (5.49) на вектор Х° и учесть
определение множества К(Х), и соотношение
(Х°, а)= 1,
то получим
х = ц(^°) = L > 0.
Пусть теперь
(0, 0 < t < th
^i^ = [ 1,
g (0 = т; S Y4 (^) gj (0-
/=i
Тогда на основании определения интеграла Стилтьеса
и (5.49) имеем
г
J ф (0 dg (0 = т S	ф = а’
о	/=1
или в покомпонентной записи
т
/ Ф/(0dg(t) = ah	i = 1, ..., п.
о
Далее, g(t)—кусочно-постоянная функция, имеющая
скачки, равные y/g(//)L"’1 в точках tj. Поэтому ее
полная вариация равна просто сумме абсолютных ве-
личин скачков. Но
'1 = т2^ = т = а-
/=1 /=1
Таким образом, норма функционала, соответствую-
щего g(t), равна а. Поэтому на основании замечания
к теореме 5.10 мы можем утверждать, что построен-
ный функционал есть решение проблемы моментов.
Теорема 5.11. Если	линейно незави-
симы, то проблема моментов всегда имеет решение в
виде функции ограниченной вариации, которая кусоч-
но-постоянна и имеет не более чем п + 1 точку раз-
рыва, где п — число функций quit).
I3Q
Проблема моментов имеет многочисленные прило-
жения к решению задач линейного оптимального уп-
равления. В заключение этого пункта мы коротко
рассмотрим одну из таких задач.
Пусть объект описывается системой уравнений
х = Ах + Ьи,
где А — пХ n-матрица, b — n-мерный вектор-столбец,
и — одномерная функция управления. Требуется за
время Т перевести систему из начального состояния
%0 в конечное х1, используя импульсное управление с
минимальным суммарным импульсом. Использование
импульсного управления означает, что и (7) имеет вид
k
«(О = 5 yfi {t-tj),
/=1
где tj — моменты подачи импульсов, |у^|—мощность
k
/-го импульса, a | У/1 — полная мощность. Функция
7-1
6(7)—дельта-функция, формально удовлетворяющая
следующему свойству:
3
J <р(0б(0 л = ф(0),
а
если а<0, р>0, причем а и (3 не равны нулю одно-
временно. Если же оба аир одного знака, то приве-
денный выше интеграл равен нулю. Очевидно, что
если
[ 0, 7<0,
1,
то вычисление интеграла с дельта-функцией вполне
эквивалентно вычислению интеграла Стилтьеса
3
J ф(О^о(О-
а
В связи с вышесказанным ясно, что каждому
импульсному управлению можно поставить в
131
соответствие функцию ограниченной вариации
g(t)= 5 Nigo(.i~ tj)>
/=i
k
Varg(/) = 2lY/l-
/=1
Вернемся теперь к поставленной задаче. Посколь-
ку каждое решение линейной системы уравнений мо-
жет быть представлено в виде формулы Коши
t
х (0 = Ф (/) xQ + J Ф (t — т) Ьи (т) dx,
о
Ф(/) = ЛФ(/), Ф(0) = / (единичная матрица), то по-
ставленная задача о переходе из точки х° в точку х1
эквивалентна нахождению управления, удовлетворяю-
щего системе равенств
т
х (Г) = Ф (Г) х° + J* Ф (Т — т) Ьи (т) dx = х1,
о
или
т
J qp (т) и (т) dx = а,
о
где
Ф(т) = Ф (Г - т) Ь,
а = х1-Ф(Г)х°.
Если поставить в соответствие по указанным выше
правилам управлению u(t) функцию g(t), то исход-
ная задача трансформируется в следующую: найти
функцию g(t) с минимальной полной вариацией, ко-
торая удовлетворяет условию
т
/ Ф W dg (т) = а.
о
Но это есть как раз рассмотренная выше проблема
моментов в пространстве непрерывных функций. Если
а =# 0 (при а = 0 решение тривиально: u(t)=O) и
компоненты вектор-функции ср(т) линейно независимы
132
(что также выполняется, если выполнено условие «об-
щности положения», см. [18], стр. 131), то на основа-
нии теоремы 5.11 поставленная проблема моментов
имеет кусочно-постоянное решение g(t), содержащее
не более чем п + 1 точку разрыва. Но такой функции
соответствует импульсное управление, содержащее не
более чем п + 1 импульс, мощности которых совпа-
дают с величинами разрывов g(t) и которые подают-
ся в моменты разрывов g(t). Таким образом, если
tj — точки разрыва g(t), то
w°(0=S(g(^ + 0)-g(//-0))6(/-//)> г Сп+1.
i = l
Суммарная мощность этого управления равна
2 I g (ij + 0) - g (tf - 0) I = Var g (/).
1 = 1
Поскольку полная вариация g(t) минимальна, то от-
сюда следует, что и°(/)—импульсное управление с
минимальным суммарным импульсом.
Таким образом, при широких предположениях о
системе дифференциальных уравнений оптимальное
управление состоит не более чем из п + 1 импульса.
Если использовать результаты, полученные при дока-
зательстве теоремы 5.11, то можно утверждать, что
моменты подачи импульсов лежат в множестве
Л(Л°)={/:	|(Л°, ф(/))| = Л),
L= шах | (Л°, qp(O)l= min max I U, ф(0)1-
9. Дискретный принцип максимума. Широкий класс
процессов управления может быть описан следую-
щим образом: в дискретные моменты времени t = 1,
2, ... выбирается управление uhi и если система на-
ходилась в состоянии xk, то в момент t = k + 1 она
перейдет в состояние которое определяется урав-
нением
Xk+i fh(xhi Uh) =0.	(5.50)
Здесь xh — n-мерные векторы, />(х, и) — n-мерная век-
тор-функция с компонентами ^(х, u), /= 1, ..., п.
Управление uk выбирается из множества (7, которое
представляет собой подмножество r-мерного прост-
ранства.
133
Задача оптимизации описанного процесса состоит
в выборе таких управлений uhi k = 0, W—1, что
выполнены условия
az(xo) = O, i= 1, Ро, (5.51,1)
fe = 0, 1, W (5.51,2)
и функция £o(xn) принимает минимальное значение.
Относительно функций a,(x0), фИх&) будем предпо-
лагать, что они обладают непрерывным градиентом
\а/(хо)> dx^k{xk) соответственно.
Предположим теперь, что функции f*(x, и) непре-
рывны по х и и и непрерывно дифференцируемы по х.
Кроме того, множество fhix^U), которое пробегает
вектор fh(Xk, и), когда вектор и пробегает U, выпукло.
Тогда легко видеть, что поставленная задача укла-
дывается в задачу (4.18). В самом деле, если ввести
векторы
х = {х0, х{, ..., xN},
U = {U0, ^1, • •
и множества
Х=(х: xk<^E", fe = 0, .... ЛД
U = {и: uke=U, /г = 0, N — 1},
то уравнения (5.50), (5.51,1) можно рассматривать
как ограничения типа равенства в задаче (4.18), а
(5.51,2)—как ограничения типа неравенства. Функ-
ции фо(х, и) в задаче (4.18) соответствует функция
go (Xn) 
Пусть теперь вектор е имеет структуру
е = {е0, еь ..., eN}, ek (= Еп.
Тогда производные при сдвиге вектора х в направле-
нии е от ограничений (5.50) и (5.51) имеют соответ-
ственно вид
/z^(u, a) ek+i dXffk(xk, uk)ek,
ha^u' е) = (дха^Хо), e0),
e) = (\^W> ek)-
(5.52)
134
Здесь для ограничений (5.50) сохранены векторные
обозначения, так что hfk(uy е) есть вектор с компо-
нентами
(м, e) = e‘k+l-(dXkf‘k(xk, и), eky
е£+1— /-я компонента вектора efe+1, дх^к(хк, и) — гра-
диент по xk функции zz), а матрица dXffk(xk, и)
имеет в качестве своих строк градиенты дх и).
Проверим выполнение основных предположений
1—4, при которых справедлива теорема 4.6. Для вы-
полнения первого предположения необходимо, чтобы
векторы
{^o(X/v)’	wo)’ •••’ XN~^ N-\{XN-V UN — 1)’
Mxo), •••> flpo(xo)’ <Po(*o)> — ФлгЫ
заполняли выпуклое множество, когда и пробегает (7,
а вектор х — фиксирован. Но это предположение вы-
полняется, так как векторы и0, ..., uN-i меняются не-
зависимо в U и при этом каждый из векторов /\(х&, uk)
пробегает выпуклое множество.
Далее, поскольку X — все пространство E(/V+I)rt, то
можно положить
+ п
так что и второе предположение выполнено.
Наконец, выполнены и предположения 3 и 4, так
как все функции в (5.50) и (5.51) непрерывно диффе-
ренцируемы.
Теорема 4.6 также требует, чтобы функционалы
hi(u, е), соответствующие ограничениям типа равен-
ства, были линейно независимыми.
Выясним, какие требования это налагает на нашу
задачу. Для этого допустим, что они линейно зави-
симы, т.. е. найдутся такие числа аь i = 1, ...» Ро, и
векторы k = 0, 1, N—1, что
Ро	/V-1
2аД;(«> е)+ S	е)) = °	(5.53)
135
для любого вектора е. Подставив сюда выражения
(5.52), получим
Ро
2 Oxfli (х0), е0) +
7V-1
"Ь [(ф&, &k+1) (ф^, k.	~
Перегруппировка членов дает
/ Ро
2	(х0) ~ (<Wo (х0, «о) )* Фо, ^о) +
\i = l
W-1	\
+ 2(Фа-i -(dXkfk(xk, е*) + (Флг-ь eN) = 0.
(Звездочка над матрицей означает транспонирова-
ние) .
Учитывая теперь, что векторы ел, k = 0, ..., N,
меняются независимо, получаем систему уравнений
Ро
2 o-tdx'flt (х0) = (dXifo (х0> «о) )* Фо>
t=l
^k-\~{dXkfk(xk, ий))*фА = 0,	k=\.......W-l,
Флг-l = 0.
Но из этой системы сразу же следует, что tyk = 0,
k = 0, 1, N—1, так что в итоге получаем равен-
ство
Ро
2 а.дЛа; (х0) = 0.
£ = 1
Если мы предположим, что векторы дХьаДх^ линейно
независимы, то последнее равенство будет выпол-
няться лишь при ai = 0. Но отсюда следует уже, что
все функционалы /ц и hfk линейно независимы, так
как мы убедились, что соотношение (5.53) выпол-
няется лишь при нулевых аг- и
Теорема 5.12. Пусть система управления описы-
вается уравнениями (5.50) и йь, £ = 0, 1, ..., N—1,
xh, й = 0, 1, ..., W, соответственно оптимальное уп-
равление и оптимальная траектория, минимизирую-
щие go(xN) при ограничениях (5.51). Допустим, кро-
136
ме того, что fk(xhiu) непрерывно дифференцируемы
по xh, и то же справедливо относительно функций
а{(х0) и qpft(xft).
Тогда, если множества
fk(xk, U)={fk(xk, и) :u<=U],
k = 0.........W-l
выпуклы при любом фиксированном xh, а векторы
dXtat(xo), г=1, Ро, линейно независимы, найдут-
ся такие не все равные нулю числа ₽о 0, Кк О
(6 = 0, 1,	N), а((/=1,	Ро), и векторы
(6 = 0, 1, .... У- 1), что:
Ро
a)	(dxJ0 (х0, «о) )* to = S ^d^at (х0) + А.0<Зл<Ро (х0);
<=1
б)	$k-i-(dXkfk(xk, йк)у-ф* + КкдХк^к(хА) = О,
k=l, Х-1,
в)	tjv-i + ^NdxN<PN (xN) + $0dXNg0 (x,v) = 0;
г)	(tfe, fk(xk, uA)) = max(^, fk(xk, u)),
u^U
k = 0, 1, W-l;
Д) Mt fe) = 0,	£ = 0, ..., W.
Доказательство. Как было показано выше,
наложенные в условии теоремы требования позво-
ляют полностью применить теорему 4.6 к данной за-
даче. На основании этой теоремы мы можем утвер-
ждать, что найдутся такие числа Ро^О, Х/г>0, оц и
вектора tyk, что
ШЙ) = 0,	6 = 0, 1, jV, (5.54
и
Ро	N
(«» е) + 2 aiha, (й,	4"	(^>	4”
0	г=1	1	k=0
+	е))>0 (5.55)
Ю Б. Н. Пшеничный
137
для всех е <= Лх, а также
Ро	<v
Ро£о (х) + 2 аА (хо) + 2 КЯь (хк) +
i=l	fe=O
TV —1	Г	N
+ 2 Oh, xk+i-fk(Xk, йк)) = min pogo (x) + 2 MtCh) +
k = Q	u^U[.	k=Q
Po	/V-1
+ 2 aiat (x0) + 2 Ofc, xfe4 j - fk (xk, uk))
i=l	k=O
(5.56)
Из (5.54) следует выполнение п. д) теоремы.
Далее, очевидно, (5.56) эквивалентно условию
TV—1	TV—1
2 Oh, - fk (Xk, йк)) = min 2 (г|)Ъ - fk (xk, uk)),
fe=0	ue u k=Q
откуда в силу независимости изменения каждого из
uh следует утверждение п. г).
Далее, подставляя в (5.55) выражения (5.52) и
Л«о(«, e) = (<3xA,go(x;v), eN),
получаем
Ро
Ро (d*Ngo (x,v), Cjv) + 2 «1 (дха{ (x0), e0) +
i = 1
N
+	fe)» ek) +
N—\
+ 2q [(^, e*+I) - (грь dXfJk (xkt uk) ek)] > 0.
Перегруппировка слагаемых приводит это неравен-
ство к виду
/ р°	\
5 ^dXQai (х0) + Л^о^^сро (*о) - (dxofQ (х0, й0) )* ф0, е0 +
\х = 1	/
ЛГ-1
+ 2 (Фа-i - (dXkfk (хк, йк)у ih + hdXk<fk (,xk), ек) +
+ (4^-1 + Ро^гуу go (xN) + ^NdXN (xN), eN) 0-
Это неравенство должно выполняться для любого
е Кх. Но так как конус Кх — все пространство и
138
меняются независимо, то неравенство может выпол-
няться лишь в том случае, если равны нулю коэффи-
циенты при всех ек. Приравнивание к нулю коэффи-
циентов при е0, ek и еп дает утверждения а), б) и
в) теоремы.
Условие г) теоремы показывает, что для дискрет-
ных систем, в которых множество fk(xh, U) выпукло,
выполняется принцип максимума в форме, аналогич-
ной принципу максимума для систем, описывающихся
обыкновенными дифференциальными уравнениями
[18]. Известно [47], что если множество fk(xh, U) не
выпукло, то это, вообще говоря, не так. Для таких
систем может быть получен лишь так называемый
локальный принцип максимума. Он получается с по-
мощью теоремы 4.1, если предположить дифференци-
руемость функции fk(Xk,u) по и. Мы не будем здесь
останавливаться на его выводе, поскольку этот вывод
совершенно аналогичен приведенному выше. Вместо
этого мы приведем некоторые соображения, которые
показывают, почему для систем, описывающихся
обыкновенными дифференциальными уравнениями,
справедлив принцип максимума в его глобальной
форме.
Пусть система описывается системой обыкновен-
ных дифференциальных уравнений
«) = 0,	(5.57)
где х — /г-мерный. вектор, f(x,u)— вектор-функция,
непрерывная по обоим аргументами непрерывно диф-
ференцируемая по х. Вектор и меняется в компактной
области U r-мерного пространства.
Если интервал времени [О, Т], на котором рассмат-
ривается система (5.57), разбить на участки [/ft, /А+1],
О = to < t\ < ... < tN-i <tN = Т, то для каждого та-
кого участка можно написать соотношение
*£+1
х (tk+i) - х (tk) - | f(x (0, U (f)) dt = О,
tk
получающееся интегрированием (5.57) на отрезке
[4, 6t+iL Если теперь разбиение проведено достаточно
мелко, то, учитывая непрерывность х(/) и /(%, и),
10*
139
полученное соотношение приближенно может быть
заменено следующим:
Xk+1 - Хк - j f(xk, и (t)) dt = О,
(5.58)
где xh = x(th), k = 0, 1, N—1.
Рассмотрим теперь задачу выбора такого измери-
мого управления и(/), 0 t Т, u\t) е £7, которое
минимизирует go(xN) при ограничениях (5.51). Для
этого предварительно докажем следующий факт.
Пусть задана n-мерная непрерывная вектор-функ-
ция g(u) аргумента и, u^U. Рассмотрим отобра-
жение u(t)-+z произвольной измеримой функции
u(t)^U в м-мерное пространство Еп. Пусть.
Z =
1
z: z = j g («(/))<#
О
Множество Z выпукло. Действительно, пусть
1
Z1 = J g(ul(f))dt,
О
1
z2 = J g(u2(t))dt.
О
Покажем, что XiZi + Х2г2, М, Х2 > О, Aq + Л,2 = 1 при
надлежит Z, т. е. найдется такая функция w(/), что
1
KxZi + A2z2 = J g (и (0) dt.
О
Для этого положим
u(f) =

140
Тогда
1	Л!	I
J g(u(f>) dt = J g ) dt + J g	) dt =
oo	M
i	1
= Xi J g (u{ (t) ) dr + X2 J g (u2 (t) ) dr =	+ Z2z2,
о	о
где в первом интеграле проведена замена переменных
t
Т“ Л1 ’
а во втором
т “ Л2 •
Из приведенного результата следует, что при фик-
сированных х/г+1 и xk левая часть равенства (5.58)
пробегает выпуклое множество, когда u(t) пробегает
класс измеримых функций таких, что u(t) е U при
каждом t. Теперь, если предположить, что векторы
dx.cbi (хо), /=1, ...» Ро линейно независимы, то, так
же как и при рассмотрении системы (5.50), мы ока-
зываемся в условиях применимости теоремы 4.6.
Не будем приводить здесь громоздкие выкладки,
совершенно аналогичные тем, которые делались при
доказательстве теоремы 5.12. Приведем лишь оконча-
тельный результат.
Для того чтобы управление u(t) было оптималь-
ным для системы (5.58) при ограничениях (5.51), а
Xk было оптимальной траекторией, необходимо суще-
ствование таких чисел р0Х),	<>0, аг- и векторов
ф/t, среди которых есть отличные от нуля, что:
(Л	\ *
j д J (х0, « (0) «ft I 'Фо =
to	/
Ро
= 2 «Лй (х0) + A05xoq)o(xo);
Z = I
/^ + 1 \*
б) Фа-i - Фа -1 J dxf(xkU(f))dt Фа + МхаФа(*а) = 0,
А=1,	N—\\
141
в)	+ %,v^w<pw (x,v) + po5Xv^o U,v) = 0;
/	f£+l	\
Г) Ub J f[xk, ii(t))dt =
x	fk	7
/	*k +1	\
= max Н|)й, f f(xk, u(t))dt],
u(t)^U \	/	/
x	*k	7
fe==0, 1, ...,	Af-l;
Д)	=	* = 0, 1, ..., N.
Нетрудно видеть, что условие г) эквивалентно сле-
дующему:
0|>ь f(*k, й(/)) = шах(фь f(xk, v))	(5.59)
v^U
почти всюду на отрезке t t tk+\. Действительно,
пусть на множестве Г, лебегова мера которого поло-
жительна, выполняется неравенство
6b f(xk, «(О)Х('Фь f(xk, v0)),
где v0<= U таково, что
(tfe. f(xk, v0)) = max($k, f(xk, v)).
v^U
Возьмем управление u(t) в виде
( U(t) для	t^r,
м (0 = i	±
I t?o Для t e Г.
Тогда
/ fk+i	\ *k+i
hh, J f(xk, uk(t))dt\= J f(xk, u(t)))dt =
= j Ob f{xk, u(t))) dt+ j (a|5A, f (xk, u(t)))dt<
Vk>tk+x\^r	r
fk+l
< j Ob f (.Xk, u(t))) dt,
tk
что противоречит условию г).
142
Соотношение (5.59) выражает принцип максимума
для оптимального управления системой (5.58). Он до-
казан уже без предположений о выпуклости множе-
ства f(x, и). Выпуклость по управлениям u(t) левой
части (5.58) достигалась за счет наличия интеграла.
Заметим, что при условии
Д = тах| tk+1 -tk >0
k
приведенный результат формально переходит в обыч-
ный принцип максимума [18].
КРАТКАЯ БИБЛИОГРАФИЯ
Приводимая ниже библиография ни в коей мере не претен-
дует на полноту охвата всей массы литературы, посвященной
теории необходимых условий в экстремальных задачах. В ней
выделены лишь те работы, которые непосредственно касаются
изложенного материала и которые по тем или иным причинам
казались автору важными для развития теории.
К Введению. В настоящее время имеется ряд превосходных
и доступных руководств по функциональному анализу. Изложе-
ние основных фактов функционального анализа в этой книге ос-
новано на монографии Н. Данфорда и Дж. Т. Шварца [1]. Все
эти сведения также можно найти в справочнике [2]. Хорошее из-
ложение функционального анализа применительно к выводу не-
обходимых условий экстремума имеется во вводной части статьи
Л. Гурвица [3]. Подробную теорию дифференцирования опера-
торов и функционалов можно найти в [7] и [8].
Все основные сведения о выпуклых множествах в функцио-
нальных пространствах содержатся в гл. V книги [1]. Превос-
ходное изложение теории выпуклых конусов и доказательство
теоремы отделимости можно найти в статье М. Г. Крейна и
М. А. Рутмана [4]. Понятие регулярно выпуклого множества
было впервые введено М. Г. Крейном и В. Л. Шмульяном [52].
Теория выпуклых множеств в конечномерных пространствах
изложена в книге С. Карлина [5]. Там же имеется доказатель-
ство теоремы о выпуклых оболочках множеств в конечномерных
пространствах.
Свойства выпуклых функционалов, приводимые во Введении,
можно найти в монографии М. А. Красносельского и Я. Б. Ру-
тицкого [6].
К § 1. Этот параграф написан целиком на основе статьи
Б. Н. Пшеничного [9], где были введены и систематически изу-
чены свойства множеств опорных функционалов, а также уста-
новлена их связь с производными по направлению.
Для линейно выпуклых функционалов подобные множества
введены в статье А. А. Милютина и А. Я. Дубовицкого [10].
Следует отметить наличие связи между множествами опорных
функционалов и теорией сопряженных выпуклых множеств, раз-
витой Фенхелем (см. [5] и [53]). Ряд свойств множеств опорных
функционалов, не вошедших в § 1, приведен в работе Е. Г. Голь-
штейна [14].
144
К § 2. Выпуклое программирование является наиболее за-
конченной и полной частью математического программирования.
Первой важной работой в этой области была работа Куна и
Таккера [54]. Доказательство Теоремы Куна и Таккера в наибо-
лее общей форме дано X. Удзавой и Л. Гурвицем [11] (см. так-
же [5]). В книге Дж. Б. Денниса [12] приведено первоначаль-
ное доказательство этой теоремы, данное Куном и Таккером,
использующее дифференциальные свойства рассматриваемых
функций.
В настоящей книге доказательство теоремы Куна — Таккера
(теорема 2.5), приведенное в § 4, основано на идеях Л. Ней-
штадта [55]. Оно может быть получено также как непосредствен-
ное следствие теоремы 4.6.
Дифференциальная форма теоремы в полном объеме была
сформулирована Б. Н. Пшеничным в [9] и [56].
Теоремы 2.1—2.4 и 2.6 также можно найти в [9]. По по-
воду теоремы 2.2 см. также работу [10]. Следствие теоремы 2.1
в случае, когда выпуклый функционал является гладким, устано-
влено и использовалось В. Ф. Демьяновым и А. М. Рубино-
вым [13].
К § 3. Термин «квазидифференцируемые функционалы» вво-
дится здесь впервые. Насколько он окажется удачным, пока-
жет будущее. Однако казалось необходимым как-то выделить
широкий класс функций, который встречается в экстремальных
задачах буквально на каждом шагу.
Свойства функций, получающихся в результате взятия опе-
рации максимума от семейства функций, для простейшего слу-
чая рассматривались в работах [15] и [56]. Более полно эти свой-
ства изучались в работе [9] применительно к выпуклым функ-
ционалам, однако приведенное там доказательство фактически не
использовало свойство выпуклости и годилось для более широ-
кого класса.
Теорема 3.5 доказана в [9]. Она может быть обобщена, если
использовать результаты работы [14].
К § 4. Как указывалось в предисловии, решающий толчок
к развитию современной теории необходимых условий экстрему-
ма дала теория оптимального управления. Принцип максиму-
ма — основной факт этой теории — был сформулирован
Л. С. Понтрягиным, В. Г. Болтянским и Р. В. Гамкрелидзе в
работе [16] и доказан в [17]. Полному изложению теории опти-
мальных процессов посвящена монография [18].
Ряд своеобразных идей по доказательству принципа макси-
мума можно найти в работах Л. И. Розеноэра [19].
Р. В. Гамкрелидзе доказал принцип максимума для систем
с ограниченными фазовыми координатами, сделав ряд предпо-
ложений о структуре задачи, в работах [20], [21].
Общая формулировка необходимых условий экстремума в
терминах сопряженных конусов дана впервые А. А. Милютиным
и А Я. Дубовицким в работе [22]. Развернутому изложению
их теории с применением к теории оптимальных процессов
посвящена статья [10]. В [22] и [10] А. А. Милютиным и
145
А. Я. Дубовицким дано полное решение задачи оптимального
управления с фазовыми ограничениями.
В статьях [23], [57] Р. В. Гамкрелидзе ввел понятие квази-
выпуклых множеств, которое позволило дать простое и есте-
ственное доказательство принципа максимума.
Теорема 4.1 была доказана Л. Нейштадтом и X. Халкиным
[58] при несколько более общих предположениях относительно
множества М. Приведенное в книге доказательство отличается
от доказательства, данного в [58].
Ряд общих теорем относительно необходимых условий экс-
тремума содержится в работах [55], [59], [60], [61].
Теорема 4.6 доказана в [24].
К § 5. 1. Необходимые условия экстремума для конечномер-
ной задачи математического программирования приведены в [12],
а для выпуклого программирования в [25].
2.	Задача минимизации с континуумом ограничений рассма-
тривалась в [9] для выпуклого случая.
3.	Теоремы о минимаксе можно найти в [5], где имеются по-
дробные ссылки на первоисточники. Аналог теоремы 5.2 автору
настоящей книги неизвестен.
4.	Задачам теории чебышевских приближений посвящено
большое количество работ. Подробную библиографию по этому
вопросу можно найти в монографии Е. Я. Ремеза [26] и в статье
С. И. Зуховицкого [27]. Основные идеи и методы подхода к за-
даче чебышевского приближения с точки зрения функционально-
го анализа разработаны М. Г. Крейном в [28]. Рассмотрению раз-
личных задач наилучшего приближения на основе общей теории
необходимых условий экстремума посвящены работы [9], [14] и [29].
5.	Задача линейного оптимального управления с фазовыми
ограничениями исследовалась в [30] и [56].
6.	Двойственные задачи для выпуклого программирования
рассматривались Б. Н. Пшеничным в [31] и [15], Е. Г. Гольштей-
ном [32], [33]. Другой подход использован в работах [62], [63],
[12] Г. Ш. Рубинштейном [34] развита оригинальная общая тео-
рия двойственности.
7.	Теории линейных неравенств посвящена большая литера-
тура. Основные факты этой теории можно найти в работе
С. Н. Черникова [35] и Фань Цзи [36]. Системы выпуклых не-
равенств изучались мало. Тесно связанная с выпуклыми нера-
венствами теорема Хелли, имеющая многочисленные приложе-
ния, приводится в работе Э. Хелли [37]. Простое доказательство
этой теоремы дал М. А. Красносельский [38].
8.	Проблема моментов систематически изучалась в работах
М. Г. Крейна [28]. Он же установил двойственную связь проб-
лемы моментов и задачи чебышевских приближений, которая
была использована С. И. Зуховицким [27] для изучения задачи
наилучшего приближения.
Н. Н. Красовский установил связь между теорией моментов
и задачами линейного оптимального управления [39], [40], [41].
Эту связь также использовали Р. Куликовский [42], [43] и П. Са-
рачик и Г. Кранц [64].
Основываясь на ней, Л. Нейштадт получил необходимые ус-
ловия оптимальности в задаче оптимального импульсного управ-
146
ления линейной системой и исследовал структуру оптимального
управления [65].
9.	Обзор основных результатов по дискретному принципу
максимума имеется в приложении 3 к книге [48], написанном
А. И. Пропоем. Локальный принцип максимума для дискретных
систем был получен Е. Поляком и Б. Йорданом в [66] и
А. И. Пропоем [49]. X. Халкин [67] доказал теорему 5.12 при
более сильных предположениях, чем те, которые сделаны в § 5
п. 9 настоящей книги. Подход X. Халкина получил дальнейшее
развитие в [68]. Связь между дискретным и непрерывным прин-
ципом максимума рассматривалась в [50].
Выпуклость (или квазивыпуклость) образов множеств, полу-
чающихся в результате интегральных преобразований, а также
использование этого свойства в экстремальных задачах, изуча-
лась в работах [57], [69], [23], [51].
ЛИТЕРАТУРА
1.	Данфорд Н. и Шварц Дж. Т., Линейные операторы,
Общая теория, ИЛ, 1962.
2.	Виленкин Н. Я. и др., Функциональный анализ, СМБ,
«Наука», 1964.
3.	Г у р в и ц Л., Программирование в линейных пространствах,
в сб. «Исследования по линейному и нелинейному програм-
мированию», ИЛ, 1962.
4.	Крейн М. Г., Рутман М. А., Линейные операторы, ос-
тавляющие инвариантным конус в пространстве Банаха,
УМН, т. Ill, № 1 (23) (1948), 3—95.
5.	К а р л и н С., Математические методы в теории игр, про-
граммировании и экономике, «Мир», 1964.
6.	Красносельский М. А., Рутицкий Я. Б., Выпуклые
функции и пространства Орлича, Физматгиз, 1958.
7.	Л ю с т е р н и к Л. А., Соболев В. И., Элементы функ-
ционального анализа, «Наука», 1965.
8.	Дьедонне Ж., Основы современного анализа, «Мир»,
1964.
9.	П ш е н и ч н ы й Б. Н., Выпуклое программирование в норми-
рованном пространстве, Кибернетика, № 5 (1965), 46—54.
10.	Д у б о в и ц к и й А. Я., Милютин А. А., Задачи на экс-
тремум при наличии ограничений, Вычисл. матем. и матем.
физ., т. 5, № 3 (1965), 395—453.
11.	Эрроу К. Дж., Гурвиц Л., У д з а в а X., Исследования
по линейному и нелинейному программированию, ИЛ, 1962.
12.	Деннис Дж. Б., Математическое программирование и элек-
трические цепи. ИЛ, 1961.
13.	Демьянов В. Ф., Рубинов А. М., Минимизация глад-
кого выпуклого функционала на выпуклом множестве, Вест-
ник ЛГУ, № 19 (1964), 5—17.
14.	Гольштейн Е. Г., Задачи наилучшего приближения эле-
ментами выпуклого множества и некоторые свойства опор-
ных функционалов, ДАН СССР, т. 173, № 5 (1967), 995—
999.
15.	Пшеничный Б. Н., Двойственный метод в экстремальных
задачах, 1, Кибернетика, № 3 (1965), 89—95.
16.	Б о л т я н с к и й В. Г., Гамкрелидзе Р. В., Понтря-
гин Л. С., К теории оптимальных процессов, ДАН СССР,
т. НО, № 1 (1956), 7—10.
17.	Б о л т я н с к и й В. Г., Принцип максимума в теории опти-
мальных процессов, ДАН СССР, т. 119, № 6 (1958), 1070—
1073.
148
18.	Понтрягин Л. С., Болтянский В. Г., Гамкре-
лидзе Р. В., Мищенко Е. Ф., Математическая теория
оптимальных процессов, Физматгиз, 1961.
19.	Розен оэр Л. И., Принцип максимума Л. С. Понтрягина
в теории оптимальных систем, I, II, III. Автоматика и теле-
механика, т. 20, № 10—12 (1959), 1320—1334, 1441—1458,
1561—1578.
20.	Г а м к р е л и д з е Р. В., Оптимальные по быстродействию
процессы при ограниченных фазовых координатах, ДАН
СССР, т. 125, № 3 (1959), 475—478.
21.	Гамкрелидзе Р. В., Оптимальные процессы управления
при ограниченных фазовых координатах, Изв. АН СССР,
серия матем., т. 24, № 3 (1960), 315—356.
22.	Д у б о в и ц к и й А. Я., Милютин А. А., Задачи на экс-
тремум при наличии ограничений, ДАН СССР, т. 149, № 4
(1963).
23.	Г а м к р е л и д з е Р. В., К теории первой вариации, ДАН
СССР, т. 161, № 1 (1965), 345—348.
24.	П ш е н и ч н ы й Б. Н., Необходимые условия экстремума в
задачах частично-выпуклого программирования, Кибернетика,
№ 2 (1969), 90-93.
25.	3 о й т е н д е й к Г., Методы, возможных направлений, ИЛ,
1963.
26.	Р е м е з Е. Я-, Общие вычислительные методы чебышев-
ского приближения, Изд-во АН УССР, 1957.
27.	3 у х о в и ц к и й С. И., О приближении действительных функ-
ций в смысле П. Л. Чебышева, УМН, т. XI, в 2 (68), 125—
159.
28.	Ах,иезер Н. и Крейн М., О некоторых вопросах теории
моментов, ГОНТИ, Харьков, 1938.
29.	Т и х о м и р о в В. Н., Некоторые вопросы теории приближе-
ний, ДАН СССР, т. 160, № 4 (1965), 774—777.
30.	Д у б о в и ц к и й А. Я., Милютин А. А., Некоторые опти-
мальные задачи для линейных систем, Автоматика и телеме-
ханика, т. XXIV, № 12 (1963), 1616—1626.
31.	Пшеничный Б. Н., Принцип двойственности в задачах
выпуклого программирования, Вычисл. матем. и матем. физ.,
т. 5, № 1 (1965), 98—106.
32.	Г о л ь ш т е й н Е. Г., Двойственные задачи выпуклого и
дробно выпуклого программирования в функциональных про-
странствах, ДАН СССР, т. 172, № 5 (1967), 1007—1010.
33.	Гольштейн .Е. Г., Двойственные задачи выпуклого про-
граммирования. Экономика и математические методы, № 3
(1965), 410—425.
34.	Рубинштейн Г. Ш., Двойственные экстремальные за-
дачи, ДАН СССР, т. 152, № 2 (1963), 288—291.
35.	Ч е р н и к о в С. Н., Системы линейных неравенств, УМН,
т. 8, № 2 (54), (1953), 7-73.
36.	Ф а н ь Ц з и, О системах линейных неравенств, в сб. «Ли-
нейные неравенства и смежные вопросы», ИЛ, 1959.
37.	Хелли Э., О совокупностях выпуклых тел с общими точ-
ками, УМН, в. 2 (1936).
38.	Красносельский М. А., Об одном доказательстве тео-
ремы Хелли, Труды Воронежского университета, т. 33 (1954).
149
39.	К р а с о в с к и й Н. Н., К теории оптимального регулирова-
ния, Автоматика и телемеханика, т. XVIII, № 11 (1957),
960—970.
40	Красовский Н. Н., Об одной задаче оптимального регу-
лирования, ПММ, т. XXI, в. 5 (1957), 670—677.
41.	К р а с о в с к и й Н. Н., К теории оптимального регулирова-
ния, ПММ XXIII, в. 4 (1959).
42.	Куликовский Р., К оптимальным процессам и синтезу
оптимальных систем с линейными и нелинейными элемента-
ми, Труды 1 Международного конгресса ИФАК, т. 2, Изд-во
АН СССР, 1961.
43.	Куликовский Р., Оптимальные и адаптивные процессы в
системах автоматического регулирования, «Наука», 1967.
44.	Фихтенгольц Г. М., Курс дифференциального и инте-
грального исчисления, т. 1, Физматгиз, 1959.
45.	Ф и х т е и г о л ь ц Г. М., Курс дифференциального и инте-
грального исчисления, т. 2, Физматгиз, 1955.
46.	Л е в ш е ц С., Геометрическая теория дифференциальных
уравнений, Изд-во ИЛ, 1961.
47.	Б у т к о в с к и й А. Г., Теория оптимального управления си-
стемами с распределенными параметрами, «Наука», 1965.
48.	Фан Лянь-Цэнь, Вань Чу-Сен, Дискретный прин-
цип максимума, Изд-во «Мир», 1967.
49.	П р о п о й А. И., О принципе максимума для дискретных си-
стем управления, Автоматика и телемеханика, т. XXVI, № 7
(1965), 1177—1187.
50.	Га басов Р., Кириллова Ф. М., К вопросу о распро-
странении принципа максимума Л. С. Понтрягина на дис-
кретные системы, Автоматика и телемеханика, № 11 (1966),
46—51.
51	Аркин В. И., О бесконечномерном аналоге задач невы-
пуклого программирования, Кибернетика, № 2 (1957), 87—
93.
52.	Krein, М., S m u 1 i a n, V., On Regularly Convex Sets in
the Space Conjugate to a Banach Space, Ann. of Math., V. 41
(1940), 556—583.
53.	Fen ch el, W., Convex Cones, Sets and Functions. Office of
Naval Research Logistics Project Report, Depart, of Mathe-
mat. Princeton University, 1953.
54.	Proceedings of the Second Berkeley Symposium on Mathema-
tical Statistics and Probability, ed. J. Neyman. Berkeley
and Los Angeles, University of California Press, 1951, 481—
492.
55.	Neustadt, L. W., An Abstract Variational Theory with Ap-
plications to a Broad Class of Optimization Problems I: Gene-
ral Theory, SIAM J. on Control, V. 4, No. 3 (1966), 505—
527.
56.	P s h e n i c h n i у, B. N., Linear Optimal Control Problems, J.
SIAM on Control. V. 4, No. 4 (1966), 577—594.
57.	G a m k г e 1 i d z e, R. V., On Some Extremal Problems in the
Theory of Differential Equations with Applications to the Theo-
ry of Optimal Control, SIAM J. On Control, V. 3, No. I
(1965), 106—128.
150
58.	Halkin, H, and Neustadt, L. W, General Necessary
Conditions for Optimization Problems, Proc. Nat Acad Scien-
ces, 56 (1966), 1066—1071.
59.	Halkin, H., Nonlinear Nonconvex Programming in an In-
finite Dimensional Space, Mathematical Theory of Control, ed.
by A. V. Balakrishnan and L. W. Neustadt, Academic Press
1967, 10—25.
60.	С a n о n, M, C a 11 a m, C, Polak, E., Constrained Minimi-
zation Problems in Finite Dimensional Spaces, SIAM J. on
Control, V. 4 (1966), 528—547.
61.	M a n g a s a r i a n, O. L., and F г о m о v i t z, S., A Maximum
Principle in Mathematical Programming, Mathematical Theory
of Control, ed. by A. V. Balakrishnan and L. W. Neustadt,
Academic Press, 1967, 85—95.
62.	M a n g a s a r i a n, O. L., Duality in Nonlinear Programming,
Quart. Appl. Math., V. 20, No. 3 (1962), 300—302.
63.	Wolfe, Ph., A Diality Theorem for Nonlinear Programming,
Quart. Appl. Math., V. 19 (1961), 239—244.
64.	Kranc, G. M, Sarachik, P. E., An Application of Func-
tional Analysis to the Optimal Control Problems, Joint Auto-
matic Control Conf. Papers, July, 1962.
65.	Neustadt, L. W., Optimization, a Moment Problem and
Nonlinear Programming, J. SIAM on Control, V. 2, No. 1
(1964), 33—53.
66.	J о r d a n, B. W., Polak, E., Theory of a Class of Discrete
Optimal Control Systems, J. Electronics and Control, V. 17,
No. 6 (1964), 697—711.
67.	Halkin, H, A Maximum Principle of the Pontryagin Tipe
for Systems Described by Nonlinear Difference Equations, J.
SIAM on Control, V. 4, No. 1 (1966), 90—112.
68.	H о 11 z m a n, I., Halkin, H, Directional Convexity and the
Maximum Principle for Discrete Systems, J. SIAM on Con-
trol, V. 4, No. 2 (1966), 263—275.
69.	Warga, J., Relaxed Variational Problems, J. of Math. Anal,
and Appl, V. 4, No. 1 (1962), 111-128.
Борис Николаевич Пшеничный
Необходимые условия экстремума
(Серия: «Оптимизация и исследование
операций»)
М., 1969 г., 152 стр.
Редакторы Е. С. Левитин, М. М. Горячая
Техн, редактор И. Ш. Аксельрод
Корректор О. А Бутусова
Сдано в набор 13/VI 1969 г. Подписано к пе-
чати 13/XI 1969 г. Бумага 84Х1087з2- Физ.
печ. л. 4,75. Условн. печ. л. 7,98. Уч.-изд. л. 6,62.
Тираж 12 000 экз. Т-16009. Цена книги 47 коп.
Заказ № 211.
Издательство «Наука»
Главная редакция
физико-математической литературы.
Москва, В-71, Ленинский проспект, 15.
Ленинградская типография № 2
имени Евгении Соколовой Главполиграфпрома
Комитета пр печати при Совете Министров
СССР. Измайловский проспект, 29.
Цена 47