Б.Н. Пшеничный - Выпуклый анализ и экстремальные задачи

22лйз П98 УДК Ы9.6 Серия еНелинейный аналог и его нриложенияз вынускается иод общей редакцией Н, Н. Боголюбова, М. А, Ьрасносельского, Ю. А. Митроиольскозо © Главная релакнкя йкзкко-математической литературы издательства «наука». зээе к 202и — в10 бе.вз.

вв2оюхО 053(02)-80 Выпуклый анализ и экстремальные задачи. П ш е н н чн ы й Б. Н.— Мл Наука. Главная редакция физпко-математической литературы, 1980, Книга написана на основе курса лекций для студентов старших курсов факультета кибернетики Киевского государственного университета. Она посвящена научению широкого класса экстремальных задач, испольаующяхся при разработне математическпх моделей экономических и производственных процессов.

Отражены хорошо развитые с точки зрения вычислений новые подходы п методы. ОГЛ.4ВЛЕБИЕ Предисловие Г л а в а !. Выпуклые иножества $1. Общие свойства выпуклых множеств 1 2. Теорема отделимости 9 3. Выпуклые конусы $4. Крайние точки и многогранные множества Глава П. Выпуклые фуинции..... ° . 1 1.

Основные свойства выпуклых функций 9 2. Сопряженные функции $ 3. Производные по направлениям н субдифференциа- лы 133 133 Глава $1. 9 2. 13 ; ;4 15 $6 Глава $1. 6 2. 187 187 205 Глава 1 1. 9 2. 1 3. $ ~~, П!. Выпуклые многоышчные отображения Основные определения и свойства Локально сопряженные отображения Примеры выпуклых многозначных отобра;кенни Теорема двойственности для выпуклых многознач- ных отображении 1Ч. Выпуклое программирование Линейное программирование Необходимые условия экстремума в выпуклом про- граммировании Двойственные задачи выпуклого программирования !!екоторые задачи теории приближений 8адачи наилучшего равномерного приближения Модели энономической динамики т.

Необходимые условия экстремума Конусы касательных направлений и шатры Функции, допускающие верхнюю выпуклую аппро- ксимацню 7 7 17 24 37 95 95 10! 1!3 142 1э4 158 163 169 Огпхи1ТЕНИН 3 3. Отобра>кения, локально сопряженные к многозначным отображениям......, .. 224 3 4. Общие необходимые условия минимума... 241 310 Литература Предметный укааатель 318 Глава Ч1, Необходимые условна в задачах управления 1. Дифференциальные включения $2. Задача оптимального управления с временем $3. Необходимые условия минимума для альных включений Библиографический комментарий Указатель основных обоаначений оптимальиоге 263 264 дискретным 272 диффсреицн- 280 ПРВДИСЛОВИЕ Настоящая книга возникла в результате систематизации материала лекций, которые автор читал последние восемь лет на факультете кибернетики и механико-математическом факультете Киевского государственного университета нм.

Т. Г. Шевченко. Опыт, накопленный при чтении лекций, обусловил структуру книги и ее содержание. В последние годы теория экстремальных задач приобрела достаточно законченную форму и может быть в систематическом виде изложена для широкого круга читателей. Конечно, это не значит, что книга может читаться совсем легко. Как всякая математическая книга, она требует от читателя активной работы, но в целом овладение излагаемыми ниже понятиями и результатами не требует каких-лабо знаний, выходящих за рамки стандартных курсов математического анализа и линейной алгебры. Это достигается за счет того, что все изложение ведется в конечномерных пространствах. Однако этот факт нри формулировке теорем и доказательств не используется, если только он не необходим по существу дела. Поэтому читатель, знакомый с функциональным анализом, легко поймет, как тот пли иной факт может быть обобщен на случай пространства произвольной размерности.

Первые четыре главы составляют самостоятельное целое и содержат изложение общей теории выпуклого программирования. В основном приводимые здесь факты хорошо известны. Однако при выборе способа изложения был сделан упор на теорию многозначных отображений. Это позволило существенно сократить н унифицировать доказательства н показать, что многие известные теоремы есть в сущности различные формулировки одного и того же факта выпуклого анализа. Кроме того, многозначные отображения в последние годы становятся областью исследований, привлекающей значительное число матема- пгедисловик тиков, и знакомство широкого читателя с ними будет полезным.

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

Это позволило рассмотреть негладкие задачи оптимального управления и одновременно проиллюстрировать, как работает понятие локально сопряженного отображения к многозначному отображению. Ограниченный объем книги не позволяет охватить многие интересные приложения общей теории экстремальяых аадач. Приводимый в конце книги список литературы даст возможность читателю сориентироваться в современной монографической п обзорной литературе и углубить свои знания по отдельным вопросам теории п многообразным ее применениям. Б. Н. Пшеничный Киев, февраль 1978 г. Глава 1 ВЫПУКЛЫЕ МНОЖЕСТВА Б этой главе рассматриваются основные свойства выпуклых множеств.

5 $. Общие свойства выпуклых множеств Будем рассматривать векторы х, принадлежащие я-мерному вещественному пространству Х= К". Будем рассматривать также его дубликат — пространство Хе В. Обычно в дальнейшем скалярное произведенпе двух векторов х п хе (хжХ, хе~вХе) будет обозначаться следующим образом: (х, х') = ~, х х 1 ° 1=1 где х' и х'* — компоненты векторов х и х* соответственно. Поясним, почему сделано различие между двувгя и-мерными пространствами Х и Х*.

