Некоторые классы невыпуклых задач исследования операций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

РГб лСЬ^КОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ им. М. В. ЛОМОНОСОВА

2 О ПОП ФАКУЛЬТЕТ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ

И КИБЕРНЕТИКИ

На правах рукописи

АБАСОВ ТЕИМУР МИТАТоглы

НЕКОТОРЫЕ КЛАССЫ НЕВЫПУКЛЫХ ЗАДАЧ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ 01.01.09 — Математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА —

1903

Рг.бота ЕЫполнсиа в Бакинском государственном университете.

Официальные оппоненты:

доктор физ.-мат. наук, профессор АШМАНОВ С. Д., доктор физ.-мат. наук, профессор ДЕМЬЯНОВ В. Ф., доктор физ.-мат. наук, профессор ТРЕТЬЯКОВ Л. А.

Ведущая организация — Вычислительны» центр РАН.

на заседании специализированного совета Д 053.05.38 при МГУ им. М. В. Ломоносова (119899, ГСП-3, Москва, В-234, Ленинские горы, МГУ, факультет ВМнК, ауд. 685).

С диссертацией можно ознакомиться в библиотеке факультета вычислительной математики и кибернетики МГУ.

Автореферат разослан «. . .» ....... 1993 г.

Защита состоится « . . . »

//

часов

Ученый секретарь специализированного совета, профессор

Н. П. ТРИФОНОВ.

Обаая характеристика работы

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

Исходный моментом исследования послужили две задачи, возникающие в приложениях исследования операций:

1) нахождение необходимых и достаточных условий существования характеристик в моделях экономической динамики;

2) отыскание седловых точек при наличии функциональных ограничений на переменные.

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

от условий выпуклости (точнее говоря/ заменяя их условней монотонности, которое вполне естественно соответствует природе экономических объектов), мы получаем гораздо более' общий класс моделей. экономической динамики - управляемые динамические системы. Рассмотрение, некоторых разновидностей управляемых динамических систем без предположений выпуклости является весьма актуальным и проводилось в работах Моришимы, Никайдо и Рубинова в

направлении, связанном с исследованием их устойчивости. В нашей

*

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

вторая задача представляет собой одну из разновидностей минимаксных задач, занимающих центральное место в исследовании операций (не претендуя на полноту, достаточно сослаться на работы Ю.Б. гермейера, Е.Г. Гольштсйна, В.Ф. Демьянова, В.В. Федорова, Р.Рокафеллара). Она была исследована Гермейером и Федоровым на основе метода штр&фных функций. Нами предложен более обший и систематический подход, связанный с концепцией двойственности. Этот подход приводит к обобщению на рассматриваемую задачу теорем двойстгенности, построению модифицированных функций Лагранжа и созданию на их основе численных методов. Особенно важным является то, что двойственный подход распространяется на невипуклые задачи отыскания седловых точек.

Рассмотрение перечисленных вопросов потребовало создания специального аппарата, который на чаш взгляд предстаьляет самостоятельный интерес. Основными элементами этого аппарата но мере возрастания общности являются:

- теория отлелниости нормальных и устойчивых множеств; .

- теория положительно однородных монотонно возрастающих .функций (включая суб- и супердифференциальное исчисление);

- конструкция ^-выпуклых функций;

- конструкции т)£-седловых и слабых т)£-седловых функций.

Применение этого аппарата дало возможность решить вышеупомянутые задачи.

Цели и задачи работы, основной целью диссертации является • создание некоторых конструкций, обобщающих понятие выпуклости, и применение их для решения задач, возникающих в экономической динамике н теории игр.

Методы исследования. Основой методики исследования служит, аппарат теории двойственности, выпуклого анализа, а также специально разработанная техника, связанная с классом положительно однородных монотонно возрастающих, ^-выпуклых и т|£-седловых функций. ■

Научная новизна работы состоит в следующем:

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

2. Введены и исследованы конструкции 'С -выпуклых и оС -седловых функций, обобщающие понятия выпуклой и вогнуто-выпуклой функций. Предложена универсальная схема построения теории

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

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

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

Апробация работы и публикации. Основные результаты работы были представлены иа IV Всесоюзной семинаре по исследованию операция и системному анализу (г.Батуми, ' 1983 г.), научно-технической конференции "Методы математического программирования и их программное обеспеченно" (г.Свердловск, 1984 г.), международной конференции "стохастическая оптимизация" (г.Киев, 1984 г.), а твкге на семинарах в ипк ран, вц Ран, факультета прикладной математики и процессов .управление лгу, факультете вычислительной ыатекатики к кибернетики мгу. по теме диссертации опубликовано 16 работ (все без соавторов)!

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения и списка литературы, содержащего 39 наименований, объек диссертации - 170 страниц.

Содержание работы

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

руются основные результаты, представленные в диссертации.

В первой главе изучается важный класс моделей экономической динамики - управляемые динамические системы, представляющие собой набор положительно однородных (первой степени) монотонных многозначных отображений.

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

. изучение ПОМВФ основано но связи ПОМВФ с так называемыми нормальными и' устойчивы«« шкшествеыи, которые, - не являясь выпуклыми, все ке достаточно удобны для анализа.

Определение 1: замкнутое ыно&ество ПсЛ^ называется нормальным, если или г «Q; х&х , xclt •»

для произвольной точен celf. \{0> введем шгоиестца

К (в) »а+Я%{гей*| х&а}, L (a) ~cl(fT\Kl<x) ). (1)

Определение 2. Пустй п - нормальное множество; a Будем говорить» что а и x"t

а) нормально отделимы, если существует точка такая, что **«(«), Qct(e) ; • '

б) строго нормально отделимы, если существует с>0 и точка \{0} такие, что flc (х*)сК(е), n=L(a);

в) собственно нормально отдел;»:«, если существует с>0 и точка <м=1^\{0} такие, что В£ (x*)fyf сК(о) , ПсЦа).

