автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.18, диссертация на тему:Декомпозиция в многомерных задачах управления с перекрестными связями

í

российская акадешя наук

шчисжгежлш центр

Лнтвинчнв Игорь Семенович

на правах рукописи УДК 5Г5.6

ДИШКШИЯ В МНОГОМЕРНЫХ ЗАДАЧАХ УПРАЕЧЕНИЯ С ПКРККРЕСППМ1 СВЯЗЯМИ

05.l3.lfl - тооретичпские основы маткыйти^еского моделирования, численшл; г года и комплексы пропилы

автореферат диссертации на соискании ученой степени доктора фигшко мятииатиче.:кнх наук

Мк:кв<1 Г/94

Диссертация выполнена в Вычислительном Центр« Российской Академии Наук

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

член-корреспондент РАН,

доктор ^нзико-иатематических наук,

профессор D.H. ПАВЛОВСКИМ

доктор ^язвосо-матянатических наук,

профессор Ю.А. БЕЛОВ

доктор физико-математических наук A.C. АНТИПИН

Ведущая организация: Институт проблем управления РАН

Защита состоится " № «ИР^^-^ 1994 года в " ' часов на заседании специализированною совета Д СЮ?.3?.05 при Вычислительном Центре РАН по ад!>есу: 117967, Москва, ГСП-1, ул.Вавилова 40, конференц-зал.

С диссертацией мояно ознакомиться в библиотеке при Математическом Институте РАН имени В.А. Стеклона.

Автореферат разослан

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

Ьл

В.А. ЕУШЕНКОВ

I. ОНЦАЯ ХАРШЕРИСШКА РАБОТО

Актуальность темы и цель работы. Развитие наука и техника, услоянянцался пронзводстваннал технологии проводят а тоау, что приходится иметь дело со всв более сложными процессеин. Еалашю глубгсе а полнее иодалировать эти процессы пршюдит я нсстшювде задач оптгзилзаща с большим числом неизвестных и связей инаду ними. При }Х!шешш задач большой размерности возникают проблеш, слизанные с недостаточны!! быстродействием ПШ а ограниченность») оперативной паыятн. Во «ногах случаях эти трудности шжио преодолеть, используя дешжпоэтиш, т.е. последовательной сведение к независимым задачей небольшой размерности.

Проблемы полигиния размерности ^гя инопонерных задач начали интенсивно изучаться с начала шестидесятых годов нашаго

столетия. Первые ииопяшрные постановил еозпдк-ш из

*

цатеыитичйской экономики с ее больлшм часлш номенклатур, ¡юсу1кх)н и балансовых соогношеквй. Иерархически« елодили иднниронания во много« определили а основной объект исследования, стиьянй классически* - даделя с ярио аыримкной блочной структура связей. Такие ыодали описывает функанони^жаник системы, состоящей аз некоторого количества подсистем. При атом выделяются локальные (блочные) перегденнка с еннзи ьнутри подсасчеиы, и имеотся обеде (скнзывавдие) услогезя для »сей системы. Ок гимизация таких дьухуройнещх сивтеи и нослуиила одним ил осноинмх стшуло« для построении итеративных ыитодон Д'.т-1 :|.п; !:',иции для блочных задач оиткмазаиня. При это?4 как пранило что оптимизируемая функция и связи

иащи« с'.^ини и'ним имют специальную аддитишю сопарабельнузо

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

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

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

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

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

парабельные, часчичио-сепарабельные, блочные, блочно-сепарабелъные, задачи со связывающими пе1>еменными и заданными оценками перекрестных связей. Предлагаемый подход базируется на двухуровневой схеме итеративного агрегирования, когда на одном уровне решается ыак]тозадача в агрегированных переменных, в на другом - независимые подзадачи. Рйссмот1>ены различные способ построения макрозадачи ш подзадач шпшего уровня, в зависимости от структуры исходной постановки.

Теоретическая я тактическая ценность. Теоретическая значимость диссертационной работы заключается в разработке общего подхода к исследованию схем итеративного агрегирования и построению на его основа новых методов декомпозиции для экстремальных задач с перекрестными связями. В целом, полученные результаты дают возможность существенно раслшрпть ююгдаство практических постановок, допускающих исследование методами декомпозиции. Диссертация является составной часть» исследований по моделированию и анализу слонных сис^чл, проводимых в НЦ РАН под руководством В.И. Цуркова по теш? НТ? 01.86.0130447.

Личное участие автора в получения результатов. Вс:е вьшоса-ше на защиту результаты получены лично автором.

Ащмбация работа. Основные результаты работы получили квалифицированную апробацию на иеядунарсдиых конференциях: советско-польском семинаре по математически* метода: оптииаль-ного убавления и их нрилоявнишм (Минск, 19С9), 16 конференшы TFJP по моделированию систем и оптимизации (Ношьень, 1993); иа

