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

п о ин

7

! . . . - , I ; ;

КАЗАХСКИЙ ГОСУДАРСТВЕННЫЙ НАЦИОНАЛЬНЫЙ УНИВЕРСИТЕТ ИМЕНИ АЛЬ-ФАРАБИ

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

УТЕМБАЕВ Ерик Мылтыкбаевич

СВЕРТКА НОРМАЛЬНЫХ СУПЕРЛИНЕЙНЫХ МНОГОЗНАЧНЫХ ОТОБРАЖЕНИЙ

Специальность 01.01.09 — математическая кибернетика

АВТОРЕФЕРАТ

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

Алматы 1993

Работа выполнена на кафедре вычислительной математики Казахского Государственного Национального Университета им.Алъ-Фараби

Научные руководители: доктор физико-математических наук,

профессор А.М.ЕУБШОВ

кандидат физико-математических наук, доцент С.А.АТАНБАЕВ

Официальные оппоненты: доктор физико-математических наук

В.I.ЛЕВИН

кандидат физико-математических наук, доцент А .А .БЕДЕШЕАЕВ

Ведущая организация : Институт теоретической и прикладной

математики НАН Республики Казахстан

Защита состоится мая 1993 года в ^ часов на заседании Регионального специализированного оовета К 058.01.09 по присуждению ученой степени кандидата наук в КазГУ иы.Аль-Фа-раби по адресу: 480012, г.Алматы, ул.Масанчи, 39/47

С диссертацией можно ознакомиться в научной библиотеке Каз17 им.Аль-Фараби.

Автореферат разослан " £6 " апреля 1993 г.

Ученый секретарь Регионального специализированного совета, кандидат физико-математических наук,

доцент 0 ( __. „

/— Ш.А.АЙПАНОВ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Таким образом, тема диссертации весьма актуальна.

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

Методика исследования: При работе над диссертацией использованы метода н результаты выпуклого ' анализа, теории многозначных отображений, в чаотности суперлинейных многозначных отображений и теории экономической динамики.

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

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

- определены условия совместимости и доминирования свертки;

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

- определены и изучены обобщенные темпы роста свертки; даны оценки этих темпов.

Теоретическая и практическая значимость: Работа носит теоретический характер. Ее результаты могут быть применены в выпуклом анализе, а также при исследовании задач экономической динамики, возникших при описании совместной деятельности экономических агентов.

Апробация работы: Основные результаты диссертации докладывались и обсуждались на научном семинаре отдела матэкономики ИММ АН Азер.Республики, на научно-теоретическом семинаре под руководством профессора Кенсыкбаева А.А., на научном семинаре в ИТПМ HAH Республики Казахстан, на научной конференции молодых ученых КазГУ (1993 г.), на объединенном научном семинаре кафедр теории управления и кибернетики под руководством профессора Айсагалиева С.А. Публикации: Основные результаты опубликованы в работах (Г.-;4).

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

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

В § 1.1 дается определение свертки суперлинейных отображений; вычисляется опорный функционал свертки, находится его су-пердиффэренциал, описано отображение, сопряженное к свертке.

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

Отображение а: -"■П(К^Г) , где ^О^*4) - совокупность непустых подмножеств конуса называется суперлинейным, если

1) 0.(^x1^ + с а (а: ^ осг) Усс^е^

2) а (> ос) = ^ схс^схГ) , ас €

3) а(о>\о\

4) СХ за1.1Кнуто, т.е. график с^Сл-^Ох.^У-является замкнутым множеством.

Отображение О. '• -"> \\ (И^ называется нормальным, если из того, что Ц€а(сс) оИ4Чи следует ц'есЦос)

Декартовым произведением отображений О.''.

Ли

___. -о "-а :

П^^) определенное равенством А(Х)-аЧ^)^.. -аГЧ^ , где Х-С^.' Рассмотрим конусы 1Й.+ и и определи?.! многозначное

отображение в следующим образам:

Отображение в"1 конуса (КЛУ в ^ обратное к С> является линейным однозначным оператором и имеет вид:

Пусть а1-1Я^П(К.^суиерлинеЯное нормальное отображение С V - ^.....у-Л).

