Текст
ОПТИМИЗАЦИЯ
И ИССЛЕДОВАНИЕ
ОПЕРАЦИЙ
Б. Н. ПШЕНИЧНЫЙ
Необходимые
условия
экстремума
ОПТИМИЗАЦИЯ
И ИССЛЕДОВАНИЕ
ОПЕРАЦИЙ
Редактор серии
Н. Я. МОИСЕЕВ
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1982
В. II. ПШЕНИЧНЫЙ
НЕОБХОДИМЫЕ
УСЛОВИЯ
ЭКСТРЕМУМА
ИЗДАНИЕ ВТОРОЕ,
ПЕРЕРАБОТАННОЕ И ДОПОЛНЕННОЕ
МОСКВА «НАУКА»
ГЛАВНАЯ РЕДАКЦИЯ
ФИЗИКО-МАТЕМАТИЧЕСКОЙ ЛИТЕРАТУРЫ
1982
22.18
IJ 93
УДК 519.6
Пшеничный Б. II. Необходимые условия экстремума.—
2-е изд., перераб. и доп.— М.: Наука, Главная редакция физико-
математической литературы, 1982.— 144 с.
Книга содержит современное изложение теории необходи-
мых условий экстремума. Рассматриваются задачи выпуклого
и невыпуклого программирования. Особое внимание уделяется
задачам с негладкими функциями. Исходя из абстрактных тео-
рем, изучаются задачи математического программирования с
бесконечным числом ограничений, теоремы о минимаксе в тео-
рии игр, задачи чебышевского приближения, двойственные за-
дачи выпуклого программирования, проблема моментов, прин-
цип максимума для дискретных и непрерывных систем управ-
ления и др.
Для математиков, специалистов по математической эконо-
мике, инженеров, решающих оптимизационные задачи. Может
служить в качестве учебного руководства для студентов вузов.
Библ. 23 назв.
1702070000-09158 g9
П 053(02).-82
zg\ Издательство «Наука» <
Главная редакция
физико-математической
литературы,
с изменениями, 1982 .
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
Основу текста первого издания этой книги состави-
ли лекции, которые автор читал в 1967 году. За про-
шедшие четырнадцать лет теория необходимых условий
экстремума прошла большой путь интенсивного разви-
тия. В первую очередь здесь, по-видимому, следует
выделить углубленное исследование выпуклых функ-
ций и дальнейшее изучение различных классов не
дифференцируемых в обычном смысле функций. Это
побудило полностью переписать первые три параграфа,
посвященные выпуклому программированию и квази-
дифференцируемым функциям.
Основной текст четвертого и пятого параграфов
остался без изменений. Удален только п. 9 § 5, каса-
ющийся процессов управления с дискретным временем,
так как появилось много книг, специально посвящен-
ных этому вопросу. Вместо него мне показалось целе-
сообразным дать материал, показывающий, как теория
необходимых условий экстремума может быть приме-
нена к проблеме существования равновесных цен в
модели экономики, описывающей процесс обмена и
производства. Добавлен также п. 10 § 5, где рассмат-
риваются многозначные отображения и их применение
к изучению параметрических задач выпуклого про-
граммирования.
За прошедшие годы установилась единая термино-
логия и обозначения, которых не было в 1967 г. Есте-
ственно, что в новом издании терминология и обозна-
чения приведены в соответствие с современностью.
Обсуждение со специалистами и чтение лекций в
Киевском государственном университете убедили меня,
что в настоящее время книга может служить достаточ-
но полным введением в современную проблематику
теории необходимых условий экстремума. Дальнейшее,
5
более углубленное изучение этой теории может быть
продолжено по многочисленным монографиям и стать-
ям, опубликованным за последние годы. В связи с этим*
изменен список литературы по сравнению с первым
изданием. Основной целью этого списка и библиографи-
ческого комментария является указать читателю, где
он сможет более детально познакомиться с заинтере-
совавшими его специальными вопросами.
Автор искренне признателен своим коллегам по
Институту кибернетики АН УССР — С. Г. Лукиной,
Г. Е. Любарской, В, В. Остапенко, И. А. Шубепковой,
А. П. Яковлевой за их действенную помощь в подго-
товке рукописи.
Б. П. Пшеничный
Киев, май 1981 г.
ПРЕДИСЛОВИЕ К ПЕРВОМУ ИЗДАНИЮ
Последние 10—12 лет были периодом исключитель-
но бурного, развития теории экстремальных задач и
методов их решения. Большое количество интересных
в теоретическом отношении и важных в. практическом
отношении проблем привлекло внимание широких кру-
гов математиков и инженеров. И это не удивительно.
Сейчас трудно назвать какую-либо область знаний,
где в той или иной форме не возникали бы экстре-
мальные задачи и решение которых не было бы суще-
ственным для развития этих областей. Это и теория
автоматического управления, и проблема экономики,
и даже биология. Все эти науки выдвигают свои эк-
стремальные задачи и ждут ответов на два вопроса:
каков качественный характер решения и как его
найти?
Первый из этих вопросов — каков качественный
характер решения — побуждает математиков искать
наиболее полные необходимые условия экстремума,
ибо именно эти условия позволяют предсказать общую
структуру решения. Лавинообразный характер потока
возникающих задач ясно стал показывать, что необхо-
димы именно общие условия экстремума, т. е. такие
условия, которые были бы применимы к широкому
классу задач, чтобы избавиться от необходимости в
каждом конкретном случае строить новую теорию.
С другой стороны, уже решенные частные задачи
давали основание быть уверенными, что такие условия
можно сформулировать. Более того, они показывали,
что такие условия не будут слишком далекими от кон-
кретных задач, так что их применение для данной
задачи будет, скорее, похоже на занятие заранее под-
готовленных позиций, чем на штурм крепости,
7
Задачи на экстремум — не новость для математики.
Они встречались и решались на протяжении всей
истории математики. Однако интенсивное и последова-
тельное их изучение началось сравнительно недавно,
когда, с одной стороны, запросы экономики и автома-
тического управления сделали решение этих задач
неотложным делом, а, с другой стороны, появление
электронных вычислительных машин дало в руки ис-
следователей мощное средство, с помощью которого
решение может быть доведено до конечного итога —
численного результата. Если не говорить сейчас о
вариационном исчислении и задачах минимизации
функций при ограничениях типа равенств, задачах,
в которых необходимые условия экстремума были по-
лучены давно, то начало нового этапа развития теории
экстремальных задач можно датировать 1939 годом.
В этом году советским математиком Л. В. Канто-
ровичем были созданы методы решения нового
типа задач — задач линейного программирования.
В дальнейшем теория линейного программирова-
ния получила широкое развитие в работах Дж. Дан-
цига и многих других авторов как за рубежом, так и
в СССР.
Следующим этапом в развитии необходимых усло-
вий экстремума явилась разработка теории выпуклого
программирования. Центральным местом в этой теории
является теорема Куна — Таккера, дающая необходи-
мые условия экстремума и послужившая источником
целого ряда алгоритмов. Дифференциальная форма
теоремы Куна — Таккера применима также к задачам
невыпуклого программирования в конечномерном про-
странстве и позволяет сформулировать для этих задач
необходимые условия экстремума.
При разработке необходимых условий для задач
линейного и выпуклого программирования был выяснен
принцип, лежащий в основе всех построений. Этот
принцип был резюмирован Г. Зойтендейком в его
монографии «Методы возможных направлений». Сущ-
ность этого принципа составляет тот совершенно оче-
видный факт, что если в данной точке существует
направление, которое не выводит из допустимой обла-
сти и функция вдоль него убывает, то такая точка
не может быть точкой минимума. На основе этого
принципа были построены необходимый условия эк-
8
стремума для широкого Класса задач в конечномерйом
пространстве с гладкими ограничениями.
Параллельно с теорией конечномерных экстремаль-
ных задач — математическим программированием —
шло исследование другого класса задач,— задач опти-
мального управления. Решающую роль во всей этой
теории сыграла формулировка необходимых условий
экстремума в форме принципа максимума Л. С. Пон-
трягина. Нет нужды подробно останавливаться на том,
какое значение имела формулировка этого принципа
для всей теории автоматического управления и какое
огромное количество работ она вызвала. Учитывая на-
правленность настоящей книги, необходимо в первую
очередь отметить, что доказательство принципа макси-
мума, данное В. Г. Болтянским, было в какой-то мере
сенсационным, поскольку оно использовало методы,
которым трудно было найти аналогию в рамках уже
развитой теории математического программирования.
В связи с этим на повестку дня стал вопрос о выясне-
нии возможности доказательства принципа максимума
с помощью идей и методов, используемых в классиче-
ском вариационном исчислении и математическом про-
граммировании. Помимо чисто эстетического значения,
поставленный вопрос имел и другую, практическую
сторону, ибо его решение позволило бы применить
численные методы, разработанные в математическом
программировании, для задач оптимального управления.
Вложение теории оптимального управления в об-
щую теорию необходимых условий было впервые осу-
ществлено А. А. Милютиным и А. Я. Дубовицким.
Большое значение их работ состоит в том, что им
удалось в рафинированной форме сформулировать
необходимые условия экстремума, пригодные для при-
менения к широкому классу задач. При этом было
выяснено, какая часть результатов по доказательству
принципа максимума укладывается в общие рамки,
а какая обусловлена спецификой задачи оптимального
управления, т. е. наличием связей в виде обыкновенных
дифференциальных уравнений. Наиболее полное отра-
жение специфика связей в виде дифференциальных
уравнений нашла в работах Р. В. Гамкрелидзе, кото-
рый сформулировал понятие скользящих режимов и
понятие квазпвыпуклых множеств. На основе понятия
квазивыпуклого множества Р. В. Гамкрелидзе дал
9
йовое доказательство принципа максимума Л. С. Пон-
трягина, которое четко разделяет общую вариационную
задачу и специфику дифференциальных связей.
Работы по теории оптимального управления оказали
чрезвычайно плодотворное влияние на общую теорию
необходимых условий экстремума. Они позволили вы-
явить основные принципы, развить технику построения
необходимых условий и посмотреть с единой точки
зрения на широкий класс задач. При этом углубленное
и последовательное изучение позволило построить необ-
ходимые условия в задачах, в которых участвуют уже
недифференцируемые в обычном смысле функции. Ока-
залось достаточным рассматривать лишь функции,
дифференцируемые по направлению. В терминах функ-
ций, дифференцируемых по направлению. X. Халкин и
Л. Нейштадт сформулировали весьма общую теорему
о необходимых условиях, которая применима при реше-
нии широкого класса задач, в том числе и задач опти-
мального управления.
Интересно отметить, что как основные теоремы
А. А. Милютина и А. Я. Дубовицкого, так и теоремы
X. Халкина и Л. Нейштадта, требуют для своего дока-
зательства средств, достаточно давно известных мате-
матике. И то, что эти результаты был получены лишь
в последние пять-шесть лет, показывает, какая боль-
шая работа была проделана по осмысливанию основных
принципов, по выработке основных понятий.
Настоящая книга посвящена изложению теории не-
обходимых условий экстремума. В основу положен
дедуктивный принцип изложения, т. е. сначала изла-
гаются общие результаты, а потом показывается, как
эти результаты могут быть конкретизированы в част-
ных задачах. Такой способ изложения в данный момент
представляется оправданным, поскольку имеется очень
большое число работ, посвященных выводу необходи-
мых условий в конкретных задачах, которые вполне
подготовили переход на абстрактный уровень изложе-
ния. Далее, в теории необходимых условий можно вы-
делить две части, которые несколько условно можно
назвать следующим образом: формальные условия
экстремума и техника вычислений.
Формальные условия экстремума в настоящей кни-
ге изложены в § 4. Это некоторый набор теорем,
утверждающих, что если выполнены определенные
10
условия па минимизируемую функцию и область, в ко-
торой происходит минимизация, то в точке минимума
выполняется некоторое соотношение. Однако как кон-
кретно записать это соотношение в данной задаче,
указанные теоремы не говорят. Для эффективного
построения необходим развитый аппарат техники вы-
числений. Чтобы сделать понятными сказанные общие
фразы, поясним их на примере задачи о минимуме
функции одной переменной.
Для того чтобы в некоторой точке достигался мини-
мум, необходимо, чтобы в этой точке производная от
функции равнялась нулю. Это в приведенной термино-
логии формальное условие экстремума. Но если бы не
была развита техника вычислений производных от
достаточно сложных функций, то приведенное условие
невозможно было бы эффективно записать для сколько-
нибудь реальной задачи. Первые три параграфа книги
посвящены исследованию техники вычислений. Только
после того как эта техника достаточно развита, приво-
дятся формальные условия экстремума.
Всякая общая теория ценна лишь постольку, по-
скольку она позволяет охватить единой точкой зрения
достаточно широкий класс задач. Поэтому сравнитель-
но большой § 5 посвящен иллюстрации того, как мож-
но применить построенную тео)эпю для конкретных
гадгш. Каждая из рассмотренных задач далеко не три-
зхальна и последо-важно каждой было поовждепо доста-
точно большое количество работ, Некоторые из рас-
смотренных задач, например, теория чебышевского
приближения и проблема моментов, сами носят весьма
общий характер и имеют многочисленные приложения
в экономике и теории оптимального управления.
Из задач оптимального управления в § 5 рассмат-
риваются лишь такие, в которых результат может быть
получен без исследования специфики, вносимой свя-
зями в виде дифференциальных уравнений, так как
рассмотрение таких связей увело бы несколько в сто-
рону от общего направления книги.
Чтобы сделать изложение замкнутым, во введении
приведены основные факты из функционального ана-
лиза и теории выпуклых множеств, используемые в
ходе изложения. Отказываться от изложения материа-
ла с использованием более общих пространств, чем
конечномерные, не хотелось, так как такой отказ повел
11
бы к значительному обеднению материала п ряд задач,
ради которых собственно и строилась сложная теория,
оказался бы вне рассмотрения.
Таким образом, читатель, мало знакомый с функ-
циональным анализом, сможет ознакомиться со всеми
фактами, пебходнмыми для понимания дальнейшего,
во введении, тем более, что таких фактов очень немно-
го. Читатель, знакомый с основами функционального
анализа, может приступать к чтению сразу с первого
параграфа.
Необходимо сделать также замечание о способе
ссылок на литературу, принятом в книге. В ходе изло-
жения делаются только самые необходимые ссылки на
те результаты, которые используются в книге, но в ней
не доказаны.
Ссылки же, указывающие, в какой работе доказана
та пли иная теорема, в каком отношении данный ре-
зультат находится с другими результатами и т. п.,
приведены в конце книги в краткой библиографии.
Настоящая книга написана па основе цикла лекций,
которые автор прочел во Второй Всесоюзной школе по
методам оптимизации, г. Шемаха, 6—26 июля 1967 г..
Автор искренне признателен председателю оргкомитета
школы чл.-корр. АН СССР Н. Н. Моисееву за пригла-
шение прочитать эти лекции, а также за многочислен-
ные плодотворные дискуссии и внимание к данной
работе.
Считаю также своей приятной обязанностью выра-
зить признательность моим сотрудникам по Институту
кибернетики АН УССР, помощь которых в работе над
книгой трудно переоценить.
Б. Пшеничный
1969 г.
ВВЕДЕНИЕ
ЭЛЕМЕНТЫ ФУНКЦИОНАЛЬНОГО АНАЛИЗА
И ВЫПУКЛЫЕ МНОЖЕСТВА
Математическим аппаратом, на котором основано
построение теории необходимых условий в задачах ми-
нимизации, является функциональный анализ. В сущ-
ности, при построении теории используется лишь не-
сколько основных понятий и несколько теорем. Это в
первую очередь понятия слабой сходимости, бикомпакт-
ности и теорема отделимости выпуклых множеств. Для
удобства читателей мы кратко без доказательств изло-
жим необходимые для понимания дальнейшего основ-
ные факты функционального анализа, заимствуя их
из книги [5]. Впрочем, большинство приводимых ниже
теорем, за исключением некоторых основных, являют-
ся непосредственными следствиями определений и их
доказательство может быть проведено самим читате-
лем, желающим проверить правильность понимания
вводимых определений.
1. Основные положения функционального анализа.
Определение 1. Семейство т подмножеств мно-
жества X образует его топологию, если оно содержит
пустое множество 0, само X, каждое объединение лю-
бого числа и каждое пересечение конечного числа
своих подмножеств. Пара (X, т) называется топологи-
ческим пространством. Множества из т называются
открытыми множествами. Окрестностью точки р назы-
вается каждое открытое множество, содержащее р,
окрестностью множества А — любое открытое множест-
во, содержащее А. Точка р&А называется внутренней
точкой 4, если существует такая окрестность р, кото-
рая целиком содержится в А,
13
Очевидным следствием определения 1 является
следующая
Лемма 1. Для того чтобы множество в топологи-
ческом пространстве было открытым, необходимо и до-
статочно, чтобы оно содержало некоторую окрестность
каждой своей точки.
Определение 2. Семейство р подмножеств из
X называется базисом топологии т, если любое множе-
ство из семейства [} содержится в семействе т и каж-
дое множество из т есть объединение множеств из се-
мейства р.
Для того чтобы система служила базисом некото-
рой топологии, необходимо и достаточно, чтобы для
каждой пары множеств U, V е р и я е 17 П V нашлось
такое W <= [}, что х е W U П V, и объединение всех
множеств из [3 совпадало со всем множеством X.
Если задан базис р, то топология т задается всеми
множествами, образованными с помощью операции
объединения некоторого количества множеств из р.
Например, обычная топология в м-мерном пространстве
может быть задана с помощью семейства (3, состояще-
го из множеств, определяемых неравенствами
S U'i — ?/i)2 <
i - 1
Где у = у.Д и Л — произвольные вектор и чис-
ло, причем R > 0.
Определение 3. Множество 1 с А. называется
замкнутым, если дополнительное к нему множество
Х\У открыто. Пересечение всех замкнутых множеств,
содержащих некоторое множество А, называется за,-
мыканием А и обозначается А.
Задание топологии т на некотором множестве X
позволяет определить понятие сходимости последо-
вательности,
Определение 4. Последовательность хп, п-+ <»,
сходится к точке х0, хп е X, х0^ X, если для любой
окрестности точки xQ найдется такой номер N, что все
точки хп, п > X, принадлежат этой окрестности.
В дальнейшем мы будем рассматривать только так
называемые хаусдорфовы топологические пространства,
т. е. такие топологические пространства (X, т), в ко-
торых множества, состоящие из одной точки, зам-
кнуты п у любых двух несовпадающих точек х и у
существуют иепересекающиеся окрестности. В таких
пространствах каждая сходящаяся последовательность
имеет единственную предельную точку xQ, и можно
написать
lim хп = х0.
Введенное выше понятие сходимости вполне экви-
валентно в случае n-мерного пространства обычному
понятию сходимости, приводимому в курсе математиче-
ского анализа: последовательность векторов xh сходит-
ся к вектору х°, если для любого е > 0 найдется такое
что для к^ N
2(4-<<е2.
2 = 1
Пусть теперь заданы два топологических простран-
ства (Х1? Tt) и (Х2, т2). Говорят, что задано отображе-
ние f: Х{ -> Х2 (Х{ в Х2), если каждому х^Х{ одно-
значным образом поставлен в соответствие элемент
у Х2. Этот элемент у обозначают через j(x'). Если
U <=А\, то через /(С7) обозначается множество всех то-
чек ](х), которые получаются, когда х пробегает U.
Если V <= Х2, то /-1(Г) есть множество тех точек х, для
которых fix) е V. f(U) называется образом множества
U, а /"‘(Ю — прообразом множества V.
Определен и е 5. Отображение /: -> Х2 на-
зывается непрерывным в точке xQ, если для каждого
открытого множества V <= Х2, fix^) е V найдется такая
окрестность U точки я0, что f(U) <= V. Отображение /:
Xt -> Х2- называется непрерывным, если онр непрерыв-
но в каждой точке х^Х{.
Отображение / непрерывно; тогда и только тогда,
когда для любого открытого множества V Х2 его про-
образ /-1(Г) есть также открытое множество. В самом
деле, пусть V — открытое множество в Х2 и
По определению непрерывности в точке х и потому,
что /(я) *= Г, найдется татщя окрестность Ux, что
f(Ux) <= V. Тогда очевидно, что
/-чю- и их,
п правая часть этого равенства есть открытое множест-
во, поскольку она является объединением открытых
множеств.
15
Если перейти к более близкому для обычного курса
математического анализа определению непрерывности
через последовательности, то легко доказать, что если
](х) непрерывна в точке х0, то из хп следует, что
/UJ -* /(я0).
Точно так же, если А — замкнутое по определению
3 множество, то из того, что хп х0, хп^А, следует,
что х0 & А.
Существует важный класс пространств — метриче-
ские пространства, для которых введенные понятия
непрерывности функции и замкнутого множества экви-
валентны соответствующим понятиям, заданным на
языке последовательностей. В таких пространствах
функция непрерывна в точке xQ тогда и только тогда,
когда из хп -> Хо следует, что f(xn) -> /(я0), а множество
А замкнуто тогда и только тогда, когда из хп х0,
хп А, следует, что xQ е А.
Определение 6. Множество X называется
метрическим пространством, если для любых х, у X
определена функция р(я, у), обладающая свойствами:
1) р(лг, у) >0 и р(я, у) = 0, только если х = у;
2) р(гг, у) = р(у, х}\
3) pGr, z) < р(я, у) + р(у, z).
Топология в таком пространстве задается с по-
мощью базиса, состоящего из множеств
S(x0, г) = {х: х^ X, pGr, xQ) < г}.
В частности, обычное пространство n-мерных векто-
ров является метрическим. Метрика в нем задается с
помощью формулы.
(п \ 1/2
2 — i/i)2
i=l /
Одну из важнейших ролей в дальнейшем изложе-
нии играет понятие бикомпактности и связанное с ним
понятие компактности.
Определение 7. Покрытие множества А в то-
пологическом пространстве X есть семейство открытых
множеств, объединение которых содержит А. Множест-
во А называется бикомпактным, если из всякого его
покрытия можно извлечь конечное. Множество А на-
зывается компактным, если из всякой последователь-
ности UJ, хп^А, можно выбрать сходящуюся подпо-
16
следователыюсть, предел которой есть элемент того Жё
множества А.
Укажем па некоторые свойства бикомпактных
множеств.
Лемма 2. а) Если отображение ft Х{ Х2 непре-
рывно, то образ f(U) бикомпактного множества U би-
компактен,
б) Бикомпактное множество хаусдорфова простран-
ства замкнуто.
в) В метрическом пространстве понятия компакт-
ности и бикомпактности совпадают.
По известной из анализа теореме Вейерштрасса,
для того чтобы в n-мерном пространстве множество
было компактным, необходимо и достаточно, чтобы оно
было замкнутым и ограниченным.
Пусть Х{ и Х2 — два топологических пространства
с топологиями Ti и т2. Чтобы иметь возможность обра-
щаться с функциями вида f(xh х2), где х{^Х{, а
#2е Х21 введем понятие прямого произведения тополо-
гических пространств Xi и Х2, которое обозначается
через Xi X Х2. Топологическое пространство Х{ X Х2 со-
стоит из всевозможных пар вида (xi, х2), х{^Х{, х2^
еХ2, а топология на нем задается следующим образом:
если Ui — множество из системы a U2 — из си-
стемы т2, то множество вида U{X U2, принадлежность
к которому точки х = (х1ч х2} означает, что СЛ,
х2 е U2ч входит в систему т множеств, задающих то-
пологию в Xi X Х2, и т состоит из таких и только та-
ких множеств. Таким образом, все открытые множе-
ства в Xi X Х2 состоят из точек (хи х2\ где Xi^Ui,
x2^U2 и Ui, U2 — открытые множества в Xi и Х2 со-
ответственно. Согласно этому определению, если топо-
логию на прямой — одномерном пространстве — задать
с помощью базиса, состоящего из открытых интервалов,
—г < Xi — xQ < г, то базис в n-мерном пространстве бу-
дут образовывать системы векторов х~{х{, ..., хп},
удовлетворяющих неравенствам
— Ti < Xj — xl < i = 1, ..., п.
Таким образом, если рассматривать n-мерное про-
странство как прямое произведение п одномерных про-
странств, то базис в нем задается с помощью всевоз-
можных открытых параллелепипедов.
2 В, Н. Пшеничный
17
Теперь ясно, что понимать под непрерывной функ-
цией /: Xi X Х2 -> У, т. е. функцией х2), опреде-
ленной для хх е Xi, х2 е Х2 и принимающей свои зна-
чения в У. /(лгь х2) будет непрерывной, если она не-
прерывна как функция, отображающая топологиче-
ское пространство Хл X Х2 в топологическое простран-
ство У.
В дальнейшем мы будем иметь дело с топологиче-
скими пространствами, которые наделены структурой
линейного пространства.
Определение 8. Пространство L называется
линейным, если для любых х е L, у L определены
операция сложения х + у <= L и операция умножения
па вещественное число \х е L так, что
1. (х + у) + Z = X + (у + z).
2. х + у = у + х.
3. Существует такой элемент 0 е L, что для всех
x^L xi^ = x и Ox = 0.
4. (Л + p)rr = Хх + prr.
5. Мх + у) = Кх + ку.
6. (Лц)я = Х(щг).
7. 1 • х = х.
Элемент 0 играет роль «нуля» в этой системе, и его
часто обозначают знаком «нуль», если это не ведет к
недоразумениям.
В качестве примера линейного прострапства можно
указать пространство Еп n-мерпых векторов, в кото-
ром операция сложения векторов и умножения на чис-
ло определена обычным образом.
В линейном пространстве L может быть задана не-
которая топология. Тогда пространство L становится
линейным топологическим пространством, если эта то-
пология такова, что функции gtx, у)=х + у и /(Х.т) ==
= Хх, отображающие LX L -> L u Е1 XL L, не-
прерывны.
Ё1 — это пространство действительных чисел, топо-
логия в котором задана с помощью базиса, состоящего
из множеств
Ж, r) = U: IX- XJ <г}.
Линейное пространство называется нормированным,
если каждому элементу х поставлено в соответствие
число Ы, называемое нормой элемента, которое удов-
летворяет следующим условиям:
18
1) Ы>0 и равенство 1Ы1 = 0 эквивалентно равен-
ству х = О;
2) IIUII = IZHWI;
3) k + yll^ Ы'+ \\у\\.
Задание в линейном пространстве нормы позволяет
определить в нем топологию, базисом которой служат
множества
5k0, г) = {х: Пл: — .г0И </’}. (1)
В такой топологии последовательность хп сходится к
тогда и только тогда, когда
kn — 0.
Нормированное пространство является метрическим
пространством, поскольку метрика в нем может быть
задана с помощью формулы
рк, у) = к -- 7/И.
В силу сделанного замечания в нормированном
пространстве понятия компактности и бикомпактно-
сти совпадают, а понятия непрерывной функции и зам-
кнутого множества могут быть сформулированы на
языке последовательностей. Напримёр, множество А
замкнуто тогда и только тогда, когда из хп -> х0, хп^ А
следует, что х^А.
Функция определенная па нормированном про-
странстве и принимающая свел значения в прсстрск-
севе Е~ (т. е. /к) есть вещественное число), непрерыв-
на в точке Хъ тогда и только тогда, когда для каждого
с > 0 найдется такое 6 > 0, что
\f(x) —/к0)| < е,
как только к--< 6. Если учесть, что базис тополо-
гии в Е1 задается с помощью интервалов |% — AJ < е,
а базис топологии нормированного пространства задан
формулой (1), то легко видеть, что приведенное опре-
деление непрерывности полностью согласуется с опре-
делением 5.
Функции 4 k), задающие отображение А: В
одного нормированного пространства в другое, называ-
ются операторами.
В дальнейшем нормированное пространство будет
обозначаться буквой В. Особую роль при изучении
нормированного пространства В играет сопряженное
2* 19
ему пространство непрерывных линейных функциона-
лов В*. Напомним, что функционал называется ли-
нейным, если
fix + у) = /(я) + /(у)
и
/(Xz) =
Элементы пространства В* будем обозначать с по-
мощью латинских букв со звездочкой вверху: напри-
мер, ж*, у* и т. п.
Пространство В* есть линейное пространство, по-
скольку операция сложения функционалов и умноже-
ния "на число может быть определена следующим
образом:
(я* + у*)(х) = х*(х) + у*(я),
(Хх*)(л:) = Хя*(я).
Очевидно, что если х*, у*^В, то функционалы х* + у*
и Хя* также являются линейными непрерывными функ-
ционалами.
Так же легко проверяется, что если В = B2l то
В* = В* ХВ£, так что если х* е В*, то
л* (х) = z* (Zj) + х* (х2)
для некоторых х* е В*, х% е В* и любого х = х2).
Топология в пространстве В* может быть определе-
на двумя различными способами. Первая, так называ-
емая сильная топология, задается с помощью базиса,
состоящего из всех множеств
V (X, г, х%) = lx*: sup |д;* (х) — х* (я) | г|,
где X — произвольное ограниченное подмножество В,
т. е. такое множество, что IWI В для некоторого R и
всех х^Х. В такой топологии В* само оказывается
нормированным пространством, если норму функциона-
ла определить формулой
|| X* || = sup ж* (я),
1И1^1
а в качестве базиса взять систему множеств
S* (z*, г) — [я*: || X* —
20
Уместно заметить, что справедлива двойственная
формула
||х|| = max х* (х),
x*£S*
где 5* = {х*: Нх*Н 1). То, что базисы У(Х,г, х*)
и S*(x*, г)норой дают одну и ту же топологию, следует
из того, что 5* (x'q, г) совпадает с V (X, г, xj), если
X = S == {х: llxll^l},
и легко проверить, что множество V (X, г, х*) может
быть образовано как объединение множеств типа
5* (хо, г).
Вторая, слабая* топология пространства В *, обра-
зуется с помощью базиса, состоящего нз множеств
W (X, г, Xq ) = {.%•*: | х* (х) — Xq (х) | < г для хе X},
где X — подмножество В, состоящее из конечного чис-
ла элементов хг е В, i = 1, ..., к.
В соответствии с наличием двух топологий каждый
из таких терминов, как компактность, бикомпактиость,
замкнутость, сходимость, получает двойное звучание в
зависимости от того, сильная или слабая * топология
имеется в виду. Например, сходимость может быть
сильной и может быть слабой *.
Заметим, что семейство открытых множеств, обра-
зующее сильную топологию, шире семейства множеств,
образующих слабую * топологию, как это непосред-
ственно видно из определений V (X, г, х^) и W(X, г, Хд),
Поэтому (см. определение сходимости в топологическом
пространстве) из сильной сходимости последовательно-
сти функционалов хп к х0 следует слабая * сходи-
мость, однако, обратное неверно, так как хп сильно
*
сходится к Хо, если
II я* — *0 II -* °-
В то же время х*п слабо* сходится к х*, если для любо-
го х е В
Хп (х) -> X* (х).
Точно так же из бикомпактиости множества X* <= В*
в сильной топологии следует его бикомпактность в сла-
бой* топологии, однако обратное опять-таки неверно.
21
По-другому обстоит дело с понятием замкнутости.
Если множество замкнуто в сильной топологии, то оно
может оказаться не замкнутым в слабой * топологии.
Действительно, замкнутое множество есть дополнение
некоторого открытого множества. Класс открытых мно-
жеств в сильной топологии шире, чем класс открытых
множеств в слабой * топологии. Поэтому, если дополне-
ния к некоторому множеству есть открытое множество
в сильной топологии, то оно может пе оказаться от-
крытым в слабой * топологии. Наоборот, если множе-
ство слабо * замкнуто, то опо и сильно замкнуто.
Рассмотрим теперь функционалы специального ви-
да, определенные на пространстве В*. Пусть х0 е В.
Тогда величина есть линейный функционал на
77*, ибо каждому х* ставится в соответствие число
x*(xQ), причем
(х* + у*)(.г0) = х*(х0) + г/*(я0),
= Xx*(xQ).
Покажем, что построенный функционал непрерывен
в обеих топологиях. Для этого надо показать, что для'
любого xQ множество тех х*, для которых
I Z* Ы — 4 (*о) I <
c'-\<px>iTo, т. е. сора.ту ст Пег.отсрул-э схрэстяссть точт’.я
Xq » Но это множество совпадает. с множеством
V (х„, е, 4) = W (х0, 8, 4),
которое, по определению, открыто в обеих топологиях.
С понятием сходимости в нормированном простран-
стве тесно связано понятие фундаментальной последо-
вательности.
Последовательность называется фундаментальной,
если для всякого 8 > 0 существует такой номер что
ll^n — XmW < 8,
как только п, пг > N. Легко показать, что если хп х^
то последовательность хп, п = 1, ..фундаментальна.
Действительно, так как
llzn — #oll О
при п то для данного 8 найдется такой помер
‘N, что
kn-^oll <4-
для всех п> N. Пусть теперь т > N. Тогда
Н^в — ^/rJI = II (#n — #0) + (^о — Ят)Н
— д?011 + И^о — 2\JI < е.
Здесь использовано третье свойство нормы, указанное
в ее определении.
Пусть теперь нормированное пространство В тако-
во, что для всякой фундаментальной последовательно-
сти хп найдется такой элемент xQ <= В, что хп -> xQ. Та-
кое пространство называется полным. Полное норми-
рованное пространство называется пространством Ба-
наха или банаховым пространством.
Имеет место следующая теорема.
Теорема 1. Если В — пространство Банаха, то
для того,- чтобы подмножество X* пространства В*
было слабо* бикомпактным, необходимо и достаточно,
чтобы оно было слабо* замкнутым и существовала та-
кая константа R, что
Ня*Н В для всех х* е X*.
Во всяком линейном пространстве можно опреде-
лить сумму двух множеств Х4 и Х2 следующим образом:
Xi + Х2 есть множество, состоящее из элементов xt + х2,
где Xi е Xi, х2 Х2. Пусть рассматриваемое простран-
ство есть пространство В*, а Хг и Х2 —. его подмно-
жества.
Теорем а 2. Если Хх, Х2 слабо* замкнуты и Х2 —
слабо* бикомпактно, то множество Хг + Х2 слабо*
замкнуто.
Можно также определить произведение множества
в линейном пространстве на число. Если X cz L, то КХ
есть множество, состоящее из элементов \х, х^Х.
Через эти две операции уже определяется сумма вида
XiXi + \2Х2, которая очевидным образом состоит из эле-
ментов hiXi "Т Xi, х2 Х2.
Приведем два примера банаховых пространств, ко-
торые часто встречаются в экстремальных задачах.
Пространство Еп. Это пространство всех п-мерных
векторов х = {xh .,., в котором сложение и умно-
23
Женив на число определено обычным’ ооразом!
х + у = {xt + yh хп + уп},
кх = {Ххь ..
Норма в Еп задается формулой ||z|| 2 Любой
линейный функционал из (Еп)* задается формулой
П
я* (х) = 2 aixii где а = {а1? ..ап} — также некоторый
1=1
вектор n-мерного пространства. Таким образом, любо-
му я*е(£я)* соответствует однозначным образом не-
который вектор а. Обратно, предыдущая формула по-
казывает, что любому а^Еп соответствует некоторый
непрерывный функционал ж*. Более того, сумме функ-
ционалов соответствует, как легко проверить, сумма
соответствующих векторов, а произведению функцио-
нала на число— произведение вектора на число. Поэ-
тому пространство (Ея)* можно отождествить с тг-мер-
ным векторным пространством.
Сильная топология в (£”)* определяется нормой.
п Г п
||х* || = sup 2 = 1/ 2 а? = II а II-
||х'||<1 i=l Г 1=1
Таким образом, (£я)* не только есть пространство
n-мерных векторов, но и норма функционала оказыва-
ется совпадающей с нормой соответствующего ему век-
тора. Значит, сильная топология в СЕЯ)* совпадает с
топологией Еп и (£я)* = 2?я.
Нетрудно показать, что в конечномерном простран-
стве слабая* топология и сильная топология совпада-
ют, так как они определяют одинаковые системы от-
крытых множеств. Поэтому в сопряженном к Еп про-
странстве нет различия между сильной и слабой* схо-
димостью, замкнутостью, понятием компактности.
При оперировании с конечномерным пространством
удобно ввести понятие скалярного произведения одно-
го вектора на другой, которое обозначается как (а, х):
п
(а, х) = 2 ai^i-
i=i
В этих обозначениях
х*(х) = (а, х\ 1Ы1 = У(я, х).
24
Пространство С [О, 1]. Это пространство состоит из
всех непрерывных на отрезке [0, 1] функций, причвхМ
норма определена формулой
ИII = max |ж(0|.
Сходимость в этом пространстве совпадает с равномер-
ной сходимостью последовательности функций xn(t) к
x0(t). Пространство непрерывных функционалов С* со-
стоит из функционалов вида
1
X* (х) = $ x(t)dg(t), g(0) = 0,
О
где g(t) — функция ограниченной вариации. Норма Пл:*11
определяется выражением ||.г* ||=Var g (£), где Var g(0 =
k
^sup 2 | g (M — g (^-i) h и верхняя грань берется по
2 = 1
всем разбиениям Л, i = 0, .. к, tQ = 0, tk = 1.
В заключение этого беглого изложения элементов
функционального анализа введем еще понятия произ-
водных оператора. Пусть оператор Л(<г) отображает
пространство В и Говорят, что оператор А{х) диф-
ференцируем по Фреше в точке х^В, если существует
такой линейный оператор Л'(гг0): В -> Bh что
А(х) — Л (.Го) = А'(х0)(х — XQ) + 7'(т0, х — х0),
где r(x0, z) такова, что
Оператор Л(г) дифференцируем по Гато, если
А(х0 + Хе) — А(х0) = ХА'(х0)е + г(«г0, Хе),
где г(х0, Хе) такова, что
iim Н^-о.
Оператор А'(я0) называется в первом случае произ-
водной Фреше, а во втором — производной Гато.
Из того, что Л'(х0) есть производная Фреше, следу-
ет, что он является и производной Гато, однако обрат-
ное верно не всегда.
25
Напомним, что оператор А называется линейным,
если он непрерывен и
А (х + z/) = А (х) + А (у), А(кх) = АЛ (я).
Для линейного оператора можно определить сопряжен-
ный к нему оператор, обозначаемый А*. Если А — ли-
неиныи оператор, то для всякого хг е
/ (х) = х* (Ах), хсе= В, х* е 5*
есть, очевидно, линейный непрерывный функционал
на В.
Таким образом, каждому хг е можно поставить
в соответствие некоторый функционал х* е 5* так, что
х* (х) = х* (Л<г)
для всех х е В. Если обозначить этот функционал че-
рез А*Хц то оказывается, что А* есть линейный опе-
ратор из BY в 2?*. Таким образом, сопряженный опера-
тор определен следующими соотношениями:
Л*: В*^В*, (z) = z* (Аг).
2. Выпуклые множества. Понятие выпуклого мно-
жества играет важнейшую роль в исследовании экстре-
мальных задач. В сущности, вся теория необходимых
условий есть развернутое следствие теоремы отделимо-
сти выпуклых множеств.
Определение 9. Множество X в линейном про-
странстве L называется выпуклым, если из Xt е X,
х2 е X следует, что и Мач + Х2я2 е X для всех Xi, Z2‘^ О,
Х1 + Х2 = 1.
Иными словами, множество выпукло тогда и только
тогда, когда вместе с двумя точками оно содержит и
весь отрезок, их соединяющий.
Из определения выпуклости сразу же следует та-
кое свойство. Если множество X выпукло, то вместе с
точками Xi, i = 1, ..п, оно содержит и точку
х = 2 (2)
i-i
где 2 = 1, ^1 > 0.
26
Доказательство этого факта проводится по индук-
ции. Для п = 2 он следует из определения. Пусть он
установлен для п = к — 1. Пусть в (2) п = к и все
Х/>0, f = l, ..к. Если некоторое X; = О, то дело сво-
дится уже к рассмотренному случаю п = к — 1.
Положим Xj = Xj/X, i = 2, ... , А*, X = Х2 + • • • + Х&.
Тогда
2 = 1,
1=2
-Лл' 1 k
и точка х — 2 Xi^j = -г-2 Xj^i е X, по предположению
г=2 Л i=2
индукции. Тогда
х = X[X1 + ХУ, Xi X, х X,
k
п так как Xi О, X > 0 и Хг -ф X = 2 Хг = 1, то по оп-
1=1
ределеиию выпуклого множества х е X, что и требо-
валось доказать.
Пусть теперь В есть пространство Банаха. Основное
свойство выпуклых множеств, которое делает эти мно-
жества таким ценным орудием при исследовании экс-
тремальных задач, дается следующей теоремой — тео-
ремой об отделимости выпуклых множеств.
Теорема 3. Любые два непересекающихся вы-
пуклых множества X и Y в банаховом пространстве,
одно из которых содержит внутреннюю точку, могут
быть разделены некоторым ненулевым линейным функ-
ционалом, т. е. найдется такой ненулевой функционал
х* е что
Х*(х) С х*(у)
для всех х^Х, у е У.
Примечание 1. Точка х0 е А называется внут-
ренней точкой подмножества А, лежащего в некотором
топологическом пространстве, если найдется такая
окрестность Q этой точки, что Qcz/l. В рассматривае-
мом случае пространства Банаха точка х0 есть внут-
ренняя точка множества X, если для некоторого г все
точки, удовлетворяющие неравенству
Пя — я0И < г,
принадлежат множеству X,
27
Прнмеланпе 2. Если пространство конечномер-
но, требование о наличии в одном из множеств внут-
ренней точки, которое содержится в формулировке
теоремы 3, можно опустить.
В случае, когда множества X и Y замкнутые, тео-
рема 3 допускает уточнение.
Теорема 4. Если X и Y — непересекающиеся
замкнутые выпуклые множества из В, причем У би-
компактно, то существуют такой непрерывный линей-
ный функционал х* еВ* и такие константы с и
е > 0, что
х*(х) < с — е < с С х*(у)
для всех х^ X, у е У,
Следствие. Если X — замкнутое выпуклое мно-
жество из В и х0 ё X, то существует такой функционал
еВ*, что для всех х^Х
х* (х) хо (*о) “ е> Vz е X,
где е — некоторое положительное число.
В самом деле, множество, состоящее из одной точ-
ки, очевидно, бикомпактно.
Нам придется рассматривать выпуклые множества
в пространстве В*, сопряженном к данному простран-
ству Банаха В. В этом пространстве нас будет инте-
ресовать теорема отделимости, в которой отделяющий
линейный функционал имеет специальный вид — его
можно отождествить с некоторым элементом исходного
пространства В.
Теорема 5. Пусть X* — выпуклое слабо* зам-
кнутое множество в В*. Тогда для любого xQ е X* су-
ществует такой элемент xQ е В, что
я* (*о) < х* (*о) — е
для всех х* е X* и некоторого е > 0.
Определение 10. Наименьшее выпуклое мно-
жество, содержащее данное множество X (т. е. пересе-
чение всех выпуклых множеств, содержащих X), назы-
вается выпуклой оболочкой множества X и обозначает-
ся со X.
Данное определение выпуклой оболочки годится
для множества X из любого линейного пространства.
Если к тому же рассматриваемое пространство L есть
28
линейное топологическое пространство, то Мояйго вве-
сти понятие замкну / ой выпуклой оболочки соХ, кото-
рая определяется как наименьшее выпуклое замкнутое
множество, содержащее X.
Легко видеть, что со X состоит из всех точек т,
представимых в виде выпуклой комбинации точек из
X, т. е. из точек х, представимых в виде
h k
X = 2 ^if Xj^X, 2^г—
2=1 2 = 1
Это непосредственно следует из того, что множество
всех точек, образованных как выпуклая комбинация
точек из X, выпукло, и любое выпуклое множество,
как это было показано выше, должно содержать все
выпуклые комбинации своих точек.
Приведем некоторые свойства выпуклых оболочек.
Лемма 3. Для произвольных подмножеств X и Y
линейного пространства L:
1) со(аХ) = асоХ, со (X + У) = со X + со У.
Если L есть линейное топологическое простран-
ство, то
2Гсо(Х)_=^ТХ)^ _
3) если со_Х и со У бикомпактны, то со (X U У) =
= со (со X U со У); в частности, если X и У бикомпакт-
ны и выпуклы, то
со”(Х U У) = со (X U У).
Примечание. Черта над множеством означает
замыкание.
В конечномерном пространстве выпуклая оболочка
множества обладает одним специфическим свойством,
которое оказывается чрезвычайно полезным и из кото-
рого следует ряд тонких результатов в теории чебы-
шевских приближений и теории моментов.
Теорема 6. Если X — подмножество п-мерного
пространства Еп, то любая точка из со X представима
в виде выпуклой комбинации не более чем (п+1)
точки из X.
Доказательство. Как уже указывалось выше,
любая точка соХ представима в виде
• h
X = 2 X.
2 = 1
29
Допустим, что к > п + 1 и все Хг > 0. (Если некото -
рое Х< = 0, то число к может быть уменьшено.)
Введем векторы z/i (тг + 1)-мерпого пространства,
образованные так:
(хг\
Уг = I t •
Поскольку к >п+1, то число векторов у, больше, чем
размерность пространства, в котором они лежат, и поэ-
тому они линейно зависимы, т. е. найдутся такие не
все равные пулю числа af, что
k
2 «ij/i = °
1-1
или в покомпонентном виде
к
2 ~ 0,
г- 1
к
2 = о.
Поскольку а» не все равны пулю, а их сумма равна
нулю, то среди найдутся положительные. Положим
теперь Х/е) = Xf — eaj. Тогда
k k k
2 U № - 2 - e 2 «i = 1.
• 1=1 1=1 i~l
Кроме того, так как Xf > 0, то при малых е Me) > 0.
Будем теперь увеличивать е от нуля до тех пор,
пока какое-либо ХДе) пе обратится в пуль. Поскольку
среди сс, есть положительные, то это обязательно про-
изойдет при некотором е = е0, е0 > 0. Тогда Х* = Xj(e0)^
0, причем хоть одно из X,- равно нулю. Теперь
к
X = 2 Х^.
1=1
Действительно,
к к k к
к^Х} CgCCj) Xi kjXi Ед CCiXj = X»
i=l i=l 1=1 i=i
Итак, точка x представлена в виде выпуклой ком-
бинации к точек Xi «н X, причем хотя бы один коэффи-
циент Xj обращается в нуль. Это значит, что если х
30
представима в виде выпуклой комбинации к точек
Xi X и к > п + 1, то она представима в виде выпук-
лой комбинации (к — 1) точки.
Отсюда, собственно, и следует теорема, так как с
помощью описанной процедуры число к можно умень-
шать до тех пор, пока оно не станет равным п + 1.
Обратимся теперь к специальному классу выпуклых
множеств — выпуклым конусам.
Определение 11. Множество К лилейного про-
странства называется выпуклым конусом, если оно вы-
пукло, и из того, что х е К, следует, что \х е К при
любом Z > 0.
Нетрудно проверить, что К есть выпуклый конус
тогда и только тогда, когда из х, у е К следует х + у е
К и Хх^ К для любого X > 0.
Если исходное пространство В есть пространство
Банаха, то каждый выпуклый конус К^В порожда-
ет некоторый другой конус К* в В*, который называ-
ется двойственным или сопряженным к конусу К,
По определению
7?* = {х*' х* <= В*, х*(х) > 0 для всех х е /<}.
Так как из х* е К* и у* <= X*, % > 0 следует, что
х*(х) + у* (я) > 0, Кх*(х) > 0
для всех х е К, то К* также представляет собой вы-
пуклый конус.
Приведем некоторые свойства конуса Z£*. Ясно,
что нулевой функционал х* = 0 всегда принадлежит
К*. Если К^В, т. е. К не совпадает со всем простран-
ством, то 'К* содержит отличные от нуля элементы.
В самом деле, если К^В, то найдется такой элемент
xQ, который не принадлежит замкнутому выпуклому
множеству'/?. Тогда, по следствию теоремы 4, найдет-
ся такой функционал xQ, что
а-Ъ < а * (х0) — е
для всех х е К, пли, если обозначить х* — — х*,
xt (х) X* (£0) -I- 8.
Покажем, что х* (х) 0 для всех х^ К. Действи-
тельно, если хк (ях) < 0 для некоторого х^ е К, то, так
3.1
как е К для всех X > О,
я* (^^i) = (#i) -> — 00
при % -> + со. В то же время из е К должно еле-
*
довать по построению что
z* > х* (z0) + 8.
Полученное противоречие показывает, что х* (х) О
для всех х^ К и хх есть ненулевой функционал, при-
надлежащий конусу_А*.
Лемма 4. 1) (А)* = А*.
2) х е К тогда и только тогда, когда
х*(х) > 0 для всех х* е А*.
3) Если х — внутренний элемент К, то
х*(х)>0 для всех х*^К*, х* 0.
Доказательство. 1) Поскольку В — нормиро-
ванное пространство, то замыкание К конуса К состо-
ит из точек самого К и из таких точек х0, для
которых существует последовательность хп К, хп х*0.
Поэтому, если х* е А*, то х*(хп) >0, ив силу непре-
рывности х* x*{xQ) > 0_для любой точки х0 е К. От-
сюда следует, что_я* е (;<)*.
Итак, А*с(А)*. С другой стороны, так как мно-
жество К шире множества А, то в силу определения
двойственного конуса А* => (АО*. Поэтому А* = (А)*.
2) Если х^К, то по определению (А)*
я*Сг) >0 для всех я*^(А)*.
Но, как только что показано, А* = (А)*. Поэтому иссле-
дуемое неравенство выполняется, если х е А. Пусть
теперь точка х^ такова, что д?*(£0) > 0 для всех х* <=
е А*. Допустим, что xQ е А. Тогда, как показано при
доказательстве того, что А* содержит ненулевые эле-
менты, если К¥= В, найдется такой функционал xY е
е А*, что
Я* (^) (^о) + е > 0,
для всех х е А. Но так как \х s К для любого х & К
и X > 0, то, устремляя X к нулю, получим, что 0 А.
Подставляя 0 в предыдущее неравенство, получаем
33
— e^^i(^0). Это противоречит тому, что х* е К* и
x*(xQ) больше нуля для всех я* е АЛ
3) Пусть xQ — внутренний элемент К, т. е. най-
дется такое г > 0, что все х, удовлетворяющие нера-
венству
II# — я011 < г, (3)
также принадлежат К. Для любого ж* е К*, х* ¥* О,
£*(z) >0
при всех х е К и, в частности, при всех х, удовлетво-
ряющих (3).
По определению нормы функционала
|| х* || = sup X* (х)
IMK1
найдется такой элемент е, Hell 1, что
II z* II > х* (е) > -у-1| х* ||.
Рассмотрим точку хх = х0-------- е. х{ удовлетворяет
, ибо
ki - *oll = I -J- е|| = -J-PII <г-
Поэтому х^ е К и
я* (^1) = х* (^о)--х* (е) О»
пли
(*о) > -у я* (е) > -у II х* || > О,
(4)
что и требовалось доказать.
Лемма 5. Если К — выпуклый конус, то конус
К* слабо* замкнут.
Доказательство. Необходимо показать по оп-
ределению замкнутого множества, что множество всех
х*, не принадлежащих К*, открыто. Для этого доста-
точно показать, что если гс0 е К*, то найдется такое
открытое в слабой топологии пространства В* мно-
жество, которое содержит х$ и не имеет общих точек
с К*. Тогда множество всех х* е К* будет открыто
как объединение всех таких открытых множеств, по-
строенных для каждого х* е К*.
3 Б. Ц. Пшеничный 33
Пусть А*. Тогда, по определению А*, найдет-
ся такое х0 А, что xQ (х0) = а < 0.
Определим множество М = {#*: 2а < < 0).
Очевидно, что х$ е М и М не имеет общих точек с
А*. Покажем, что М — открытое множество. Действи-
тельно,
М = W (х0, | а о£) = {ж*: Iх* (х0) — х* (х0) | < | а |),
которое, по определению, является открытым мно-
жеством в слабой* топологии пространства 5*.
Лемма доказана.
§ 1. ВЫПУКЛЫЕ ФУНКЦИИ
Выпуклые функции являются одним из основных
объектов при изучении и исследовании экстремальных
задач.
1. Определение и основные свойства. Пусть /U) —
некоторая функция аргумента х^ В, которая может
принимать значения из расширенной числовой оси,
т. е. /(я) есть либо конечное действительное число, ли-
бо ±«>. Положим
dom / = {х: f(x) < +оо},
epi / = {{х, а): а > f(x)}.
Первое из этих множеств называется эффективной
областью определения функции f, а второе — надгра-
фиком функции /. Как правило, дальше не будут рас-
сматриваться функции, принимающие значения — оо.
Функции, не принимающие значения — 00 и не равные
тождественно +°о, называются собственными. Для
таких функций dom / есть их область определения.
Функция / называется выпуклой, если epi/ есть
выпуклое множество. Для собственных функций это
определение эквивалентно следующему: функция / вы-
пукла, если
/(Xi^i + X2rr2) + X2/(z2)
для всех х^ х2 В и Хь Х2 > 0 таких, что Xi + Х2 = 1.
Мы практически , не будем в дальнейшем сталки-
ваться с функциями, принимающими значение —
Однако один факт относительно таких функций часто
бывает полезен и его стоит отметить. Пусть у е dom / —
точка, в KOTopoii /(у) s — °0, a z^intdom/, / — вы-
3*
35
йуклая функция. Тогда при достаточно малом е > О
= х + eU — у) <= dom /.
Легко видеть, что
1 , 8
Ж = 7+Гх1 + Т+Т^
Так как f(y) = — <», то для любого [3 {р, у} е epi /.
Пусть al > /(#1), т. е. {ab xj е epi /. В силу выпукло-
сти epi /
1Т-Л— а1 + — ₽, -т4— + V7— У e₽i Л
[1 + е 1 1 + е 1 1 + 8 1 1 + е J
/ (х) = f — X, + -т-т— И ~т~г— ai + ’ 4 ?•
Так как [3 произвольно, то, устремляя £ к — °°, полу-
чаем f(x) = — оо.
Итак, если выпуклая функция / принимает значе-
ние — о© для некоторого аргумента у, то f(x) = — оо
для всех х е int dom f.
Условимся на будущее, что если не оговорено
противное, то все рассматриваемые функции являются
собственными.
Надеюсь, что читатель не сочтет за труд показать,
что если Д(я), i <= Z,— выпуклые функции, где I — про-
извольное множество индексов, то
f(x) = sup {fi(x): i <= /}
i
есть снова выпуклая функция. То же самое верно для
линейной комбинации выпуклых функций с положи-
тельными коэффициентами.
Приведем теперь простую, но очень часто исполь-
зуемую лемму.
Лемма 1.1. Пусть g(а) — выпуклая функция од-
номерного аргумента а, а0 < czj < а2, а,- dom g.
Тогда 1 •
g (К2) ~ g (а0) > g («Д) ~ g (%)
“2 ~ а0 “1 - % ’
g (И1) ~ g (tto) < g(a2)-g(«!)
“1 ~ а2 “ “1
36
Доказательство. Положим
Тогда
а, — ап ао — а
?ча2 + Х2а0 = а2 + а0= аг.
2 0 2 О
Поэтому
g (“i) ~ g (Ь1«2 + Мо) < “* g(«2) + а"-а1 g^'
а2 а0 % а0
Полученное неравенство можно преобразовать двумя
способами
1. Вычитая из обеих частей g(a0), получим
а, — аА
g («1) - g (а0) < a --a (g ~ g <“<>»’
2 О
откуда, после деления на <zi — а0, вытекает первое не-
равенство леммы.
2. Так как Zi + Х2 = 1, то
'-*'1 ------ '•Л'л --------------------------------------------
2 0 2 О
а. — ап
или
(g («1) - g (ао)) < а'-а0 (g ~ g
а2 а0 а2 %
откуда получаем второе неравенство леммы.
Заметим, что первое из неравенств, доказанных в
g(a)-g(a)
лемме, показывает, что функция ----------монотоп-
а а0
но не убывает при возрастании а, а > а0.
Теорема 1.1. Собственная выпуклая функция f
непрерывна в точке xQ е dom / тогда и только тогда,
когда она ограничена сверху в некоторой окрестности
этой точки.
Доказательство. Ясно, что если / непрерывна
в точке х0, то она ограничена сверху в некоторой ок-
рестности этой точки. Поэтому доказательство требует
только обратное утверждение.
37
Без ограничения общности предположим, что выб-
ранной точкой является точка х0 = 0. Пусть й — неко-
торый открытый шар с центром в нуле и /(х) с4 для
всех ж ей. Рассмотрим функцию g(a) =/(ая) при
фиксированном х е Й. Положив в первом неравенстве
леммы 1.1 а0 = 0, ai = a > 0, сс2 = 1, получим
g(a) — g(0) g(l)~g(0) ,
a 1
Так как g(l') = /(ж) сь g(0) = /(0), то
/(сел:) — /(0) cctc! — /(0)].
Далее, положив во втором неравенстве леммы 1.1
а0 = — 1, а0 = 0, а2 = а, получаем
g (0) — g (— 1) g(a)-g(Q)
0-(-1) a
откуда a(/(0) — ct) C f^ax^ — /(0). Итак,
— /(0)1 СсД^-ДО)). (1.1)
Возьмем е>0 и 6 =—_е < 1, йб = бй. Пусть
с] / )
у е йб. Тогда существует такой вектор х е й, что у =»
= Ьх. Согласно оценке (1.1)
1/(у) - /(0)1 = 1/(6^) - /(0)1 б(С1 - /(0)) = е,
что и требовалось доказать.
Теорема 1.2. Если выпуклая функция / непре-
рывна в точке х0, то она удовлетворяет условию Лип-
шица в этой точке.
Доказательство. Можно считать, что xQ = 0.
Пусть г—радиус шара й, фигурирующего в предыду-
щей теореме.
Пусть у е Й, llz/ll < г/2. Положим х =•=
II У II
Тогда, используя (1.1), получаем
1/(1/)-/(0) |<
ж) — / (0)
МН
т А 1 7 ' ') . ~
где Ь = ------------’ что и требовалось доказать.
Для исследования выпуклых функций часто бывает
важным понятие замкнутости. Функция / называется
замкнутой, если ее падграфик есть замкнутое мно-
жество.
38
Нетрудно показать, что свойство замкнутости эк-
вивалентно двум следующим свойствам: а) множества
уровня
Ра = U: /(я) < а)
замкнуты при любом б) функция / полунепре-
рывна снизу в каждой точке.
Напомним, что функция полунепрерывна снизу в
точке £0, если lim inf /(ar) > /(гг0).
X-»Xq
2. Сопряженные функции.
Определение 1.1. Функция
/*(#*) = sup {а:*(аг) — /(ж)},
X
определенная для х* е 5*, называется сопряженной к
/. Легко видеть, что иадграфик функции /* есть пере-
сечение надграфиков, линейных относительно х* функ-
ций х*(х) — /(я), и поэтому является выпуклым и зам-
кнутым множеством. Отсюда следует, что /* всегда
выпукла и замкнута.
Приведем теперь доказательство одной из важней-
ших теорем теории выпуклых функций.
Теорема 1.3. Пусть f—собственная выпуклая
замкнутая функция. Тогда f = где
f**(x) = sup {х*(х) — /*(#*)}.
х*
Доказательство. По определению /*(я*)
/(ж) > хЧх) — /*(#*),
и поэтому /(<г) /**(#). Отсюда, в частности, следует,
что dom / s dom /**. Пусть xQ е dom /. Выберем у < f(x0)
и рассмотрим множество
Pt = {{х, а): х — х0 <= ей, а С 7},
где Й — единичный шар в В. Так как epi f — замкну-
тое множество, то Ра и epi/ при достаточно малом
с > 0 не пересекаются.
Воспользовавшись теоремой 3, построим такой ли-
нейный функционал х* п число р, что
Ра + я*(у) > Pai + (1.2)
{у, a}^PR, {х, aj^epi/,
причем ж* и р не равны пулю одновременно. Так как
ос можно взять любым, меньшим 7, то из (1.2) сле-
39
дует, что р 0. Покажем, что Р < 0. Действительно,
если положить (J = 0, то формула (1.2) приобретает вид
х*(у) х*(х\ y — Xo^eQ, rc^dom/.
Положив х = х0, получим, что
х*(у — х0)Х), у — х0<== eQ.
Но так как Q — единичный шар, то последнее нера-
венство возможно лишь, если х* = 0, что вместе с
Р = 0 находится в противоречии с тем, что х* и р не
равны нулю одновременно.
Итак, р < 0 и, пе ограничивая общности, можно
считать, что Р = — 1. Теперь (1.2) приобретает вид
— а + х*(у) > — + х*(х),
y — Xo^eQ, ai>f(x).
Положив а = у, ai = f(x), у = х0, получаем
х*(х0) — у > sup {х*(х) — f(x)} = /*(#*),
х
ИЛИ
y^*(z0) -/*(я*), (1.3)
откуда
у sup {х*(х0) — /*(гг0)} = /**(я0). (1.4)
Так как у — произвольное число, меньшее /(я0), то
f(x0) /**(ХО),
что после сопоставления с противоположным неравен-
ством, доказанным ранее, ведет к равенству /(ж0) я
= /**Uo).
Пусть теперь х0 е dom /, т. е. f(x0) = + оо. Точно
так же, как и ранее, взяв произвольное у, можно по-
казать, что epi/ и Ре при малом е не пересекаются и
справедливо неравенство (1.2).
Если для произвольно больших у соответствующее
Р < 0, то выполняется (1.4) и, так как у©о, то
/**(х0) =4-00 =/(х0).
Пусть теперь р = 0 для некоторого у. Тогда из
(1.2) получаем, что
x*(i/) > £*(#), у-х0<^&£2, x^domf.
Поэтому
inf U*(y — х0): у — rroeeQ} > SUp {х*(х — л:0): е dom/},.
у X
40
или
—ellx*ll > sup {х*(х — х^: zedom/). (1.5)
X
Так как / — собственная функция, то существует та-
кая точка #1, что — конечное число, ^edomf.
Если применить к этой точке предыдущие рассужде-
ния, то можно получить неравенство (1.3), в котором
точка xQ заменена на хи а 7 </(xJ:
/*(#*’) x*(xj — у,
откуда следует, что /*(#*) конечно и dom /* ¥= 0.
Пусть Xi е dom /. Тогда
/* (х* + ах*) =sup {(z* + ах*) (х) — / (я)]
X
/* (#1) + а sup х* (я)*
xsdom/
Учитывая (1.5), получаем
/** (*о) > (xi + а®*) (*о) — /* (х* + ах*) >
> xi (хо) — /* (**) + а Г«* (х0) — sup х* (х)1 >
L xedom/ J
> X* (x0) — /* (x*) + ае || X* ||-> + oo,
при aИтак, f**(xQ) = + °°, что завершает дока-
зательство.
Рассмотрим теперь положительно однородные вы-
пуклые функции, т. е. функции, удовлетворяющие
условию
/(Ля)=Х/(я), Х>0.
Если эта функция замкнута, то нетрудно убедиться,
что /(0) = 0.
Теорема 1.4. Если j — положительно однородная
выпуклая замкнутая функция, то
f*{x*) = 6(z*|dom /*),
где
( о,
х е М,
х~В М.
Доказательство. По определению,
у*(д.*) = SUp {х*(х) — /(х)} > — /(0) = 0.
X
Пусть для некоторого Xi
x*{Xi) - f(xj > 0.
41
Тогда
/* (я*) sup {z* (Х^) — / (Ххг)} =
Х>0
«= sup X [Я* (^i) — f (#!)] = + °°-
Х>0
Итак, /*(#*) может принимать лишь два значения,
О и + % что доказывает теорему.
Теорема 1.5. Если f—положительно однородная
выпуклая замкнутая функция, то
f(x) = sup {х*(х): х* е dom /*}.
Доказательство получаем прямым применением тео-
ремы 1.3. Действительно,
/(я) = /**(я) = sup {х*(х} — 6(z*ldom /*)} =>
X*
= sup {х*(х): х* е dom /*}.
Теорема 1.6. Пусть М*^В*, М* — выпукло и
слабо* замкнуто и
j(x) = sup {х*(х): х* & М*}.
х*
Тогда
f*(x*) = 6(х*\М*).
Доказательство. В силу выпуклости и замк-
нутости М* б(^*|М*) также выпукла и замкнута.
Далее,
= sup {х*(х) — 6(я*|7И*)} =
X*
= sup {х*(х)\ х* е М*} = /(я).
X*
Поэтому по теореме 1.3
/*(#*) = (б( • |#*))** =
что и требовалось доказать.
3. Субдифференциалы выпуклых функций. Выпук-
лые функции, вообще говоря, не дифференцируемы в
обычном смысле. Тем не менее они обладают произ-
водными по направлению. Кроме того, для выпуклых
функций можно определить понятие субдифференци-
ала, которое в задачах не экстремум заменяет понятие
градиента обычной гладкой функции.
Пусть f — выпуклая собственная функция, х е
е dom /, р е В. Тогда нетрудно видеть, что справедливы
42
неравенства
/(z) —/(z —ер) /(* + —/(*) ^ fix + \P)~ /(*)
8 \ X2
для e > 0, 0 < Ai < A2. Эти неравенства очевидны, если
х — гр, х + К^р или х + К2р не принадлежит dom/. Если
же все эти точки принадлежат dom /, то неравенства
следуют из леммы 1.1, примененной к функции g(a) =
= fix + ар).
Из построенного неравенства следует
Теорема 1.7. Пусть /—выпуклая собственная
функция, x^domf. Тогда при АЛО разностное отно-
шение
/(^ + АР)-/(х)
А ’
монотонно убывая, стремится к производной по на-
правлению fix, р), которая конечная или бесконечная,
всегда существует.
Если существует такое е > 0, что х + Хр е dom /,
А L—8, +eJ, то fix, р) есть конечная величина.
Лемма 1.2. fix, р) есть положительно однород-
ная выпуклая функция р.
Доказательство. По определению, для а>0
f (х, ар) = lim /^ + Хар)-/(х) =
= а lim /(* +(Ха) р)-/(*) = af р}
х-»о
Далее, для Xlt > 0, Aj + Х2 = 1 имеем
%ар2)) —/(х) _
X '
“ X
/ (* + kpt) ~ / (*) . f + \р2) — f (х)
1 X +Л2 X
Переходя к пределу при X I 0, получаем
/'U, X,Pj + Х2р2) ^hf'^x, Pi) +X2/'U, p2),
что доказывает лемму.
Определение 1.2. Множество
dfix) {я* е= В*; fiy) - fix) > x*iy - х), Vy}
43
называется субдифференциалом выпуклой функции /
в точке х, а его элементы х* — субградиентами.
Очевидным следствием данного определения явля-
ется выпуклость и слабая* замкнутость множества df.
Лемма 1.3. х* является субградиентом выпуклой
функции f в точке х тогда и только тогда, когда
fix, р) x*ip) для всех р.
Доказательство. Если х* е dfix), то
/(я + Кр) - fix) > hx*ip),
откуда > х* ip), и fix, р) > x*ip).
Обратно, если,это неравенство выполнено для всех
р, то для X е (0, 1)
/ (у) - /(х) = -./<*),
> /’ I/ _ X) > г* (у - ж),
т. е. х* s dfix).
Теорема 1.8. Если fix, р) есть замкнутая функ-
ция р, то dfix) #= 0 и
fix, р) = sup {x*ip); х* dfix)}.
х*
Доказательство. Так как fix, р) положитель-
но однородна и выпукла, то при условии замкнутости
к ней может быть применена теорема 1.5. Согласно
этой теореме
fix, р) = sup {x*ip): х* g= domifix, •))*}, (1.6)
X*
где ifix, •))* означает функцию, сопряженную к
fix, р) относительно р, т. е.
ifix, •))*(#*) = sup U*(/>) - fix, p)}. (1.7)
Но по теореме 1.4.
tv i \\* t *\ ( dom (/'(x, .))*,
/U,4*U* = __
[ +oo, x* e dom if ix, •))*,
поэтому, с учетом (1.7), получаем, что x* e
e dom if ix, •))* тогда и только тогда, когда 0 x*ip} —
— fix, р), что согласно лемме 1.3 эквивалентно соотно-
шению х* dfix). Итак,
dfix) = dom if ix, •))*.
44
Подставляя это выражение для д{ в (1.6), получаем
требуемый результат.
Теорема 1.9. Если выпуклая функция / непре-
рывна в точке х, то dj(x) не пусто, ограничено по
норме и
f'(x, р) = max {х*(р); х* е= df(x)}.
X*
Доказательство. Так как х — точка непрерыв-
ности /, то существует такое 8 > 0, что для всех у,
Hi/ — xll С 8, f(y) ограничена некоторой величиной с.
Поэтому, если ИрН С 8, то
/'(х, р) Кх + р) - /(х) с - Кх\ (1.8)
Итак, /'(х, р) есть выпуклая ограниченная сверху
функция аргумента р в окрестности точки р = 0. Сог-
ласно теореме 1.1 f'(x, р) непрерывна в точке
и, тем более, замкнута. Поэтому по теореме 1.8 спра-
ведлива формула
f'(x, р) = sup {х*(р): х* е df(x)}. (1.9)
X*
Учитывая теперь (1.8) и выражение для Их*II, получаем
с — /(х)> sup /' (х, р) =
||рКе
= sup supx*(p)= sup 81| X* ||,
||p||^e x*ed/(x)
т. e. || x* || (c — / (x))/8 для x* e 5/(x).
Тем самым ограниченность d/(x) доказана. Так как,
с другой стороны, <Э/(х) слабо* замкнуто, то д}(х)
слабо* бикомпактно (см. теорему 1 Введения). Но не-
прерывный в слабой* топологии функционал х*(р)
(р — фиксировано, аргумент х*) достигает своего мак-*
спмума на бикомпактном множестве, согласно обоб-
щенной теореме Вейерштрасса (см., например [5J,
стр. 29). Поэтому верхнюю грань в (1.9) можно заме-
нить на знак max, что завершает доказательство.
Легко видеть, что <Э(а/) = adf. Аналогичное прави-
ло для субдифферепциала суммы двух выпуклых функ-
ций представляет уже содержание важной и далеко
не тривиальной теоремы.
Теорема 1.10. Пусть / = Л + /2, где ft и f2 —
собственные выпуклые функции, и пусть существует
точка
х^ е dom ft П dom /2>
45
в которой fi непрерывна. Тогда
dj^x) = д/М + д/ДаД,
для всех точек х, в которых df^x) и df2(x) не пусты.
Доказательство. Если хх е df^x), х2 е df2(x),
то, суммируя иеравепства
—/i (•*)>** (*/ — *),
/2 (*/) - /2 (*) > 4 {У — *),
получаем
f {у) — f (х) х* (у — х), X* = X* + X*,
т. е. 4 + 4 £ df (х). Таким образом, д{ 5/j + df2.
Докажем обратное включение. Для упрощения
выкладок предположим, что х = О, /ДО) =/2(0) “=0
(этого всегда можно добиться сдвигом начала коорди-
нат и вычитанием констант из функций f^ и /2). Пусть
х*еЗ/(0), т. е. согласно определению
/Ду)+/2(у)^**(у), (1.105
где учтено, что х == 0, /ДО) = /2(0) = 0.
Перепишем неравенство (1.10) в виде:
/Ду)-**(у)^-/2(у). (1.11)
Введем в В ХЕ1 выпуклые множества:
А = {{а, у}; а > /Ду) — я*(у)},
£ = {{₽, z): p<-/2(z)}.
Выпуклость А и В легко следует из выпуклости Д и /2.
Из неравенства (1.11) следует, что А и В не пере-
секаются. Далее, так как хх — точка непрерывности
/1, то точка-{аь яД, где cci >/ДяД--я*^), является
внутренней точкой множества А. Согласно теореме 3
Введения множества А и В можно отделить, т. е. най-
дутся такое число V и zoeZ?*,£0 и xQ не равные
нулю одновременно, что
£°₽+*о* (z) < в°а + х* (у), (1.12)
{[3, z} s /э, {со, у} <= А.
Так как а можно увеличить неограниченно, то из
(1.12) следует, что > 0. Покажем, что > 0. Дей-
ствительно, если |° = 0, то (1.12) можно переписать
4G
в виде
4 (z)<z* (г/), zedom/г, г/edom/p (1.13)
Положим z = xt. Далее, так как х{ е dom Д — точка
непрерывности /1, то + гр е doim/л, 1» при
достаточно малом е > 0. Подставляя z = xh у = -Ь
+ гр в (1.13), получаем
О<ехо(/?), ||р||<1.
Но это возможно, лишь если ||х*| = 0, т.е. х* — 0 и
В° = 0, в противоречии с предыдущим.
Итак, > 0 и можно считать, что £°=1. Теперь
с учетом определения А и В из (3.12) получаем
— /2 (z) + *0 (2) < /1 (//) — (у) + 4 (!/), (1.14)
zedom/2, (/Gdom/?
Так как вне dom/2 и dom Л функции /2 и бесконеч-
ны, то можно считать, что неравенство (1.14) выпол-
няется при всех z и у. Положив z = 0, получаем
— Хо)(у),
т. е. х* — я* е д/± (0). Положив у = 0, получаем /2 (2)
Xq (z), т. е. х^ е df2 (0). Поэтому
X* = (х* — а?о) + 4 (= д/г (0) + dft (0).
Так как х* — произвольный элемент 5/(0), то
5/(0) 5/ДО) + 5/2(0).
Учитывая ранее доказанное противоположное вклю-
чение, окончательно получаем 5/(0) = 5Д(0)' + 5/2(0),
что и требовалось доказать.
Проиллюстрируем приведенную теорему одним из
ее применений. Как было определено выше для вы-
пуклого множества М
6(*|М) = - ’
I + °°i х^ М.
Пусть х ^М. По определению, я*‘^5бШЛ/) тогда и
только тогда, когда
6(у \М) — 6(х\М) > х^(у — х).
Но 6UW) = 0. Если у то б(у|Л/) =.+«? и неравен-
47
ство выполняется для любого х*. Для у М получаем
CL> <г*(у — х), У*=М. (1.15)
Итак, соотношение х*^д§(х\М) эквивалентно нера-
венству (1.15). Пусть, по определению,
con (М — х) = {р: р = к(у — я), Z > 0, у М},
Тогда легко видеть, что (1.15) просто выражает тот
факт, что
—х* е [con (М — x)J*.
Итак,
aS(x|M) = -[con (М - я)]*. (1.16)
Если теперь М = К — конус, х = 0 е К, то легко ви-
деть, что
con (К-0)=К,
так что
06(0170 = -Я*. (1.17)
Теорема 1.11. Пусть i = 0, 1, ..m — вы-
пуклые конусы и
Ко 0 int Ki П ... Г) int Km ¥= 0.
Тогда
(KQ n^n ... R7Q* = К* + K*+
Доказательство. Так как конус К и его за-
мыкание имеют одинаковые сопряженные конусы,
а точка 0 всегда принадлежит замыканию конуса, то
можно считать, что 0 е Кг. Заметим теперь, что
(7И \
х| П К, =6(z|ZQ + 6(z|tf1)+ ... +6(z|tfm).
i=0 /
Согласно предположению теоремы существует точка
Xi такая, что
Xi е Кй = dom 6( • IЯо),
Xi е int = int dom 6(-|7£t), i = l, ..
Очевидно, что в точке Xi функции 6(-|7£г), г=1, ш
непрерывны, так как принимают в некоторой окрест-
ности этой точки постоянное значение 0. Поэтому,
применяя теорему 1.10 (вернее, ее очевидное обобще-
ние на пг + 1 слагаемое), получаем
(771 \
0| П Кг =56(0|^) +56(01^)+... +<?6(0|Ят),
1=0 /
48
или, с учетом формулы (1.17),
/ т \* * » .
- лаЛ = — к* — к* — ... — Кт,
\i=0 ]
что и требовалось доказать.
В заключение этого параграфа установим еще од-
ну полезную формулу для вычисления субдиффереп-
циала.
Теорема 1.12. Пусть М* — выпуклое слабо*
замкнутое в В* множество и
fix) = sup {x*ix)\ х* е 71/*}. (1.18)
х*
Тогда dfix) = {х* <= М*: x*ix) = fix)}.
Доказательство. По определению x*^dJix)
тогда и только тогда, когда
/(*/) — /(я) > x*iy — х) для всех у,
т. е. x*ix) — fix) > x*iy) — fiy), или, беря верхнюю
грань в правой части по у,
x*ix) — fix) > f*ix*).
Но так как очевидным образом выполняется противо-
положное неравенство (ведь можно положить у = х),
то окончательно получаем, что х* е dfix) тогда и толь-
ко тогда, когда
fix) + f*ix*) = x*ix). (1.19)
Это утверждение справедливо для любой выпуклой
функции. Применим его к функции (1.18), рассматри-
ваемой в теореме. Согласно теореме 1.6 f*ix*) =
= bix*\M*), так что соотношение (1.19) переписыва-
ется в виде
fix) + 8ix*\M*) = х*(х).
Ясно, что в силу свойств функции б это равенство воз-
можно, лишь если х*^М*, т. е. 6(±*|71/*)=О и
x*ix) = fix), что и требовалось доказать.
§ 2. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
Основываясь на свойствах выпуклых функций, изу-
ченных в предыдущем параграфе, мы построим здесь
теорию необходимых и достаточных условий экстре-
мума для задач выпуклого программирования.
4 Б. Н. Пшеничный ^9
Пусть / — выпуклая функция, заданная па прост-
ранстве В и х* — ее точка минимума. Тогда
/ (я)— /(#*) ^> О Для всех я, (2.1)
Очевидно, (2,1) означает, что 0еЗ/(^), и наоборот,
из последнего включения следует (2.1). Итак, справед-
лива
Лемма 2.1. Для того чтобы выпуклая функция f
достигала своего минимума во всем пространстве в точ-
ке х*, необходимо и достаточно выполнение условия:
0еЗ/(^). (2.2)
Несмотря на простоту и очевидность этого резуль-
тата, из него в сочетании с другими теоремами сле-
дуют очень важные выводы.
Теорема 2.1. Пусть f — выпуклая функция и
М — выпуклое множество в В. Пусть существует такая
точка х^М, в которой f непрерывна. Тогда для того,
чтобы точка х* была точкой минимума функции f на
множестве М, необходимо и' достаточно выполнение
условия
df Ы П [con (М - ^)]* 0. (2.3)
Замена н и е. Напомним, что
con (М — х*) = {р е В: р = К (х — х*), X >> 0, х е М}.
Доказательство. Рассмотрим задачу минимиза-
ции функции
/о (ж) = /(я) + §(х\М).
Очевидно, /о(ж) = +°° для х е М и /0(я) = fix') для х &
е М. Поэтому функция /о имеет те же точки миниму-
ма, что и функция / на множестве М, Итак, для того,
чтобы точка х* была точкой минимума / на М, необ-
ходимо и достаточно, чтобы х* была точкой минимума
/о на всем пространстве, или согласно предыдущей тео-
реме, 0 dfQ (х*). Но согласно теореме 1.10 и формуле
(1.16)
dfQ (я*) = df (z*) — [con (М — z*)]*.
Из этих соотношений сразу следует утверждение (2.3)
теоремы.
Следствие. В предположениях теоремы 2.1 для
того, чтобы точка х* доставляла минимум f на мно-
50
жестве М, необходимо и достаточно, чтобы нашелся
такой линейный функционал xQ ^df(x^), что
(х) X* (х*) (2.4)
для всех х s М.
Доказательство. В самом деле, если (2.4)
выполнено, то
/ (я) ~ / (**) >£*(* — **) > о
для всех х М.
Обратно, если х* — точка минимума, то по теоре-
ме 2.1 найдется такой линейный функционал xQ е
е (я*), что х^ е [сон (Л/ — я#)]*. Последнее означает,
что
ж* (р) = х* (К (х — х*)) = Хх* (х — я*) > О
для всех х е М, X > 0, откуда следует (2.4).
Обратимся теперь к общей задаче выпуклого прог-
раммирования. Пусть М — выпуклое множество, а А —
выпуклые собственные функции i = 0, 1, ..., тп. Будем
в дальнейшем предполагать, что все функции fi не-
прерывны в точках множества М.
Рассмотрим задачу
min{/0U): /i(^) 0, г=1, ..., тп, х^М}. (2.5)
Для дальнейшего удобно данную задачу вложить в се-
мейство задач, зависящих от параметра у <= Ет. По-
ложим
7(z/) = inf {/o(rc): №х) i = 1, же M}. (2.6)
X
Теперь исходная задача (2.5) является частным слу-
чаем задачи (2.6) при у = 0.
Лемма 2.2. Функция 7(у) выпукла. Если сущест-
вует такая точка х е М, что
fi(x) <0, i = 1, ..., тп,
и 7(0) — конечное число, то V(y) непрерывна в точке
у = 0 и 37(0) #=0.
Доказательство. Пусть ^>7(у0, / = 1, 2.
Тогда существуют такие точки Xj е М, что
/о (‘Zj) < fb’ /i (^j) £/i>
i = 1, ..m, Х]<= М, / = 1,2.
4*
51
Теперь в силу выпуклости входящих в последние со-
отношения функций
/о (^1^1 4~ ^2^2) ^1/о (^1) 4“ ^2/0 (^2) < 4" ^2^2»
А (^1^1 4“ ^2*^2) 4“ ^2^/i > i = 1, . . . , ТП.
4“ ^2^2 M ^1 4" ^2 == 1Д2 > 0,
откуда следует, что
V&rf 4- W) < Mi + M2-
Итак, мы доказали, что множество {{у, £}: (J > 7(у)}
выпукло, а отсюда следует выпуклость
epi V = {{у, £}: 7(у)}.
Если существует точка х, удовлетворяющая условиям
леммы, то очевидно, что
/<(£) С у<, i = 1, ..., т
для всех у из некоторой окрестности нуля. Поэтому
7(у) /0(х)
и 0 int dom 7. Отсюда (см. § 1) следует, что 7(у)
в окрестности нуля принимает конечные значения и
ограничена сверху. Поэтому по теореме 1.1 она непре-
рывна в точке у = 0, а по теореме 1.9 д7(0) 0. ,
Лемма доказана.
Определение 2.1. Вектор и е Ет называется
вектором Куна — Таккера задачи выпуклого програм-
мирования, если и > 0, и
7(0) =inf{Ux. и): х^М}, (2.7)
X
т
TJ&L (я, и) = /0 (х) + 2 uifi (я)« Функция L называется
i=l
функцией Лагранжа,
Теорема 2.2. Пусть 7(0) — конечное число.
Вектор и является вектором Куна — Таккера тогда и
только тогда, когда —и s 97(0).
Доказательство. По определению —и е 97(0),
тогда и только тогда, когда
7(у) > 7(0) - (и. у),
т. е. когда
inf {7(у) 4- (и, у)} = 7(0).
у
52
Подставляя в эту формулу выражение (2.6) для
F(y), получаем
inf inf {/0(я) + (щ у): /г(я)^7Л, * = 1, ..т, х^М} =
У X
= F(0). (2.8)
Нетрудно заметить, что если щ < 0 для некоторого i,
то минимизацией по уг (устремляя yt к +°о в левой
части (2.8)) получим значение —°°, что противоречит
конечности F(0). Итак, и 0, и левую часть формулы
(2.8) можно переписать в следующем виде, явно вы-
числив нижнюю грань по у:
!т 'j
/о Сг) + 2 uifi (х): х& М ? — inf {L (а?, и): х е М}.
i=l J х
Таким образом, — u^dVW) тогда и только тогда,
когда
inf {Ш, u): x^M} = VW>,
X
т. е. когда и есть вектор Купа — Таккера.
теорема z.o. пусть
такая, что /Дх) <0, i = 1,
число. Тогда существует
Если при этом х* — точка
то выполняются условия:
/о (*^*) = (*^*» L G
Uifi (**) = ’
существует точка х е= м
.. ., тп, и F(0) — конечное
вектор и Куна — Таккера.
минимума в задаче (2.5),
г, u), х^М, и^О, q
), i = 1, ..., m.
Эти условия являются и достаточными для того, что-
бы точка х* была решением задачи (2.5).
Доказательство. Существование вектора и
следует из леммы 2.2 и теоремы 2.2. Поэтому необхо-
димо убедиться только в справедливости последней
части теоремы.
Пусть х* — решение задачи 2.5. Тогда
А(^*)<0, г=1,
/о(^) = 7(О).
Так как и > 0, то
m
F (0) /0 (х%) /о (•£*) Н" uifi (*•£*) ~ L (х%, и).
г=1
Но в силу (2.7) F(0) ^L(x*, и). Поэтому
/о (х$) ~ — F (0) L {х, и), х е М,
53
т
и, кроме того, IE Uifi (х*} — 0. Но так как ш > 0,
i=i
A(z*)<0, то последнее возможно, лишь если
Uifi (#*) = 0, г = 1, ..., тп.
Докажем достаточность условий (2.9). Пусть х*
удовлетворяет ограничениям задачи и соотношениям
(2.9). Пусть х — любая точка, также удовлетворяю-
щая ограничениям задачи (2.5). Тогда в силу усло-
вий (2.9)
т
/о (*£*) ~ /о (*£*) 4“ 2 u^fi (z*) L (х, и) =
1=1
т
= /о (*) + 2 Uifi (я) < /о
i=l
т. е. в точке я* достигается минимум /0 при сделан-
ных ограничениях.
Теорема доказана.
Теорема 2.4. В условиях теоремы 2.3 для того,
чтобы точка х* была решением задачи (2.5), необхо-
димо и достаточно, чтобы существовал вектор Куна —
Таккера и и выполнялись соотношения
дхЬ (х*, и) П [con (М — я*)]* =/= 0, и > 0, (2.11)
Uifi (**) = 0, * = 1, • •гп.
Доказательство очевидно. Первое из условий
(2.9) означает, что функция 1Лх, и) достигает миниму-
ма по х на М в точке х*. Теперь остается только при-
менить теорему 2.1.
Попробуем вычислить функцию, сопряженную с
V(i/). По определению,
V* (u) = sup {(и, у) — V (у)}
У
= sup {(и, у) — inf {/0 (х): л (х) <
у »
I = 1, ..., пг, х^ М}} =з
{тп
— /о (*) + S ШУг fi (х) <
г=1
i=l,...,/n, х(=м\.
54
Легко вычислить верхнюю грань по у*
у* = , sup /о (*) + .2 Uifi (z): х t= М, и < о},
+ ос, если Ui>0 для некоторого i,
или •>’ •
f— inf {L (яг, — и): х е М, и 0},
7* (u) = 1 х (2.12)
Н~ оо, если щ^>0 для некоторого Z. v ’ 7
Теорема 2.5. Если функция 7(у) полунепре-
рывна снизу при у = 0, в частности, если выполнены
условия теоремы 2.3, то
V (0) = sup inf {L (х, и): хе М}.
и>о х
Любой вектор Куна — Таккера и* является решением
задачи
max {(р(и): и 0),
и
где ф(и) = inf {1Ах, и): х е М}.
X
Доказательство. Из теоремы 1.3 вытекает,
что
7(0) = 7**(0) = sup {(и, 0) - 7*(и)} -
U «.
= sup {inf L(x, —и)\ х е М},
и<С0 х
где была использована формула (2.12). Заменяя те-
перь —и на и, получаем первое утверждение теоремы.
Пусть теперь и 0 — произвольный вектор. Имеем
{m 'j
/о (х) + 2 uifi (г): хе Л/ <
i=l )
inf {/0 (х): fi (х) 0, i = 1, ..., т, х е М} = V (0).
X
Итак, для любого и > (0) ф(и) 7(0).
Если же и* — вектор Куна — Таккера, то
ф(и) 7(0) = ср(и*), и > 0,
что завершает доказательство.
Теорема 2.5 называется теоремой двойственности,
а задача максимизации <р(и) при и > 0 — двойственной
задачей. Теорема двойственности играет важную роль
во многих приложениях теории выпуклого програм-
мирования.
55
В заключение этого параграфа приведем еще одну
полезную теорему.
Теорема 2.6. Пусть множество М задается не-
равенством
М = {х\ fix) 0}, *
где f — выпуклая функция, непрерывная в точке х0,
f(x0) 0, и для некоторого х fix) < 0. Тогда
[сон (М — гг0)]* =
= \х*-.х* = —е =
(2.13)
Доказательство. Если /(х0) < 0, то в силу не-
прерывности / в точке Xq
/(х0 + Хр) < 0
при малых X для любого р. т. е. х0 + Хр е М при ма-
лом X > 0 для любого р. Поэтому con iM — xQ) совпада-
ет со всем пространством, а его сопряженный состоит
из единственной точки {0}. Тот же результат дает и
формула (2.13). Пусть теперь /(х0) = 0. В этом случае
con iM — х0) =
= {р: /(х0 + X/?) < 0 = /(х0) для некоторого X > 0L
Отсюда следует, что если р е con (Л/ — х0). то
0 > / (я0 + М ~ (р)
для любого Xq е df (х0). Поэтому — ух* (/?) 0 при
Y>0 для всех р е con (71/ — х0). Но это значит, что
— ух* е [con (М — х0) 1* •
Докажем обратное включение, т. е., что для любо-
го х* е [con (Л/ — х0)]* найдется такое число у > 0 и
такой х* е 5/(х0), что х* = — ух0.
Допустим противное. Тогда найдется такой функ-
ционал х* [con iM — х0)]*, что ах* ё 5/(х0) при лю-
бом а<0. Более того, ах* е dfix0) и при а = 0, ибо
0 > /(х) — /(х0) х*(х — х0)
для х* е д/(х0), откуда следует, что 0 е df{xQ).
Рассмотрим множество
{ах* — д/(х0): а 0}.
Оно выпукло, слабо* замкнуто (ибо для непрерывной
56
функции 5/(^0) слабо* бикомпактно) и не содержит,
согласно предыдущему, нулевого функционала. Поэто-
му найдется (см. теорему 5) такой элемент р^ В, что
ах* (р) — х* (p)Z^ & > О (2.14)
для всех а >0, х* е df (xQ). Но тогда по теореме 1.9
/' (^о, Р) = фтах (Р) < — е-
х*еа/(х0)
Поэтому в направлении р f(x) строго убывает, и при
малых X > 0 f(xQ + Хр) < 0, т. е. р con (М — х0). Бо-
лее того, легко видеть, что р на самом деле принадле-
жит внутренности con (Л/ — х0) и поэтому по лемме 4
Введения £*(/>)> 0. Но это противоречит неравенству
(2.14), которое должно выполняться при всех а 0.
Полученное противоречие показывает, что любой эле-
мент х* <= Icon (Л/ — х0)J*, /(я0) = 0, представим в виде
я* = — ух*, Y>0, XQ<=df(xQ),
что и требовалось доказать.
§ 3. КВАЗИДИФФЕРЕНЦИРУЕМЫЕ ФУНКЦИИ
Для вывода необходимых условий экстремума в
общем случае глобальная выпуклость функции не нуж-
на. Достаточно, чтобы локально поведение функции
было подобно поведению выпуклой функции.
Введем следующее определение.
Определение 3.1. Функция / называется квази-
дифференцируемой в точке х, если существует конеч-
ная производная по любому направлению
f(x, р) = lim +
Ио Л
и такое выпуклое слабо* замкнутое множество dj(x\
что
ftx, р) = sup {#*(/?): х* е д/Ы).
х*
Множество dftx) мы так же, как выпуклом случае,
будем называть субдифференциалом.
Из приведенной для производной по направлению
формулы видно, что квазидифференцируемая функция
имеет производную по любому направлению и эта
57
производная есть положительно однородная выпуклая
замкнутая функция направления. Нетрудно видеть, что
это свойство полностью характеризует квазидифферен-
цируемую функцию.
В самом деле, есть f'Gr, р), определенная для всех
р, положительно однородна, выпукла и замкнута по /?,
то согласно теоремам 1.5, 1.6
df(x) = dom (/'(#, •))*.
Обсудим, насколько широк класс квазидифференцп-
руемых функций. Во-первых, ясно, что в него входят
все дифференцируемые по Гато функции, ибо в этом
случае в качестве df(x) может быть выбрано множест-
во, состоящее из единственного функционала т0, являю-
щегося производной Гато от /(х) в точке х. Во-вторых,
результаты § 1 показывают, что квазидифференцируе-
мыми являются все выпуклые функции.
Далее, сумма с положительными коэффициентами
п операция взятия максимума от конечного числа
функций не выводят нас из класса квазидифференци-
руемых функций.
Теорема 3.1. Пусть BQ и В{ — пространства Ба-
наха, — квазидифференцируемая функция на BY,
удовлетворяющая условию Липшица, а А (х): В^-^ Bi-
дифференцируемый по Гато оператор. Тогда
fttx) = f(A(x))
есть квазидифференцируемая функция на Во, причем
где Ао— производная Гато от А(х) в точке х0.
Доказательство.
/о (*о + - /о (*о) / (Л (*о + ^)) - f (А (*о)) __
X л
[/ Р (Ы + Ч* + r (М) - f (л (г0) + м»]
_------------------------------------ +
+-------------х----------’
lim-Ц^- = 0.
При X->+0 правая часть этого равенства стремится
58
к веЛичийё
/' (Л (х0), Л^) = max у* (Хе).
V*S0/(A(xo))
Отсюда следует теорема.
Покажем теперь, что в широком классе случаев
операция взятия максимума по параметру не выводит
из класса квазидифференцируемых функций. Мы нач-
нем с доказательства нескольких вспомогательных ут-
верждений.
Пусть ф(х, а) — непрерывная функция параметров
х и а, где х принадлежит нормированному простран-
ству В, а а - элемент компактного топологического
пространства Z. Образуем функцию
/(я) = шах ф(я, а)
«GZ
и обозначим Z(#) = {а: а е Z, ф(гг, а) = /(я)}.
Лемма 3.1. /(я) — непрерывная функция.
Доказательство. Имеем
а) = /(я) > ф(х, а0),
ф(гг0, а) < /(я?0) = ф(я0, а0),
a^Z(^), а0 Z(x0).
Вычитая эти неравенства, получаем
ф(х, а) — ф(х0, а) >
> /(я) — /(т0) > фСг, а0) — ф(^о, ао). (3.1)
При х -> х0 правая часть стремится к нулю. В силу
компактности Z и непрерывности ф(т, а) по аргумен-
там левая часть также стремится к нулю.
Действительно, допустим, что разность ф(гг, а) —
— ф(я0, а), а е ZU), не стремится к нулю, когда х -*
х0. Это значит, что найдется такая последователь-
ность Xi Xq, а< е Z(^), что
аг) — ф(я0, аг)1 > 6 > 0.
Поскольку Z компактно, то из последовательности at
можно выбрать сходящуюся. Не ограничивая общности,
будем считать, что сама исходная последовательность
Оа сходится к а0 Z.
Переходя в последнем неравенстве к пределу, по-
лучаем в силу непрерывности ф(я, а) 0 > 6 > 0. По-
лученное противоречие показывает, что левая часть
59
(3.1) стремится к нулю, что завершает доказательство
леммы.
Лем м а 3.2. Для любой окрестности а Z мно^
жества Z(x0) существует такое 6, что Ztx) <= со, как
только || я — а?0|| 6.
Доказательство поведем от противного. Пусть
для некоторой окрестности о)о существует такая после-
довательность Xi .го, а в множествах Z(xt) такие
точки а«, что <Xi ё= со0. Так как Z — компактно, то мож-
но считать, что а< -> а0.
По определению j(xt) = <p(^rf, а<). Переходя к пре-
делу, получаем, что /(х0) = ф(гг0, а0), т. е. а0 е Z(xQ).
Но это невозможно, ибо а<а0 и а» е со0, и если мы
допустим, что а0 Z(#o) с то в силу открытости
множества о)о а, е (о0 для достаточно больших г, что
приводит к противоречию.
Исследуем теперь дифференциальные свойства функ-
ции /(я). Пусть хШ = Хо + Хе. Подставляя в (3.1) и
деля это неравенство па X > О, получим
<р (^ (%), а) — Ф(*о, а) / (^ (А)) — /(я0)
X X
<р(х(Х), а0)-(р(г0, а0)
к
a<=Z(x(K)). (3.2)
Из левой части неравенства получаем, что если <р(я:, а)
дифференцируема по направлению е, то
lim /^(М)-/(х0)
ь-»+о
> <р' (х0, е, а0)
или, так как а0 — произвольный элемент Z(x0),
lim f(x0)
к-»+о ’*
sup <p' (x0, e, a).
aez(x0)
(3-3)
Допустим теперь, что ф(я, а) дифференцируема по
направлению е в точке х0, т. е. для X > О
ф(яо + Хе, a)=<p(#0, а)+Х<р'(х0, в, а)+Х^(Х, а)
и при этом ^(Х, а)О при X->+0 равномерно
по а. Тогда производная q/(£0, е, а) непрерывна
по а, как равномерный предел непрерывных функций
Ф(*0+Хе, a)-<p(x0, а)
inf ' sup ф' (xQ, е} а) = sup ф' (гг0, е, а).
wZ)Z(x0) aSco a=Z(xQ)
60
Ё силу леммы 3.2 получаем из (3.2)
-------т-------< sup [ф (х0, е, а) + у (X, а)]
Л--------------ае«
при любом ® Z(z0) и достаточно малых X. Переход
к пределу по X -* +0 дает
/(х(Л))-/(т0)
lim--------г----— sup ф (х0, е, а).
Х^-4-о otGco
Учитывая, что со — произвольная окрестность, содер-
жащая ZU0), окончательно получаем
lim -------г------< mf sup ср' (х0, е, а) =
1-> + 0 coDZ(xo) аесо
= sup ф' (я0, е, а). (3.4)
aeZ(x0)
Сопоставление (3.3) и (3.4) приводит нас к следующей
теореме.
Теорема 3.2. Пусть ф(я, а) — непрерывная функ-
ция аргументов х и а, где х В, a a^Z (Z — ком-
пактное топологическое пространство). Кроме того,
пусть
ф(х0 + Хе, а) =
= ф(аг0, ос) + Хф'(яо, е, а) + }щ(х, а) для X > 0,
причем у (Л, а) -> 0 равномерно по а при X -* +0.
Тогда в точке х0 функция f (х) = max ф (х, а) диф-
aez
ференцируема по направлению е и
f(x0, е) = sup {ф'(^0, е, a): a^Z(x0)}. (3.5)
Замечание 1. Нетрудно видеть, что условие не-
прерывности по х и а может быть без всякого ущер-
ба заменено на условие непрерывности функции
ф(#о4- Хе, a) по X п а.
Теорема 3.3. Если ф(^0 + Хе, а) — непрерывная,
по X и а функция, причем существует непрерывная для
дер (я + Хе, а)
X е= Ю, 11 и а е Z производная ------, то имеет
место формула
f (я*о, е) = тах ф' (^о» еу а)- (3-6)
aez(x0)
61
Доказательство аналогично доказательству преды-
дущей теоремы, за тем исключением, что при выводе
неравенства (3.4) необходимо воспользоваться форму-
лой Лагранжа
ф (х0 + Хе, а) — ф (а:0, а) . дф (л?0 + g (X) е, а)
X “ дХ *
где 0 £(Х) X, и заметить, что
<9ф (х + Хе, а) I
------й.------|х=0 = Ф е, а).
Теорема 3.4. Если <р(гг, а) — квазидифференци-
руемые в точке х0 функции, для которых выполнены
условия теоремы 3.2 при любом е, то f(x) — также
квазидифференцируемая в х0 функция, причем
df М = со U дф (.г0, а), (3.7)
a=Z(x0)
где дф(гг0, а) — субдифференциал функции ф(я, а),
dj(xo') — функции f(x), а со Л означает слабое* замы-
кание выпуклой оболочки множества А.
Доказательство. На основании теоремы 3.2 и
определения квазидифферепцируемого функционала
получаем
/' (xQ, е) = sup ф' (z0, е, a) = sup sup х* (е).
aSZ(x0) aSZ(xQ) х*едф(х0,а)
(3.8)
Но, как легко видеть, максимум в правой части равен
максимуму величины х*(е), когда х* меняется в опре-
деленном формулой (3.7) множестве df(x0). В самом
деле, 3/(х0) есть слабое* замыкание множества точек
вида
х* = 2 ,
где х* е Зф (xq, a^), 2 М = 1» М 0. Поэтому
я* (*) — 2 (г) шах х* (е) sup sup х*(е),
i aGZ(x0) х*^дф(х0,а)
и значит, в силу того, что верхние грани непрерывной
функции х*{е) аргумента х* по некоторому множеству
и по его замыканию совпадают,
sup х* {е) sup sup х* (е).
к*еб/(х0) aeZ(x0) х*едф(х0,а)
62
Но, с другой стороны, dfixo) => дср(х0, а) для любого
а е Z(x0), и поэтому
sup я* (е) sup sup х* (е).
oc*Gd/(x0} aGZ(x0) x*edq?(x0,a'j
Итак, указанные максимумы совпадают, и мы можем
написать
f'(x0, е) = sup {х*(е)\ х* 3/(z0)}.
Для завершения доказательства теоремы осталось
заметить, что df(xQ) выпукло и слабо* замкнуто по са-
мому определению.
Уточним теперь теорему 3.2 для случая, когда
ф(<г, а) выпукла по х при каждом а.
Теорема 3.5. Пусть Z —компакт, (fix, a) — вы-
пуклая функция при каждом a^Z. Кроме того, пусть
ц>(х + \р, а) непрерывна по К и а для Х^[—б, 6], б>
>0, a^Z. Тогда функция ftx) = max{ф(гг, a): a^Z}
а
дифференцируема по направлению р, и
f(xQ, /?) = max {q/tao, Р, a): a^Z(x0)},
а
где ф'(х0, р, а) есть производная ф(гг, а) по направ-
лению р в точке х0.
Доказательство. Положим для упрощения
выкладок
g(X) = ](х0 + Хр), g(X, a) = ф(я0 + Хр, а),
Z(X) = Z(x0 + Хр).
Ясно, что
/Ъо, р) = g'(0), ф'(я0, р, а) = g'(0, а),
где gf (0) = lim h и аналогично определяется
Ыо Л
g'(0, а). Так как функция
g(X) = max {g(X, a): a е Z}
a
конечна при [—S, б], ибо g(X, а) непрерывна по а,
и Z — компакт, то производная g'(0) существует и
ограничена.
Положив в (3.1) х = х0 + X/?, получим
Я(Х, a)-g(0, a) g(X)-g(O) %)
aeZPQ, aueZ(0). <3-9>
63
Так как разностное отношение для выпуклой функции
стремится к нулю, монотонно убывая, то из правой
части (3.9) получаем, что
> g' (°, «о). ао s Z (0),
Л
и поэтому
g'(0) > sup {g'(0, а): a<=Z(0)}.
а
Обратимся теперь к левой части (3.9). По лемме 3.2
для любого открытого множества С э Z(x0) = Z(0) най-
дется такое е > 0, что Z(X) С при 0 X < 8. Поэтому
для X < 8 (3.9) дает
У(0)< < sup (Ш* a-)-ma)
(3.10)
Возьмем нижнюю грань от правой части (3.10) по
всем C^Z(O). Так как g(X, а) непрерывно по а п
Z(0) — замкнутое подмножество компактного множест-
ва, то нетрудно убедиться, что
• с ( g U» а) — g (0, а) z/|
inf sup i ~ : а е 6] =
C^Z(O) а I J
= т*ах {• g(X. a)-g(0, а) . а s z (0)),
Поэтому
g' (0) < max {g(X| №)-g-(0, к) : a e= Z (0)J. (3.11)
Пусть -> 0 и ah e Z(0) такое, что
g (h’ «ft) - g (°- “ft) _ ( g (**> a) - g (0> a) . 1
--------a-----------llldA<--------г------- . CZtzZ/ (UH.
a ( j
(3-12)
Без потери общности можно считать, что -> a0 е Z(0).
Далее, по лемме 1.1
g (°' ak) -g(-b Kft) ? (Ч ’ ak) ~ g (°' «ft)
6
g (5, aft) - g (0, aft)
6
так что отношение (g (X^, a&) — g (0, a^)] в силу не-
64
прерывности g(X, а) и компактности Z ограничено.
Можно считать, что оно стремится к некоторой вели-
чине ц.
Пусть Л > 0 фиксировано. Тогда при больших к
< Л и по лемме 1.1
g(X, aft)-g(0, g(Xv aft)-g(0, ak)
4
Переход к пределу по к -> о© дает
‘ *(^aoW(o’ao)
и при X 0 получаем g'(0, a0) > Ц.
Используя теперь (3.11), (3.12), получим, что
g'(0) |i g'(0, a0), a0 s Z(0).
Совмещая это неравенство с ранее доказанным, по-
лучим, что
g'(0, a0) > g'(0) > sup {g'(0, a): a e Z(0)},
a
t. e.
g'(0) = max {g'(0, a): a g Z(0)}.
a
Последнее соотношение эквивалентно утверждению
теоремы.
Теорема 3.6. Пусть Z — компакт, ф(я, а) вы-
пукла по х при Z, и ф(я, а) непрерывна по х и а
для х из некоторой окрестности xQ и сс^ А. Тогда
df (*0) = со f U дф (я0, а)\.
\asZ(x0) )
Доказательство полностью повторяет доказа-
тельство теоремы 3.4.
§ 4. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
В ОБЩИХ ЗАДАЧАХ МАТЕМАТИЧЕСКОГО
ПРОГРАММИРОВАНИЯ
В этом параграфе мы выведем необходимые усло-
вия экстремума, обобщающие обычное правило множи-
телей Лагранжа на широкий класс задач.
Пусть L — линейное пространство, <р^, I » — т, .
..., О, .. .г А,— заданные на L функции, и М — неко-
торое подмножество L.
5 Б, Н. Пшеничный 65
Рассмотрим задачу.*
min q)o(^),
фг(гг) 0, i < О,
( у п (4.1)
ср*(а?) = 0, i> О,
х е= М.
Поскольку в такой постановке задача имеет весьма об-»
щий вид, для получения эффективных условий экстре-»
мума необходимо сделать некоторые предположения.
Пусть х0 — решение задачи.
1. Существует выпуклый конус Км такой, что если
е е Км, то
k
х (X) = xQ + Ke + 2 гг (X) (4.2)
i=l
принадлежит множеству M для любых векторов ех е L
и любых функций г<(Х), удовлетворяющих условию
lim ri (X) X"1 = 0.
4 2ь-»+о
2. Для i 0
ф.1111)1Л,(е), (4.3)
где х(Х) определено с помощью (4.2), a hM —выпук-
лые по е функции и dom hi = L,
3. Для i > 0
(4.4)
X->+0 4
где hM — линейные функции.
Теорема 4.1. Если xQ — решение задачи (4.1) и
выполнены условия 1—3, то найдутся такие числа Х<,
не все равные нулю, что
h
2 X^i(e)^O для всех е^Км, (4.5)
. i=—m
Кг > 0 для Z 0 и K^Xq) — 0 для i < 0.
Прежде чем приступить к доказательству, устано-
вим следующую лемму.
Лемма 4.1.. Пусть функции hi, i = 1, ..., к, ли*
нейно независимы. Тогда для того, чтобы xQ было ре*
66
шением задачи (4.1), необходимо, чтобы выпуклая
оболочка множества
К = {*: & = hi (е), е е= Км, i<=I (ж,)}
и множество
Р = {£: 5г < о, f^O, 5< = о, i>0)
не пересекались. Множество Kxq) определяется фор-
мулой
/(#о) = {*: Ti(^) = 0, i<0 или j^O},
а 1Ж)1 есть число элементов в I(xQ).
Доказательство леммы. Допустим, что лем-
ма неверна. Тогда существует такой вектор 5°е со
что
51 <0, 1^Цх^, /<0;
5? = 0, i>0.
Так как 5° е со К, то найдутся такие V е R, что
7
причем Xj > 0 и “ 1- Далее, так как V <= то для
некоторых ej е Км V = Л(е’), где Л(е) — вектор с ком-
понентами М(е),
Пусть е° = 2^’^* Так как Км — выпуклый конус,
7
то е° е Км. В силу сделанных предположений
3
= SMi=U°<0, i<0, i<=I(x0),
3
= = = = 0, «>0.
3 3
Рассмотрим теперь систему уравнений
/ h \
Ipi (%, ги г2, .,. , г*) = Ф,- х0 + Хе° + 2 rjai - (4.6)
\ 7=1 /
где а} L выбраны так, что M(aj) — 6ц. Такой выбор
векторов а* всегда возможен, поскольку М линейно не-
зависимы.
5*
67
Легко видеть, что
^- = ^(eo) = O, ^- = ^(^) = 6у,
где производные взяты в точке Х = 0, г, = 0, / = 1, ...
,.к. Из теоремы о неявных функциях, доказанной в
конце этого параграфа, следует, что система (4.6) име-
ет решение г/А), причем
lim r\ (X) X*"1 = 0.
ь->Н-о
А
Рассмотрим точки х (1) = х0 + keQ + 2 гз W
3=1
Во-первых, я(%) е М при достаточно малых X. Это
следует из того, что е° е Км, и из условия 1 основных
предположений.
Во-вторых,
(₽iU(A)) + АЛ(е°) + 0(Х) 2Д(е°) + 0(Х) < 0,
для всех достаточно малых X, если i<0, i^/(^0), так
как Л<(е°)<0. Если же i<0 и i&Itxo), то д)Дх(А))
меньше нуля при малых X, так как ф/хо) < 0.
В-третьих, для i =« 0
Фо(я(Л)) фо(^о) + ЛА0(е°) + 0(A) < фо(^о),
ибо hQ(e°) < 0.
Наконец, по построению г<(Х)
ф/я(Х))=0
для i = 1, ..к.
Таким образом, при малых V точка х(к) удовлетво-
ряет всем ограничениям и значение функции ф0(я:)
в ней также меньше, чем ф0(х0). Это противоречит
предположению о том, что х0 — решение задачи (4,1),
. Лемма доказана.
Обратимся к доказательству теоремы.
Если hif i = 1, ..., к, линейно зависимы, то до-
статочно положить все Л; = 0, i 0, а в качестве
i > 0, взять те коэффициенты, для которых
h
5 Ми = о.
i=l
Если же hh t = 1, ..., к, линейно независимы, то на
68
основании леммы множества со R и Р не пересекаются.
Поскольку это выпуклые множества в конечномерном
пространстве, то их можно разделить. Это значит, что
найдется такой вектор Л с компонентами Х{, i €= I(xQ\
что
2 2 Ш
ie/(x0) is;(xo)
(4.7)
для всех | е R, £ Р. Так как все | R представимы в
виде £ = Л(е), е е Км, то мы получаем У (е) О
iei(x0)
для всех е е Км. Правая часть неравенства (4.7), как
легко видеть, позволяет заключить, что >0 для i е
e/(rr0), i^O. Но при i^I(x0\ i < 0, ^i(xQ) = 0. Поэто-
му Хгф/^о) = 0,2 < 0, i е I(xQ).
Если теперь положить X, = 0 для i е Z(x0), то мы
получаем все утверждения теоремы.
Следствие. Если ограничения типа равенства
отсутствуют или фг(гг) для i > 0 линейны, то в основ-
ных предположениях 1—3 можно положить
х(Х). = х0 + Хе, = 0, i > 0.
Действительно, в этом случае фл-Л,- и система (4.6)
приобретает вид
/ h \
нг0 + ^е° + 2 riaj ==
\ J=i /
k
= Vi (*о) + Мц (е°) + 2 rjhj (с^) = 0.
г=0
Но поскольку ф/яо) = 0 по предположению, а Л<(е°) в
= 0 по построению вектора е°, то для удовлетворения
полученной системы уравнений достаточно положить
Tj == Q, / = 1, .. ., к.
Конкретизируем теперь теорему 4.1 для случая ба-
нахова пространства В и квазидифференцируемых
функций ф<(я), £ С 0. По определению квазидифферен-
цируемой функции
Т. GW)-К- + -
Ио Л
= sup {я* (г): х* s дфг (z0)}.
Если предположить, что фг- удовлетворяет условию
09
Липшица, то легко видеть, что в формуле (4.3) в ка-
честве hM можно взять <Pi(x0,e).
Пусть для i > 0 ср,(х) также удовлетворяют усло-
вию Липшица, и
(*0, е) = 4 (е), с>ф{(х0) = {яч1, х*^В*.
Тогда выполнены все условия теоремы 4.1 и, зна-
чит, для точки Хь, являющейся решением задачи 4.1,
найдутся такие числа X,, что
° z /г
2 М«Рг(х0, е) + 2 Мяч (е)>0, ее Км: (4.8)
i=—т i=l
Лемма 4.2. Если существует точка е^ Км такая,
что в ней все функции <Pi (^0, в), i^O, непрерывны,
то для выполнения условия (4.8) необходимо и доста-
точно, чтобы нашлись такие функционалы Х[ е 5ф<(х0),
что
h
2 М4 е Км. (4.9)
г=—m
Доказательство. Неравенство (4.8) означает,
что выпуклая функция, стоящая в левой части нера-
венства (4.8), достигает своего минимума по аргументу
е на выпуклом множестве {0} U Км в точке е = 0. Точка
0 не принадлежит Км, но ее всегда можно присоеди-
нить к этому множеству без ущерба для выполнения
неравенства (4.8). В силу теоремы 2.1, предположения
которой выполнены, среди элементов субдифференциала
указанной функции
ф (е) ss 2 (я:0, е) + 2 М4 (М
i=—m i=l
должен найтись хотя бы один, принадлежащий
[сои (Км - 0)]* = Км.
Но по теореме 1.10 справедлива формула
5ф(0)= 2 Меф1 (я^о. 0)+ 2 Мяч. (4.10)
i=—m г=1
Так как ф< (х0, е) = sup {х* (ё): х* <= <9ф, (х9)}, то по
ж*
70
теореме 1.12
де <Pi {х0, е) =»
= U* g= 5<pi (ж0): x* (0) = <p,' (x0,0)} = dcpi (x0),
ибо <Pi(x0, 0) = 0, #*(0)=*0 для любого линейного
функционала х* е В*. Итак,
о k
5<р(0)= 2 M<Pi (^о) + 2 • 011)
i=—m i=l
Теперь из доказанного выше условия <Эф (0) Q Км =£ 0
сразу следует лемма.
Теорема 4.2. Пусть ф<, / = —тп, ..., 0, ..., /с,—
квазидифференцируемые функции, заданные на прост-
ранстве Банаха и удовлетворяющие условию Липшица.
Пусть, кроме того, дф/^о) для i > 0 состоят из единст-
венной точки Xi е В*. Тогда для того, чтобы точка xQ
была решением задачи 4.1, необходимо, чтобы нашлись
такие не все равные нулю числа Х<, что выполнено со-
отношение (4.8) и Ъ > 0, i 0, Хгфг(гго) = 0, i < 0. Если
же^и (х0, е), i 0, непрерывны по е в точке e — G, то,
кроме этого, найдутся такие функционалы Xi е 5ф;(я:0),
i = — ш, ..к, что
2 KiX* е= К*м.
i=—m
Доказательство теоремы непосредственно сле-
дует из предыдущих рассуждений.
Теорем а. 4.3 (Куна — Таккера). Пусть ф»Сг) вы-
пуклые функции в В, dom ф< = В, для i > 0 ф<(я) ли-
нейны. Пусть также множество В — выпукло. Тогда
для того чтобы точка хо была решением задачи мини-
мизации (4.1), необходимо существование таких Х<, Xi >
0 для i 0, что
h k
2 2 ^гфг (^о) &ЛЯ всех Х^М. (4.12)
i=—m i=—m
Кроме того,
Ki^i(xQ') = 0 для i^O. (4.13)
Если Хо > 0, то условия теоремы являются достаточ-
ными.
71
Доказательство. Определим конус Км?
Км я {е: е = Их — xQ) для х е М, x^xQl X > 0}.
Легко видеть, что если е е Км, то я(Х) = х0 + Ke е М,
при малых X. Далее,
1ш T,fa + 4-^.(S)=T;fae)<
х-*+о л
< Ф1 (*о + е) —Фг(^о) = hi (е);
Для i > 0 неравенство превращается очевидным об-
разом в равенство. При i 0 оно следует из того, что
выражение
Ф1 (*о + Хе) ~ Ф*(*о)
X
монотонно убывает, с уменьшением X (см. лемму 1.1).
Если учесть следствие теоремы 4.1, то видно, что все
условия теоремы 4.1 выполнены. Поэтому найдутся
такие X;, 0 для i 0, что
k k
2 Mi (е) = 5 м [ф! (*о + е) — <Pi (хо)] > 0
г=—т i=*—m
для всех е Км. Взяв здесь е = х ~ х0, х <= М, получим
k k
2 M>i(*)> 2 Mi(^o)
l=—m i=—m
для всех x e M.
Пусть теперь (4.12), (4.13) выполнены и Хо > 0.
Тогда х0 — решение задачи 4.1. В самом деле, для лю-
бой точки х, удовлетворяющей всем ограничениям, мы
имеем в силу (4.12) и (4.13)
h k
^'оФо(Д'о) = 2 Мфг (*0) Мфг (^) ^ ^оФо (Д:)»
1=—т 1=—т
ибо фг(я) 0 для i < 0 и ф/я) = 0 при i > 0. Итак,
фо(£о) < фо(я),
откуда следует, что х0 — решение задачи (4.1).
Опишем теперь некоторый общий подход к решению
экстремальных задач, развитый в работах А. А. Милю-
тица и А. Я. Дубовицкого. Пусть задана некоторая
функция /(х) на В и необходимо найти ее минимум
72
при ограничениях х & Qf, i = 1, .;тп, где Q» — неко-
торые множества. Пусть <г0 — искомая точка миниму-
ма. Введем дополнительное множество
Qo = {х'. f(x) < /(z0)}.
Допустим теперь, что множества для i < т таковы,
что существуют открытые выпуклые конусы Кг, обла-
дающие следующим свойством: если е е Км, то при
малых X > О
х* + Хе + r&) е= (4.14)
для любой функции г: [0, 1] -> В такой, .что
Ит-ф- = 0. (4.15)
Мо Л
Далее, для Qm существует выпуклый конус касатель-
ных направлений Км. Это означает, что для любого
е^Км существует такая функция г(Х), что соотно-
шения (4.14) и (4.15) для 1= тп выполнены.
Совершенно очевидно, что конусы Z<0, Kh ..., Km
не пересекаются. Действительно, если в е Q Ki, то по
1=0
определ' ;тчо Кт существует такая функция г(Х), что
(4.15) выполняется и xQ + Хе + r(X) Q™. По опреде-
лению Ki, i = Q, 1, ..., т — 1, соотношение (4.14) так-
же выполняется. Если воспользоваться им для i = О,
то получаем, что
/Сг0 + Хе + ?’(Х)) < /Сг0),
что противоречит тому, что xQ — точка минимума.
Теорема 4.4. Пусть Ко, К{, .. ., Кт выпуклые ко-
нусы, причем конусы К{ для i < т открыты. Для того
чтобы они не пересекались, необходимо и достаточно,
чтобы нашлись такие функционалы x^^Ki, i =
= 1, ..m, не все равные нулю, что
^* + ^*+•••+^*1 = 0. (4.16)
Доказательство. Необходимость. Рас-
смотрим в пространстве Вт = ВХВХ...Х5- прямом
m
произведении m пространств В выпуклый конус
К = Кй X X ... X Km_t.
73
Элементами его являются наборы {я0, . Zm-J такие,
что Xi Kh i = 0, 1, ..., т — 1. Образуем также вы-
пуклый конус
Р = {{^Гпг, Хт, • • «, В • Хт Кт}.
Так как пересечение конусов Кь i = 0, ..., т, пусто,
то легко видеть, что К П Р~ Кроме того, ^" — от-
крытый конус, так открыты все К{ для i = 0, ..т — 1.
Поэтому К и Р можно разделить ненулевым линей-
ным функционалом из (В?п)*, т. е. функционалом вида
। * * * 1
Uo,^, ...
Я* (*о) + • • • + ^п-1 (^т-1) > (^н) + • • • + 4i-l (^m),
(4.17)
Xi е i = 0, 1, ... , т.
Положим к
— хт = 4" • • • + #m-l« (4-18)
Теперь (4.17) можно переписать в виде
хо (хо) + • • • + хт Ы >0, Xi е Ki, i = 0, , т.
(4.19)
Из (4.19) следует, что величина х* (xi) б^ лничепа
снизу, когда х, меняется в Ki. Отсюда (этот факт не-
однократно отмечался ранее) вытекает, что Xi (^)^О,
x^Ki, т. е. Xi^ Ki. Таким образом, нашлись такие
функционалы Xi^Ki, сумма которых в силу (4.18)
равна нулю.
Достаточность. Допустим, что (4.16) выпол-
нено; но найдется такая точка е0, что е0 е К{, i =
= 0, ..., т. Тогда из е Ki следует, что Xi (е0) не-
отрицательны. Кроме того, так как Кг, i < ?п, открыты
и Xi не все равны нулю, то по лемме 4 Введения хотя
бы одна из величин х^ (е0) строго положительна. По-
этому
(4 + • • • + *т) (е0) = х* (ео) + • • + (ев) > 0
в противоречии с (4.16).
Доказательство завершено.
Полученные результаты позволяют сформулировать
следующую теорему.
74
Теорема 4.5. Пусть точка х0 —решение задачи
min {/(ж): х е Qt, i = 1, ..ш).
X
Пусть = /(я) <и множества Q., i=*
==0, 1, ...» m, допускают в точке х0 построение кону-
сов с описанными выше свойствами. Тогда найдутся
такие не все равные нулю функционалы х^^ что
^ + ^ + ...+4 = 0.
Приведенная теорема дает возможность с единой
точки зрения подойти к решению многих экстремаль-
ных задач.
В заключение этого параграфа приведем доказа-
тельство теоремы о разрешимости системы нелиней-
ных уравнений, на которую делались ссылки *).
Теорема 4.6. Пусть х k-мерный вектор, а непре-
рывные функции ф{(Х, х) удовлетворяют следующим
условиям:*
а) *фг(О, 0) = 0, i = 1, ..к;
б) г|?г(Х, х) дифференцируемы в точке X = 0, х = 0,
т, е.
(0, 0) & <Эф. (0, 0)
ipi (X, х) — i])j (0, 0) — X —-щ— Xj <
/ h \ 1/2
где || х || = I У х] ] , г (z) z-1 -> 0 при z 0;
\j=i /
в) ---£7---= 0, г = 1, . . . , к;
' оЛ
f ]
г) матрица & = 1, • • •> Л, 7 = 1» • • •>
не вырождена.
Тогда система уравнений
ф<(Х, я) = 0, 1 = 1,..., к,
разрешима при достаточно малых X и существует ре-
*) Если предположить, что фДХ, х) непрерывно дифферен-
цируемы в некоторой окрестности точки % = 0, х = 0, то тео-
рема 4.6 совпадает с обычной теоремой о неявных функци-
ях [9].
75
шение х(Х), обладающее свойством
lim II* WII = о.
х-ю А.
• Доказательство. Рассуждения удобно прово-
дить в векторных обозначениях. Поэтому обозначим
1р(Х, ж) = {г|)1(Х, я), ..., я)}.
Из условий теоремы следует, что
х) = 5ж1|%г + г(Х, х\
Пг(Х, х)11 < г(П2 + Ы2). (420)
Рассмотрим отображение g(X, х) = х — (3x^)“1tp(X, я).
Используя (4.20), получаем
g(%, х) = — х\
Ш x)ii < r(vv + Нх112)пед-111. (4,21)
Заметим теперь, что без ограничения общности мы мо-
жем считать r(z) неубывающей функцией z. В самом
деле, если это не так, то rtz) можно заменить на
со (z) = sup г (i),
0^i<z
так что co(z)>r(z). При этом co(z) уже, очевидно, не-
убывающая функция и co(z)/z -> 0. Действительно, так
как -> 0, то для всякого е>0 найдется такое 6,
что г(£)/£^е, как только t С б. Если теперь z<6, то
co(z) 1 -/4Ч - г (t)
—— = — sup г (t) sup —г2- е-
2 2 ,o<«z г
Пусть теперь
тШ = inf {т: KfWW + т2) т),
где К = 11(5ж'ф)”111. Так как при достаточно малых X
выполняется неравенство
Я/XVF+V) = КНШ) Z,
то при достаточно малых X т(Л) < К. Кроме того, по
определению нижней грани для каждого такого X су-
ществует такое т*(Х), что t(?v) т*(Х) С т(Л) + X2, и
^(УЛ2 + (т*Ш)2) т*(Х). (4.22)
Покажем, что
1^-+о,
В самом деле, по определению
т(Л) - V < Ч- (т(Х) — X2)2)
^Ш+ |т(Х) — VI), (4.23)
где мы воспользовались тем, что r(z) — неубывающая
функция и W + (o2^7i + (o для X и со положительных.
Далее, так как для малых X т(Х) %, то правую часть
(4.23) можно оценить следующим образом:
Кг (X + | т(Х) - V1) Кг (к + X) = Кг (2Х).
Итак, мы получаем т(Л) — X2 Лт(2Л) или
+ х,
Л Z/L
т. е. т(Х)/Л-> О при к 0. Но тогда и т*(Х)/Х0.
Итак, для достаточно малых к выполнено неравен-
ство (4.22). Если теперь 11x11 т*(%), то согласно (4.21)
llg(X, я)И Яг(П2 + Ы2) < ^(П2 + (т*(Л))2) т*(А).
Отсюда следует, что непрерывное отображение g(X, х)
отображает шар Ы т*(Х) в себя. На основании тео-
ремы Брауэра [17] теперь можно утверждать, что ото-
бражение g(X, х) обладает неподвижной точкой, т. е.
найдется такая точка х(к), что
х(к) = g(X, я(Х)), Ш)И т*(Х).
Но из определения g(A, х) следует, что
*ф(Л, х(кУ) = 0,
т. е. исследуемая нелинейная система уравнений раз-
решима.
гг II * (МII (к)
При этом -——г-2-’ откуда следует, что
Л Л
1|г(М1|
*
при X -> 0.
Теорема полностью доказана.
§ 5. НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
В КОНКРЕТНЫХ ЗАДАЧАХ
В этом параграфе мы проиллюстрируем примене-
ние развитой и предыдущих параграфах общей теории
к различным экстремальным задачам. Сила всякой
77
общей теории состоит в том, что опа позволяет рас-
смотреть единообразным способом различные частные
задачи и получить полные результаты единым
методом.
Многие из исследуемых ниже задач рассматрива-
лись раньше, и им посвящено большое количество ра-
бот. Как правило, для изучения каждой задачи при-
влекались свои специфические методы, пригодные для
решения именно данной узкой задачи. Мы покажем,
что применение развитой общей теории в каждой из
исследуемых ниже задач сразу же, без привлечения
каких-либо дополнительных длинных рассуждений, да-
ет полные результаты, зачастую даже более общие, чем
те, которые были получены специальными методами.
1. Классическая задача математического програм-
мирования. Пусть заданы в n-мерном пространстве
дифференцируемые функции i = —m, ..., к. Не-
обходимо найти условия, которым удовлетворяет точка
я0, являющаяся решением следующей задачи:
min /0(я),
fi(x) С 0, i = —m, ..., —1,
Л = 0, i = l, ..., к.
Предполагается, что функции Д(я) непрерывно диф-
ференцируемы.
Так как функции /г(я) дифференцируемы, то они
входят в класс квазидифференцируемых функций, при-
чем для них множество дфДяо) состоит из одного-един-
ственного вектора, совпадающего с градиентом /<Сг)
в точке х, который мы обозначим через Л(х). В са-
мом деле, по известной теореме анализа [9]
е) = (j'i(x), е).
Легко видеть, что мы находимся в условиях приме-
нимости теоремы 4.2, где в качестве множества М на-
до взять все пространство. Поэтому Км — также все
пространство и Км={0}.
Из теоремы 4.2 теперь следует, что найдутся такие
числа Zi > 0 для i 0, что
k
2 Wi(^) = 0, Wi(*o) = O,
i=—m
Мы получили известное правило множителей Лагранжа.
78
2. Математическое программирование с контину-
умом ограничений. Требуется найти минимум непре-
рывно дифференцируемой функции /(я) n-мерного ар-
гумента х при ограничениях
/(а, х) 0,
где /(а, х) — непрерывная по а и х функция, облада-
ющая непрерывным градиентом /х (а, х\ a Q — ком-
пактное множество. Введем функцию
fSx) = max /(а, х).
аей
Тогда поставленная выше задача эквивалентна задаче
min {/(я): fSx)^Q}.
Согласно теореме 3.3 f-i(x) есть квазидифференци-
руемая функция, причем согласно теореме 3.4 множе-
ство df-i(xQ) для нее дается формулой
й/-1 Ы = со ( (J df (a, zon,
где QCr0) = {a: a^=Q, /(a, rr0) = f-SxQ)}. Так как функ-
ция /(a, x) непрерывно дифференцируема по х, то
5/(a, xQ) = {fx (а, я0)}, и мы можем написать
(^о) = со f U fx (a, z0)Y
\aeQ(x0) J
причем знак замыкания убран, поскольку выпуклая
оболочка замкнутого множества в конечномерном про-
странстве замкнута, а множество U fx (ос, #о) замк-
aeQ(x0)
нуто, так как замкнуто множество Q(x0), а /х(ос, xQ)
непрерывно зависит от а.
На основании теоремы 4.2 можно утверждать, что
найдутся такие неотрицательные константы Ло, X-i, не
равные нулю одновременно, что
М* (^о) + ^-1С = °> (*о) = 0.
где с df-Sx0). Но df-i(xo) есть выпуклая оболочка
и-мерных векторов fx (ос, xQ), а Й(я0). Отсюда следует,
что вектор с представим в виде
п+1
С = 2 ^ifх (0Cj, Я’о))
i=l
79
где ct/^Qtao), > 0, 2 M = 1- Таким образом, окон-
г=1
чательно получаем
п-Н f
K>fx (*o) + 2 Yi/x (а{, x0) = 0, (5.1)
i=l
7l+l
где Yi = Xi%i> 0, причем 2 Yt = Сформулируем
i=l
полученный результат.
Теорема 5.1. Для того чтобы точка х0 была ре-
шением задачи математического программирования с
континуумом ограничений, необходимо, чтобы нашлись
такие не все равные нулю константы Zo >0 и >0
и точки а< i = 1, п+1, что выполнено со-
отношение (5.1) и все = 0, если /-4U0) < 0.
Допустим теперь, что /(я) и все /(а, х) выпуклые
по х функции, причем найдется такая точка х, что
/_1((Г1)<0. Тогда исследуемая задача становится зада-
чей выпуклого программирования.
Применяя теорему 2.4 для случая одного ограни-
чения, получим, что найдется такое неотрицательное
число Х-i и такой вектор с^д/Дяо), что
/'Uo) = —Х-1С,
причем это условие является необходимым и доста-
точным.
Рассуждая теперь аналогично предыдущему, мы
получим
Следствие 1. Если fix) и fia, х) — выпуклые
функции и f-i(Xi) < 0 для некоторой точки Xi, то для
того, чтобы точка х0 была решением задачи с конти-
нуумом ограничений, необходимо и достаточно, чтобы
нашлись такие числа у, 0 и cti^QC^o), что выполня-
ется условие (5.1) с Хо = 1.
Следствие 2. При предположениях следствия 1,
для того чтобы точка xQ была решением задачи с кон-
тинуумом ограничений, необходимо и достаточно, что-
бы нашлись такие a.i^QixQ), что точка х0 есть решение
задачи
min fix),
(5.2)
f (cti, x) < 0, I = 1, ..., n + 1.
80
В самом деле, соотношение (5.1) (Хо = 1) есть одно-
временно необходимое и достаточное в силу теоре-
мы 2.4 условие, для того чтобы точка xQ была решени-
ем задачи (5.2).
Таким образом, следствие 2 показывает, что в вы-
пуклом случае решение задачи с коптипуумохМ огра-
ничений может быть сведено к решению специально
подобранной задачи с числом ограничений, не больше,
чем п + 1.
3. Теоремы о минимаксе. Пусть в пространстве В
задано выпуклое компактное множество М, а в про-
странстве В* — выпуклое ограниченное слабо* замкну-
тое множество Л/*. Введем функцию <р(я) = тахя*(я:).
х*^М*
Пусть Xq е М — точка минимума функции ф(я) на
М, Тогда по теореме 2.1 найдется такой х0 &дср(х0),
что 1соп(М — ж0)]*.
Далее, по теореме 1.12
5фСг0) = {я*: x*f=M*, х*(х0) = ф(х0)}.
Таким образом, найдется такой функционал х*, что
Xq (х — х^} 0 для всех х е М
и
я* (гг0) х* (я0) для всех х* е М*.
Таким образом, из двух предыдущих неравенств сле-
дует, что
(#) 4 (*о) (*о) Для ЕСех х е х* е
(5.3)
Теорема 5.2. Если М — выпуклое компактное
множество в В, а М* — выпуклое ограниченное слабо*
замкнутое множество в В*, то
min max х* (х) = max min х* (я). (5.4)
хем х*ем* х*ем* х&м
Доказательство. Утверждение теоремы есть
непосредственное следствие (5.3), поскольку (5.3) (см.
[11] ) эквивалентно (5.4).
Следствие 1. Если X и Y—компактные мно-
жества, К(х, у} — непрерывная функция х^Хи y^Y,
а X* и Y*— множества всех мер соответственно на X
6 Б- Н. Пшеничный 81
и Y таких, что ц(Х) ==у(У) = 1, то
min max J k (x, у) ц (dx) v (dy) =
цех* veY*
~ max min J k (x, y) ц (dx) v (dy)'
veY* ЦЛЕХ*
Доказательство. Рассмотрим в качестве В
пространство всех непрерывных функций на У. Возь-
мем в качестве М множество всех функций с(у), пред-
ставимых в виде с(у) = J k(x, y)p\dx), а в качестве
Л/* — множество У*. Тогда доказательство следствия
полностью совпадает с утверждением (5.4) теоремы 5.2.
Следствие 2. Если X и У — компактные мно-
жества, а функция к(х, у), непрерывная по совокупно-
сти аргументов х^Х и у е У, вдобавок выпукла по х
и вогнута по у, то min max к (х, у) = max min k (x, у).
xeX y&Y y=Y xt=X
Доказательство. На основании предыдущего
следствия теоремы 5.2 мы можем утверждать, что най-
дутся такие меры ц0 и у0, Цо(А') = у0(У) = 1, что
^k(x, y)[i(dx)vMy)
>j7v(rr, y)[i0(dx')v(dy'). (5.5)
Пусть теперь х^ = ^ц(йх), yv = ^yv(dy). Тогда, по-
скольку к(х, у) выпукла по х и вогнута по у,
(ж, у) Но (dx) v (dy) > j А (а:ц0, у) v (dy), (5>6)
J/,- (х, у) ц (dx) v0 (dy) < J к (x, yYo) |x (dx). <5-7)
Покажем, что , ‘’ \
J Л (*, y) Ho (dx) v0 (dy) = \k (a;go, y) v0 (dy). <5-8>
В самом деле, па основании неравенства (5.6) правая
часть может быть только меньше, чем левая. Допу-
стим, что она строго меньше, так что
J А’ (х, у) ц0 (dx) v0 (dy) > J к (^0, у) v0 (dy).
Взяв теперь в левой части (5.5) в качестве меры ц ме-
ру, сосредоточенную в точку яЦ(), мы придем к проти-
воречию.
82
^к(х, z/)poWx)voWz/)
Точно так же показывается, что
U (*ц0, у) v0 (dy) = к (Zgo, yv#). (5.9)
Действительно, из вогнутости к(х, у) по у следует, что
Р (*ц0’ У) vo (^) < к (£ц0, J/v0).
Допустим, что выполняется строгое неравенство. Из
(5.5), (5.6) и (5.8) следует, что
\к (хи0> У) vo > j*к (^о’ У) v
Выбрав v сосредоточенной в yVQ, получим противоре-
чие с предположением.
Теперь на основании (5.5) —(5.9) получаем, что
pc (я, J/v0) И (dx) > к (zgo, j/Vo) > рс (ггЦ(), у) v (dy).
Если взять меры ц и v сосредоточенными соответ-
ственно в точках хну, получаем
к (*. Уч0) > к (*Ц0, Pv0) > к (Яцо, у)
для всех х е X и у Y, что завершает доказательство
теоремы.
4. Задачи чебышевского приближения. Пусть зада-
па функция цСг, а), где х меняется в некотором мно-
жестве й, а а — в множестве 31. Будем предполагать,
что й — подмножество Еп, а 31 — компактное множе-
ство в Es. Функция ц(х, а) непрерывна по своим аргу-
ментам и имеет непрерывный градиент цх (я, а) по х.
Рассмотрим задачу минимизации функции
ц(гс) = шах ц(я, а)
на множестве й, которое в каждой точке х обладает
непустым выпуклым конусом Кх:
Кх — {е: х + ^е^О, для достаточно малых Х>0).
По доказанному в § 3 функция ц(я) квазидифферен-
цируема, причем множество 5ц Сг) для нее определя-
ется соотношением
5ц (х) = со ( U Цх (#, a)Y
\as=2l(x) )
31 {х) = {a : a е 51, ц (х, сс) = ц (я)}.
6*
83
На основании следствия теоремы 4.1 и теоремы 4.2
можно утверждать, что если pt (ж) достигает минимума
на й в точке то выполняется следующее условие:
существует такой вектор cq^KXq, что с0 е Но
поскольку мы имеем дело с n-мерным пространством,
то любой элемент выпуклой оболочки некоторого мно-
жества представим в виде выпуклой линейной комби-
нации векторов из самого множества. Таким образом,
найдутся такие i=l, ..., п +1, и ai^Sl(rr0), что
п+1 п+1
с0 = 2 Ki[i'x(x0,ai), 2^ = 1. (5.10)
2=1 2=1
Теорема 5.3. Для того чтобы определенная вы-
ше функция ц(х) достигала своего минимума в точке
Хо е Q, необходимо, чтобы нашлись такие константы
Xi > 0 и точки щ е 91Ст0), i = 1, ..п + 1, что
п+1 п+1
2 (*о, “0 е С, 2 М = 1- (5.11)
2=1 2=1
Если ц(я, а) выпукла по х для всех а и множество Q
выпукло, то приведенные условия достаточны.
Доказательство. (5.11) есть непосредственное
следствие соотношений с0 е К* и (5.10). Если же вы-
полнены дополнительные предположения о выпукло-
сти, то достаточность следует из того факта, что функ-
ция ц(^) выпукла и к ней применима теорема 2.1, ко-
торая в данном случае вполне эквивалентна в части
необходимых условий теореме 4.2, однако показывает
дополнительно, что в выпуклом случае необходимые
условия одновременно являются и достаточными.
Следствие. Если Q совпадает со всем простран-
ством, то условие (5.11) в теореме 5.3 может быть за-
писано в ваде
п+1
2 Мн» (х0> ai) = 0-
2=1
В самом деле, если Q — все пространство, то и ко-
нус KXq совпадает с Еп, а поэтому конус kXq содержит
единственный элемент 0.
Полученные выше результаты, сформулированные
в теореме 5.3 и ее следствии, можно рассматривать как
необходимые условия в нелинейной задаче чебышев-
84
ского приближения. Действительно, мы сейчас пока-
жем, что из них можно получить обычные условия для
классической задачи о чебышевском приближении.
Пусть на компактном множестве Е zn-мерного про-
странства заданы непрерывные функции фЛ(а),
s=l, п, и непрерывная функция /(а). Ее требуется
приблизить обобщенным полиномом
п
F (а) = 2 Wfk (а),
fe=i
коэффициенты которого Xi меняются в замкнутой вы-
пуклой области Q. Это приближение должно быть наи-
лучшим в том смысле, что величина
ц (х) = шах
п
/ (а) — 2 ^фл(а)
Ь=1
должна быть минимальной.
Представим функцию ц(д;) в несколько ином, более
удобном для исследования виде
(п \
/(а) — 2 ^фл(а) •
k=l 1
*-1<с£<+1
(5.12)
Легко видеть, что ц(я) есть выпуклая функция х, при-
чем она образована как максимум по компактному
множеству семейства функций
(п \
/(а) — 2 •W (а)).
1=1 /
Эти последние очевидным образом непрерывно диф-
ференцируемы по х и
(я, а, £) = — (а), £ср2 (а), ..., Есрп (а)).
На основании теоремы 5.3, для того чтобы точка х^ &
е й доставляла минимум, необходимо и доста-
точно существование таких X, > 0 и {а,, £г), что
п+1 /фх (а.) \ п+1
- 2 • • • • е 2 = 1, (5.13)
i=l \Фп (ai) /
причем все пары {а>, £,} таковы, что на них достига-
85
егся максимум в (5.12) при х — х°. Отсюда следует, что
ц (х°) =
п
f («i) — 2 4фа (“»)
/1=1
(5-14)
(п
/ («г) — 2 («i)
/1=1
Этот результат резюмирует следующая теорема.
Теорема 5.4. Для того чтобы коэффициенты хЦ,
k = 1, ..., тг, были решением поставленной выше зада-
чи чебышевского приближения, необходимо и доста-
точно, чтобы нашлись такие числа Ki > 0 и точки
что выполняются соотношения (5.14), (5.13),
где Кх<* есть двойственный конус к конусу допустимых
направлений в точке xQ области Q.
Следствие. Если Q — все пространство, то ус-
ловие (5.13) может быть записано в виде
п+1 / фх (<Xi) \
2Ui •••• =0. (5.15)
i=l \ Фи (ai) /
Применим теперь полученный результат для слу-
чая, когда Е — множество на числовой осп, а <рЛ(а) =
= ex'1-1. Пусть (Xi — точки, в которых
п
у, (я0) = max f (а) — У,
aSE /1=1
п
— 2 4а*-1
/1=1
(5.16)
(п
/ («О — 2 я’а*-1
/1=1
причем ai < а2 . С an+i, существование которых
гарантируется теоремой 5.4. Тогда на основании (5.15)
найдутся такие числа Ki > 0, сумма которых равна еди-
нице, что
= 0. (5.17)
86
Заметим теперь, что если среди точек а< имеются
равные, то им соответствуют одинаковые векторы
(а?, а|, ... Собирая при них коэффициенты в
(5.17), мы получим, что найдутся такие af, a« < oti+i,
и числа М >0, что выполнено (5.16) и
(aq \
• • =0, 2%i = 1,
аП-1/ i = l
где г < п+ 1 и г есть число различных Но так как
при различных векторы 5i(af,ah ... , а?-1) линей-
но независимы, если г С п, то отсюда следует, что
г = 1, т. е. найдется в точности п +1 точка а», для
которой выполняется (5.16), и при этом все М =
Таким образом, можно считать, что все аг, входя-
щие в (5.17), различны.
Рассмотрим теперь (5.17) как систему уравнений
относительно неизвестных Хг^г-. Перенося столбец, со-
ответствующий г = п+1, в правую часть, получаем си-
стему уравнений
относительно неизвестных i = 1, ..п. По прави-
лу Крамера решение этой системы можно записать
в виде
Л t __ Л ? •••’ «i-l’an+Pai+l’
---------_____ ,
a2 • •• ап
«2 ••• “п
где
i
D(a,i, a„) есть определитель Вандермонда, который,
как известно, положителен, если < а2 < ... < an.
Далее, так как каждая перестановка столбцов опре-
делителя ведет к изменению его знака, то
.., ai-1, ап+1, ai+1, ..., an) =
= (—l)n"’D(ai, ..cct+i, ..., an, an+i).
87
Поэтому
= — ^n+l?n+l (— l)n 1 —
«{_rgi+1) •. an,«n+1)
D (ai....an)
Так как Xi, X„+1 и оба определителя положительны, то
из последней формулы следует, Что & = (—l)"_‘£n+i,
т. е. в точках ab a2, ..., ап+ь в которых / (a)— S4aft-1
I Л=1
достигает своего максимального значения, знаки укло-
нения чередуются.
Таким образом, показано, что для того, чтобы по-
лином
F (а) = 2
h=l
был наилучшим приближением непрерывной функции
/(а) на компактном множестве Е, лежащем на дей-
ствительной оси, необходимо и достаточно, чтобы ук-
лонение
/ (a) — 2 4а'1-1
/1=1
достигало своего максимума не менее, чем в п + 1 точ-
ке ai < а2 < ... < an+i, «Iе Е, причем знаки уклоне-
ния в точках аг чередуются. Это есть классический ре-
зультат теории чебышевского приближения.
Возвратимся теперь снова к случаю, когда множе-
ство Е есть компактное множество s-мерного простран-
ства Е9,
Теорема 5.4 и ее следствие утверждают, что для
того, чтобы обобщенный полином
(a) = 2 4<Рл (а)
h=l
был наилучшим приближением непрерывной функции
/(а), необходимо и достаточно выполнение условий
(5.14) и (5.15), т. е. чтобы уклонение |/(а) — Р(а) I
достигало своего максимума в точках а,, г = 1, ..., г,
г ^ п+ 1, и было выполнено (5.15), Но если мы рас-
89
смотрим вместо Ё множество Е, состоящее из точек
а.? i = l, ..., г, то условия (5.14), (5.15) будут также
необходимыми и достаточными условиями того, что
полином F°(a)^ наилучшим образом приближает /(а)
на множестве Е. Таким образом, доказана
Основная теорема теории чебышев-
ского прибли жени я. Полином наилучшего при-
ближения к непрерывной функции /(а) на компактном
множестве Е является одновременно полиномом наи-
лучшего приближения для функции /(а) на множестве
Ё = {аь ..., аг), г < n + 1.
Другими словами, существуют такие точки щ^Е,
z = 1, ..., г, г < п + 1, что один из полиномов наилуч-
шего приближения для /(а) на множестве Ё одновре-
менно является полиномом наилучшего приближения
на всем множестве Е.
Рассмотрим теперь общую задачу теории чебышев-
ского приближения в пространстве Банаха В. Пусть
Q — произвольное выпуклое замкнутое множество в В
и ц(х) = Ид;11. Найдем необходимые и достаточные ус-
ловия того, что точка минимизирует ц(х) в Q.
Так как
ц(х) = 11x11 = шах х*(х), S*={х*: х*^В*, Их*Н 1),
x*es*
то ц(х) — выпуклая функция и ее субдифференциал в
точке х состоит из тех x*g=S*, для которых х*(х) =»
= 11x11 (см. теорему 1.12).
На основании следствия теоремы 2.1 мы можем ут-
верждать, что точка х0 Q тогда и только тогда до-
ставляет минимум 11x11 в Q, когда существует такой
Хо е дц (х0), что
х* (^о) (^) Для всех х е Q. (5.18)
Учитывая данную выше характеристику субдифферен-
циала, мы можем сказать, что
*0 ко) = ко II и ко II = 1- (5Л9)
Допустим теперь, что Q состоит из элементов вида
п
X = X 4- 2 cixii
" 1=1
где вектор с = {с1? ..., сп} меняется в некоторой
89
выпуклой области С. Тогда минимизацию
к 11 =
_ п
X —J— CjX}
i=l
по с е С можно рассматривать как наилучшую аппрок-
симацию элемента х с помощью линейной комбинации
элементов Хг с коэффициентами из заданной области.
Теорема
нимизировал
5.5. Для того чтобы вектор с° ми-
п
i=l
необходимо и достаточно
существование такого функционала xQ, что
ко 11=1, (5.20)
п
2 х* (ci — ci) 0 для всех се С, (5.21)
2=1
Доказательство. В рассматриваемом случае
Q есть множество элементов вида х+1±СгХ^ с^С. Ут-
верждение теоремы есть теперь непосредственное след-
ствие (5.18) и (5.19), если подставить в них выраже-
ния для х и xQ:
п п
X = X + 2 сгхи = Х + 2 cixi*
7=1 2 = 1
Следствие. Если С = Еп, то условие (5.21) за-
меняется на условие
z*(^) = 0, f = 1, ... ,п. (5.22)
Действительно, если С = Еп, то величины в левой
части (5.21) могут быть любыми и неравенство (5.21)
не будет нарушаться только если справедливы равен-
ства (5.22).
5. Задача линейного оптимального управления с
фазовыми ограничениями. Рассмотрим объект, поведе-
ние которого описывается системой дифференциальных
уравнений - -
^ = Ах + Ви, (5.23)
где х — n-мерный вектор, А — (п X тг)-матрица, а В есть
(?г X г)-матрица.
90 '
Управление utt) есть измеримая функция, причем
для каждого t u(t) принадлежит выпуклому компакт-
ному множеству U, U <= Ег. Такие управления будут
называться допустимыми.
Среди всех допустимых управлений u(t) необходть
мо найти такое, что соответствующая траектория удов-
летворяет условиям
^(0)-^° = 0, х(Г)-х' = О,
н-i (*(•)) = тах (ОХ °,
ОШТ
и такое, что функция
Ио И-)) = max g0(x(t))
достигает па нем своего минимума. Здесь g^x\ i —
= 0, — 1, непрерывно дифференцируемые функции х.
Изучим поведение функций щ. Это функции, опре-
деленные на пространстве /г-мерных непрерывных
функций Сп. Поскольку каждая траектория системы
(5.23) зависит от соответствующего допустимого управ-
ления, то через эту зависимость щ становятся функ-
циями над пространством управлений.
Нетрудно видеть, что в силу свойств интеграла
Стплтьеса
т
(.li (z (•)) = max f gt (x (<)) du (<),
OEM* 0
где 71/* — множество всех монотонно неубывающих
функций, удовлетворяющих условию о(0)=0, а(Т) = 1.
Каждой функции x(t) можно поставить в соответ-
ствие функцию g7(<rU)), которая также есть непрерыв-
ная функция из пространства С1. Таким образом опре-
делен некоторый нелинейный оператор S: Сп -> С1.
Если теперь определить функцию v в пространстве
С1 как
т
v(j/(-))=max \y(t)du{t),
OEM* "
то мы можем записать цХН•)) = v(@(H-))). Замечая
теперь [5], что множество Л/* функции о есть выпук-
лое слабо замкнутое ограниченное множество в про-
Ш
страистве, сопряжением к С1, и применяя теоремы 1.12
и 3.1, получаем, что цМ)) есть квазидпфференцпру-
емая функция, причем
т
ц'(Х°(.)), е(-)) = max J (gix (х° (I)), е (t)) da,
где ЛРСгЧ-))— множество тех для которых
т
Jgi = (*°(-)),
О
e(t) — произвольный элемент Сп.
Покажем теперь, что цг-(х(-)) есть квазидпффереп-
цируемая функция пе только относительно простран-
ства непрерывных функций, но и относительно про-
странства управлений. Для этого заметим, что спра-
ведлива известная формула Коши [121, выражающая
решение системы (5.23) через управление в виде
t
х (t) = ф (Q xQ + Ф (t) J Ф”1 (т) Ви (т) Л,
где Ф(£) — матрица, удовлетворяющая системе урав-
нений
^ = ЛФ, Ф(О) = Л
I — единичная матрица.
В силу этой формулы каждому сдвигу управления
в направлении E(t) соответствует сдвиг траектории в
направлений
t
е («) = Ф (О J Ф-1 (т) BE(r) dr. (5.24)
О
Если теперь рассматривать щ(.т(-)) как сложную
функцию над пространством управлений, то юна ока-
зывается квазидифференцируемой и
^o(-),£(-)) = FV(zo(-)> *(•))==
т / t \
= max J g’ix («)),Ф («) J Ф-i (Т) BE (т) dr da (f).
о£М*(х°(-))о \ 0 /
92
Далее, в силу формулы Коши ограничение х(Т) =
= х1 определяет ограничение
т
Ф (Г) х0 + Ф (Г) J Ф-1 (0 Ви (f) dt - X1 = О,
О
которое эквивалентно заданию п скалярных ограни-
чений.
Применим теперь к исследуемой задаче теорему
4.2. Для этого возьмем в качестве множества М мно-
жество допустимых управлений. Тогда в силу выпук-
лости множества U и линейности ограничений типа
равенства в качестве конуса Км можно взять конус
Км = {Ekt): Ekt) = *kkukt) — u°U)), ukt) — допустимое уп-
равление, X > 0), где u°U) — оптимальное для данной
задачи управление.
В исследуемой задаче множества (ЭрД^о), / = 0, — 1,
в силу формулы для производной по направлению со-
стоят из функционалов Xj вида
т / t \
J gix (*° (0). Ф (0 J Ф-1 (г) BE (т) dx do (t),
о \ о /
где o(rt Л/*(.г0(-)).
Для ограничений типа равенства в силу их линей-
т
пости функционал х* имеет вид Ф (Т) J Ф-1 (t) BE (£) dt.
о
Применяя теорему 4.2, мы можем утверждать: для
того чтобы управление uQkt) и соответствующая ему
траектория x°kt) были оптимальными в поставленной
задаче, необходимо, чтобы нашлись такие числа Хо,
Х-! > 0, вектор К = {Xi, ..(причем Хо, X-i, X не
все равны нулю) и неубывающие функции о0(£), o-i(f),
что
0 П , ' \
2 М gix (Х° (<)), ф (Q J Ф-1 (0 BE (т) dx d<Ji (t) +
i=~i о \ о J
I T \
+ X, Ф (T) J ф-1 (t) BE (t) dt > 0 (5.25)
\ 0 J
для всех Ekt) Км. или, что эквивалентно, для всех
E{t) = u(t) — i4°U), где wU) — допустимое управление.
93
Кроме того, должны выполняться условия
* а<(0) = 0, ai(7’) = l,
= i =—1,0, (5.26)
Мы не будем утомлять читателя несколько громозд-
кими выкладками, сводящимися к замене порядка ин-
тегрирования в (5.25). После таких выкладок неравен-
ство (5.25) приводится к виду
т т
J (4? (т), Ви (т)) dx J (ip (т), BuQ (т)) dx, (5.27)
о о
где
гр (т) = ф-1* (т) X
Ф* (0fc(^°(9) d^ (0 + Ф*(Г)Х
(5.28)
и звездочка при матрице означает транспонирование.
По из условия (5.27) следует, что оптимальное управ-
ление должно удовлетворять условию
(хр(т), Ви°М) = min (хр(т), Bv) (5.29)
veu
для почти всех т, 0 т < Т.
Полученные выше результаты резюмирует следу-
ющая теорема.
Теорема 5.6. Для того чтобы допустимое управ-
ление u°(i) было решением сформулированной в на-
чале пункта задачи, необходимо существование таких
чисел Xi > 0, i = —1, 0, вектора X и неубывающих функ-
ций что выполняются условия (5.29), где функция
гр(т) определена соотношением (5.28), a Xi, X и ajd)
удовлетворяют условиям (5.26).
Замечание 1. Легко видеть, что если £,(#) —
выпуклые функции, то рассмотренная задача есть за-
дача выпуклого программирования, и если Хо > 0, то
условия теоремы 5.6 являются достаточными.
3 а м е ч а п и е 2. Отметим некоторые свойства
функции 'ф(т). В каждой точке, где щ(т), i = — 1, О,
дифференцируема, т. е. почти всюду (так как о((т) —
94
неубывающие функции) г|?(т) имеет производную, ко-
торая дается формулой
0 ,
77 = “ “ 2 (Т)) >
i= —1
получающуюся простым дифференцированием (5.28).
В точках разрыва функции о<(т) функция -ф(т) также
терпит разрыв, причем в силу определения интеграла
Стилтьеса
о
ip (т — 0) — -ф (т + 0) = 2 (т) gix (z° (т)).
i= —1
Здесь Ааг(т) — величина скачка о< в точке т. *
В заключение отметим, что различные более слож-
ные ограничения па правый конец траектории и на
фазовые координаты в рассмотренной задаче могут
быть учтены, подобно тому как это было сделано вы-
ше, без особых трудностей.
6. Принцип двойственности в выпуклом програм-
мировании. Пусть В — пространство Банаха, ф/я),
i = — т, — (пг — 1), ...., —1, 0, — выпуклые функции,
Ф,-(гг), 1=1, ..., А‘,— линейные функции, и X — выпук-
лое множество. Требуется решить задачу
min фо(гс),
-- V, v Ч/,
х^Х.
Рассмотрим множество М в пространстве размерно-
сти т + к+1, определенное следующим образом:
М = {z: z Em+*+1, Zi = фХ#), —тп Аг, х е X}.
В дальнейшем будем предполагать, что множество М
компактно.
Положим
k k
р (и) = шах 2 ui4i W = max S Uizi, (5.31)
x&X I — — т г=—т
п рассмотрим задачу минимизации этой функции на
множестве
Q = {и: и0 = —1, lit 0 при i < 0}.
95
|л(и) есть выпуклая функция. Так как. функция
k
2 uizi
г~—т
дифференцируема по и, *
|4 (u, z) = z, z = {z_m, ... , z0, ... , zk},
то согласно теореме 3.5 субдифференциал ц(и) в точ-
ке uQ есть выпуклая оболочка векторов z, удовлетво-
k
ряющих условию 2 UiZi = [к (u°), Mg z, или, что
i=—т
то же самое, есть выпуклая оболочка векторов ф(я)
таких, что
k
2 и?(р| (rr) = [л (u°), х^Х,
f \ > ( u (5-32)
ф(3?) ~ дф—?n(«W, • • •? фо(*£/, • • •> флхЛ')/*
Таким образом, любой вектор из Зц(м°) представим
в виде
i i
2 \?ф 2 ~ ije о,
2=1 2=1
причем каждая из- точек х$ удовлетворяет условию
(5.32).
Рассмотрим теперь конус допустимых направлений
к области Q в точке п°, т. е. конус Киь = con (Q — и0).
Легко видеть, что Кио состоит из таких векторов е =
— тп, • • «, в0, » • ., , ЧТО
ei произвольно, если ui <0, i < 0,
ei 0, если и? = 0, i < 0,
eQ =0,
ei произвольно, если j>0.
Поэтому двойственный конус состоит из векторов
е*, имеющих следующую структуру:
е* = 0, если < 0, i < 0,
е*^0, если иг = 0, f<0,
го произвольно,
е* = 0, если i > 0.
96
Согласно теореме 2.1 в точке и6 ей, в которой ц(и)
достигает минимума на Q, должно выполняться ус-
ловие
5ц(и°) А#*о=£0.
Это значит, что найдутся такие точки Xj е X, / = 1, ...
,.I и числа Xj > 0, что вектор
i
с = 5 (^)
i=i
будет принадлежать Х*о, причем дополнительно вы-
полняются условия
2 j = 1»
$=i
а каждая точка Xj удовлетворяет условию (5.32). Но
тот факт, что с е Кио означает в силу сказанного вы-
ше о конусе Кио, что
i
2 (•£;) = 0, если Ui < 0, i < О,
i
2Ш)<0, если = 0, j<0, (5.33)
0=1
i
,2 ^фг (#;) = 0, если i > 0.
5=1
I
Рассмотрим теперь точку х0 = 2 Так как X
3=1
выпукло, х} е X, то и #о X. Далее, из выпуклости
функций ф<(я) для i 0 и их линейности для i > 0 на
основании (5.33) получаем
i
ф{ (^о) < 2 Mt (^) 0 Для 1 < о»
фг (^о) — 2 ^ф1 (^j) — О ДЛЯ I О,
3=1
Наконец,
i
Фо (^о) 2 ^‘Фо (^j)’
;==i
7 Б. Н. Пшеничный
97
Таким образом, мы показали, что точка xQ удовлет-
воряет всем ограничениям исходной задачи выпуклого
программирования. Покажем теперь, что точка xQ яв-
ляется ее решением, т. е. минимизирует ф0(я).
Так как и® 0 для i С 0, а ф<(х) выпуклы для
i С 0 и линейны для I > 0, то
h k I
2 ^гфг (*о) 2 \?фг (^j) ~
i=—m i = — m j=l
I h I
= S 2 и°фг (^) = 2 (u°) = В (M°),
j=l i=—m j=l
где использовано то, что Xj удовлетворяет (5.32). Но
так как xQ е X, то из определения ц(и) следует, что
k
2 U-<Pi (х0) < ц (и0).
i =—m
Таким образом,
h k
2 «?ф« Uo) = p. (u°) = 2 Wiepi (*;)•
i——m i = — m
Умножая последние соотношения па Xj и складывая,
получим, учитывая, что сумма Xj равна единице и вы-
полнены соотношения (5.33):
h k [ i \
2 Uo) =. 2 4 I 2 k>q>i (^) =
i=—тп i=—m \j=l 1
I
— U0 2 \/Фо (^j)*
j=l
Так как ф0(я) — выпуклая функция и uj= — 1, то из
последнего равенства получаем
k
2 Ф1 (^о) < ^оФо (*о)
2 =—771
пли
k
2 w?tpi(xo)<O. (5.34)
i=—т
г^О
Но выше уже было показано, что фХ^о) 0 для i < О
и ф<(х0) = 0 для i > 0.
98
в силу того, что tii 0 для i < 0, все слагаемые
в левой части (5.34) оказываются неотрицательными.
Поэтому неравенство (5.34) возможно лишь тогда,
когда '
н?фг(^о) = О ЯЛ Я Z=^0.
Пусть теперь х — произвольная точка, удовлетворя-
ющая ограничениям (5.30). Тогда, по определению
ц(и°),
k
— Фо(*о) = 2 И?фг(^о) = ц(и°)>
г=—т
k
> — ф0(^) + 2 и°фг(^)> — Фо (*-)>
г=—т
1^0
ибо для i < 0, а ср/я) 0 для £<0 и ф£(я) = 0.
для i > 0. Таким образом, выполнено неравенство
фо(#о) фоСД показывающее, что точка хй есть реше-
ние исходной задачи выпуклого программирования.
Нами доказана
Теорема 5.7. Пусть определенное выше множе-
ство М компактно и uQ — точка минимума функции
ц(н) (5.31) в области Q. Тогда среди точек, удовлетво-
ряющих условию
h
2
н’фг (х) = ц(г/°),
х^Х,
найдется такая, которая будет решением исходной за-
дачи выпуклого программирования (5.30).
В чем основной смысл полученного результата? Он
показывает, что исходной задаче выпуклого програм-
мирования можно поставить в соответствие другую за-
дачу выпуклого программирования с более сложной
функцией, но с простыми ограничениями, решение ко-
торой эквивалентно решению исходной задачи. Из
классической теории линейного программирования из-
вестно, что двойственная задача подчас оказывается
более удобной для решения, чем исходная. Кстати,
если применить полученный результат к обычной за-
даче линейного программирования, то действительно
получается задача, двойственная в смысле теории ли-
нейного программирования [6].
7* 99
Наконец, отметим следующую важную особенность
двойственной задачи: она конечномерна, даже если
исходная задача не была таковой. Именно этот факт
широко используется в ряде алгоритмов для решения
линейных задач оптимального управления.
7. Системы выпуклых неравенств. Теорема Хелли.
Покажем, как полученные результаты по теории необ-
ходимых условий экстремума могут быть применены
к изучению условий разрешимости систем выпуклых
неравенств.
Пусть L — линейное пространство и фг(гг), 2=1, ...
..., п,— выпуклые функции па нем. Рассмотрим систе-
му неравенств
фг(гг) 0, 2=1, ..п, х^Х, (5.35)
где X — выпуклое множество в L. Пусть
ф(ж) = {ф1 (х), ..фп(я)},
М == {z: ze Еп, z = ф(я), х е X).
Допустим, что множество М компактно. Тогда су-
ществует ограниченная функция
ц(Х) = max(X, z) = шах(Х, ф(я)).
геМ хе X
Рассмотрим эту функцию па множестве
£2 = (х: %<0, = -11,
ц(Х) — выпуклая функция на этом множестве и дости-
гает на нем своего минимального значения в некото-
рой точке Х°.
Теорема 5.8. Если множество
М = {z: z^ Еп, z = ф(я), х^= X}
компактно, то для разрешимости системы (5.35) необ-
ходимо и достаточно, чтобы функция
ц(Х) = тах(Х, ф(я))
хеХ
была неотрицательной при всех значениях X Q.
Доказательство. Мы уже неоднократно имели
дело с функциями типа ц(Х), в частности, в предыду-
щем пункте этого параграфа. Там было показано, что
субдифферепциал этой функции есть выпуклая обо-
100
дочка всех векторов ср(.г), удовлетворяющих условию
(X, qAx)) = ц(Х), х^Х. (5.36)
Пусть теперь Х° е Q есть точка минимума функции
ц(Х) в Q и ц(Х°) неотрицательно. Па основании след-
ствия теоремы 2.1 в точке Х° должен существовать та-
кой вектор с° е 5ц (Хо) (поскольку пространство конеч-
номерно), что
(Х°, с°) (X, с°) для всех X е Й,
т. е. в силу определения множества Q
(Х°, с°) = min(X, е°) = — max с?. (5.37)
leQ i4i<n
Далее, согласно вышесказанному о структуре мно-
жества 5ц(Х), найдутся такие числа и точки xh
удовлетворяющие (5.36), что
k k
с° = 2 УзЧ> (*>), 2 Y? = 1. Уз > О-
j=l j=l
Отсюда следует, что
k
(*°, С°) = 2 <р(^)) = ц(Х«)>0.
j=l
С учетом (5.37) и выражения для с° это дает
k
max 2 (хз) 0* (5.38)
i i=i
ft
Пусть теперь z0= 2 ТА*- Так как ф/я) — выпуклые
j=i
п п
функции, то <Pi (я0) < 2 TiTi (Xj) < max 2 УзУ^з) < °.
j=l г j=i
т. е. точка х0 есть решение системы (5.35).
Достаточность условий теоремы доказана. Их необ-
ходимость очевидна, так как, если для некоторой точ-
ки xQ *= X, фг(^0) < 0,- то ц(Х) = max (X, <р(х)) >
> (X, <р(х0)) > 0 для А,е й.
Рассмотрим теперь случай, когда L конечномерно
и имеет размерность р, L = Ер.
101
Теорема 5.9. Пусть X — компактное множество
в Ер. Тогда для совместности системы (5.35) необходи-
мо и достаточно, чтобы любая подсистема из (5.35),
состоящая не более чем из р +1 неравенства, была
совместна.
Доказательство. Необходимость опять очевид-
на. Покажем достаточность. Для этого рассмотрим за-
дачу
min ц(я:), х е X,
где ц(я) == max фг(я). На основании теоремы 3.6
1
5pi(x0) = cof и <9(pi (ж0Й, Z(x) = {i: ср;(х)=ц(а:)}.
Ve/(*o) )
Поскольку рассматриваемое нами пространство р-мер-
по, то всякий вектор из выпуклой оболочки может
быть представлен в виде выпуклой линейной комбина-
ции не более чем р + 1 вектора из исходного множе-
ства. Поэтому всякий х* е дц(я0) может быть записан
в виде
я* = 2 r Р + 1» (5.39)
3
где Ц е I (х0), х[. е (rr0). Выпуклая функция ц(я)
достигает своего минимума па компактном множестве
X в некоторой точке х0. Согласно следствию теоре-
мы 2.1 в ^ц(^о) найдется такой функционал xQ, что
я* (х0) х* (х) для всех х^Х. (5.40)
Для нашей задачи это означает, что найдется такое
г^р+1, такие и такие xt- е дер,- ,(<г0), что xQ
в (5.40) представим в виде (5.39). При этом ij^I(x0) и
2 — !•
Но, согласно теореме 3.6 Хц е дц (z0) для выпуклой
функции
(X (х) = max фр (х).
Согласно следствию теоремы 2.1 (5.40) есть необходи-
мое и достаточное условие того, что функция ц(л?) в
точке хй достигает своего минимума. При этом ц(я0) ==
102
= ц(я0), ибо ij е Z(rr0), и значит, в точке х0
Tij(^o) = ИЙ. / = 1, ..., г,
по определению Z(z0)-
По условиям теоремы система неравенств
7 = 1, . ..,г, r^Lp+1, х^Х
совместна. Это значит, что для некоторой точки <= X
\ фг/ЯйХО, /=1,
а следовательно, С 0. Поэтому
? |iGr0) = ц(#о) = min ц(я) jLiUJ С 0.
хех
Но из определения ц(я0) следует, что
фг(^о) < Ц(ЯО) 0,
т. е. точка х0 есть решение системы. Теорема доказана.
Покажем, что следствием предыдущего результата
является известная теорема Хелли (см., например, [11J,
[21]). Пусть в ^-мерном пространстве задана конечная
система выпуклых компактных множеств Xi, 1, ...
,.т. Положим
(ф) = max (ip, х), Fi (х) = max [(\р, х} — (я)].
||1Ж1
Легко показать, основываясь на теореме отделимости,
что х Хь тогда и только тогда, когда Fikx) 0, при-
чем F^x) — выпуклая функция. В самом деле, если
xQ е Х{, то по определению И\-(ф)
(ф, Xq) — Ж<(ф) < 0 для всех гр.
Обратно, пусть Fi(x0) 0, т. е. для всех ф, Пф11 = 1
выполнено последнее неравенство. Если допустить, что
Xq е Xh то по теореме отделимости найдется такой век-
тор ф0, Нфо11 = 1, и 8 >0, что
(фо, я) < (фо, я0) — б для всех х е Xh
т. е. б (ф0, Xq) — Ж/фо), а это противоречит предпо-
ложению.
Итак, каждой системе компактных выпуклых мно-
жеств можно сопоставить систему неравенств
Fikx) 0, i = 1, ..т, х е X,
с выпуклыми функциями Fi и множеством X, в каче-
' 103
стве которого можно взять шар достаточно большого
радиуса, содержащий все Хг. Очевидно, пересечение
множеств Xi не пусто тогда и только тогда, когда си-
стема совместна. Но по теореме 5.9 такая система сов-
местна тогда и только тогда, когда совместна любая
ее подсистема из не более чем р + 1 неравенства. Ес-
ли перевести это на язык выпуклых множеств, то по-
лучаем теорему Хелли.
Теорема Хелли. Если выпуклые компактные
множества Xif i = 1, ..., тп, таковы, что любые р + 1 из
них имеют не пустое пересечение, то и пересечение
всех множеств не пусто.
8. Проблема моментов. Одной из весьма важных
математических задач, которая имеет широкие прило-
жения, является проблема моментов. Она может быть
описана следующим образом. Задано пространство Ба-
наха В и конечное число элементов хг этого простран-
ства. Необходимо найти функционал я* е В*, облада-
ющий минимальной нормой и удовлетворяющий си-
стеме неравенств
я*(о:г-) — cZi 0, i = 1, ..., п,
где at — заданные числа.
Чтобы связать поставленную задачу с вопросом
о разрешимости системы выпуклых неравенств, иссле-
дуем совместность следующей системы:
х*(х^ — ai С О, Z=l,..., п, Ня* II С р. (5.41)
Очевидно, что нахождение минимального р, при ко-
тором система (5.41) совместна, эквивалентно решению
проблемы моментов.
Для того чтобы была применима теорема 5.8, не-
обходимо убедиться, что множество
М = {z: z^En, Zi = x^(Xi) — i = 1, ..., n, Пя*Н < p}
компактно. Но на основании того, что выпуклое огра-
ниченное слабо* замкнутое множество в В* слабо* би-
компактно, можно утверждать, что множество
= ИКР}
слабо* бикомпактно.
Действительно, если ||#Л|>р, то найдется такой
элемент х0, Ня0Н С 1, что я0 (xQ) >> р. Выберем теперь
е > 0 таким, чтобы xQ (xQ) — 8 было больше р. Тогда
104
окрестность
W0={x*: |z* (х0) — я* (z0)| <е]
точки х0 не пересекается с множеством 5*, ибо для
х*
я* (я0) > W — е > р,
а значит, Ия*Н = sup х*(х) > > р.
М<1
Таким образом, каждая точка множества, дополни-
тельного к множеству Sp, может быть окружена ок-
рестностью, не пересекающейся с 5Р, откуда и сле-
дует, что множество, дополнительное к 5Р, открыто,
а значит, Sp слабо* замкнуто. Далее, по определе-
нию слабой* топологии отображение
Zi = X*(Xi) — OLi, i = 1, ..., n,
непрерывно. Отсюда следует, что множество М как не-
прерывный образ бикомпактного множества само би-
компактно в обычной евклидовой топологии, а значит,
просто компактно, поскольку в евклидовой топологии
понятия компактности и бпкомпактности совпадают.
(По поводу использованных здесь понятий и опреде-
лений функционального анализа см. Введение, а также
[5], гл. 1, § 5, 6 и гл. V, § 4, теоремы 2, 3).
Из сказанного следует, что множество М компакт-
но, а значит, мы находимся в условиях применимости
теоремы 5.8.
Для системы (5.41) функция цШ, использованная
в теореме 5.8, имеет вид
п
|Л (X) = max 2 (х* (х^ — czj) =
2=1
max x*
I|x*Kp
(5.42)
Теорема 5.10. Система неравенств (5.41) сов-
местна тогда и только тогда, когда
sup
= 1,. ,.,?2
(5.43)
105
Поставленная выше проблема моментов разреши^
ма, если правая часть (5.43) (обозначим ее через о)
конечна. В этом случае минимальная норма функцио-
нала, являющегося решением проблемы, равна
шах (0, о).
Доказательство. На основании теоремы 5.8
для совместности системы 5.41 необходимо и доста-
точно, чтобы функция (5.42) была неотрицатель-
на при всех At, i = l, ..., ft, удовлетворяющих усло-
вия м
Xi<o, 2 и = -1,
(5.43) есть просто другая запись этого факта, непосред-
ственно следующая из (5.42). Условие того, что сумма
А» равна единице, при этом может быть отброшено,
так как правая часть (5.43) при умножении всех А,
па одну и ту же константу не меняется. Утвержде-
ние теоремы о разрешимости проблемы моментов
следует из отмеченной уже выше связи между этой
проблемой и разрешимостью системы (5.41), с уче-
том того, что норма функционала всегда положи-
тельна.
Часто проблема моментов встречается в литературе
в несколько другой форме. А именно, требуется найти
функционал минимальной нормы, удовлетворяющий ус-
ловиям г
Х*(х^ — CZi = 0, 1=1,..., п.
(5.44)
Очевидно, что такая постановка эквивалентна пре-
дыдущей, если расписать каждое из равенств в виде
двух неравенств
х*(х^) ~ сс/ 0, x*(—Xi) — (—aj О,
i = 1, ..., п.
Поэтому к такой постановке проблемы моментов при-
менима вся предыдущая теория. Если применить тео-
рему 5.10 с учетом удвоения системы неравенств, то
получим, что система (5.44) имеет решение х*, Нх*11
106
£< р, только если р о, где
2 ~ *г) -i
а = sup -т-^—------------------
или (если ввести обозначение X = V — V и учесть, что
когда V и меняются в отрицательной области, то X
пробегает все пространство)
о = sup
х
(5.45)
Таким образом, мы можем сформулировать следую-
щее следствие теоремы 5.10.
Следствие. Минимальная норма функционала,
удовлетворяющего ограничениям (5.44), равна о и оп-
ределяется равенством (5.45).
3 а м е ч а н и е. Очевидно, что если не все ос* равны
нулю, то
о=-^-, А = (5.46)
где нижняя грань берется по всем X, удовлетворяющим
ограничению
2 = 1. (5.47)
i=i
Если х,, f=l, ..., п, линейно независимы, то ниж-
няя грань достигается и отлична от нуля. Действитель-
но, применяя неравенство Буияковского — Шварца к
(5.47), получаем, что
1 = 2 < I Х|-|а I,
i=l
где
(п \ 1/2 / п X 1/2
2М , |а|= 2 <4 .
г=1 / \ 1=1 /
Таким образом, из (5.47) следует, что |А| > 1/1а1.
107
Пусть теперь
п
р = min 2
i=l
Так как Xi линейно независимы, то р > 0. Тогда для
любого вектора X = {Хи ..ХД отличного от нуля,
или
>р|Ч
Из последнего неравенства следует, что область зна-
чений X, для которых
содержится в области |Х| 2 ^ixt Р- Ио ясно,
что минимум 2 надо искать именно в этой
области. А поскольку эта область компактна и мини-
мизируемая функция непрерывна, то минимум дости-
гается. Кроме того, этот минимум отличен от нуля.
Действительно, как мы видели выше, если X удовлет-
воряет (5.47), то IXl > Iczl-1. Поэтому для всех та-
ких X
Полученные результаты позволяют установить
связь между проблемой моментов и задачей чебышев-
ского приближения.
Пусть даны элементы х, ..., хп пространства
Банаха. Рассмотрим проблему моментов
min II я* II,
я*(х) = 1,
х*(х^ =0, i = 1, ..., п.
На основании предыдущего замечания норма функ-
108
циоиала, являющегося решением этой задачи, равйа
о = 1/L, где
II п ||
L = min х + 2 L г = 1, ..., тг.
II г=1 ||
В самом деле, в рассматриваемой задаче а0 = 1,
ai = 0, г=1, ..., п, и поэтому условие (5.47), записы-
вающееся в виде
2 = 1,
г=0
эквивалентно условию Хо = 1.
Таким образом, нахождение минимальной нормы
функционала в рассматриваемой проблеме моментов
эквивалентно решению задачи наилучшего приближе-
ния элемента х с помощью линейного агрегата
п
i=l
< Обратно, если числа таковы, что
то на основании теоремы 5.5 и ее следствия найдется
такой функционал что
(_ п \ |1 __ п ||
х “F KiXj j = Lr -|-
i=l / II i=l II (5.48)
||x*||=l, XQ (Xi) = 0» j=l,
Если L=#0 (а ясно, что только в этом случае о < + оо
и проблема моментов имеет смысл), то, положив
х* = LT^Xq, получим из (5.48), что
11#*И = о, х*(х) = 1, х*(х^ = 0,
т. е. функционал х* является решением проблемы мо-
ментов. Таким образом, мы установили, что между
проблемой моментов и задачей чебышевского прибли-
жения существует двойственная связь и решение од-
ной из них может быть получено при решении другой.
Рассмотрим специальный случай проблемы момен-
тов, когда рассматриваемое пространство есть про-
странство С непрерывных функций аргумента tt ме-
109
няющегося на отрезке [О, Т]. В таком пространстве
норма задается формулой
1И| = max |.г(0|.
Непрерывные функционалы в С* по известной теоре-
ме [5] имеют вид
т
х* (х) = x(t)dg(t), g (0) = О,
b
где g(£) — функция ограниченной вариации, причем
||х*||= Var g(t).
В связи с этим проблема моментов для пространства С
может быть сформулирована следующим образом: най-
ти функцию g(t) с минимальной вариацией на отрез-
ке [0, 71], удовлетворяющую соотношениям
т
J cpi = ah i = l,
о
где — непрерывные функции, а — заданные
числа. Согласно замечанию к теореме 5.40 этой задаче
соответствует следующая задача:
п
min max 2 ?Чфг (0 ,
X 1=1
2 = i.‘
1=1
Таким образом, необходимо найти минимум выпуклой
функции
(72
2 Мфг (0
1—1
конечного числа аргументов на множестве
Q = 2 — 1
I i=i
С функциями такого типа, как ц(Х), мы уже неодно-
кратно встречались, например, в пн. 4 и 6 этого пара-
110
графа. Если положить
К(к) = 0<£<7\
2=1
то субдифференциал ц(%) является выпуклой оболоч-
кой векторов
K0 = sign(s Xi<pi(o),
\i=] /
Далее, легко видеть, что в каждой точке К е Q ко-
нус Кк допустимых направлений состоит из векторов е,
удовлетворяющих условию
п
2 ^2^2 = 0.
1=1
Поэтому двойственный конус состоит из векто-
ров вида ха, где а = {ai, ..., ап}, < х < +<*>. В са-
мом деле, если то (а, е) > 0 для всякого
е е Кк, т. е. для е, удовлетворяющего условию
(в, а) = 0.
Представим а в виде а = ха+Ь, (а, Ь) = 0. Такое
представление однозначно. Тогда х(а, е) + (Ь, е)>0
или (&, е) > 0 для е^Кк, Но — ибо (—Ь, а) =
= 0. Таким образом,
-(&, Ъ) = - НЫ12 о,
т. е. Ъ = 0.
Функция ц(%) есть непрерывная функция своих ар-
гументов.
Допустим, что функции срДО линейно независимы,
a ai не все равны нулю. Тогда па основании замеча-
ния к теореме 5.10 минимум ц(Х) на Q достигается и
отличен от нуля.
Пусть Х° Q — точка минимума. На основании тео-
ремы 2.1 тогда в множестве дц(Х°) найдется такой
функционал, который принадлежит множеству
Из данного выше описания Зц(Х) и 7Г*0 следует, что
найдутся такие > 0, / = 1, ..., г, х и точки t3 е= 7Ш?),
Ш
что
S тЛ (*j) Ф (У = «а»
5=1
?5>0, 2 Уз = 1> г <71+1.
5=1
(5.49)
Если умножить скалярно (5.49) на вектор %0 и учесть
определение множества К(Л), £(£) и соотношение
(%0, а) = 1, то получим и = ц(%°) = L > 0.
Пусть теперь
О < t < t},
(О,
г
^(0=4-2^ ^(9.
5=1
Тогда на основании определения интеграла Стилтьеса
и 5.49 имеем
г
J<p(«)^(0 = 4-2v;Uy<P(i;)-=a,
о 5=1
или, в покомпонентной записи,
т
jcPi(zW(z) = а», 1 =
О
Далее, g(t) — кусочно-постоянная функция, имеющая
скачки, равные в точках tj. Поэтому ее пол-
ная вариация равна просто сумме абсолютных величин
скачков. Но
г г
2 М№_11 = 4-2 y, = 4-=°-
5=1 5=1
Таким образом, норма функционала, соответствующего
g(t), равна о. Поэтому па основании замечания к тео-
реме 5.10 мы можем утверждать, что построенный
функционал есть решение проблемы моментов.
Теорема 5.11. Если срД^) е С линейно незави-
симы, то проблема моментов всегда имеет решение в
виде функции ограниченной вариации, которая кусочно
постоянна и имеет не более чем п + 1 точку разрыва,
где п — число функций срХ£).
112
Проблема моментов имеет многочисленные прило-
жения к решению задач линейного оптимального уп-
равления. В заключение этого пункта мы коротко рас-
смотрим одну из таких задач.
Пусть объект описывается системой уравнений
х = Ах + Ьщ
где А — (п X и)-матрица, Ь — п-мсрпып вектор-столбец,
и — одномерная функция управления. Требуется за вре-
мя Т перевести систему из начального состояния х9
в конечное х', используя импульсное управление с ми-
нимальным суммарным импульсом. Использование им-
пульсного управления означает, что и (Л) имеет вид
u(0 = S т,б(г-«Л,
?—1
где Z, — моменты подачи импульсов, Ivj — мощность
h
y-го импульса, а 2 | у,1 — полная мощность. Функ-
7—1
ция 6U) — дельта-функция, формально удовлетворяю-
щая следующему свойству:
рР(/)б(О^ = Ф(О),
а
если а < 0, > 0, причем а и не'равны нулю од-
новременно. Если же а и Р одного знака, то приведен-
ный выше интеграл равеп нулю. Очевидно, что если
(О, 1<0,
go^ = |l, t>0,
то вычисление интеграла с дельта-функцией впол-
не эквивалентно вычислению интеграла Стплтьеса
Г
J Ф (£) dgQ (t). В связи с вышесказанным ясно, что
« I
каждому импульсному управлению можно поставить
в соответствие функцию ограниченной вариации
h
g (0 = Tj»O
7 = 1
Var g (0 = 2 IYj I-
i=i
S Б. H. Пшеничный
113
Вернемся теперь к поставленной задаче. Поскольку
каждое решение линейной системы уравнений может
быть представлено в виде формулы Коши
t
х (t) — Ф (/) х° -]•- j Ф (t — т) Ьи (т)
о
Ф(/) = ЛФ(^), Ф(0) == I (единичная матрица), то по-
становленная задача о переводе из точки х* в точку х1
эквивалентна нахождению управления, удовлетворяю-
щего системе равенств
т
х (77) = Ф (Г) xQ + [ Ф (Т — т) Ьи (т) dx — х1,
i)
т
или j* ср (т) и (т) dx = сс, где $(т) = Ф(Г — т)Ь, а = х1 —
о
- Ф(7Ъ°.
Если поставить в соответствие по указанным выше
правилам управлению u(t) функцию git), то исходная
задача трансформируется в следующую: найти функ-
цию gU) с минимальной полной вариацией, которая-
удовлетворяет условию
т
.[ Ф (т) dg (т) = а.
о
Но это есть как раз рассмотренная выше проблема мо-
ментов в пространстве непрерывных функций. Если
а + О (при а = 0 решение тривиально: u(t) = 0) и ком-
поненты вектор-функции ср(т) линейно независимы (что
также выполняется, если выполнено условие «общно-
сти положения», см. [18], стр. 131), то па основании
теоремы 5.11 поставленная проблема моментов имеет
кусочно постоянное решение g(O, содержащее не более
чем п + 1 точку разрыва. Но такой функции соответ-
ствует импульсное управление, содержащее не более
чем м+1 импульс, мощности которых совпадают с ве-
личинами разрывов g(£) и которые подаются в момен-
ты разрывов gU). Таким образом, если tj — точки раз-
рыва gU), то
= i -1-0) — — 0))6(f — +
i=l
114
Суммарная мощность этого управления равна
2 -0)| = Varg(f).
i 1
Поскольку полная вариация g(t). минимальна, то отсю-
да следует, что n°U) — импульсное управление с мини-
мальным суммарным импульсом.
Таким образом, при широких предположениях о си-
стеме дифференциальных уравнений оптимальное уп-
равление состоит не более, чем из п + 1 импульса. Ес-
ли использовать результаты, полученные при доказа-
тельстве теоремы 5.11, то можно утверждать, что мо-
менты подачи импульсов лежат в множестве
AW) = {/: О С t Г, |(Г, Ф(П)| =М,
L = шах | (Х°, ср (/)) | — min max |(Х, ср (/)) |.
04КТ (Х,а)=1
9. Равновесные цепы. В математической экономике
почти во всех задачах естественным образом возника-
ют величины, которые удобно интерпретировать как
«цепы» за ресурсы. Обычно — это множители Лагран-
жа и они как-то указывают па величину, которую име-
ет смысл платить за приобретение дополнительных ре-
сурсов.
Здесь рассматривается модель обмена па заданный
момент времени, в который «цены» выступают как
некоторые величины, которые каждый участник готов
заплатить за приобретение или получить за продажу
ресурса, если это ему выгодно. Слово «выгодно» здесь
означает, что деньги, которые участник заплатит за
дополнительные ресурсы, компенсируются уменьшени-
ем расходов производства. Мы не разделяем здесь
потребителей п производителей, как это делается в
обычных моделях равновесного обмена [14].
Удобнее также говорить в терминах «расходов»,
а не в терминах «функций полезности», как это обыч-
но делается. Основное отличие рассматриваемой здесь
модели от классической модели Вальраса — Эрроу —
Дебре. [17] состоит в том, что расходы на приобрете-
ние ресурсов включаются в общий «расход», который
несет каждый участник экономики.
Как это уже в достаточной степени принято, эконо-
мические термины в математических моделях эконо-
мики используются условно, так как реально Соответ-
S’1 115
ствующие величины образуются в результате гораздо
более сложных процессов. Этот факт подчеркнут взя-
тием в ковычкп терминов «цепа», «расходы» и тому
подобное. Ниже кавычки будут опускаться, однако, мы
надеемся, что читатель понимает определенную услов-
ность этих понятий.
Пусть в обмене участвует т участников, каждый из
которых располагает вектором ресурсов i= 1, .. ., т.
Здесь Xi е Е\ и /-я компонента вектора xh обозначае-
мая #•, /=1, ...,7г, есть количество ресурса /-го ти-
па у участника i. Использование вектора ресурсов Xi
приводит i-го участника к расходам V^Xi). В этих тер-
минах тот факт, что V^xJ < 0, интерпретируется как
доход в количестве — Т7/#»).
т
Обозначим х « Х{. Таким образом, х есть сум-
i = l
марпое количество ресурсов, участвующее в обмене.
Предположим, что участники мгогут обменяться сво-
ими ресурсами, т. е. заменить свои векторы ресурсов
xt на векторы z/t, удовлетворяющие условию баланса:
З’/у^у — х. (5.50)
i=“l
Тогда достаточно очевидно, что этот обмен будет вы-
годен участникам, если цены р 0, р <= R\ по которым
производится обмен, удовлетворяют условию
V+ (р, ip — х^ С V^Xi), i = 1, ..., т. (5.5 I)
Если при этом участники имеют ограниченные капи-
талы Л, то их расходы на приобретение дополнитель-
ных ресурсов не должны превосходить Л:
(/?, r/i - х{) С /„ i = 1, ..т. (5.52)
Определение 5.1. Цепы р > 0 называются рав-
новесными, если существует такое распределение ре-
сурсов {// J, i = 1, ..., т, что
Vi (У») + (/>, — X») =
min (Fi(</i) + (р,у; —xi): (р, yt - .г;)< Л};
vi
тп тп
У = ^ У1= 2 Xi = x.
i—1
не
Основное содержание данного раздела состоит в до-
казательстве того, что при достаточно естественных ус-
ловиях равновесные цены существуют.
СформулируехМ и обсудим основные предположения,
при которых будет установлен факт существования
равновесных цен.
А. Функции Vвыпуклы, замкнуты и dom Vj s
S E+-
Здесь E± — неотрицательный ортант пространства
Е\ Требование выпуклости и замкнутости К обычно
для математической экономики [171. Условие, что об-
ласть определения Vi лежит в положительном ортанте,
отражает тот факт, что ресурсы есть неотрицательные
величины. Однако па самом деле чисто математически
достаточно потребовать, чтобы dom Vi лежала в неко-
тором сдвиге положительного ортапта, причем этот
сдвиг может зависеть от номера участника г.
В. Л > 0, i = 1, ..., m, т, е. наличные капиталы
всех участников строго положительны.
С. Существует такое распределение ресурсов
I = 1, ..., т, что
iji xh у{ е dom К, i = 1, ..
m m
^У[ = У< 2 = z.
г—1 г-1
Сформулированное требование можно назвать ус-
ловием некрптичности любого ресурса. Содержательно
оно обозначает, что для любого ресурса с номером /
найдется такой участник г, что он может несколько
уменьшить свой наличный ресурс х\, не приводя се-
бя к катастрофе, т. е. не попадая в область, где Vi в
== + о©. Ясно, что равенство И, = + оо должно интер-»
претироваться как невозможность экономического су-
ществования участника I.
D. Для любого ресурса j найдется такой участник I,
для которого бесплатное получение этого ресурса вы-
годно, т. е.
VSy + М VSy), X > О,
для всех у е dom Vt.
Здесь е}^ Eh — /-й единичный орт пространства
Теорема 5.12. Если выполнены условия А — D,
ГО существуют равновесные цены.
Доказательство. Поясним основную идею.
Пусть
(т т
< У, (р, I/i — *i-X Л, t = (5.53)
Допустим, что для у = х при любом р > О в задаче
(5.53) существуют множители Куна — Таккера q > О
по ограничению
ТП
2 X*- (5.54)
Тогда решение задачи (5.53) при у = х — обозначим
его у^р\ i = I, .. ., т,— как легко видеть, одновре-
менно минимизирует и функцию ТД^Л) + ((7, !/< — #»),
при условии
(р, yi — х{) Ц. (5.55)
Это легко следует из применения теоремы Куна — Так-
кера, из того, что в задаче (5.53) все переменные
входят независимо, если убирается ограничение (5.54),
771
и равенства х
i = l
Обозначим через Q(p) множество векторов Куна —
Таккера в задаче (5.53) при у = х. Тем самым опреде-
лено многозначное отображение р -+ Q(p). Если ока-
жется, что существует неподвижная точка этого ото-
бражения, т. е. р Q(p), то соответствующий вектор р
будет вектором Куна — Таккера, и согласно только что
сказанному, положив q~p, получим, что векторы
у Ар), решают задачу
min{Vi(yi) + (р, у{ — х): (р, у> — х) 7J. (5.56)
Если доказать равенство
m
5 Vi (р) = х, (5.57)
<==1
то существование равновесных цен будет установлено.
Заметим теперь, что у Ар) удовлетворяют (5.54).
Если при этом для некоторой компоненты ; в (5.54)
имеется строгое неравенство, то соответствующая ком-
118
понента вектора р (ведь это вектор Купа — Таккера!)
равна нулю. Воспользуемся условием D, согласно ко-
торому для данного j найдется такой участник г, что
увеличение компоненты у\ (р) ему выгодно, т. е. ве-
дет только к убыванию функции Ясно, что такое
изменение позволяет добиться в (5.54) равенства по
компоненте /. При этом целевая функция в (5.53) бу-
дет только убывать (па самом деле оставаться посто-
янной), а бюджетное ограничение (5.55) не будет на-
рушаться, так как = 0.
Итак, если р — неподвижная точка отображения
р Q(p\ то ей можно поставить в соответствие такое
решение ySp), которое является решением задачи (5.56)
и удовлетворяет балансовому соотношению (5.57). Тем
самым доказано, что если р есть неподвижная точка
Q(p), то р есть искомый равновесный вектор цен,
Если теперь удастся показать, что можно найти та-
кое ограниченное выпуклое замкнутое множество
Q Е\, что С(р) — Q и отображение <?(р) полунепре-
рывно сверху, то существование неподвижной точки
будет следовать из теоремы Какутани [17J.
Обозначим
Ор (у) = |{гл}, I 1, • • , rn : 2 Ух < Ух
Ух о, (/?, у, — i 1, •.. , nJ. (5.58)
Очевидно, что эта область компактна и нижняя грань
в (5.53) ищется именно в этой области (см. условие А).
Так как функции замкнуты, то замкнута и их
сумма и поэтому нижняя грань в (5.53) всегда дости-
гается, если Dp(y) 0.
В силу условия С вектор {//,), i == 1, . . ., лг, принад-
лежит Dp(y) для iji из некоторой окрестности х{,
i == 1, . . ., т, и поэтому
т
1Гр(1/)< у Ш = (5.59)
для у из окрестности х при любых р > 0. Отсюда сле-
дует, что Wp(y) в окрестности х есть конечная непре-
рывная выпуклая функция и существует ее субдиффе-
ренциал dWptxY Но согласно теореме 2.2 множество
119
векторов Куна — Таккера совпадает с — dWp(x}z
Q(p) = _ dWp(x).
Так как D0(x) э Dp(x\ 0, то Hzp(x) > Hz0(x). Ис-
пользуя теперь (5.59) и выражение для производной
по направлению через субдифферепциал, имеем
sup {(q, у — х): q е dW^x')}
<Wp{y)~ WPU) -XV^x).
Если г > 0 — радиус окрестности точки х, в которой
(5.59) справедливо, то из приведенного неравенства
легко получить, что
II ? IK ——, q е (х),
т. е. все множества '0Wp(x) находятся в шаре радиуса
R = г~'(С — IVoU)). Отсюда следует, что множество
Q = {p>0-. WpW^R)
отображается в себя при многозначном отображении
Qtp) и является выпуклым компактом.
Таким образом, для полного завершения доказа-
тельства теоремы осталось только показать, что (?(/>)
полунепрерывно сверху зависит от р, пли, что то же
самое, график отображения Q есть замкнутое множе-
ство. Напомним, что gf Q = {{/?, vl: v е (>(/;)}.
Докажем, что 1ИР(//) непрерывно зависит от р в ок-
рестности х.
Пусть у — фиксировано, а {//,•(/;)} — решения зада-
чи (5.53). Они лежат в D^y) и поэтому равномерно
ограничены. Если -> р0, то, не ограничивая общно-
сти, можно считать, что yApi) у10. Далее,
7)1
WPt (у) = И Vi (У; (Pi')),
i —1
И
lirnJFp, (у) J] lim V, ((/io)
l—tao l~l i оо
в силу замкнутости функций
120
Так как (/>(, Z(, то (р0, yia - х) < Л,
т. е. {j/io} <= А>0 (;/). Поэтому
т
lim WPl (!/) > 2 Vi (Ую) > (У)>
l-^go i—1
Тем самым доказано, что Wp(y) полунепрерывна сни-
зу по р. Возьмем для данного р точку
i/i = (1 — Myi9 + Kyh 0 X С 1,
где теперь {z/l0} — решение (5.53), соответствующее
рд и у. Тогда
(р, l/i -
= (1 — X)[ (р, z/io — %i) — 7 J + Шр, yi — — 7J
(1 - X)lИД/И1С + (pOi yiQ — x^ — ZJ — Ze
< (l-Z)IIApllC-Ze, (5.60)
где e = min 7, >0, Др = p — p0, a С — ограничение no
норме разностей yi0 — xt. Если теперь
то при достаточно малом Др, Zp е 10, 1), правая часть
в (5.60) равна нулю и
{уд == {(1 — Zp)z/i0 + Zpi/J <= Dp(y).
При этом, так как yi <= dom Vh yiQ s dom то и соот-
ветствующая точка у{ e dom Vit
Далее, при Др достаточно малом 0 1 и
2 Vi (У1) < 2 l(i - h) (ут) + Wi (in)] =
i=l i= 1
~ WPa (y) + Xp i [Vi (yi) - Vi (yl0)],
i—1
t. e.
p (y) W7p0 (p) 4*
/ m \
+ т+тЬтг (26.) - mJ i
Из последнего неравенства следует, что Wp(y) по-
лунепрерывно сверху по р. В соответствии с доказан-
121
ной ранее полунепрерывностыо снизу, получаем непре-
рывность WP(y) по р.
Переходим к завершению доказательства.
Пусть pi рд,' qi <= d\Vp ^х). В силу доказанного
выше все множества dWp{x) равномерно ограничены;
поэтому ,qt ограничены и можно считать, что qt q^
По определению субдттфференцпала
wPl О) - О') >0/,!/ -
Переходя к пределу, получим
Wp0 (у) - Wpq (*) >(«#, у - *),
т. е. q^ е д№рв (х). Но это эквивалентно полунепре-
рывности Q(p) по р.
Теорема доказана.
Из доказательства теоремы вытекает следующий
интересный результат.
Следствие. Если р — равновесные цены, то со-
ответствующее им распределение ресурсов {уд, i = 1, ...
. . ., пг, минимизирует общественные расходы на про-*
изводство.
В самом деле, как показано выше, равновесные це-
ны р являются вектором Куна — Таккера, а {уд — ре-
шением задачи (5.53) при у=х. Но целевую функ-
цию этой задачи — сумму Vdyd — очевидно, можно ин-
терпретировать как общественные расходы па произ-
водство в соответствии с тем, что Vdyd — индивидуаль-
ные расходы.
10. Многозначные отображения и параметрические
задачи выпуклого программирования. Пусть заданы
два банаховых пространства X л Y. Обозначим через
Z их прямое произведение X X Y. Если М — подмно-
жество в Z, то многозначное отображение а может
быть задано следующей формулой:
а(х) = {у: {х, у}^М}.* (5.61)
Напомним, что здесь z = {х, у} Z, а х е X, у & Y.
Множество М называется графиком отображения:
gf а = {{х, у}; у (= а{х)} = М,
а множество dom а = {х\ а(х') =0= 0} — его эффективной
областью,
122
Многозначное отображение а называется замкну-
тым, если gf а — замкнутое множество, и выпуклым —
если gf а — выпукло.
Положим для у* е У*
IVa(z, у*) = inf {у*(у): у =-а(х)}. (5.62)
и
Л е м м а 5.1. Пусть а — выпуклое многозначное
отображение. Тогда
+ Х2.г2) }^а{х^ + Z2aU2), (5.63)
At + Z2« 1, М, Z2>0,
и Wa(x, у*) — выпуклая по х функция.
Доказательство. Если {х1? yj с= gf a, {«r2, у2) s
е gf «, то
{Хи?! + }.,х2, )^у{ + Х2у2) gf а.
так так gfа —выпуклое множество. Таким образом,
Х1У1 +/<2у-2 е + ?,2.г2). По у\ и у2 — произвольные
точки а{х^ и а{х2) соответственно. Поэтому справедли-
во' (5.63). Далее, точная нижняя грань по более широ-
кому множеству меньше, чем по более узкому. Поэто-
му в силу (5.63)
И7а(Х1-Г1 + ЛА, У*)
= inf {у*(у): у а(ТЛхЛ + Z2z2)}
и
inf {у*(2.1У1 + Л2у2): У1 е a(Xi), у2 а(х2)} =>
V\ ,’/s
= л11Ев(т1, у*) + Z2H/a(^2, y*)t
что и требовалось доказать.
Пусть теперь z — произвольная точка из gf а. По-
ложим K0(z) = con (gf а — z\ т. е.
7\a(z) = {z: z = >Azt — z), л > 0, & gf a).
Обозначим a(.r; y*) = {y e a(x): y*(y) = W^x, у*)}. Ta-,
ким образом, a(x; у*) ест-ь множество точек, на кото-
рых линейный функционал у* достигает своего мини-
мума па а(х).
Отображение
а* (у*; z) = (х* А’*: {— х*, у*} е Kq (z)]
называется локально сопряженным в точке z к выпук-
лому отображению а.
Теорема 5.13. Пусть а — выпуклое отображение.
Тогда
a*(u*-z)-!0’ у^а(х-,у*),
а {У ,Z)~[dxWa(x, у*), уе=а(х-,у*).
Доказательство. Пусть х* & а*(.у*; z), z =®
« {rr, у} е gf а. Тогда, по определению сопряженного
конуса,
— Х*(х) + г/*({/)^ 0, {х, у} /<а(2),
или, в силу определения Z<e(z),
- x4Xi - х) + y*(r/j - у) > 0, (5 64)
Ui, yJ е gf а.
Если х{ = х, е а(хУ9 то получаем, что
> У*(у\
т. е. у а(х', у*) и ?/*(?/) = Wa(x, у*).
Из неравенства (5.64) теперь следует, что
y*(yj — wa(x, у*) > x*(Xi — х), у{ е= а(х{у
Беря в этом неравенстве нижнюю грань по г/i е a(Xi),
получаем
*/*) — И7а(х, г/*) > х*(хк — х), (5.65)
т. е. х* & dxWa(x, у*).
Обратно, если х* dxWa(x, у*), у & а(х; #*), то, ис-
ходя из (5.65), нетрудно убедиться, что х* s a*(j/*; z).
Это завершает доказательство.
Пусть теперь ср;(х, у), i = 0, .. ., тп,— выпуклые не-
прерывные функции, а — выпуклое отображение. Пусть
также существует такая точка {х1? у{} е gf что
ф<(#1, < 0, i *= 1, . . ., ш. Положим
/(х) - £
-= inf {ф0(х, у): cpjx, у) С 0, i = 1, ..zn, у е а(х)}.
Г (5.66)
124
Нас будет интересовать вопрос о вычислении
Пусть F == Y X Е' и
'а(х) = {{у, уЧ: у <= У, у° ge Е', ф0 to, у) < у\
фД*, у) о, 1=1, ..,, т, у €= а(х)}.
Тогда
(х, у*, у„) = inf (//* {у) + (/*у°-{г/, /} S а (ж)],
j/,s/0
и нетрудно видеть, что /to) = H7ato, 0, 1). Отсюда сле-
дует, что /to) — выпуклая функция и для вычисления
gi‘ можно применить теорему 5.13. Для этого надо по-
строить <7*.
Очевидно, что gf а = Л/о П А ... А Мт А Л/г„+,, где
= {to, у, у0): q?oto, у} У'\
Мх = {to, у, у0): ф/л:, у) С 0), i = 1, ..,, т,
3/„41 = {to, У, У°): to, у) ^gfa, у”^£’}.
Поэтому и /<7 получается как пересечение конусов воз-
можных направлении для соответствующих множеств.
Пусть у0 е= tftoj--какая-либо точка, в которой до-
стигается нижняя грань в формуле (5.G6), а yj ==
=-То(-Тсм £/<»)» г0 = Uo, ,'/(>• i/ol. г0 = Гго> у»}- Множество
ЯЕ задается неравенством
Фи to, у) - у0 0,
где в левой части стоит выпуклая непрерывная функ-
ция совокупного аргумента to, у, у0) е X X Y X Е1.
Легко видеть, что субднфферепцпал этой функции име-
ет вид too, //о, — 1), где [д*, уо] е <?ф0 to, у). В силу
теоремы 2.6 и сделанных предположений
[сон (Мо — z0)]* = ( — ToUo, у*д, — 1]: Ь>0, (л*, y*Q ]<=
е <9<р0 (Тд, Уд), Уд (ф0 (^, IJ д) — = 0]. (5.67)
Аналогично
[con (.Vi — z0)]* = [ — Yi k.’, У*, о]: >0,
(7, J/П е= дф;(.т0, Уд), YiTi (.Гд. Уд) = 0J,
(5.68)
(26
Наконец,
con (Мт+1 — z0) con (gf a — z0)x {у0 — уЦ : V° e £11,
и поэтому
[con (Л/т+1 — z~0)]* = K* (zo)x{o}- (5.69)
В последней формуле учтено, что когда yQ пробегает
все Е1, то и yQ — у% пробегает всю прямую Z?1, а конус,
сопряженный ко всей прямой, может состоять лишь из
единственного элемента 0^ Е1.
Пусть теперь у*> Ф0(х1> Uih где tat, yj точка,
фигурирующая в предположениях. Положим =
{-ГрУп У?) еХхУхА4. Очевидно, что Zi^Mh
i = 0, 1, ..т, /?г+ 1, и при f = 0, 1, ..., т она явля-
ется внутренней точкой Mt. Этот факт справедлив оче-
видным образом и для соответствующих конусов воз-
можных направлений. Поэтому согласно теореме 1.11
К'а (z0) = S [con (Mi - z~)]‘.
i—0
Подставляя сюда выражение (5.67) —(5.69), с учетом
того, что <р0 (z0, у Q) — у о = 0, получаем
К~ £) = [— То U'o> !/о> — 1) — 2 Yi У*, 01 +
+ U'*,y*,0]: у,>0, [z*, у*) е dtp, (z0, y0),
f = 0, Yi<Pi (z0, y0) = 0, i =
{.T*,y*}eZ<:(z0)}. (5.70)
Вспомним теперь, что / (я) = TF~ (я, 0, 1) и поэто-
му согласно теореме 5.13 df(x°) = a*({0, 1); z0). Исходя
из определения а* и формулы (5.70), получаем
д! (*о) = IТот* + 2 Ti'H —х*'- — 2 Yil/Г-i-J/* = 0,
I i=l г=о
у0 = 1, [z*, у*| е 5ф1(т|), у„), i = 0, .т,
* 1
Уо) = °> г = 1, .... т, {z*, у*} <= Ка (z0)J.
126
Учитывая, что теперь у() = 1 п заменив х* на —я*,
окончательно получаем формулу
(т
''о + 2 V;-’ * г а* (//*; 20): у*й 4-
г—1
т
+ 2 УгУ* = У*, к*< У* 1 е дф; (т0, г/0),
i-1
i = 0, .. ., т, 0, Yicpi (<г0, у0) = -О, г = 1, . .., j.
(5.71)
Сформулируем окончательный результат.
Теорема 5.14. 'Пусть ср/я, у), i = 0, ..т,— не-
прерывные выпуклые функции, а а — выпуклое ото-
бражение, существует такая точка {^f, z/J е gf а, в ко-
торой ф£(^и z/t)<0, i = 1, .. ., m. Пусть, кроме того,
нижняя грань в (5.66) при х = конечна и достига-
ется в точке у0. Тогда справедлива формула (5.71).
Важность формулы (5.71) определяется тем, что она
позволяет судить об изменении величины минимума
некоторой функции, когда меняются не только пара-
метры, входящие в эту функцию, но изменение этих
параметров влияет на форму области, в которой ищет®
ся минимум.
ДОПОЛНЕНИЕ
О НЕКОТОРЫХ СОВРЕМЕННЫХ
НАПРАВЛЕНИЯХ В ТЕОРИИ
НЕОБХОДИМЫХ УСЛОВИЙ ЭКСТРЕМУМА
1. Материал, изложенный в основном тексте книги, отража-
ет ситуацию, сложившуюся в начале 70-х годов. Цель этого до-
полнения— дать читателю некоторые представления о тех на-
правлениях, которые сформировались за носледние годы. Естест-
венно, что небольшой объем не позволяет дать доказательств.
Исследования по необходимым условиям экстремума в пос-
ледние годы были связаны в основном с более детальным изуче-
нием задач, в которых участвуют негладкие функции. При этом
на первый план выдвигаются два аспекта: широкое использова-
ние техники выпуклого анализа для невыпуклых задач и учет
негладких ограничений типа равенства. На взгляд автора ис-
пользование техники выпуклого анализа в невыпуклых задачах
привело скорее к приданию более законченной и изящной
формы формулировкам теорем в уже исследованных задачах,
чем к получению принципиально новых результатов. Не так
состоит дело с ограничениями типа равенств. Техника изучения
этих органичений была связана с той или иной формой теорем
о неявных функциях. Поэтому всякое обобщение этих теорем
немедленно приводило и к новым формулировкам в теории не-
обходимых условий экстремума. С такого сорта результатами
читатели могут ознакомиться по исследованиям, проведенным
в [10], [1Д], [4Д].
Кроме того, был получен ряд результатов, и достаточно оо-
щих, в которых теоремы о неявных функциях не используются
[5Д]. Ниже мы не будем касаться обобщений, связанных с ра-
ботами [10], [4Д], и сосредоточимся на тематике, связанной
идейно с работой [5Д].
2. В ряде работ (в частности, см. [5Д]) Ф. Кларк ввел по-
нятие субдифференциала для локально лппшицевой в В функ-
ции /(2). Положим для такой функции
FUi=hin sup ------------у---------. (1)
0 А-^0 X10 Л
Замечательно, что, несмотря на невыпуклость /, функция FQ(x, х)
выпукла и положительно однородна по х и
[ЛД*, х) 1 <
128
Поэтому она непрерывна по т в нуле и имеет смысл определе-
ние субдифференциала / в точке х ио формуле
д J (х) == d-F (х, 0) = lx* s В*'. F (х, х) х* (x)t is 5).
(2)
Оказывается, что если х, x-t -+х*, xi е dj (xfi, то 0Qf(x)t
т. е. многозначное отображение x-^dof(x) полунепрерывно свер-
ху по х.
Несмотря на хорошие свойства субдифференцпала dj(x),
его использование в необходимых условиях экстремума не всег-
да приводит к удовлетворительному результату. Дело в том, что
локальное поведение невыпуклой и негладкой функции в ок-
рестности точки х не всегда достаточно точно можно описать
с помощью Fq(x, i7). Поэтому возникает идея с каждой точкой
связать семейство аппроксимаций, каждая из которых достаточ-
но хорошо отражает локальное поведение по какой-то части на-
правлений. Эга идея оформляется с помощью следующих опре-
делений.
Пусть f(x) — функция, заданная па В и принимающая как
конечные значения, так и значения ±оо. Положим
и для х е dom /
dom f = {z: |/(z) | < + ос}
F (z, x) — lim sup
y-rx 1 О
/ (a + A.y) — / (*)
Л
(3)
Очевидно, что функция F(x, x) —конечная или бесконечная —
существует всегда. Скажем теперь, что к(х, х) есть верхняя
выпуклая аппроксимация (сокращенно — в. в. а.) / в точке я,
если h(x, х) выпукла, положительно однородна и замкнута по
X, и
Л (А х) > F(x, .г), х 0.
Функция Л, очевидно, определена не однозначно. Поэтому,
стремясь реализовать вышеуказанную идею, следует с каждой
точкой х связывать возможно более широкое семейство в. в. а.
Очевидно, что для липшицевой функции FQ(x, х) всегда есть
в. в. а.
Для иллюстрации рассмотрим функцию /(д?) = — [j|, хе
s Е'. Нетрудно посчитать, что
Fo(0, х) = |х|,
F(0, х) =-И,
и поэтому Л(0, х) = кх, к е [—1, +1] есть в. в. а. Тем самым
вместо одной верхней выпуклой аппроксимации получается це-
лое семейство таких аппроксимаций.
Так как /?(.г, х) положительно однородна, выпукла и замк-
нута, то согласно результатам § 1 множество
df(x) - d-h(x, 0) = {z* S В*: Л (z, х) х* (х),х s В} (4)
К
9 В. Н. Пшеничный 1^9
не пусто, имеет место формула
h (х, х) = sup {x* (x): x* e df (x) }, (5)
*
X
и можно соотношение (4) взять в качестве определения субдиф-
ференциала / в точке х. При этом субдифференциал всегда свя-
зан с некоторой в. в. а., и эта связь отражается полностью фор-
мулами (4) и (5). В частности, F0(x, х) соответствует субдиф-
ференциал Ф. Кларка drf(x). Для приведенного выше иллюстра-
тивного примера с>о/(О) — [—1, +1], по каждое число К е [—1,
+1] также является субдифференциалом в смысле введенного
определения.
В [2Д], [ЗД] рассматривалось обобщение введенных в этой
книге квазидифферепцируемых функций. А именно, рассматри-
ваются лишпицевы функции, дифференцируемые по направле-
нию в точке х и такие, что производная по направлению имеет
специальный вид
/' (х, х) = max х* (х) -f- min у*(х), (6)
х*ед/(х) v*ea?(x)
где df(x) и д{(х) — выпуклые ограниченные множества в В *.
Нетрудно видеть, что для таких функций
h (х, х) = max х* (х) + у* (х), у* с=д/(х), (7)
х*ед/(х) ’
есть в. в. а., а 5/(х) + у *, у* е dj(x) — соответствующий суб-
дифференцлал.
3. Верхние выпуклые аппроксимации и соответствующие
субдифференциалы могут быть вычислены для широкого клас-
са функций. Совершенно ясно, что обычные гладкие функции,
имеющие производную в смысле Фреше — /'(х) <= В *, допуска-
ют верхнюю выпуклую аппроксимацию, так как для них
Г(т, х) =/'(т)(1),
т. е. F(x1 х) есть просто линейный по х функционал, и поэтому
в. в. а. совпадает с F(x, х), а субдифференциал состоит из одной
точки — f'(x).
Далее, в [5Д] показано, что если / — выпуклая функция и
х — ее точка непрерывности, то
^о(л х) f'(x, х),
и субдифференциал по Ф. Кларку dof(x) совпадает с обычным
субдифференциалом выпуклой функции в смысле определений
п. 3 § 1 этой книги.
Чтобы не осложнить изложение излишними техническими
деталями, всюду в дальнейшем будем предполагать, что /(х) —
непрерывные в рассматриваемых точках х функции, а соответ-
ствующие этим точкам в. в. а. существуют и непрерывны по
х. Тогда легко видеть, что на основании известных свойств вы-
пуклых функций (см. § 1 этой книги) справедливы следующие
утверждения,
130
1) Если /(x) =/i(x) + /г(^) и h^x, f), h2(x, х) — соответ-
ствующие /1 и /2 в. в. а., то
х) =Л1(.г, 5:) 4—*)
— в. в. а для f(x) и
df(x) = д^(х) + df2(x).
2) Если
/ (х) = max fi (г),
1=1, .т
I (х) = {1: 1 < i< т, f. (х) = / (ж) },
ТО-
h (х> х) = max \hi (х, х): I е Г(х) }
есть в. в. а. для f(x) и
df(x) = со U дЦ (х)
— соответствующий субдпфферепциал.
3) Пусть /0(х) = — /(х), где /—выпуклая функция, т. е«
/о есть вогнутая функция. Тогда
h(r, х) = — х * (х), я*ед0/(я),
— в. в. а. для /о(«г), а — х* — соответствующий субдифференциал
функции /о в точке х, (Напомним, что в данном случае д0/ есть
субдифференцпал по Ф. Кларку, совпадающий для выпуклой
функции / с обычпым субдифференцпалом.)
4) Пусть М — множество в Z?,
d (х | М) = inf { || х — у |]: у е М}
v
^-расстояние х от Я. Тогда d(x\М) — функция, удовлетворяю-
щая условию Липшица с соответствующей константой, равной
единице. При этом если d(x\M) =0, то
h (х, х) = inf [И х — у ||: у <= К AJ (х) ] = d (х | Км (.г) )
X
есть в. в. а. для d(x\M), а
dd(x\M} = S* п (-/СдДх)).'
Здесь S * — единичный шар п В *, а Км (х) — выпуклый конус
касательных направлений к М в точке я, т. е. выпуклый конус
таких направлений х е В, для которых существует функция
г(Х): [0, 1] -> В, удовлетворяющая условиям
lim-L^l=0, г + 1^ 4-г(Х)е М, 2.€=(0,1].
Uo X
Более подробные сведения о технике работы с верхними
выпуклыми аппроксимациями читатель найдет в [20].
4. Обратимся теперь к необходимым условиям минимума/
Следующая теорема является' достаточно простым следствием
определений.
9* 131
Теорема!. Пусть г* — точка минимума функции f на
множестве М. Допустим, что f в точке г* допускает в. в. а.
А(.г»и,.г), непрерывную по х, а К(.г*)— выпуклый конус ка-
сательных направлений к М в точке, х*. Тогда
dj (•*♦) Я (*♦) ¥= 0.
В частности, если М совпадает со всем пространством В, то
0g= dj (.г*).
Подчеркнем существенный момент —- утверждения теоремы
выполняются для любой в. в. а. Чтобы проиллюстрировать, к че-
му это приводит, допустим, что для функции / справедлива фор-
мула (6). Тогда, как сказано выше, dj (х*У -J- //*, у* е dj (х*},
есть субдифференциал /, и поэтому .г* есть точка' минимума /
во всем пространстве, только лишь если
О (= д/ (.г*) у*, у* €= dj Сг*)>
т. е.
— dj (.г*) CZ Я/ (т*).
Использование функций, допускающих в. в. а., в задачах на
экстремум не вызывает никаких затруднений. если они входят
в ограничения тина неравенства. В самом дело, достаточно по-
смотреть на предположение 2 § 4 (с. 66). чтобы попять, что в
качестве функции h, (с). фигурирующей в соотношении (4.3),
можно взять в. в. а. функции ср, (.г), / ^ (). задающей ограниче-
ния типа неравенства в задаче (4.1). К сожалению, с ограниче-
ниями тина равенства так легко обойтись не удается.
Рассмотри м з а д а ч у
min {/0('r): И=Г,х^М}, (8)
где I— конечное множество индексов {1, 2, ../?/}. Положим
V (А) = inf {/о (.г): f. (х) < T,i - 1,х е= М}. (9)
Очевидно, что Р(л) при л 0 — невозрастающая функция.
Г е о р е м а 2. Пусть г* — решение задачи (8) и
iiif ге.)-г((»_ = _л, (10)
Х>0 л 0
Тогда для Аг > .Vo все решения задачи (8) одновременно явля-
ются решениями задачи
П>iИ {/0 (х) .Vf (х): х <= М),
(Н)
Г(х) = тах{0, Ц (х), ..fm (х) }.
И наоборот, если
liminf ПО-ПО) ._лг >_те> (12)
X I о 0
то существует такая достаточку малая открытая окрестность Q
1Я2
точки что т* есть точка минимума в задаче
min |/0 (х) 4" АТ (я): х е М, х s Q}. (13)
30
Доказательство этой теоремы мы оставляем читателю. Подобная
теорема рассматривалась в [5Д].
Из этой теоремы и теоремы 1, используя приведенные выше
правила вычисления верхних выпуклых аппроксимаций и суб-
дифференциалов, без труда получается следующий результат.
Теорема 3. Если выполнено условие (12), то, для того
чтобы точка х* была решением задачи (8), необходимо, что-
бы нашлись такие числа и\ i = 1, ..m, и функционал х* s
е А'*/7'*)’ ЧГ°
х* е= dfQ (.г*) У и{дЦ(х>),
г=1
и* 0, uifi (х*) = 0, I = 1, ..тп.
Выполнение условия (12) позволяет на самом деле рассмат-
ривать и ограничения типа равенства, так как каждое равенство
fi (х) == 0 эквивалентно двум неравенствам
А (я) < 0, —Л (х) < 0.
В качестве иллюстрации приведем результат для задачи мини-
мизации выпуклой функции при ограничениях типа равенства
min {fQ(x): fi(x) =0, i = 1, ..m}, (14)
где fi (x) — также выпуклые функции.
Теорема 4. Пусть х* — решение задачи (14),
У (X) = inf {/0 (я): | /i (х) | < X, i-1,
lim inf
x j о X
Тогда для любых функционалов
х* « dji (z*), t = 1, ..., m,
найдутся такие числа i = 1, ..mt что
m m
У, u-x* « Vo (*♦) + 2 “+Vi)>
i=l i^l
> 0, > 0, i == 1, ..., m.
(Напомним, что знак д$ обозначает обычный субдпффереи-
циал выпуклой функции.)
Из сказанного видно, что предположение о выполнении (12)
практически снимает все проблемы с получением условий ми-
нимума. Однако это предположение трудно проверяемо. Пожа-
луй, единственное просто проверяемое условие, которое гаран-
тирует выполнение (12), состоит в следующем: если функция
А» i ж 0, ,, м т, и множество М в (8) выпуклы и существует
13Э
такая точка ri е Л/. что f.(xi) < 0, / == 1. т, то выполнено
соотношение (10). При этом в качестве Л70 можно взять сумму
компонент вектора Куна — Таккера задачи (8).
Таким образом, усилия должны быть направлены па то,
чтобы заменить неравенство (12) более эффективно проверяе-
мым условием. Это конечно невозможно сделать без некоторых
дополнительных предположенпй.
В [5Д] доказана следующая теорема:
Теорема 5. Пусть х* есть точка минимума в задаче
min {/о(^): fi (z) < 0, i е 7~, /,(г) =0, I е 7°, х е Л7},
где все fi — локально липшицевы функции. Тогда существуют
не все равные нулю числа u°, и‘, i е 1~ U 7°, и вектор х* е
е Км (,гф) такие, что
X* е и°50/0 (х») 4- У u'dj, (хф),
ie7~U/°
0, и{^>0, (^*) — 0, I е 7Л
Эта теорема доказана без какого-либо использования теорем
о неявных функциях, но зато использует теорему И. Эклапда
[6Д], которую мы приведем в силу ее самостоятельной важно-
сти и широты приложений.
Теорема 6. Пусть F(x)—непрерывная и ограниченная
снизу на множестве Л/ функция. Пусть е >> 0. Если .v <= М удов-
летворяет условию
F(x) < inf {F(x); х е Л/} + е,
то существует такая точка z е Л/, что
Г(х) +уе||х-г|| F(z.)^ те Л/.
5. Приводимые ниже теоремы формулируют необходимые
условия экстремума в терминах верхних выпуклых аппроксима-
ций. Эти теоремы получены автором совместно с Р. Хачатряном.
В этих теоремах наложены определенные ограничения па функ-
ции, входящие в задачу, но зато получаются более полные ре-
зультаты.
Расматрпвается задача
П1*П(/0(;г): /fW<0> g(x) = 0].
Пусть г* —точка Минимума. Обозначим через (т Д),
х), h~ т), и hi, i ±= 1, ..m, — в. в. а. для /0, g+ = g,
g~ = g и fi в точке x*.
Теорема 7. Пусть fi, i = 1, ..., ni, и g непрерывны в не-
которой окрестности точки х*, h+, h~ и )ц, i = 1, ..., т, непре-
рывны по х, и существуют такие w\, w2 е В, что
Л+(х*, иц) < 0, (х*, u>j) <0,
и’2) < 0, 7ц (х*, ш2) < 0
при
t s /(хо) = {(: /г(х0) == 0}.
134
Тогда либо существуют числа 0, О такие, что
m
(*о) + S *М),
- 1-1
'vi Л (хо) = °’ i =
либо существуют числа К О, ^0 такие, что
тп
0 е Ч (*#) + '~д^~ (л>) + S МА (*<,)-
<=1
АШ) = 0’ i = t •••>'"•
В качестве характерной иллюстрации применения теоремы 7
рассмотрим условия, при которых гладкая функция /о(^), х s
е R2, может достигать своего минимума на поверхности
2 1 • ( 1
х =« х sin —г- L
Теорема 7 приводит к следующему результату: если х = 0
есть точка минимума /0 на указанной поверхности, то
% (°)
дхх
*/,«>)
да?
Насколько нам известно, этот результат не может быть получен
ни одним из известных ранее методов.
Следствие {.Пусть /0 и f\— непрерывные выпуклые
функции и х* —точка минимума fo(x) при ограничении fa(x)=^
— 0. Тогда либо существуют не равные нулю одновременно
числа 2.0 0, Xi. 0 такие, что
0 Хо^о/оС^о) + Xi50/i(^o)»
либо
dofdxo) s con 50/о(х0),
еде
con М = {tx: t > 0, х €= М}.
Замечание. Напомним, что для выпуклых функций dQf
совпадает с обычным субдифференциалом.
Следствие 2. Пусть /0 — непрерывная и выпуклая, .gf,
ге/, — гладкие функции, а [—конечное множество индексов.
Если х* — решение задачи
min {/ (х): / (х) =s max (х) = о),
« i 0 1 iei J
а
Цхо} = {1 е gi(x0) = 0},
то либо существуют не все равные нулю числа Хо 0, О
135
такие, что
Ое Wo(<h-s >-Ze0).
MiWs0- /еЛ
либо
«' (То) s con да1й (хй), < е / (х0).
Пусть теперь В — Rn конечномерно.
Теорема 8. Пусть х* —точка минимума в задаче
min{/o(z).- fi(z) 0, ie 7~, /i(x) = О, I = 7°},
еде 7~, 7°— конечные множества индексов, и выполнены условия
1) i s {0} (J 7" U 7°, ~ непрерывные в окрестности х*
функции;
2) М (*».*)’ i G= {0) J I (J 7°,— в. в. а. для fi, непрерывные
по х;
3) Л“ (х, х), i е 7°, — в. в. а. для — существуют векторы
Wi такие, что
hi (**’ wi) <°»
Л"(хф>ш.)<0,
и функции (х, и*-) полунепрерывны сверху по х в точке
х*, i 6= 7°;
4) dff,df~ — соответствующие h'f и h~ субдифференциалы.
Тогда существуют такие числа М > 0 , i е {0} U и
* j г0
торы х^, is / , что
os 2 М/Г (*»)+ S ХЬ
ie{0}U7~ 4^1°
^ifi (г.) = 0, is I~,
x* e [con 5/+ (x.) + con df~ (x.) ],
к Xi, Xj не все одновременно равны нулю.
БИБЛИОГРАФИЧЕСКИЙ КОММЕНТАРИЙ
Целью этого комментария является указать читателю на
те основные источники, по которым он сможет более углублен-
но изучить вопросы выпуклого анализа, теории недифферевци-
руемых функций, необходимые условия экстремума и их раз-
личные применения. Там же даны подробные ссылки на ориги-
нал ь н ы е и ст о ч н п к и.
1. Сведения из функционального анализа, используемые в
книге, вполне элементарны. Их можно найти в первых главах
книги II. Данфорда и Дж. Шварца [5] и в монографии Ж. Дье-
донне [9].
2. Теории выпуклых множеств и функций посвящепа огром-
ная литература. Различным вопросам этой теории уделяется
много места в монографиях А. Д. Иоффе и В. М. Тихомирова
[10], II. Ж. Лорана [13], Б. II. Пшеничного [20], Р. Т. Рока-
феллара [21].
3. Теория выпуклого и, в частности, линейного программи-
рования — наиболее полно и детально разработана. В частно-
сти, существенным разделом этой теории является двойствен-
ность выпуклых программ, которая широко используется как
в чисто теоретическом плане, так и при построении численных
алгоритмов. Линейное программирование и обширная литера-
тура по этому вопросу содержится в книге Дж. Данцига [6].
Различные вопросы выпуклого программирования подробно ос-
вещены в книгах Е. Г. Гольштейна [3], [4], Б. И. Пшеничного
[20], Р. Т. Рокафеллара .[21].
4. Педпфферепцпруемые функции прочпо вошли в обиход
современного анализа и их свойства широко используются в не-
обходимых условиях экстремума. Исследованию различных
классов таких функций посвящепа значительная литература.
Фактически, может быть не всегда в явной форме, анализ таких
функций проводился уже на ранпих этапах разработки теории
необходимых условий и отражен в статье А. Я. Дубовицкого и
А. А. Милютина [8|. в монографиях В. Ф. Демьянова и
В. II. Малоземова [7]. Л. Нойштадта [16]. Дальнейшие ссылки
но этому вопросу можно найти у 15. И. Пшеничного [20].
5. В § 4 приводятся далеко не самые общие теоремы об аб-
страктных необходимых условиях экстремума. Развитию этих
условий п их обобщениям и вариантам посвящены монографии
И. В. Гирсанова [2]. А. Д. Поффе и В. М. Тихомирова [10L
П. Ж. Лорана [13], Л. Нойштадта [16], Б. II. Пшеничного [20].
6. § 5 данной книц! должен был в какой-то мере отразить
многообразие и содержательность абстрактных теорем о необ-
137
ходимых 'условиях экстремума. Естественно, что при малом
объеме это удалось лишь в очень скромной степени. Более под-
робно с различными приложениями можно познакомиться по
книгам В. Г. Болтянского [1], А. Д. Иоффе, В. М. Тихомирова
[10], С. Карлина [11], II. II. Красовского [12], II. II. Моисеева
[15], Л. С. Понтрягина, В. Г. Болтянского, Р. В. Гамкрелидзе,
Е. Ф. Мищенко [18], А. И. Пропоя [19], В. М. Тихомирова [23].
Интересную область приложений представляет собой мате-
матическая экономика, где, по-видимому, возможность использо-
вания далеко не исчерпана. С этой проблематикой можно позна-
комиться по книгам В. Л. Макарова, А. М. Рубикова [14],
X. Никайдо [17]. Перспективная область исследований — тео-
рия многозначных отображений и их применение отражена в
монографиях В. Л. Макарова, А М. Рубипова [14], Б. II. Пше-
ничного [20], А. М. Тер-Крикорова [22].
ЛИТЕРАТУРА
1. Болтянский В. Г. Оптимальное управление дискретны-*
ми системами.— М.: Наука, 1973.
2. Гирсанов И. В. Математическая теория экстремальных
задач.— М.: МГУ, 1970.
3. Г о л ь ш т е й н Е. Г. Выпуклое программирование. Эле-
менты теории.— М.: Наука, 1970.
4. Гольштейн Е. Г. Теория двойственности в математиче-
ском программировании.— М.: Наука, 1971.
5. Д а н ф о р д Н., Шварц Дж . Т. Линейные операторы.
Общая теория.— М.: ИЛ, 1964.
6. Данциг Дж. Б. Линейное программирование, его приложе-
ния и обобщения.— М.: Прогресс, 1966.
7. Д е м ь я н о в В. Ф., М а л о з е м о в В. Н. Введение в ми-
нимакс.— М.: Наука, 1972.
8. Д у б о в и ц к и й А. Я., Милютин А. А. Задачи на экст-
ремум при наличии ограничений.— ЖВМ и МФ, 1965, т. 5,
№ 3, с. 395—453.
9. Дьедонне Ж. Основы современного анализа.—М.: Мир,
1964.
10. Иоффе А. Д., Тихомиров В. М. Теория экстремаль-
ных задач.— М.: Наука, 1974.
11. Карлин С. Математические методы в теории игр, про-
граммировании и экономике.— М.: ИЛ, 1964.
12. К р а с о в с к и й Н. И. Теория управления движением.— М.:
Наука, 1968.
13. Лоран П. Ж. Аппроксимация и оптимизация.—М.: Мир,
1975.
14. Макаров В. Л., Р у б и н о в А. М. Математическая-тео-
рия экономической динамики и равновесия.—М.: Наука,
1973.
15. Моисеев Н. Н. Численные методы в теории оптимальных
систем.— М.: Наука, 1971.
16. Неиштадт Л. (Neustadt L.) Optimization: a Theory of
Necessary Conditions.— Princeton University. Press., 1976,
17. Ник ай до X. Выпуклые структуры и математическая эко-
номика.— М.: Мир, 1972.
18. И о н т р я г и н Л. С., Б о л т я н с к и й В. Г., Гамкрелид-
з е Р. В., М и щ е н к о Е. Ф. Математическая теория опти-
мальных процессов.— М.: Физматгиз, 1961.
19. Пропой А. И. Элементы теории оптимальных дискретных
процессов.— М.: Наука, 1973.
20. Пшеничный Б. Н. Выпуклый анализ и экстремальные
задачи — М.: Наука, 1980,
139
21. Р о кафе л л ар Р. Т. Выпуклый анализ.— М.: Мир, 1973.
22. Тер -Кри коров Л. М. Оптимальное управление и мате-
матическая экономика.— М.: Наука, 1977.
23. Тихомиров В. М. Некоторые вопросы теории приближе-
ний.—М.: МГУ, 1976.
ЛИТЕРАТУРА К ДОПОЛНЕНИЮ
1Д. Болтянский В. Г. Метод шатров в теории экстремаль-
ных задач,—УМ II, 1975, 30, 3, с. 1—55;
2Д. Д е м ь я н о в В. Ф., Полякова Л. И. Условия минимума
квазидифферепцируемой функции на квазидифференцируе-
мом множестве.— ЖВМ и МФ, 1980, 20, 4, с. 819—856.
ЗД. Д ем ь ял о в В. Ф., Р у б и н о в А. М. О квазидифференци-
руемых функционалах,—ДАН СССР, 1980, 250, 1, с. 21— 25.
4Д. Д м и т р у к А. В., М и л ю т и п А. А., О с м о л о в с к и й II. П.
Теорема Люстерника и теория экстремума.— УМН., 1980, 33,
5, с. 11—16.
5Д. Кларк Ф. X. (Clarke F. II.). A new approach to Lagrange
multipliers.— Math of operations research, 1976, 1, 2.
Necessary Conditions.—‘Princeton University. Press.. 1976.
6Д. Экланд И., Темам P. Выпуклый анализ и вариацион-
ные проблемы.— М.: Мир, 1979.
II РЕ ДМ ЕТНЫЙ УКАЗ АТЕ Л Ь
Базис топологии 14 Бикомпактность 16 Вектор Куна — Таккера 52 Задача.двойственная 55 — чебышевского приближения 83 Компактность 16 Конус выпуклый 31 — двойственный 31 — касательных направлений 73 — сопряженный 31 Множество 13 — бикомпактное 16 — выпуклое 26 — , замкнутое 14 — , замыкание 14 — компактное 16 — окрестность 13 — открытое 13 Надграфик функции 35 Область определения функции 35 — эффективная 122 Оболочка 28 — выпуклая 28 замкнутая 29 Окрестность множества 13 — точки 13 Оператор 19 — сопряженный 26 Отображение 15 — выпуклое 123 — , график 122 — многозначное 122 — непрерывное 15 — , эффективная область 122 Покрытие 16 Последовательность фундамен- тальная 22 Проблема моментов 104 Принцип двойственности 95 Производная 25 — Гато 25 — по направлению 43 — Фреше 25 Пространство 18 — линейное 18 — метрическое 16 — нормированное 18 — полное 23 — , прямое произведение 17 — сопряженное 19 — топологическое 13 — — хаусдорфово 14 — С [0. ‘1] 25 23 Субградиент 44 Субдифференциал 44, 57 Сходимость 14
141
Теорема двойственности 55
— Куна — Танкера 71
— о минимаксе 81
— Хелли 104
Топология множества 13
— сильная 20
— слабая 21
Точка внутренняя 13, 27
Функция замкнутая 38
— квазидифференцируемая 57
— Лагранжа 52
—, надграфик 35
— положительно однородная
41
— полунепрерывная снизу 39
— собственная 35
г- сопряженная 39
Функционал линейный 20
Функция 35
— выпуклая 35
Цены равновесные 116
СОДЕРЖАНИЕ
Предисловие ко второму изданию ....... 5
Предисловие к первому изданию........................ 7
Введение. Элементы функционального анализа и вы-
пуклые множества . ................13
1. Основные положения функционального анализа ' . 13
2. Выпуклые множества........................- 26
§ 1. Выпуклые функции ......... 35
1. Определение и основные свойства...............35
2. Сопряженные функции..................... . 39
3. Субдифференциалы выпуклых функций . , , 42
§ 2. Выпуклое программирование.......................49
§ 3. Квазидифференцируемые функции...................57
§ 4. Необходимые условия экстремума в общих задачах
математического программирования..................65
§ 5. Необходимые условия экстремума в конкретных за-
дачах . .................................77
1. Классическая задача математического программи-
рования . ж....................................78
2. Математическое программирование с континуумом
ограничений.............................. 79
3. Теоремы о минимаксе.................. 81
4. Задачи чебышевского приближения .... 83
5. Задача линейного оптимального управления с фа-
зовыми ограничениями...........................90
6. Принцип двойственности в выпуклом программи-
ровании .......................................95
7. Система выпуклых неравенств. Теорема Хелли . 100
8. Проблема моментов.......................... 104
9. Равновесные цепы.............................115
10. Многозначные отображения и параметрические за-
дачи выпуклого программирования .... 122
Дополнение. О некоторых современных направлениях
в теории необходимых условии экстремума . . . 128
Библиографический комментарий.................137
Литература....................................139
Предметный указатель................... 141
Борис Николаевич Пшеничный
НЕОБХОДИМЫЕ УСЛОВИЯ ЭКСТРЕМУМА
(Серия: «Оптимизация и исследование операций»)'
Редакторы М. М. Горячая, Л. Ф. Лапке
Технический редактор Е. В. Морозова
Корректор Е. А. Белицкая
ИВ ЛЛ 12114
Сдано в набор 18.12.81. Подписано к печати 03.08.82.
Т-11123. Формат SAxlOS1/^. Бумага тип. 3. Обык-
новенная гарнитура. Высокая печать. Условн. прч.
л. 7,56. Уч изд. л. 7,1. Тиран: 9500 экз. Заказ М 838.
Цена 55 коп.
Издательство «Наука»
Главная редакция
физико-математической литературы
117071, Москва, В-71, Ленинский проспект, 15
4-я типография издательства «Наука»
030077, Новосибирск, 77, Станиславского, 25.
55 коп