Всесошных конференциях г семинарах: 10 Всесоюзном семинара "Управление иерархическими активными системами" (Тбилиси, 1986), 6 Всесоюзной конференции по управлению в механических системах {Львов, 1988), Всесоюзных конференциях по декомпозиции и координации в слоеных системах (Челябинск, 1986, Миасс, 1988, Алушта, 1990), а тякдк на семинарах в Вычислительном Центра Ail, ИПУ АН, КГУ вн.Т.Г.Шевченко.

Публикации. По теме диссертации опубликовано 29 работ. Основные результаты диссертации представлены в [1-21J.

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

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

ii. краткое содержание работы do главам

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

В главе I рассматриваются конструкции метода декомпозиции на основе итеративного ахрегарованпя д;м вьшунлых задач ыатеьгатщческого програгашровання шда

сшх{/(х) | хеР), Р - [xf Rn : gft(x)íO, х >0) (1)

где скалярные функции -fix), выпуклы. В §1 исследуется

блочное линейное агрегирование дзя задачи (1). Кшпоиентн вектора х разбиваются на I (7í,n) непересекающихся подвелторов с Jj компоненташ в <-ш подвектора: х » {xj, Í»1,I, J« Вводятся агрегаровашша переиеюшо п шюаество А весогах элементов, удовлатвордазяих условш) иорцаровка

А - (ají Е oj ■ 1, aj > 0, ы7т. (2)

j

В дальнейшее, где это не вызывает разшчтзнйй, индекс сувашрования по J будем опускать. Дезагрегированными перемен-ик.'Л1, соответствукщзш набору аеЛ и пастору Кьй1 называется xj - aj JT1 шш в ыатричном вдде х. » eúf, гдо a - блочно-даанжальлал матрица соответствующей размерности. Из апрадала-пая дезагрегированных пеххашнных я условия норизровка (2) следует, что X*- 2 х1 пра любой а (А. Макрозадача получается пря

фиксирсванной aCi подстановкой дезагрегированных переменных в (1):

6(a) - nax{/(a*)i ^(аХЩ faUm, X > 0) (3)

ч содерешт I переменных X. В линейном случае такой подход соответствует агрегировали» столбцов ьштрзцы ограничений е зюэф$вциентов целевой функции. Если 1 - оптимальное решение ьшкрозадачв (3). то дезагрегированной решение х=а£ допустимо к исходной задаче (1). В «входах итеративного агрегирования • осуществляется последовательная корректировка весовых элементов а с целью нахождения такого значения а, что соответствующее дезагрегированное решение оптимально для (1).

Пусть Pía) - множество • оптимальных решений макрозадачн (3). Предполагается, что прз всех а(А ыакрозадача имеет строго положительное оптимальное решение l€P(á). Рассматривается • задача выбора весовых элементов

га» (6(a) | aíi) (4)

Функция б(а) вообще говоря не выпукла, тем не менее имеет место следующая связь между исходной, макрозадачей и задачей (4):

' Теорема 1.1 Пусть а(А - локальный максимум в (4), IfP(á), Jt>0. Тогда дезагрегированное решение х=аХ оптимально для (1).

Далее предполагается, что функции /(х), gfe(x) непрерывно дифференцируемы с частными производными, удовлетворяющими условию Липшица, а для макрозадачи при всех ai А выполнено условие регулярности Слейтера. Через 0(a) обозначается мноияство 4 оптимальных -решений двойственной ыакризгдачи.

Предполагается, что Р(a) a Р(а) равномерно по aíi ограничена. Бела ыаярозадача а двойственная к ней шест единственные решения, то с использование« теоремы о иартаиалышх значениях устанавливается даффврещцируеыость б (а) в точка à с проазводньвш

ав(а)/дaj - Pl(tj), Ш,Л [af/dxJ - g W01]1!;*

где âe.4, ôeO(à), В атда случае справедлив аналог

теоремы.1.1:

Теорет. 1.2. Пусть в точке fe А для задачи (4) вапоянтш необходимые условия оптимальности первого порядка (v9(á), a-âj-^O, aíЛ. Тогда веля IfP(â) и -?>0, то х-ал оптпдалап для (1).

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

SÍ&) « гах ÍS S <4 t'â(tj) | agi) - 0 (5)

a i J J

Для находдшшя стецсонарюй точки прадлагаятся использовать «етода первого пордда - условного градиента, возможных направлений, прекциц грндаинта. Основная подзадача, еозшшзодш* в таких методах - это задача шбора ¡ направления Еозрастшшя. Для нахождения такого направления необходимо ыаксимизнро^ать вддитавно-сепарабельную функцию (линейное прарадвясе) ( на инигестве А. В данном случае задача выбора направления

распадается на I независимых подзадач, поскольку А"А^Аг.. где а|»1. J-1,Jl). Подробно анализируется иетод

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

Тшшл образш, исходная задача (1), содержащая п=£ пергиенлых, сводится к задечадз меньших размерностей. Макрозадачэ содержит I переиешшх, I независимых задач выбора направления возрастания содержат. пераиашшх каздая. Существенно, что деяшпозшщя в данвш случае достигается благодаря специальной блочной структуре дезагрегирования и не зависит. от структур исходной постановит. Это позволяет исследовать несепарабедьныв эадата. Метод декошозвдш строит последовательность дезагрегированных решений, допустимых к исходной задаче, так что соответствующая последовательность значений целевой функции монотонно возрастает.

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

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

В §2 основное виташше уделяется использовании структурных особенностей исходной постановки. С этой целью переформулируется задача выбора направления возрастания для задачи (4):

0(á) « шх{(х,Д)|х«П}, Jr-tr1,). К » (A<í,j)} (ó)

г J

ГДО ÜUi.J) смеет тот sa сяысл, что а ранее, а шгогостга П, опуская технические детали, долото ссдяряать в себэ допустима ешоотство задачи (1), т.е. Пэр. Для адднетвйшшн реяашй npi*»ñ п двойственной ыакрозадачп устанавливается