ОПРЕДЕЛЕНИЕ: Композицию отображений , А ,<$ \ где (\--а1х„ла1 называется сверткой отображений сх\.. ,а"\ По определению -

В первой главе изучаются согласованные четверки векторов относительно свертки. Дадим необходимые определения. Пуоть о.■ -■»Г\суперлинейное отображение. Отображение

называется сопряженным к а.

Четверка векторов эс.ц,^,^ называется согласованной по отношению к а , если ^еаЛ'сс), , Ц, - .

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

Изучение сопряженных отображений и согласованных четверок проводится обычно с помощью суперлинейных функций вида "ЭС

Вернемся к свертке С5 А <5 суперлинейных нормальных отображений

Пусть задан • С помощью определим функции С^ и

С^ следующим образом:

су (рО - то ас IЦ, ^ • ^ Сх) = ^•. 14 6 .

ЛЕММА 1.1. Справедливо равенство а (с*) -- ^ р сс ^(ре) .

Для .ОС*4) положим

Нетрудно проверить, что ЪЪ ,

... кд^с^)

(Через Ъи обозначается супердифференциал суперлинейной функции , определенной на конусе [I

супердифференциал функции 17 в точке ос; 11),х\-скалярное произведение векторов { ах).

ЛЕММА 1.4. Супердифференциал суперлинейной функции с^ имеет вид: =

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

Заметим, "что равенство ос-Тсс1" , где влечет со-

отношение 1г(рС)-\7 Рассмотрим экстремальную задачу

при условии

Хе (2)

Значение этой задачи совпадает о Маогеотво всех решений

этой задачи обозначим ^С*). Иными словами

хч^, - , -5Г) € с^ху ^ОО1}..

ЛИМА 1,5. Пусть сс е . Следующие утверждения равносильны: а) ^еЪ^сх)

б) существует такой вектор ^(^^..-^е^СХ) при любом Хс^(^),что при этом . для воохХ€

6 ^(зс^всех ^С^СЗ-О и всех и .

в) существуют такие векторы X = ...,х")^(тс) п

Ь(С ,Г>*то ^ при че 1 ^.....

м

ЛЕЖА. 1.6. Справедливо равенство - .

ЛЕММА 1.8. Отображение, сопряженное к б А (> имеет вид

Эта лемма хорошо известна. В работе приводится ее новое доказательство.

В § 1.3 рассматриваются условия построения согласованной четверки векторов относительно свертки при заданных ос и с^^. Эти условия основаны на следующей лемме.

ЛЕММА 1.9. Пусть заданы векторы ос и и функция построена указанным выше способом по вектору q: - v^a^c ^ Тогда следующие утверждения эквивалентны*.

а) вектор \ таков, что при некотором ^четверка С-dc,^,^,с^) согласована относительно отображения a ;

б) ^G a^4).

В дальнейшем рассматриваются согласованные четверки, у которых векторы X и Cj фиксированы. Нас в основном, будут интересовать множество векторов ^ , входящих в некоторую согласованную четверку с данными ос и е il* .

ТЕОРЕМ I.I. Пусть даны нормальные суперлинейные отображения а1,... ,аГ и заданы векторы осСледующие условия эквивалентны:

а) вектор|таков, что при некотором ¡^ четверка (зс,^» V^) согласована относительно свертки "S'^AcS.

б) существует такой вектор Р = (^У..Д*)еЪЪ(Х)при любом X € ^(зс^что ^^Р^при этом ^ч" ^ ^ всех Xt^teO, всех wel^-sj) и

Дадим необходимые и достаточные условия того, что вектор X является решением задачи (1)-(2), то есть

При этом используются необходимые и достаточные условия максимума супердинейной функции на выпуклом множестве XI в терминах

конуса допустимых направлений Г^СТГ). Дается описание конуса Г^(<$(-=£)) и сопряженного к нему конуса Гх(<$(:£)) - ЛЕММА I.14..Справедливо равенство

ТЕОРША 1.2. Предположим, что либо точка X = Срс.^ • - -, строго положительная, либо граф!1ки отображений а.1" многогранны. Тогда следующие условия эквивалентны

а) Xe^5Ctxy f t