Дело в том, что элементы из Х* будут играть роль линейных функций, заданных на Х. Хорошо известно, да зто к несложно показать, что любая линейная функция иа Х вЂ” ((х) — может быть задана некоторым вектором х* так, что Нх) = = <х, х*>. Чтобы подчеркнуть тот факт, что вектор х* задает некоторую линейную функцию, введено такое обозначение. 1.

Определение выпуклых множеств. Определение $.1. Множество М называется выпуклым, если вместе с каждыми своими двумя точками х~ п хз оно содержит и весь отрезок, ил соединяющий, т. е. точки вида й щ + ) тхз ~ ))у, Лп Лз~О, Х~+Хз=1. Пустое множество И будем считать выпуклым по опре- делению, Гл. 1. Выпуклые множества Отметим некоторые простейшие свойства выпуклых множеств. Д е м и а 1 1. Пусть Х вЂ” произвольное множество индексов 1, М, выпукло для каждого 1!ПХ.

Тогда множество М=ПМ! 1Я1 также выпукло. Доказательство. Если х! и хг принадлежат М, то х1 хз ~ Мь 1 ли Х~ и Л1х! + Л2х2 ля М! для любого 11и Х, т. е. Л1х1+Лзхг БАЛХ. Л е м м а 1.2. Если множества М! и М2 выпуклы, с1, с2 — вещественные числа, то множество с1М1+с2М2 выпукло. Д о к а з а т е л ь с т в о. Напомним прежде всего, что по определению с1М1+с2М2 есть множество, состоящее из всех точек вида с1х1+сзхз, где х! шМ1, хзжМ2. Теперь доказательство получается просто из определения выпуклого множества.

Определение 1.2. Будем говорить, что точка х является выпуклой комбинацией точек х1, ..., х„, если найдутся числа Ль ..., Л„ такие,что х=Лх+...+Л х, И.1) 1 = 1, ..., ж, Л1+... + Л = 1. Л!>О, Лемма 1.3. Если точки х1, ..., х принадлежат выпуклоллу мнолсвству ЗХ, то множество М содергкит все их выпуклыс комбинации Доказательство удобно провести индукцией по числу точек.

Для пл = 2 утверждение следует из определения. Пусть лемма доказана для т ~ й. Покажем, что х = Л1х1 + Л2х2 + ° ° ° + Ллхл + Лл+1хл+1 ы М для любых Л, таких, что Л!>О, Л!+...+Л„+1 —— 1. По- скольку можно считать, что Л!>О, то 1 — Лл+1=Л1+... ... +Л, ) О.

По предположению индукции Л у= — 'х,+ ... + — хлепИ, 1 — Лл+л ' ' " 1 — Л„+, ф ! Овшне сВОйстВА Выпуклых множестВ 9 ибо Но тогда х = И вЂ” Лмы)у + ЛА+1хь+~ ш М по определению выпуклого множества. 2. Выпуклые оболочки. Если задано произвольное множество, то по нему можно определить некоторое выпуклое множество, его содержащее. О и р е д е л е н и е 1.3. Пересечение всех выпуклых множеств, содержащих данное множество М, называется выпуклой оболочкой множества М и обозначается со М.

Согласно лемме 1.1 со АХ есть выпуклое множество. Так как со йХ содержит М, то по лемме 1.3 оно должно содержать п все точки вида х=Л1х1+...+Л х, Л4)о л3+ ° ° .+л 1 т. е. выпуклые комбинации точек из М. Нетрудно убедиться, что множество точек такого вида само выпукло. Итак, со М содержит множество точек вида (1 1), а, сдругой стороны, по определению само должно в нем содержаться.

Тем самым доказана Лемма 1.4. со АХ есть множество всех выпуклых комоиначий точек иг вХ. Нижеследующая теорема является одной из важнейших в выпуклом анализе. Теорема 1.1. В пространстве Х= В" любую точку соМ можно представить в виде выпуклой комбинации не более чем и+ 1 точек ив М, т. е. для любой хшсо М найдутся хн ..., х„~и М такие, что х = Л~х1 +... + Л,х„ И.2) Л|+ ° ° +Л 1 Л~)0 ° ° л )О где г(п+1. гл.

1, Выпуклые множеств»» ~ а»х» — — О, »=1 (1.З) ~2~~ а» = О. »=1 (1.4) Среди чисел а» обяаательно есть полон'ительные в силу соотношения (1.4). Положим ( Х( ео —— ш(п~ — *: а»)0, 1'=1, ...,т. Пусть минимум достигается прп 1 = »о. Тогда Х; =Х»- еоа» Р'0 для любого 1=1, ..., т. Это очевидно для а»~0, а для а» ) О следует из выбора ео. Теперь из соотношений 1И 1о / о» Х Х»х»= Х)»х — ео~ Х ах» =х »=1»=1»=1 о» о» / о» ХХ;= Х)» — е.~Х »=1»=1»=1 вытекает, что точку х можно представить в виде выпук- лой комбинации меньшего числа ненулевых слагаемых.