л

Теорает 7.1. Пусть х - оптгаааыюо paseinia (6), такоо, что

I1- £ х' >0. Полета а1, » х\/Х1, з1. « I1 (а'-а1.)/!1. 1Ъгда:

J J J J J 3 . „ А

а) если Й(а)>0, то найдется р>0, тагаз что 6(áU0(á+p¿j)т.о. а

- папра&леншз возрастания; б) если 5{á)°=0, то х оптимально для

(1); в) для всех áfЛ найдется чпело Т>0, таклз что

где S(á) определено 0 (5).

Устанавливается сходшость птаратгшного процесса

А

а ^»а , хда роИ) шб<5раатсл из услэвпй позрастанпл в(а), а я определено пая а теореип 2.1.

Имевдияся свобода выбора шюкэства Л а (ó) реализуется тип, чтобы наделать (6) декоыпозгадеакншн своДстпстл. Пусть в исходшЭ задаче ("1) гаеатся блочные ограничения, соответствуя пща L подсистемам и связываете огрнничегал, так что

Í4j>(rt...xj|4(xt)-í0, Xj^O, м7ь, СПХКО, S^ÍTS}Í7)

Оиределяя мноиество О»? с помощью блочных ограничений из (7), получаем, что задача (6) распадается на Ь независимых подзадач

max ((Xj.AjHg^fejXO, x¿iQt Ы,Кг),

где ij - часть вектора соответствующая xJf a A«(A(i,J)) определяется по решению макрозадячи и двойственной к ней аналогично тому, как. это сделано ранее.

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

Р - (i >*r*(x)«D' Il-Гь. dD(x)^0, s»V3)

и для всех х&О, d°(x)«0 известна оценка перекрестных связей где числа заданы. Положим

Я « (х | g^íXj)^. ts-UKr- l-UL)

Тогда ít»P и соответствупцая задача (6) распадается на L независимых подзадач в силу блочной структуры й.

Далее, с использование« определения выпуклой дифференцируемой функции, теоремы Куна-Таккера и теоремы о седло вой точке функции Лагранна для задачи (1) при Р из (7) устанавливается неравенство

б (а) » *(а) - гаах (/(х)~2 иЧа{х) |«П) - fix) (8)

X в

где Í5 определено с помощь» блочных ограничений из (7). Устанавливается справедливость утверждения, аналогичного теореме 2.1, в которой б(а) заменено на г(а). Если целевая функция и

связывапцие ограничения аддитивно-сепарабельны по блочка» переменным: f,(Xj), da(x)*% то вычисление *(á)

сводится к решению L независимых подзадач вдда

нюх {/,(.г )-E«edJ(x )|gj(x )<0. х,=Ю. X«ñF{) (9) xi

С использованием неравенств, аналогичных (8), исследуа/тся частично-сепарабельные постановки, когда либо целедал функция, либо связывапцие ограничения несипнрабвльны. Показано, что ряд известных методов декомпозиции для бяочно-сепарабалышх задач являются частным случае« рассмотренной схемы декомпозвтща прз специальном выборе агрегирования а нногшства О.

При использовании exea дякогягазищзд, основанных на теорте 2.1 а ее модификациях с учете» неравенства тала (8) генерируется последовательность дезагрегированных решений, допуспзшх к исходной задаче. Соотввтствущая последовательность значений целевой функции ионотонно возрастает. Крсыа того, на o-oü итерации справедлива оценка оптшалького значения исходной задачи atn(%(ár)+f(¿r)) » f(x*) > /Чх^). Здесь шшшун берутся по всем нрядыдущш цтеряцпяи. Крятернеы оптшальности слугит совпадение верхней н mrsmeñ оценок.

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

Свобода выбора агрегирования реализуется для блочио-

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