теорема 1. Пусть П нормальное множество, а х*£П. тогда: X) если x*Gint то О и х* строго нормально отделимы; 2) если if\{0>, то Q и х* собственно нормально отделимы, с точки зрения нормальной. отделимости важную роль играет слабая паретовская граница нножество. Kar. известно, называется . слабо .эффективной в смысле максимума точкой множества п, если не существует такого, что х>х*. Множество всех слабо эффективных в смысле. максимума точек (слабая царетовская граница) множества (1 обозначим через S(0).

Напомним, что конус if имеет 2" граней, причем произвольная И- мерная грань его имеет вид ^"{А-еж") .*4=0, Viel}, где

Теореиа 2. Пусть Q нормальное множество, a r*€S((Jfj ri где 1*0. Тогда П н Анормально отделимы.

Очевидно теореиы 1, 2 являются.аналогами обычных теорем об отделимости выпуклого анализа.- с их поиощью мояпю получить представление нормального, множества Как пересечения содержащих его множеств вида Г,(а). обозначив Л={аС1^\{0} | ficl.(a)}, iieTpv^.j' показать, что

л-{ и ri я.) }U(ñ"\o>.

1*0 •

Леиип i. Пусть С1 норналыюе- мнозкестао. тогда

П=п{£(«> I асЛ}°л№(«) I «6 U S (f3fl ri я )}.

1*0 ,

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

определение з. Замкнутое мнояестпо ХеЛ® называется устойчивым,

если Х=Х+Пп , или х*еХ. ггзг* <■> .тех. ♦

ясно, чтог а) если 0 нормальное ниояество, то с] (я"\П) устойчиво; б) если X устойчиво, то ci (Я^\Х) нормально. Поскольку мему норйальными и устойчивыми множествами имеется довольно прозрачная аналогия, uu приведен, не останавливаясь на подробностях, основной результат, который иоясно ■ получить, действуя по той so сзока, что и вниз. Предварительно напомним, что х*ех называется слабо эффективной п смысла цинимуна-течкой инопества х, если но супэствуот как такого, . что х<х*. множество всех слабо эффективных в сшсло одшшуна точек множества X обозначим через с(х).

лааиа г. пусть X уетойчивоэ мнотастзо, но содаряааае нуль То!'да х-п;х.'(а)| «sAf\int R"}«n(í.' (a)| e¡<£C(X)ftintííj}, где

к' (а)=(а-я;;)пн>{хек?| *sa>, V (а)-сЦ%\К' (.«))• (2)

Отвлекаясь от геометрического содержания определения 1, следует подчеркнуть, что отделение фактически осуществляется с помощью некоторых, специальных функций, не являющихся линейными:

Q„(jf) = ®ах i—il, Vae int Rn - функция максимума, (3)

tsisn I / *

P (*)» min ■[-—•}, V<*€ Rn\{0) - функция минимума, (4)

l€I <ct» l *

r,,j 7(ot)-{i | - a >0} (в данном ' случае уместно провести аналогию с работами Воробьева, ГермеПера и др., в которых использование функций указанного типа было положено в основу исследования некоторых классов экстремальных задач). Этот факт, в свою очередь является одним из проявлений более общей связи, сунествукщей между нормальными и устойчивыми ыиоксстваки с одной стороны и сеиейстбом ПОМВФ, с другой. Коротко говоря, эта связь состоит в том, что любая помас есть не что иное как. калибровочная функция некоторого нормального множества.

Пусть /:r"-*r'. как изве.стно, е называется:

а) положительно однородной (первой степени), если для любого x^jf

Г(Хх)-ЛГ(х), Vä>0;

б) монотонно возраставшей, если для любых x^lf

х*хг + f{ xjsflxj.

Напомним, что множество Q называется телесным, если'1лс Ш0.

определение .4. Калибровочной функцией нормального телесного множества ßcR^ называется функция f :R%R', определенная формулой Цх)-ine {А>0| хеАП}.

Очевидно, что Ра, 0а , являющиеся ПОМВФ, одновременно являются

калибровочными функциями множеств Ца) из (1) и К' (а) из (2) соответственно.

Teopeus '3. Функция f:lf-*R1 неотрицательна положительно однородна и монотонно возрастает тогда и только тогда, когда она является калибровочной функцией некоторого телесного нормального множества Clf.

Теореиа 4. Функция fslf-»!?1 непрерывна неотрицательна поло-зрительно однородна и монотонно возрастает тогда и только тогда, когда она является калибровочной функцией некоторого регулярного нормального множества

Замечание 1. Множество fif, о котором шла речь в теоремах 1,2, однозначно восстанавливается по своей калибровочной функции с помощью равенства n.={jrei<"|f (x)si}.

Теоремы 3, 4 дают возможность охарактеризовать ПОМВФ' с помощью результатов, полученных для нормальных мноиеств.

Теорвиа 5. помвф иожет быть представлена в виде

f(x)» sup P_(Jf)- sup.{)>(*)! ae U S(ft■ nri n )>, аев a 1*0

где в={«ек"\{0} | Pa(x)it(x), Ухея"}. Более того, в случае, когда f полунепрерывна сверху,

f(x)=. sup р (х)- sup Pa(x)" inf О (*)- inf

аев aes(0 > aeo aes(fi mint в

г г ♦

где D={aeint Qa{x)if{x), V*ei?").

К совершенно аналогичным результатам приводит подход, использующий калибровочные функции устойчивых множеств. Последние имеют вид С(*-)=sup{Aso| *€АХ}, где X - некоторое устойчивое множество, причем предполагается, что o*Q*r£.

обозначим семейство неотрицательных ПОМВФ, определенных на

и', через Ал. С учетом содержащегося в теореме 5 двойственного * .

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

определение 5. Супердифференциалом ПОМВФ называется

множество 0Л»{а€.£лС 0&(х)ъГ(х), Ухей").

■ Супердифферёнциалоы этой не функции в точке называется

множество (г*)=<в€5г| 0С(**)-Г<**)>.

Определение 6. Субдифференциалом ПОМВФ называется

множество Ра(*)«Г(*), Ухе»">.

субдифференциалом этой жа функции а' точке называется

множество в/(**)-{«€£/| Ра(х*) •»/(**)}.

Поскольку суб- и супердифференцнал понятия симметричные, то их свойства вполне аналогичны. В связи с этим мы ограничимся изложением свойств одного из этих объектов - супердифференциала. Теорема б.Суперднфференциалы ПОМВФ имеют вид: аг-{ае!пс Г(а')«1>(

г * *

äf(*V| <a€lnt Ю if(«)и1>, если f{x )фо,

* а , если f(x*)=»o.

Введем S(äf) - множество слабо эффективных в смысле максимума точек dt. Это множество имеет довольно простую структуру, причем, зная его, легко восстановить весь супердифференциал.

Леииа 4. Справедливы соотношения:

1) S(äf)-{aeint Ifj f(e)-t)- U äf(x),

»Clnl r"

♦ •

2) 5f"(s<3f)-n^)nint íf.

Супердифференциал не является замкнутым, а Тек более нормальным множеством. В то же время он достаточно близок к нормальному множеству по своим свойствам, что позволяет "регулярнзнровать" его, вводя, замыкание A"cl (äi). ' " -

Летя 5. Л является-нормальным регулярна множеством, причем int Л» in С äf°{aslnt f(a)<l}.

в

Huste представлены . основные элементы сулерднфференииального исчисления. При этом предполагается, что аса. функции, о которых пойдет речь, являются ПОИВ®. • ' . ..

Теорвиа 7, 1) Пусть F=Xf, где Я>0, тогда

эг- i df;äF (**)■* £ Ух*еф

2) Пусть F»f,+f . тогда ей*» U [Л 5/,п(1-л)5г„], а такке

18 Лею, i» 12

зг(а-*) = U [X di (х4)п(1-*)^,(**)Ь

xsto. и 1 ■

3) Пусть F= taax {f ',f }, тогда

Sf= Ъ{рр£; 3F(x*)c U , afAx*),

leu»') *

где r(x*)={ie{i,2}| il{x*)'F(x*)}!

4) Пусть ftF»f®g, тогда 3F-.g~1 (Sf). Ленча б. df^cat^ тогда и только тогда, когда

i2(*)sf,i*), V*€int R™.

следствие l. в/,« af2 тогда и только тогда, хогда гг (г) =ft (*), при веек xeint r".

Рассмотрим маргинальную функцию, определенную на

F(x)- sup f

■у€т ...

где fsR"xr-»R|, а У - некоторое подмножество R*.' '

Jleuua 7. Пусть /"(• ,у) является ПОМВФ при любом y&t. Тогда aF~ п ё¿Wt 5F(r")c U ' •вJ{x*,y), Vx*€RV

Уб* »€*<« > ,

где через .^ffy) (соответственно,' a^fix*,/)) обозначек супердифферен-цна'л функции f(»,y) ( в точке **), a Y{x*)- Arg иах f(x*,y).

В заключение отметим, что. если х*-точка минимума ПОМВФ f :R;-»R* на некотором множестве Xcnj , то для любого aeaf(x*) имеет.место

Приведенные выше результаты представляют', собой некий

инструмент, предназначенной для исследования . управляемых

»

динамических систем И их характеристик в частности. Заметив при , этом, что само определение характеристики опирается на некоторый специальный класс многозначных отображений и тесно связанное с ним понятие двойственного отображения. Напомним, что многозначное отображение называется г

1) положительно однородным (первой степени), если для любого хеп" ■ .

2) монотонно возраставшим, если для люби« дг ,х2ея°

Г15Х2 * Г(У1)сГ(х1);

3) нормальный, если, при любом гсгг* множество Г(2г) нормально. Семейство положительно однородных монотонно возрастающих

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

о

является и то, что указанное . секейстао замкнуто относительно

теореткко-икокествешшх операций взятия объединения и

пересечения. В результате, объединение, например, суперлкнейних

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

положительно однородных монотонно возрастающих отображений.

Определение 7. Пусть Г':И"-»-*П®. отображение Г' : Дп->-«Д°,

имеющее вид Г* (а)"{/?сД°| в(г)20(у), Улгсл^, ЧучГ(х)}, называется

.двойственным * Г.

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

многозначными отображениями н лежащий в основе .нашего подхода к

изучению управляемых 'динамических снстен, это теорема, об

отображении, двойственном к композиции, иапокнии, что ¡сомпозйцня

т°Г многозначных отображения Г«ц%-«я£#' определяется по

формуле (Т«ГИ*)" и Т(у) - •

»еГ<о -

Теорема 3. Пусть Г и Г палосятально однородные монотонно возрастающие отображения. Тогда (Т«Г)'«Г'®Г'.

Схема доказательства теореиа 3 является достаточно общей. В то же время, сужая в определении 7 класс л" до некоторых его подклассом, можно получить более интересные результаты для некоторых

3 5

типцв отображений.

I) Пусть 1;"- семейство линейных функций (можно считать, что поскольку каждую линейную функцию «(•)=«*,•> можно отождествить с соответствующим неотрицательным вектором а). Заменяя в определении 7 л" на La, получаем, что двойственным отображением к Г будет Г' определяемое формулой Г'(a)-{0eL'j <a,x>z<ß,у>, Vx£R", Vyer(x)}.. Следствием этого является классическая теорема об отображении, двойственном к композиции суперлинейних отображений.

Теорвиа э. Пусть Г и Г суперлинейныё нормальные отображения, причем Г(к")=Я*. Тогда (Т«Г) '«Т' ®Г'.

II) обозначим через Qn семейство функций (3), Поскольку «(•)« aQa{') можно отождествить с соответствующим вектором «eint Е^, будем считать, что Qn»int й". Замена л" на Q° в определении' 7 приводит к тому, что двойственное отображение к Г в дашюи случае есть Г':Q"-»->q", имеющее вид. Г'(a)-(߀Qe| Qa{x)tQß(y), VxeR?, УусГ(х)}. Ö итоге теорема 8 трансформируется к следующему результату.

теореиа ю. Пусть Г(х)»(у€Я*| ysF(x)}, Т(у)-(гея' | zsG(y)}, где и 'положительно однородные монотонно возрастающие ото-

бражения, причем (xeint F(x)>O}*0. тогда (Т»Г)'«Т'®Г'.

III) пусть Р"- семейство функций вида (4). Рассуждая так же, как и раньше, приходим к следующему определению двойственного отображения: Г':Р"-»-»Р* называется двойственный к Г, если Г' (а)»{реР*| P^iJtfßiy), Vxe«?, УуеГ(х)}.

.<_ теореиа 11. пусть Г(х)«{уеЯ^| F(y)sx), r(y)»{zen'| a(s).sy}, •где' G'.R^it непрерывные полснштельно однородные монотонно

возрастающие отображения. Тогда (Т«Г)'<»Т'®Г" .

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

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

Перейдем непосредственно к нашей основной задаче - выяснению условий существования характеристик управляемых динамических

п

систем. Пусть по,п1 >... ,пя~ натуральные числа. Обозначим Е^-Д^0, V

, ...»я^-д^ . Управляемой динамической системой назовем набор положительно однородных монотонно возрастающих нормальных многозначных отображений ««Г,,., таких, что .

Траекторией системы (Г^'Цказывается набор точек хдГ...,хм таких, что (*,), 1-0,Н-Х. Обозначим через Г| ^-»-»Л^

двойственнре к Г( отображение, где Л^ множество ПОМВФ о^Е -»^. Так как Г| то набор Го""'Гк-1 такя;9 образует

управляемую динамическую систему (хота л не являются конусами конечномерных пространств). Траектории системы будем

обозначать а,а еГ'бо.), ¿»Б.//-1.

О ■ ' И 1*1 V * I' '

Непосредственно из определений внтекает, что для любых траекто рий х0,...,хи и ао,...,аа систем и соответственно,

справедливы неравенства «0{.т0)ав1(г1)й...йоя(*и).

Определенна 8. Пусть х0,...,х - траектория системы Набор «*0, ...,о называется характеристикой этой траектории, если он является траекторией системы и удовлетворяет условию

«о < V " V*!1 ~ • • • ~ V V >0 •

Ввздем обозначение Г =Г в г •.. .»Г„. Следующая теорема да-

К,О N«1 И-2 О

ет необходимые и достаточные условия существования характеристики.

1.7

Теорена' 12. Траектория х0,...,г|1 окстени обладает

характеристикой тогда и только тогда, когда выполняется одно из двух условий:

а) существует функция такая, что

б) существует функция такая, что

Имеется несколько подходов к получению подобного рода реэ-угьтов. оди!1 из них связав с принципов Лагр&ияа, когдь вопрос построения характеристик» сводится к некоторой задаче оптимизации. При. наличии предполохзинЯ сщлукяостй теорема Куиа-Таккера приводит к существованию множителей лаграижа (двойственных оценок}, которые представляют собой не что иное как

а

характеристику.

Другой подход, так называемый повагопыП, состоит с сведан!;« исходной задачи к • .последовательности вспомогательных оптими-зационнкх задач, в каабой их которых применяется необходимые условия экстремума. Последние, в свор очередь, базируются на теореме .отделимости^ •

Мы избрали более обдий по сравнению с предыдущими способ построения характеристики, с основе которого лежит теорема о композиции многозначных отображений. Это позволяет получить результаты, которые охватывают как известные, так и новые. Я частности, в рамках предлагаемой общей схемы выделим два основных хл&сса отображений, используемых в экономической динамнке-суперлинейные и положительно однородные монотонные однозначные отображения. Первый класс достаточно подробно описан в литературе

•¡илом/ яы остановимся на втором. Рассмотрим две динамических системы ■

i-ôTTTT, (6)

где F "и положительно однородные монотонно воз-

растающие отображения.

Теорема 13. Любая траектория системы (5) (соответственно, (б)) обладает характеристикой вида Qa ,Qa Л...Q (Рв ,Ра ,....Р^ ).

О 1 MOI *

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

Во второй главе предлагается реализация этой идеи. Главным элементом предлагаемой схемы является конструкция Ç-выпуклости, различные варианты которой рассматривались, например, в работах Кутателадзе, рубинова, Бальдера. в соответствничс общим подходом будем говорить, что функция ÇiiTxT-tR1 приводит множества Y и Г в двойственность.

* определение 9. функция fir-.«1 называется 5-выпуклой, если существует множество .DcT такое, что f(y) = sup £(y,t).

ICD

Введем функцию УхТхн'чЯ1, определенную формулой (£•»)

(У.с,с)=5(у,с)+с. ioi-випуклые функции играют в дальнейшей особую роль, поскольку. для них можно определить сопряженные функции и построить на этой основе некоторый аналог теории двойственности.

Заметим, что определения а также В-выпуклости распространяются, естественно, и на функции, на определенные на мнокес- * тве т. например, функция . f>:T-*R' называется £»1-выпуклой, если существует множество £сУхЯ% такое, что .

(P{t)- sup. <e«l)(y,t,c) - sup [e(y,t)+c].

I у , e > €t (y,c)€E

функция /*:г-»яг называется сопряженной к f, если-f*(t>- sup t£(y»t)-f(y)).

rei

Для произвольной функции р:Т-»Я1 сопряженная определяется таким же образом, т.е. р*(у)■ sup t?(y,t)-jp(t)]. Следовательно, мож-

■ t€T

но ввести сопряженную к /* функцию, которая называется второй сопряженной х £ и обозначается I**.

определение 10. Заииканиеи -(или ^-выпуклой оболочкой) f называется функция clfiY-*Rx, определенная формулой

elf{у) - sup {C(y,t)+c| C(y',t)+c s /<у'),Уу'еУ>. Понятно, что elf это максимальная 8-внпуклая функция, не превосходящая f. Более того, elf совпадает с f**. Нетрудно также

Ä 'АД

видеть, что f , а значит и t , $<>8-выпуклае функции, откуда вытекает обобщение.теоремы Фенхеля-Ыоро.

Teopeüa 14. Функция fxY-*nx является £«о-выпуклой в том и толь-

■ Aft

ко том случае, аогда f«/ .

го

Назовем субдифференциалом (-выпуклой функции £гУ->К1 множество ЭГ»(£ет| (у), УуеУ). Субдифференциалом этой же функции-в точке у*еу называется мнояество м(у*)-(С€а/'| £(у*,е)=

отметим, что субдиффереициал ¿-выпуклой функции £ всегда непуст, причем £[у)т вир Уу€У.

В соответствии с определением субдифференциалоы £®1-выпук-

1 * ■ * '

лой функции Г:У-»Л в точке у СУ является множество Э£(у )»{(с>с)|

(у), УубУ; С(У*.С)+с-1Г(у*)>. Однако, учитывая, что для * * *

(С,с)еэПу ) выполняется равенство с*£(у )-£(у ,с), можно дать более удобное определение субдифференциала.

Определение 11. Субдифференциалом £®1-вылуклой функции £:У-»й' в точке у*0У называется мнояество

¿Г(У*)-<С€Т| ?(у',С)-С(у*,С)зГ(у)-Г(у*), УУ€У>.

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

1. У"Т^вГ, £(у,С)-<у,О. Тогда ¿-зипукдиЬ функции на У-это полунепрерывные снизу сублинейные функции, а £в|-выпуклые -• полунепрерывные снизу выпуклые в обычисш скисла функцнп.

2. у-л°, г-I?41, ?(У,С)-<У,Ь>+3, где здесь с-» а также £«1-выпуклые функции составляют один и тот яз класс выпуклых в обычном смысле полунепрерывных снизу функций.

3. у=я", т-рГ, С(у,с)-<у,е>. тогда £-выпуклнё на У функции это возрастающие полунепрерывные сниэу сублинейные,' а £«1-вы-

пуклые, соответственно, образуют класс возрастающих полунепрерывных снизу выпуклых в обычном смысле функций. Назавем функцию f:R,"-»H':

а) выпуклой по лучам, если для любого хея" функция F(A)=f (Ах) выпукла на полуоси (0,+со);

б) квазиоднородной, если для любого xetf'

/(Ах) i Af(x), VA€(0,1). .4. r«jf\{0}, 5 берется из формулы (4)

C(y,t)= min где I(t)-{x| t;>0}. (7)

Тогда (см. теорему 5) е-выпУклые функции образуют класс всех возрастающих положительно однородных функций а £»5-вы-

пуклые функции совпадают с классом возрастающих выпуклых по лучам функций ftü^R*. 1

5. r-J^, T-»(if\{0})xR*, а С имеет, вид

min { win' -i—i?Y,,vпле t-[b,ß). Wet { ь> V i> '

В данном' случае ^-выпуклые функции составляют совокупность всех возрастающих квазиоднородьых функций ,

6. пусть У»{у€й"| f у »1}-единичный симплекс, г»я^\{0>, С -

* i »i *

функция (7). Секейство с»1-выпуклых функций состоит в точности из полунепрерывных снизу функций tiY-*R*.

Одним из важнейших приложений (-выпуклости является задача математического программирования:

{F(v-) -> rain,

»ев (8)

B={reV| h(r)ao),

где Kc R*, htV-*F?, FiV-tR*. Вознушая праву» часть ограничений, .

введем маргинальную функцию задачи (8)

f(y)=lnf Г(г), ? (9)

»е*

Мi>*у

где предполагается, что оеУсК". Наложим некоторые ограничения на функцию

А1. С монотонно возрастает по у при. любом сет; А2. £(o,t)=o, VteT;

(0, если уен", -<о, если уеяг .

Функция вида (v,t) —^(v) — ç(h(r) ,t). называется модифицированной функцией Лагранжа (МФЛ) задачи (8). Нетрудно видеть, что

f(0)= Inf sup Le{v,t), (0)- sup Inf Lç{r, t). »ev t€T ^ 4 tCT »6* ^

Пользуясь полученными выше результатами, сформулируем теорему двойственности. ' *

Георема 15. Пусть f Çog-выпуклая функция, тогда имеет место соотношение двойственности ' '

Inf sup L-(r,t)= sup int t-lr,t). . (10)

»ev t6T * t€T r€v '

Укажем два примера применений теоремы двойственности.

7. y»Rn, €(y»t)«<y,t>. Пусть V выпуклый компакт, F -

выпукча и полунепрерывна снизу, й-вогнутая полунепрерывная сверху вектор-функция. Тогда маргинальная функция (9) Çoi-выпухла (см. пункт 3) и вследствие этого справедливо соотношёние (10).

в. Пусть выполняются условия предыдущего примера, в вместо скалярного произведения в качестве С возьмем произвольную функцию, удовлетворяющую Д1,лз н дополнительному ограничению Л4. А4. Для любого еея^ существует t'eJ? такое, что

. sup [C(y,t')-<y.t>]-o. ■ • yen"

чтобы отличать обозначения, используемое далее, от аналогичных. обозначений, соответствующих £{y»t)»<y,C> нз предыдущего п-лгаера, мы, будем опускать в•последних индекс Кстати, в связи с зпы иапомнии, что в отличие от ' функция

L(r,t)~F(r)-<h(r),t> называется классической функцией Лагранха.

основным результатом в данной случае является двусторонняя оценке; вида

f**(Q)sf**(0)si<0), .

из которой следует, что если соотношение двойственности справедливо для классической функции лагранка, то оно имеет место и для МФЛ •« • '

как известно, вогнутые и выпуклые функции являются объектами, своего рода симметричными, друг к друГу. По совершенно -естественной аналогии мы можем ввести в данном случг.е симметричное к ^-выпуклости понятно ч-вогнутости, а также осуществить все дальнейшие построения, включая т>»1 -вогнутые и сопряженные функции, супердифференциалы и т.д. Не останавливаясь на этом подробно, отметин,что результаты для ц-вогнутога случая вполне аналогичны полученный выше.

Дальнейшим обобщенней ^-випуклдо являются т;С-сед^овыо функции (аналог вогнуто-выпуклых функций), переход к которым подр^зу-

мевает рассмотрение задач отыскания седловых точек, ч£-седловые функции в этом смысле представляют очень удобный инструмент и, в первую очередь, с точки.зрения теории двойственности.

Пусть X,Y,S,T - некоторые мноаества, tjiXxs-»»1 и Ç:YxT->Rl. Будем говорить, .что ч приводит X HS, a Ç, соответственно, гит, в двойственность.

Определение 12. Функция fiXxY-tR1 называется riÇ-седловой, если

а) f(r,-) является ÇH-выпукдой п°рн любом хеХ;

б) f("»y) является п»I-вогнутой при любом уеУ.

Введем функции,- которые будем называть замыканиями или оболочками С (по первой и эторой перененнын, соответственно): cli f(x,y)- Inf {tj(x,s)+c| ч{х' ,s)+«f(x' ,у), Yx'eX}, с1г f(x,y)- sup (Ç(y,t)+c| €(y',t)+csf(x,y'), Vy'er>. очевидно, что cl^f s t s cllC, причем необходимым и достаточным условие» того, что f ч^-седлооаа функция,. является равенство cl2C» f - cltf (или cl2f- cl,f).

Заметим, что с 1г( £«9-выпукла по у, а с1{{ и«1-вогнута по х. В то яе время, вообще'говоря, ничего нельзя сказать о el f как функции от у. В связи с.этим иогшо попытаться улучшить' свойства этих фукаций, аэодя cljcljf a e^cl f. Для последних имеет место с1гС s cJ2ei,f s cl^t, clft a c^cJ f s cl^f, причем для ijÇ-седловой функции эти соотнокэнпя • преарецаотся в сплошную цепочку равенств.

Определение 13. Никней и верхней соярякешышн к t функциями называются, соответственно,

t*(s,с)- sup Inf [4(r,a)+e(y.t)-f(»,y))^ »€t «ex

f <s,t)= inl sup (D(*,s)+C(yft)-jr(r,y)]. • k£I y€y

Определение 14. второй нижней и второй верхней сопряженными к

** *>' , * * >*

■f функциями называются, соответственно, £ —■ (£ ) и f

<fV-

Для 1](-седловых функций имеет место обобщение теоремы Фенхеля-Моро.' ■ '

Теореча 16. Пусть f ч£-седловая функция. Тогда £ »f -f.

Теорема 16 в принципе создает основу для построения соответствующих двойственных конструкций в • задаче отыскания сед-ловых точек с ограничениями. Вместе с тем в процессе изучения г)€-седловых функций вырисовывается возможность еще более общего подхода.

Определение 15. Функция FtXxY-R1 называется эквивалентной f если -

sup [f(*,y)-i)(x,s)]» sup [F(*,y)-n(*,s)b Vyer,VseS,

x€X x€X '

inf [f(*,y)-C(y,t)]- inf (f(jf,y)-e(y,t)], V*eX,Vter.

у € Y y€V

Отношение эквивалентности является предпорядком, разбивающим множество, функций, определенных на Хху, на классы эквивалентных функций, очевидно, что именно эти классы, а не отдельные функции, являются естественными объектами минимаксной теории, поскольку' пара эквивалентных функций обладает одинаковыми седловыми значениями и седловыми точками - '(если последние существуют), сопряженными и-вторыми сопряженными функциями.

определение 16. Функция tгХхУ^к'называется слабой 7)€-седло-

ьой, если и эквивалентны (или, что то же самое, экви-

валентны f).

Очевидно т|£-седловая функция является слабой Tj^-седловой.

Обозначим через £(f) семейство эквивалентных /функций. Оказывается структура E(f), как впрочеи и произвольного класса слабых тг5-седлових функций, инвет довольно простой вид.

Теореиа 17. пусть f слабая т^-седловая функция. Тогда £r(f) состоит из слабик тг^-седловых функций и имеет вид £(f)={F| ci^srscJj/}, причем clj-cljzl^, ■ di cl i.

Теореиа 1С. Пусть £ класс эквивалентных слабых ijg-седловых функций. Тогда существуют функции р и ф такие, что E»{F| fSF^t) .

Поеден классы вторых сопрязешшх функций:

а) Е*л (f)••Elf**) -класс функций, эквивалентных

б) sft*(f)«E(f**>-класс функций, эквивалентных £**.

** в я"

Теореия 19. Пусть f слаба? nf-садлозая®функция, тогда

30

»

Эта теореиа есть обобцэкна теорчиа'16 длв слабых ч^-садловых функций.

тзС-седловые функции прелЬаэ.иачепп, как рте отмечалось, прежде всего для использования в задача отыскания седловых точек с ограничениями на исходные пзрснаннкз:

F(U,V) ■* fup ini » inf sup , •

<|<=A v<=3 vOB uGA .. .

A={u€U| g(u)ao>, • ("J

0={r<=K|. h(v)zQ). .

где Uci?4, PcR" выпуклие компакты, g:U->R*, вогнутые век-

тор-функции/ вогнута по в и выпукла по. г. Очевидно в (11) гарантировано существование седловых точек. Введем маргинальную функцию

max min F(u,r) - ein mar F(u,v), xeX, yeY ,

u£t »CS »CS vCA

* У У ■ * ' '

+». ДйХ0, уйГ0,

-в, *«Х0, У€У0,

(12)

где X=r", g(u)sr}, В -{reK| h(r)sy} ,Х0^ХСХ\ л #О),

У0={уег| ву*0).

h )

Предположим, что Ç и ч обладают следующими свойствами ': Al. tj(»,s) убывающая выпуклая функция при любом ses,

4

А2., г? (О,s)-О, VseS;

О , хей",

( о , xeir,

A3, sup 1)(JC,S)"*{.

• es i 4<в, хея".

1 . ♦

Назовем модифицированной функцией Лагранжа (МФЛ) задачи (11) функцию вида L^vCu,r,s, t)*F(u,r)-v(g(u) ,s)S(ti(r) , t). С ее помощью седловое значение (11) моано записать следующим образом: f(0,0)»sup inf sup Inf Leb{u,v,s,t)"in[ sup sup inf L- (u,r,s,t)=

ieu v€V l€T »€S »€V iveu t€T m€S ^

= sup inf inf sup L. (u,v,s,t)- inf sup ihf sup L Ju,v,s,t). u€u. >6» »€S t€T v€» a€U «es t€T

верхняя и нижняя сопряженные к f функции в данном случае имеют вид .

flL (s,C)=sup Inf L. (и,Y,s,t), ft '(s,t)-inf sup Lp (u,v.s,t).

44 , »«=* m€u 44 54 u€u v£» 41

В результате получаем

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

f- (0,0)~si/p inf inf sap L- (u,v,3,t)-sup inf sup inf L. (u,r,s,t),

t€T ICS »SY u<=U lG1 aCS uSU »€V ^^

A

fp (0,0)»"inf sup sup inf L, (u,v,s,C)=inf sup inf sup £., (u,r,s,t).

«es t€T оби y€» «es t^T »ev <.eu

Теореиа 20. Пусть f т^-седловая функция, тогда имеет место соотношение двойственности sup inf sup Inf Lp (и,v,s4t)*sup Inf inf sup Lp (и,у,s,c)=

uSU y€» tCT «6S «€0 »€» «6s t€T 7

»inf sup sup inf L. (u,v,s,t)-inf sup inf supL, (U,V,s,t)" »ev Ueu tST .es »e* 0€u ««s teT

»sup inf inf sup L- (u,r,3,t)-sup inf sup int Lp (u,r,s, t) = teT «es »ev ucu Чет »es ueu »€y 5

=inf sup sup inf L.^(U,V,S,t)»inf sup inf sup Lp (и,v,s, t). «es t6T «Gu »6* ' »es «,6t »ev neu

Рассмотрим два примера, иллюстрнрукцнх теорему 20.

1. пусть S*!?, (y,t)«<y,t>, 4(x,s)-<x,a>. в этом случае удовлетворяют ограничениям А1-АЗ, а маргинальная функция f является т)£-седловой. Такни образом, можно воспользоваться теоремой 30.

2. положи« .WT, а а качество ( и и возьмем пронзволь-; ние функции, удовлетворяющие ах,.a3 и дополнительному ограничению A4 (напомним, что для £'условие a4 уяе приводилось выше).

A4, длп любого sgr" сукоствует s'en* такое, что

inf.^ t4(*,s' )-<x;s>]=0. «CR

Зарезервируем обозначения без индексов за фу.икцЬяик, соответствующими случаю скалярных произведения из.предидуцего примера., тогда двусторонняя оценка

ciIf(0,0)a(ciif)Ci?(0,0)af(o,0)a(clai")54(0,0)s ei..f(0f0),

• *

приводит к виаоду о той, что .если соотношение доойствениости

справедливо для обычной функции Лагранжа Ци.г ,s ,t)=F(u ,v)-

- <э(и),»>-ч(h(r),t), то оно имеет место и для L^.

. Задача отыскания седловых точек с ограничениями (XX), рассмотренная в заключительной части второй главы,,, представляет собой одну из. разновидностей минимаксных задач, занимающих центральное место в исследовании операций. ' Впервые она была поставлена и изучалась в работах Герцейера и Федорова на основе метода штрафных функций. Теория чС-седлопык функций, являясь альтернативой, иетоду штрафных функций, , дает возможность рассмотреть задачу (11), опираясь на концепцию двойственности. ■

В третьей главе диссертации систематически. развивается двойственный подход к исследованию задачи (11). здесь, в частности, отмечается, что сопряженные к (12) функции и Г*^

совпадают, и вводится двойственная к (11) задача отыскания седловых точек: ,

* "

max int ° ain sup, (13)

» • ' t • к t

где Нетрудно выразить (13) с помощью

модифицированной фуихции-Лагранжа L^s

sup Int (u,v,s,t)-> max int min sup, u€u »€v * • t • • » t

int sup L- (и,r,s,t) - max int » min sup.

v<cV u€U t » ' » t

(X4)

В связи с этны можно указать н симметричную запись исходной задачи (IX)

sup int Lg tu,v,s,t)-* max Inf - min sup,

t£T nGS' u£U v€V <£« u£u

(15)

inf sup L. [и,v,s,t) - ,-nax int = min sup. »6s t€T uCu »€v »<=v Чёи

Теорема 21. Седловое значение в двойственной задаче (13) существует и совпадает с седловыи значением исходной задачи.

Теорему 21 естественно называть . слабой теоремой двойственности, так как оиа не гарантирует непустоты множества решений задачи (13).- Между тем вопрос существования решений двойственной задачи является, : пожалуй, основным в теории двойственности.

Теореча 22. Множество рекгннй двойственной задачи равно

Э(^*)(0,0)-Э<Г°*)(0,0). ,

Следствие 2. Пусть € - и$-седловая функция. Тогда множестве решений.двойственной задачи равно Э/(О,0).

Важнейший час.тный случай, -к которому применимо следствие .2, это случай скалярных , произведений. В следующей теораме предполагается, что С(у,С)»<у,0, {к,в)шж<х,а> и соответственно 1(и,у,з,€)»Г(и',г)-<д(и) ,я>-<1г1гу,0 - функЬия Лагранза.

Теореиа 23. пусть в исходной задаче (11) выполняется условие • регулярности СлеЯтора: , .

Зйеи: д(П)с1М тР, ЗгеУ. . (16)

Тогда множество решени!) двойственной задачи непусто, выпукло и компактно.

Теорему 23 ни назовви сильной теоремой двойственности, поскольку она обеспечивает но только совпадение седловых значений в задачах (11), (13), но ¿1 существование решений двойственной задачи. В то ;хе время следует подчеркнуть, "что она уступает по силе аналогичным результатам для задач условной .оптимизации. В частности, мы имеем в виду, что из теоремы 23 невозможно извлечь

утверждений,- обобщающих на задачу отыскания седловых точек теорему Куна-Таккера. . ,

' Дальнейшим развитием двойственного подхода, вызывающим особый интерес,, является переход от пары взаиыодвойст&енных задач (14), (i5) к представляющей собой некоторую их комбинацию задаче отыскания седловых точек (без ограничений) ЫФЛ:

L.(u,v,s,t)-*sup Inf - Inf sup , (17) .

* «eu «€»' »e* ucu

t€T «es »es tci

Теорема 24. Пусть' в. -задаче (11) выполняется ' условие регулярности (16), а функции £ и ч удовлетворяют ограничениям А1-А4. Тогда для того, чтобы (и*,И) была решением задачи (11) необходимом достатбчно существования з gr", t ея" таких, что пара ((u*,t*);(v*,s*)] является решением задачи"(17).

Безусловно теорема 24 есть наиболее сильны!} результат, полученный в отношении задачи (11). Из иге, в частности, вытекают и теоремы двойственности, причем уточнить-их взаимосвязь' помогает соотношение . .',,

r*4xs*4^(t,s)erxs| 3(u,r)s С(а,С);(г,а)]е^чУ, где 1/*ч~ множество решений задачи (17), #а r^xs*^- множество решений двойственной задачи (14). '

В совокупности теоремы 21-24 позволяют устранить-, основную трудность исходной задачи (11), связанную с функциональными ограни чениями. Это, в принципе, открывает возможность применения известных методов для поиска седловых точек МФЛ, которая является мощным вычислительным инструментом и активно применяется при решении зе.дач условной оптимизации (не претендуя на полноту списка-, сошлемся на работы Рокафеллара, Гольштейна, Третьякова, .

Бертсекаса). К сожалению, условия сходимости - этих методов являются довольно жесткими, и далеко не всякая МФЛ удовлетворяет им. В связи с. этим встает вопрос дальнейшего усиления свойств МФЛ.

Введем еще одно ограничение на £ и т).

А5. При любых эбЛ* и сей" имеет место т)^(о,5)=з;

Теорема 25. Пусть выполняются условия а1,а2,а5 (отсюда автоматически следуют, аз, а4} • тогда "

* *

Теорема 25 выделяет семейство МФЛ, являющееся наиболее полноценной заменой функции Лагранжа, поскольку значение

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

*

ограничениями определяется ее .седловин множеством I/ . Развивая эту идею, можно обобщить понятие ' модифицированной .функции Лагранжа, отказавшись от ее конструктииной форми

Пусть Р - произвольная функция, определенная на (УхГ)х(йхэ), где и,У1Т,3 - выпуклые замкнутые подмножества конечномерных пространств Кч,йр,Пш и рГ , соответственно. Обозначим седловое множество функции. Р(у) через И* и напомним, что Ч* эта седловое множество функции Лагранжа 1.(1/) ,■ определенной, как известно, на (ихй^)х(Ихй").

Определение 17. назовем функцию Р(ь'), вогнутую по (и, с) н выпуклую по (к,б), модифицированной функцией Лагранжа (МФЛ) задачи (11), если иси, УсУ, л"сг, «"сЭ и Ы* =(/*.

* р ,

Ясно, что расматривавшиеся ранее функции х.^^, где £ и л удовлетворяют а1,а2,а5, являются МФЛ в смысле определения 17.

Заметны, что все сказанное относится к достаточно широкому семейству модифицированных функций Лагранжа, обобщающих в той илк иной степени характеристические свойства классической функции Лагранжа. однако внутри указанного семейства удается выделить такие разновидности,. ■ которые по сравнению с функцией Лагранна обладают дополнительными полезными качествами. Пусть функции 0J:R<,-»Rl, ßz'. Я% К1, ß3'. ß^: л"-»«1 удовлетворяют

следующим ограничениям: 1) сильно выпуклы неотрицательны и обращаются нуль в нулевой точке'; 2) ßt дифференцируемы, причем f-^оязводные ß't удовлетворяют условию Липшица с соответствующими константами Ki .

Сведем с помощью ßt следующие конструкции:

Р. («.»'.s,t)- шах {L(x,v,a,X)'ß.(u-x)-ß(t-X)},

x€U

хеи" ♦

Р (u,v,s,t)- min {L(u,y,ii,t)+0,(v-y)+ß (s-ti)},

yevr 3 4

ые в*

P{u,v,8,t)- Dax min lHx,y,u,X}-ß, (u-x)-S (t-A> +

• x€U yC« * * •

Хек"

+ßiiv-y)fß4(s-u)i,

P4(u,r,»,t)« «as min it(u,i',n,V)-ß2{t-A)+ß4(s-y) }• цея"

определенные на множествах е><"(й,,>слв>х(кхд"), Уг»(17хй")х(нрхл">), . ' VJ«{K,xR,,)x(R,'xRe), У4«(0хя,|)х(кхяв), соответственно.

Следует отметить, что могут быть записаны в более

компактной виде

P (u,v,s,t)= шах {L-(x,v,s,t)-ß (ц-х)},

x€U 4

P,(u,r,s,t)= min {L(u,y,s,t)+ß(r-y)}, i ev. 71

P (u,v,s,t)- max nin {L, (x,y,s,t)-ß (u-x)+ß (r-y)},

3 xeu yev 571 1 3

P4(u.«,»s,t)= L?l)(u,r,s,t),

используощем МФЛ рассматривавшегося ранее типа

Lv(u,r,a,t)-F(u,r)-v(g(u) ,s)-<(ti(r) ,t>, L^u,r,s,t)'Flu,v)-<g(u),s>-^(h(v),t), L^(u,v,s,t)-F{u,v)-T)(g(u) ,s)S(h(v) ,t), которые, в свою очередь, определены с помощью функций £(y,t)= sup [<y+a,t>-0*(y+a)], v(x,s)-= Inf [~<x+b,s>-ß*(х+Ъ)],

»SR Ь€П

- . ♦

it h

где ßz, ß4 функции, сопряженные ß2, /?д.

P,-P4 являются мфл в смысле определения 17 и обладают всеми свойствами, необходимыми с' точки зрения сходимости стандартных градиентных методов поиска седловых Tq4eK. Результатом их применения к р,~р4 явились четыре класса алгоритмов мфл градиентного типа, предназначенных для решения задачи (11):

Kl"1»rev(Kk-rittF;(xt,i',,)-c;(ii(K'!),tk)j), . tkM-tk-Tke;(h(H),tk),

sk,,-(sk+Tkg(xk))_,

где xk=arg max [F(x,vk)-<g(x) ,sk>-ß (uk-x) ; *eu

где ук-аг<г «.¿п [Г(и\у)-<Ь(у),ек>+<3Г^-у)],

С к*1 "С к ^ (Ь (гк > , с 4 ) ,

где (* ,у ) седловая точка функции Р(г,у)-,(?(г),г'). -е(Л(у),с")(цк-х)+рз(г к-у) на инокестве иху,

■ . У,-'

где (х\ук) - седловая точка Функции ■*ч(г(*).вк)-С.(й(|г),ек) на множество ихг.

сходимость этих алгорнтыов обеспечена с любого начального приближения в„р„ соответствующей подборе параиетров, который поразуиевает Г ( возможно <« ,, £с <е> н

к*р .■..■.■' »«о ; >о' ■

коротко характеризуя нетоЛы Мфл можно

отметить, что конструк-

Кшше особенности делают их взаимно дополняющими друг друга, и Целесообразность применения какого-то из этих алгоритмов в ка»дом конкретном, случае определяется индивидуальными особенностями задачи. •

В связи с. изложенными чнслеиними методами МФЛ представляют интерес вопросы сходимости градиентного метода отыскания седловых точек. Как известно, сходимость этого метода имеет место лишь в довольно десткнх предположениях. "Тем • более любопытными представляются полученные для важного случая квадратичной подели вогнуто-выпуклой функции результаты, -в соответствии с которыми существует необходимое и достаточное для сходимости градиентного метода условие.

Рассмотрим квадратичную функцию /,:ЯпхЯ*-*Л| вида |<аг,:>-<6,г>, '1?",

где Л-сиииетричнал матрица, Представляя Л в блочном вид«,

введен матрицу • . .

Л «

в |с

СТ10

, я

-СТ1-0

ч

Будем считать, что В неположительно, О неотрицательно определены, что эквивалентно вогнутости по лг к аипуклостн по у функция

Градиентиий цетод отцеканая садлопой точки функции е а данном случае кисет вид! • '

г"*,«(И-73)г,1-уП, (18)

где X - единичная матрица, а Б»(Ь1,-Ь3). обозначим через собственные значения, р(л )-спектральный радиус. иатриОн И и введем наше

») значок "т" означает транспонирование.

основное условие.

. Ф. Система-уравнений Вх=0, 0у=0, Су=&х, Стг=/3У может иметь

ненулевое решение г=(х,у) лишь в той случае, когда $=0.

* .

Теореиа 26. Пусть сейловое множество г функции Г(г) непустс Тогда: ' .

1) условие Ф необходимо и достаточно для сходимости градиент ного метода'(18) с любого начального приближения;

2) при наличии условия Ф алгоритм (18) сходится со скоростью геометрической прогрессии:

2

гк-»г*, я*шагд ш1пл |2-2°|, где г€ . 1€2

[о,-з—- т!п- |Яе А,|).

1 1Р(А)]2 А,*0 • >

9 случае, когда 'градиент в (18) вычисляется са погрешностью:

можно утверждать, что последовательность {2к)кгосо скоростью геометрической прогрессии попадает в некоторую окрестность седлового мнот

жества г в соответствии с .оценкой

../ „ * гс

где £е[0,1), г-,то же, что ; и в теореме 26, а р(»,г ) означает расстояние от точки до множества-г*.

Заключение

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

являющихся их калибровочными функциями;

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

- получены необходимые и достаточные условия существования характеристик оптимальных траекторий управляемых динамических систем в невыпуклом случае;

- введены и исследованы конструкции £ - выпуклых и седловых функций, применение которых дает возможность изучения невыпуклых задач оптимизации. Предложена универсальная схема построения теории двойственности для задач оптимизации и отыскания седловых точек;

рассмотрена задача отыскания седловых точек с ограничениями, для которой получены исчерпывающие результаты на базе двойственной концепции. Доказаны обобщенные теоремы двойственности и Куна-Таккера;

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

Список основных работ по тепе диссертации

1. Абасов Т.Н. О модифицированных функциях Лаграняса в минимаксных задачах. Вести.' МГУ, серия вычнсл. иатем. и кибернетики, 1982, НЗ, С.32-40.

2. Абасов т.м. Модифицированные лагранжианы в задаче поиска седловых точек с ограничениями, вести. МГУ, серия вычисл. матем.

и киЬернетики, 1985, Hl, с.35-40.

з. лбасов Т.М. Два новых типа кодифицированной функции Лагранжа в задаче отыскания седловых точек с ограничениями. Вестн. мгу, серия вычисл. матеи. и кибернетики, 1986, н2, с.50-55.

, 4. Абасов т.м. об отыскании седловых точек, дан Азербайджа! на, 1987, HI, С.15-18.

5. Абасов Т.М. Двойственность в задачах отыскания седловых точек, дан Азербайджана, 1987, N6, с.8-12.

6. Абасов Т.М. Двойственность в задачах отыскания седловых точек с ограничениями. Изв. АН Азербайджана, 1989, N4-5, с.145-153.

7. Абасов Т.М. Модифицированные функции Лагранжа в задачах отыскания седловых точек с ограничениями. - Баку: Эдм, 1989,

124 с.

8. Абасов Т.М. теореиы о характеристике в невыпуклом случае, вестн. Бак. ун-та, 1992, N2, с.9-16.

9. Абасо^) Т;М. теорема об отображении, двойственном к композиции многозначных отображений. Вести.* Бак. ун-та, 1992, N2, С. 17-24. " '' | . '

10. Abasov Т.Н. Optislzation problem with pozitive hoDogeneous aonotonioally increasing objective function. The 2md Turkish- Azerb. eynposiu», Baku, 1992, p.3.

Зак-У Г Тир. à^û Печ. л.^'ХТнп. ЛГНА Баку-ГСП, пр. Аэпдлыг, 20