б) существует такие векторы V € ¡Ьс^х^что для вектора ^{'"выполняется соотношения ^ - ^ при vte IjQsC').

В качестве пршлера рассматривается свертка отображений где = о б ) ТL - линейный положительный

оператор.

Положим ^ - (j , где * означает переход к сопряженному оператору, супремум векторов вычисляется покоординатно.

ТЕОРЕМА 1.3. Пусть ^¿Т'ос^ ( где V -ли-

нейный положительный оператор. Четверка векторов (a,согласована относительно свертки , где А* А'4..**^ в том и только в тем олучае, когда при и кроме того найдутся такло векторы ее1, в, ;что

1) , ^ , ^ = ^ при Кб^ОЗсГ)

2) i=v.....m. _

В § 1.4 изучаются неймановские отображения. Как известно суперлинейное нормальное отображение

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

d(cc) - | о-, "i ^ 1ЙГ„ : Ьмх , С

Пусть с € . Положим

а(ху \ ц-* о •. 4 ^ с] (з) где ^Срс) - л \ ¿Л ^ -ЭС ^ (з')

ОПРЕДЕЛЕНИЕ 2. Отображение С1, определенное фч^мулой (3), при некотором назовем элементарным.

ТЕОРЕМА 1.4..Суперлинейное нормальное отображение является неймановским тогда и только тогда, когда оно представимо в виде свертки элементарных

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

Пусть заданы векторы V и с.1 (¿.=1,... , отображение О. и функция Л.1 определены по этим векторам с помощью формул (3) и (3'). Зафиксируем некоторый вектор и рассмотрим .функции и 1 определенные с помощью этого вектора теми же формулами, что и выше

Справедливы следующие равенства с^сс) = ^а з: 2 ^ с1} ,,)

(5)

-- ^сЯ Ъ^Сос>: 1 ^ , (6)

та® , где

ТЕОРЕМА 1.5. Пусть ХЧ^,...эс^е^и вектор таков, что и ^ при к€ 12(^е),где

Пусть далее = ^^ . ^г^' Тогда при 1б ^ вектор ее.1" обладает свойством: найдется такое число У ^ О , что :

- V- при всех

Предположим, что множество пусто. В этом случае

оптимальное разложение вектора ос на слагаемые происходит следующим образом: рассматривается многогранный конус ^ натянутый на образующие ... , 6м. Вектор ос лежит в этом конуое. Рассматривается далее, все разложения вектора ос по образующим:

где в данном случав множество индексов I при которых ^>0 и векторы X вида X =■ & \ .. •, ^

Множество оптимальных разложений ^(ос.) содержится в множестве векторов указанного вида. Заметим, что если ос не принадлежит конусу 1С, то ^ не может быть строго положительным, то есть

\0 ,-ф-Ф'.

ТЕОРЕМА 1.6. Четверка векторов (сс.^.ф согласована относительно свертки §У\^,где А^сН*.

если существуют такие векторы Ос!" > О ,что и

Ц\ г г^це для любого при

В диссертации применен и другой подход к изучению согласованной четверки для неймановского отображения. Используя определение этого отображения нетрудно показать, что величина совпадает со значением следующей задачи Л.П.

—»тазе • (7)

I ^ оа (8)

'V >, О (9)

ЛЕММА 1.26 Пусть эге Тогда ^множество (ой совпадает с

множеством всех решений двойственной задачи линейного программирования (Ю)-(12).

X .£чоск ПО)

Г^^ЬЦ^еЛ ' (II)

Этот результат с помощью леммы 1.9 позволяет описать согласованные четверки. Отметим еще, что справедлива ЛЕММА. 1.27: Пусть . СС. не входит в конус И , натянутый на образующие V, ..., Тогда найдется вектор 5с. е. VI, такой, что ее сс и Двойственные оценки . V*) Для векторов -эс и -5с.

совпадают.

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