В 53 рассматриваются другие способа введения макропеременных, отличные от блочного агрегирования. Формулируются условия, пра которых смеет место утварзденш, 'аналогичное теореме 1.1 о связи исходной, макрозцдачп и задачи выбора весовых элементов. Основное внимание уделяется линейному агрегированию для задачи (1) без ограничений на знак переменных. Вводится вектор макро-переаениых ЯеШ*1, 13<п. Линейное дезагрегирование имеет вид дмхУ, где а - прямоугольная п*М матрица, а условия но^ьгярошш задаются соотношением Л=[а|Са-Я). Здесь С - фиксированная прямоугольная матрица ранга 1/, а Б - единичная матрица порядка Из определения дезагрегированных переменных и условия нормировки получаем Х«=Сх при всех а€4. Макрозадача получается кик. и ранее, подстановкой дезагрегированных переменных в исходную задачу при фиксированном аеЛ. Получены необходимые и достаточные условия оптимальности . дезагрегированного х>ешения. Сформулщхжаны условш диф$еренцщ>уемости ф\ткции 9(а), установлена связь стационарных точек задачи шх{6(а)с оптимальным дезагре I"И!»ванным решением. Для нахождения стационарной точки мсполь-

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

В §4 представлены способы вычисления оценок показателя субоптимальности агрегирования для задачи (1), определяемо!« как разность значений исходного целевого функционала на оптимальной н дезагрегированном решении. Предполагается, что процедура дезагрегирования осуществляется однократно, а но в рамках итеративного процесса. . Показатель субоптимаяьностн оценивается после того, каа решена макрозадача, так что речь идет об апостериорных оценках. Рассматривается линейное деэаг-решрование при фиксированной матрице а с неотрнцательнькш элементами. Представлены декомпозиционные способы вычисления оценок субонтЕмалъности. При доказательстве соответствующих утвервдений используется неравенство б(а)5/(х )-/(х), справедливость которого установлена для произвольной матрицы дезагрегирования а с неотрицательными элементами. Здесь б(а) имеет тот не смысл, что и в (6). Полученные результаты применяются для обобщенной транспортной задачи. Для этого случая рассмотрен такие способ получения априорных оценок субонтшальности, вычисляемых до решения макроэадачи.

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

оптшальнсш дезагрегированном решении. Одну из оценок дает текущее дезагрегированное решение, для вычисления другой строится вспадсгатальная задача типа (6) или (8), определенная па иникестве Л. Првт этой мнсаество Й выбиралось так, чтоб» наделать вспомогательную задачу декошюзицшзнньаш свойствами.

В §5 реализуется дрптй подход к выбору иновества О, которое строится так, чтобы получить по возможности более точную оценку оптимального значения исходной постановка. Ирг , атаа, как следует вг (6), чт уже ыногество 0, тем меньше величина б (а) в, соответственно, меньше разность иееду верхней, а нианей оценками. С этой точка зрения гелательно при определении множества П удершшать по возможности больше ограничений исходной задачи. Соответствующие построения реализуются в рамках метода внутренних точек, который рассматривается как специальный случай метода итеративного, агрегирования. Основное внимание уделяется исследованию скорости убывания разности между верхней и тайней оценками оптимального значения.

Исходная постановка рассматривается в виде

шЫГ(х)\х€Р), \К7, хт (10)

где V - ограниченное выпуклое множество, /(х) выпукла. На о-ой

х л ф

итерации имеется точка х°<С/, х°>0 и х"£У, такая, что /(х"К/ . Новое приближение строится по формуле х"+1«(1-)х"+р^х", где

выбирается из условия х^Ьо. Пусть на и-ой итерации

имеется оценка снизу оптимального значения: . Положим

. А

z1* «raar(z*\/(x°)). Через Yo обозначается диагональная матреца с элементный х" на даагонали. Рассматривается множество

ß - (х * 0. хт(Г1)гх < (в^х)2) (11)

о р п w

где в - единичный u-иэршй вектор-столбец. Вели х>0, то поскольку второе неравенство в (11) оаяачгет, что сукна квадратов неотргщателышх чисел х{/х" не превосходит квадрата ах суши. Вводится мноквство flo=Wlufe. Па определению, 0[;->Р, где Р - допустимое инокаство в (10). Полтей р 1+2(втГ"1хв>1~1.

А Ö И

Творвж 5.1. Цусть х°*Лп, /(^Д Тогда

ц » aoxf £ хЛп(Пс°))-1/п | х*Р, /(х)*/^))

1 i '

А

В качества точки х", удовлетворяющей уедавши теореш, берется решение вспошгэтвдьной задача

min (/(zilxtOJ 02}

А

Требования теорею* к х шполнепы, поскольку Л^эР. Для случая линейной задача (10) предлпяеп способ рашения всотжогатольной задачи (12), сводящейся к проектяроиашго на шюгестю, задаваемое сзстешй лкнейшх уравнений. Устанавливается связь иезду методом внутренней точка я методой втератишюго щ-регаревьния из §2. В частиостп, задача (12) совпадает с ¡задачей выбора направления спуска (в) дал рассмотренного определения мяоавства Я а шрагарования, при которой вводится

одна макропеременная, а весовые, элементы определяются по текущему решению хи>0.

В главе II применение метода декомпозиции конкретизируется для некоторых бесконечномерных экстремальных задач. В §1 рассматривается задача классического вариационного исчисления с интегральными ограничениями. Исходная постановка имеет вид

Г*2/<*.х(*)У (*>)<« -*• шах, »1

»О > _

Г 2 в^ЛхШ.х и))си Ь « 1,Х (13)

где предполагается, что £ а^ * 0, 2 Ь* Ф О, 1=1,1, выпуклые функции ~f и gk имеют непрерывные частные производные но всем переменным до второго порядка включительно, ограниченные в совокупности. Условия выпуклости записываются в виде

Г(*,х,х')-/а,х,х ) ^ 2 Шх\-х1ЖЦ,х,х' )/дх\ +

1 J 3

+ ((х])'-(х])')а/(/,х,^')/д(х])'

Вводится вектор макропеременных КО с Т компонентами и блочное дезагрегирование ), где множество А двнкды

непрерывно дифференцируемых весовых элементов задается в вид«

Из определения дезагрегирования и условий нормировки следует, что х£.(0. При фиксированном а(А макрозвдача имеет над

ir, (¿X)' )dt max,

rtzgkUMAáX)')dt P¡t, fe. 1Д, 'i

а*. Г(*2НСЬ]. í-Í7l

i J

Устанавливается критерий оптимальности текущего дезагрегирован него решения для задачи (13). При обосновании используется условия оптимальности первого порядка, в качестве которых выступают уравнения Эйлера. Вводится дифференциальный оператор v= - d(d/d(Xj)')/dt я критерий оптимальности х

записывается в виде

vjKf,¿}.<xj)»b0, ф = ;(f.x,x')-E *^(í,x,x')

где t>k - оптимальные множители Лат-рашса в макрозадаче. Дал ¡а с использованием теоремы о маргинальных значениях для случая единственных ¡«лтний макрозадачи и двойственной к ней устанавливается дифф<!1х;нцируемость по Фреше функционала 0(а) с »цюизводнынм dfl(á)/¿)aj = X1 (i )vji|)(t ,x,x'). Формулируется- аналог те* 1.2 из глаш I о связи мезду стационарной точкой задачи íw.u(G(a)|aM) и оптимальным- дезагрепцюванным решением. Зто уг1«;цядений справедливо, если компоненты V(t) оптимальною 1'.'!:;!'НШ1 мак1*)задачи нигде на огузке (í^í.J не ожидаются в и •.:)•. При доказательстве используются условия стационарности, '.'-:11Иойнныв с 1ИИЛ-.ГМ» оператора проектирования на мнонкство .4. ÍI- .что nj4iM"HKHi!« метода проекции градиента для поиски

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

Дая использования структурных особенностей исходной постановки (13) рассматривается модифицированная задача выбора направления возрастания

й^^с/^Е^Ш^ФаЛ*')«»^»,)«^. ^<*аН>}. хШеО) 1 * (14)

где П - замкнутое ограниченное ыноавство из С,, такое что ОэР,

Л

где Р- допустимое множество в (13). Пусть х(1) - оптимальное

Л . Л,

решение (14), такое что X (*)■! ие обращается в нуль на

отрззлв . Тогда по аналогии с теоремой 2.1 главы I

л

устанавлизаюгся свойства направления Свобода выбора