В § 2.1 изучается доминирование и совместимость. Пусть задано семейство отображений СХ1-1...)ам. Рассмотрим их свертку 5'А <5", где А - а**...*.а.*4. Добавим к исходному семейству еще ряд суперяинейных отображений СХ4**, . .. и рассмотрим свертку расширенной системы с*.1;... 1 о.**, сх"^, ... о*"'* Обозначим & СЯУ ОЧ^) * ... * о!* (ДЧ к .к С^Ч^^' и рассмотрим свертку ^. (В обозначении отображения С> мы не указываем число слагаемых и размерность пространства, предполагая, что это нигде не приведет к недоразумению. Зафиксируем вектор О и пологим

Понятно, что

при всех о;.

ОПРВДЕЛЕНИЕ. Пусть задан вектор ^О. Говорят , что сверт-•ка 'А <5" доминирует свертку при данном и всех х,

если при всех сс+О.

ТЕОРЕМА 2.1. Свертка ^зvД'S доминирует при данном свертку для любого ссе^.*, то есть при

всех сс^О,тогда и только тогда, когда найдется такое £>0,что

тле

Рассмотрим свертку g'A'S' и отображения а\..

ОПРЕДЕЛЕНИЕ: Отображения сх\ ..., Gl"1 назовем совместимые

в свертке для любого осе ^ при данном с^е^ , если

С^сф > с^ (о) при всех Сй^О для любого то

есть: „

V^Q^C. \1а иЛ > w\aoc ^v^ V v1^-

ЛЕММА 2.2:' Отображения Q4;. • .Ol* совместимы в свертке при данном для любого осе^Д , тогда и только тогда, ког-

да найдется такое £>0'. с^ ■+с "йсу- ■ дая любого L-

ТЕОРЕМА 2.2. Свертка § А<$ доминирует свертку <5 Д<5 при заданных векторах ос, ^ , то есть Qx) > ^otT) тогда и только тогда, когда

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

ТЕОРЕМА 2.3. Свертка ^'А^ доминирует при заданном осе^ свертку для любого , с^О тогда и только тогда,

когда

В § 2.2 вводятся и изучаются обобщенные темпы роста. Даются оценки обобщенных темпов роста свертки.

ОПРЕДЕЛЕНИЕ. Положительное число Ü называется собственным числом нормального суперлинейного отображения а:

найдется непустое выпуклое отличное от грани конуса подмножество этого конуса такое, что

о-С^ - Ач

Как известно, если СХ определяет модель Неймана-Гейла, т.е. Q-C^+V^-v» то собственное число всегда существует и собственное число совпадает с неймановоким темпом роста:

& - va о 3c.|d(,oc> •. -Осе Kl* , зс* о") , где dC"X> w\cvx\ А-. А-хеоЛ^ Если собственного чиола может и не существовать.

Пусть CV -неймановский темп роста отображения СХ. Напомним, что состоянием равновесия суперлинейного нормального отображения а/. ^^ называется набор (А,О., р} , где

el - положительное число, SL, £ обладающий следующими свойствами

1) doc^a^-íL)

2) Ир,ig «с для любых Ос, v^ е aA¿x)

3) Lf>,5L"\>0

Если Зч - неймановский темп роста, то состояние равновесия (сЦ<х.,р) называется неймановским.

ЛЕММА. 2.5. Если существует неймановское оостояние равновесия (л , ос, р) . такое, что оче. úu-t ,то неймановский темп

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

, , • к,'^ с гч CLCp.'X'Í

d= vvtLn vnaoc. —- - v*..* 4

При этом минимум достигается на векторе p.rne a(o,<xV v^aoctp^l

' vjíttlOC)

ОПРЕДЕЛЕНИЕ. Пусть О- произвольное суперлинейное отображение. Назовем величину

j „ аЛРос^)

¡. р* о «WV4

обобщенным темпом роста отображения Q..

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

ство & = о. Однако, если то <£>о

ЛЕША 2.6. Пусть^обобщенныИ темп роста отображения свертки и обобщенные темпы роста отображения ,с^,.-«1™

Тогда <3, * >ч\а-=с

Будем говорить, что свертка <3 ^ отображений усиленно доминирует свертку отображений б1, если найдется

такое ¿>о , что выполнено условие

ТЕОРИЕЙ. 2.4. Пусть свертка отображений §ЧА <3 усиленно доминирует свертку <^А<$ отображений

Тогда обобщенный теш роста с! свертки больше обобщен-