множества П реализуется так, чтобы наделить задачу (14) декомпозиционными свойствами. (. этой точки зрения исследуются блочные и бдочно-сепарабельные постановки, в такса задаче с известны;.™' оценками перекрестных связей. Соотнетствухщце построения обощаются на случай нескольких независимых переменных с задянншш значениями на границе области, а такта для задач с одной независимое переменной и производными высоких порядков.

В §2 метод декомпозиции на основа итеративного агрегирования применяется к задача оятшального управления типа .Т&яыха' ■

т

J(u(•)) » Q(x(T)) + f ffou.fjdf —и max о

x(t) ш A(t)x(t) + b(uft) , xfoj - X0 , (14)

v(x(t>) < O, p(x,u,t) < 0, \i(t)X>,

где управление u(f) есть n-мерный вектор, A(t) - квадрастая матрица, v в p - вектор-функции. Предполагается, что для задачи (14) и промежуточных задач метода разложения выполнены условия A.M. Тер-Кринорова, обеспечивание сведение указанных задач к задачам выпуклого программирования в банановых пространствах вместе со справедливостью принципов двойственности, в тенно, теоремы Куна-Таккера и теоремы о седдовой точке функции Лаграняа.

Агрепфуотся управления, рассматривается блочное дезагрегирование uJ(f)"aj(<Wl(f). где весовые элементы удовлетворяют условиям нормировки аеА при

A-{a(í)ISaj(t)-1. aj(fí-ííj. J-lJr í€{0,T]).

Макпозадача получается подстановкой дезагрегированных управлений в исходную задачу при фиксированном agyí. Предполагается, что при всех макрозадача имеет оптимальное решение Ü(t), полояительное покомпонентно для всех fe(0,7). Для макрозадачи ¡рассматривается двойственная в смысле Е>улфа, причем в силу положительности оптимальных макроуправлений спответствувдие ограничения двойственной задачи имеют вид [равенств. С использованием условий Куна-Таккера устанавливается критерий оптимальности дезагрегированного управления для задачи

(14). Условия оптимальности сводятся к выполнению неравенств

¿0 (15)

.1 rr, db(u,t) , , dp(x,u,th df(x,u,t)-. J 11 dulj ' 1 du'j 1 duj 1

» •

x.u

где X(t) и r|(i) - оптимальные сопряженные функции и многагтели Лагрзнка какрозадачи. Для случая единственных макроулравлений и ынокителей Лагранка устанавливается дифферешхируемость по Фреше функционала 9(а) с производными дВ(а)/да^01 (t)h^(t). Условия стационарности а для задачи выбора весовых элементов записываются в виде

S(a) = maxi SET Ül(t)h\(t)a\(t)dt | a€A }« О (16) a i j о J J

Показано, что если a ei такое, что выполнено (16), то дезагрегированное управление оптимально для (14). Up« доказательства используется критерий оптимальности (15)- В силу блочной структура множества Л, задача выбора' направления возрастания в методах первого порядка при поиске стационарной точки распадается на I независишх подзадач, зависящих от структуры агрегирования. При- этом независимые подзадачи получаются и для каадого itlO.T).

Для задач со специальной структурой связей формулируется модифицированная задача выбора направдешш возрастания

, б(а) - шх( s S X h\(t)u\(t)dt | u(f }€fl. i€[0,TJ) (17) : u t з о J J

5 гдо >f»r.n(O.TJ • замкнутое ог1»ниченное ынокество в простр^н;: im: ' VftpiiiUf.i'aü, такое что ßsP, где Р - множество допустимых

управлений в (14). Устанавливается аналог теоремы 2.1 главы I.

А

На основании этого результата но решению u(f) задачи (17) строится направление з возрастания функционала 0(a) в точке а. При 8(а)=0 констатируется оптимальность текущего дезагрегированного решения и. Показано, что величина 8(a) дает оценку субоптимальности и, т.е. b(a)^J(u*)-J(u). Сформулированы условия сходимости метода итеративного агрегирования с «одафшшровяшюй задачей выбора направления возрастания.

Рассматриваются способы выбора множества Л, приводящие к декоштоэищш задачи (17) и связанные со структурными особенностями смешанных я терминальных ограничений в (14). Соответствупвде построения аналогичны приведенным в главе 1. При этом, если в определении шюячства Q отсутствуют связи, задаваемые дифференциальными уравнениями, то независимые шздзидача формулируются и для кавдого ¿еЮ.Г]. Для случая, когда при определении мнонества П удерживаются дифференциальные уравнения исходной постановки, получено нехэавенство

Г Е f l\(thi\(t)dt >- Q(x(T)) - (jl.u(x(i')))+ jlf(x,u,t)

i J О J J О

- (т)( f) ,p(x,u,t))]dt - J(u) (10)

выполненное для всех х,н, таких что x(i)~A{t )x{t)+b(u,t), x(0)-=j . Яднеь |1 - оптимальный мнокиткль Лазранна для Т4'1«инильн:^х ограничений мак1«)задачи, J(u) - оптимальное значение- urvMvjv фунюжонала минцлзпда-ш. Неравенство (18), ииил<>:'и-1н.- ни11чн,'н:.тву (Г»), используется, в частности, при

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

pl(xrurt)'<o, OjCXjW^o, ut(t)ZO, 1*1.L, (19)

q(x,vft}&>, d(x(T))*0,

а целевой функционал и связывающие ограничения аддитивно-сепарабельны: /-£flt 0=20<Z"£<Zj. Тогда с использова-

нием (18) устанавливается, что задача выбора направления возрастания сводится к решению Ь независимых подзадач максимизации фуша;иинала

<?, (х{ (?) )-(|1, d, (хг(!Р)) )+f[(х, ,и,, t)-(f|( t) ,qt (x, ,u,. t)))dt

о

при блочных условиях из (19). Неравенство (18) используется аакса для анализа частичьо-сапарабелы№ постановок в задач со связывающими переменным в терминальных в смешанных ограничениях. Для Схлочно - с еп врябеяьнык задач рассмотрен тагаш способ введения ыакропеременныя, при которой п макрозадачо сводится к решению независимых блочных иадач.

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

т

tf(x,u,t)dt —»- тах

о

x(t) « Â(t)x(t) + b(u,t) , x(0) » x0 . (20)

a(t) S Cu(t) * û(i)

где С - постоянная прямоугольная п*Ы матрица полного ранга. Здесь U<n, a q(i), â(t) - заданные И-мериые вектор-функции. В качестве матрицы, задащей линйное агрегирование, берется матрица С, фигурирующая в ограничениях задачи (20). Соответственно, в макрозадаче ограничения на макроуьравленоя имеют вид a(t)^IJ(t)^à(t) и не зависят от весов агрегирования а. Это позволяет упростить решение макрозадачи, а также процедуру выбора шага вдоль направления возрастания. Подробно исследован случай квадратичного целевого функционала.

В третьей главе дается обоснование метода декомпозиции для задач управления системами, описываемыми дифференциальными уравнениями в частных производных. В §1 рассматривается эллиптический случай. Основное внимание уделяется блочным постановкам. Подсистемы описываются уравнениями Лапласа -и ставится задача Дирихле или вторая и третья краевые задачи. Управления являются распределенными и оптимизируется интегральный функционал, заданный на рассматриваемых областях. В §2 изучается задачи оптимального управления с параболическими уравнениями при граничных управлениях. В блочном случае теплообмен ча границах сред задается уравнениями Ньютона, в которые входят граничные управления. Интегральный функционал состоит из двух слагаемых, первое из клтор« берется по пространственной облас-

ТИ в конечный момент времени, а второе представляет собой интеграл по боковой поверхности цндлиндра. В §3 метод декомпозиции применяется к оптимизационным задачам, которые описываются двумя типами гиперболических уравнений. Первый тип - это уравнения второго порядка по пространственным переменным, где « правых частях присутствуют распределенные управления. Рассматриваются нулевые граничные условия, а в целевой функционале один интеграл берется по всему щшшндру, а другой - по пространственной области в конечный момент времени. Второй топ - это системы уравнений первого порядил с одной пространственной переменной, записанные в инвариантах Ришна вдоль характеристических кривых. Рассматриваются ^определенные управления и ставится смешанная задача, в которой задаются условия в начальный момент времени и на левей 1ршшци. В целевой функционал входят интегралы по всей области, но правой границе а в коночный шаент времени. Во всех пар.ичшфах данной главы агрупдрувт-ся управления. Основное внимание уделяется установлении связи цедцу исходной задачей, иакрозадачеВ и модифицированной задачей выбора направления спуска. В доказательствах используется понятие слабого решения в пространствах Соболева.

В четвертой глава иетод декогяюзцццц п равняется дот численного реиенвя понкрзтиш: задач оптимизации. В §1 расссют-пена задача сопровождения тершческого процесса в вертикальной печи. Печь гаикзт равноудаленные по шеоте зоны обогрев. Требуется достичь заданного распределения температур ддя вврта-' кального объекта, помещенного в печь. Управлениями слукат

подводшые к кзедой зоне обогрева потоки теплв, температура объекта измеряется в точках, находящихся в соответствующих зонах на равных расстояниях друг от друга. Простейшая линеаризованная постановка, формулируемая для управления рассматриваемой системой представляет собой линейно-квадратичную задачу оптимального слеяеная с большим числом фазовых переменных и управлений. Для решения этой задачи применяется блочное агрегирование управлений. Используются последовательно два типа агрегирования - "пространственное" а "временное". В перьш случпе агрегируются управления, соответствующе размтншл зон ш обогрева, во втором управления агрегируются вдоль интервала времени. В целой кавдое макроуправленна представляет собой сукигрное по всем зонам обогрева тепло, подводнкгое к печи в течение определенного интервала времени. Приводятся результаты расчетов для конкретных значений исходных данных, проводится сравнение с известными подходами. Следующая постановка формулируется для задачи обогрева системы тонких стеранвй. Подвод тепла к каждому стерашо осуществляется отдельным нагревательным элементом, заданиям на его правом конце температуру 1 реющей среда, которая рассматривается как упраилание. Поток тепла на левом конце отсутствует, а на правом подчиняется закону Ньютона. Перекрестные связи мекду подсистемами, соогветствувди-ми отдельным стеркням, возникают из-за частичного распространения тепла, подводимого к одному стернню, на остальные стержни. Кроме того; подсистемы связаны ограничением на общий расход 1>«сурса, идуго ни обогрев. Целевой функционал состоит из

интогральнопэ терминального слагаемого и интегрального слагаемого, квадратичного по управлениям. С использованием техники разлоньния в рад Фурье, исходная постановка сводится к линейно-квадратичной задаче оптимального управления с ресурсными ограничениями на управления. Для решения задачи используется блочное агрегирование управлений. Приводятся результаты расчетов, дается оценка требуемой оперативной памяти. Далее рассматривается задача с нелинейной зависимостью правых частей даффаренцнальных уравнений. Исходная постановка формулируется на основе модели оптимизации помех в динамических системах. В еадаче имеется ресурсное ограничение на управления, а сами управления неотрицательны. При решении применяется метод деком-шзцции с «одЕфицировэдшой задачей выбора направления спуска. Лт формулировки декомпозируемой задачи выбора направления спуска используются оценки перекрестных связей в ограничении на управления. Полученные оптимальные управления непрерывны, но имеют разрыв производной. В §2 исследуются линейно-квадратичные задачи с линейными ограничениями на управления. Здесь используется линейное агрешрованио управлений по схема §3 главы II, когда матрица агрегирования связана с ыатрщей ограничений исходной задачи. Результирующая ыакрозддача юлеет только ' интервальные ограничения иа макроуправлещщ, что облегчает определение точек переключения оптсагаяьнш: макроуправленый. (йядоальные декагрегиревалкая управления имеют значительно болье ехтшй вид, что иллюстрируется соответствующей графи-

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

III. ОСНОВШВ ПОЛОЖЕНИЯ, ШШШШ НА ЗАЩЕУ

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

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

3. Для частично-сепарабельных, блочных, блочно- сепара-белышх, задач со связываищши переменными и известными оценками перекрестных связей обоснована модификация метода, в которой

указанные особенности структуры используются при формировании

*

подзадач.

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

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

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

6. Представлены результаты вычислительного эксперимента для задач оптимального управления, подтвервдающие теоретичесие обоснования метода разлсшяння, а тага» его эффективность.

Основные результаты диссертации опубликованы в следующих работах:

1. Литвинчев И.О. Декомпозиция путем замены переменных в экстремальных задачах.- М.: Щ АН СССР, 1986. -25

2. Литвинчев И.С. Ыетод декомпозиций для задач оптимизации не обладающих блочно-сепарабельнсй структурой// Цурн. тчпсл. матемьтики и «аг.физики.- 1967.- Т.?7, В 3. - С.332-339.

3. Литвинчев И.О. Декомпозиция для несенарабельных экстремальных задач // ДАН СССР. - 198?. Т.292, & 1. - с.33-36.

4. Литвинчев И.С. Декомпозиция в динаыичесшс. задачах со смешанными 01раннченшши // Дифференциальные уравнения. -1989. - Т.25» >5 в.- С.1453-1457.

Литвинчев И.С. Итеративная декомпозиция в данааических задачах с перекрестны»! связный // ДАН СССР.- 19в9.-Т.306, $ 5.. - 0.1046-1048.

6. Литвинчев И.С. Декомпозиция больших дшшшческнх систем с перекрестными саязяшт // Изв.АН СССР. Техн. кибернетика. -1989- - й 3- - А-20-28.

7. Литвинчев И.О. Итеративное агрегирование в лшшёно-квадратичных задачах о перекрестными связями // Курь

вычисл. математшш и мат. физики.-1989.-Т.29, ЖГо. -С. 1594-1596.

8. Литвинчев И.О. Исследование многомерных задач управления процессом теплопередача // Мат.моделирование. - 1969. -Т.1, » 11. - С.25-33-

9. Литвшчев И.О. Декошюзяцня в управлении системами гипер-бсиамеского типа с перекрестная! связями // Изв. АН СССР. Техн. кибернетика.- 1989. - Я.6. - С.85-9?..

10. Литвннчев И.С. Декомпозиция в экстремальных задачах со специальной структурой // ВУрн. вычисл. математики и мат. физики.- 1990. - Т.30, В 7. - С.1008-10016.

11. Литвинчев И.О. Использование структуры я оценок перекрестных связей в методе декомпозиции задач оптимального управления // Изв. АН СССР. Техн. кибернетика.-1990.- IfS.-С.104-115.

12. Литвинчев И.С. Итеративная декомпозиция задач с уравнениями в частных производных первого порядка // Кибернетика.-1990.- J86.- С.58-62.

13- Литвинчев И.С., Курков В.И. Задачи управления большой размерности с перекрестными связями. I. Примеры постановок // Мат. Моделирование.- 1990.- Т.2.Й12.- С.3-16.

14. LItvinchev T.S. Dewmpoa it ion-aggregation method for convex programing problems // Optimization.- 1991.-V.22, HI.- P. 47-56.

15. Литвинчев И.О., Цуркяв В.И. Задачи управления большой размерности с пе^^рестными связями. ТТ. Итеративные методы

декомпозиции// Иат. Моделирование.- 1991.-Т.З,Ш.- С.79-85.

16. Литвинчев И.С. Итеративное агрегирование и декомпозиция в Ляочно-сепарабельных задачах // Бурн. вычисл. математики и мат. физики.- 1992.- Т.32.Ш.- С. 1320-1323.

17. Lltvinchev I.S. Iterative aggregation method for the constrained optimal control problems //J. Computet. Appl. Math.- 1992.- V.39.H3.- P.315-328.

18. Lltvinchev I.S. Aggregation-decomposition approach to large-scale syatema control: methods and results // Proc. European Space Agency Workshop on Spacecraft Guidance Navigation and Control Systems, Jfoordwijk, 1992.- P.2C.4.1 - 2C.4.18.

19. Литвинчев И.О. Оценки субоптимальности агрегирования в выпуклом программировании // Курн. вычисл. математики и мат. физики.- 1993,- Т.ЗЗ.Ш.- С. 1145-1154.

20. Литвинчев И.О. Использован ia низших оценок при минимизации методом внутренней точки // Щурн. вычисл. математики и мат. физики.- 1994.- Т.34.К'.- С. 986-992.

21. Цурков В.И., Литвинчев И.С. Декомпозиция в динамических задачах с перекрестными связями. М:Наука, 1994.-352 с.