ного темпа роста & свертки (^'А^*.

Пример. Пусть О.1 - элементарное отображение, определяемое парой векторов с1), где

С^ (о,...^', >¡,0,......0>

Можно показать, что обобщенный темп роста А1" отображения а'совпадает с нулем, в то же время обобщенный темп роста свертки больше нуля.

В третьей главе рассматривается свертка для конкретных видов отображения.

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

ТЕОРЖА 3.1. Пусть (Д, состояние равновесия свертки §1А Оь и вектор Хе обладают следующим свойством: найдется

такой вектор . чт0 • , ^е алС^У ¡.-(....о^

Тогда Хе^Ьс}, то есть X - является решением задачи (1)-(2). ЛЕММА. 3.1. Для ^^ справедливо равенство «АИр, оас1 - ^(сх.^ -"

Следствие 3.1. Справедливы следующие условия:

Если то = и наоборот, если

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

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

ОПРЕДЕЛЕНИЕ: Отображение Си ^ - называется линей-

ным, если а_0х+^= + .аЛф ,

Зафиксируем и пологим

Из линейности СХ следует, что функция с^ линейна на конусе^. Тогда существует такой вектор ^ (д) , что

С^-Ш^.гхЛ Оператор ^ сублинеен и возрастает

ТЕОРМА 3.2. Отображения О.1; .... 1 СХ" совместимы в свертке при данном с^е и всех ссе^Ц^. тогда и только тогда,

когда

I

8 I,

Рассмотрим случай, когда отображения Си задаются с помощью линейных положительных операторов Т1;

Тогда суОхУ- I оА

ТЕОРЕМА 3.3. Свертка 1 б" не доминирует свертку ^Дб1 ни при каком с^ о и ни при каком осеслА тогда и только тогда, когда матрица оператора Т** 4 обладает следующим условием: найдутся такие числа О , "^-Ы^,-1 , п такие векторы , что

,

Здесь - \t-ufl столбец ^^^ (или что то же самое, у.-ая строка СГ^Т4) , ^¿Ч-ый столбец матрицы Ч

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

Пусть дано \п производителей, производственные возможности, которых определяются суперлинейными отображениями а1",.. и СО. общий вектор ресурсов. Множество выпусков всей системы может получено так: вектор1разбивается произвольным образом на уч частей •х1,... , ее.*"" передаваемых соответственно первому, второму, • ът_- а^ производителю. Они выпускают, используя эти векторы ^ей'^1),..., ^оГфГ).Суммарный выпуск всей системы составит Таким образом множество всех выпусков как раз описывается сверткой Это обстоятельство делают свертку удобным аппаратом для изучения взаимодействия экономических субъектов.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Получены необходимые и достаточные условия согласованности четверки векторов относительно 'свертки.

2. Определены услбвия совместимости и доминирования свертки.

3. Предложен новый подход к исследованию модели Неймана,

основанный на использовании свертки элементарных отображений и дается анализ этой модели 1

4. Определены и изучены обобщенные темпы роста свертки, которые можно рассматривать как обобщение собственных чисел.

5. Получены необходимые и достаточные условия оптимальности разложения заданного вектора аргумента (вектора начальных ресурсов).

ОСНОВНОЕ СОДЕЕКАНИЕ ДИССЕРТАЦИИ В СЛЕШВДХ ПУБЛИКАЦИЯХ:

1. Рубинов A.M., Утембаев Е.М. Представление неймановского отображения в виде свертки элементарна отображений. Алма-Ата,

1992. - 15с. - Деп. в КазНИИНКИ 30.11.92, Ji 3920, Ка 92.

2. Атанбаев С.А., Рубинов A.M., Утембаев Е.М. О нахождении собственных чисел свертки многозначных отображений и их оценки // Тезисы докладов конкурса молодых ученых КазГУ. - Алматы,

1993.

3. Утембаев Е.М. О свертке оуперлинейных многозначных отображений. Алма-Ата, 1992. - 12с. - Деп. в КазНИИНКИ. 30.11.92,

ü 3919, Ка 92.

4. Утембаев Е.М. О совместимости и доминировании в свертках. Алма-Ата, 1992. - 20о. - Деп. в КазНИИНКИ 30.11.92,

» 3121, Ка 92.