автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Управляемые методы решения прямых и обратных задач оптимизации

АКАДЕМИЯ НАУК СССР ИНСТИТУТ ПРОБЛЕМ КИБЕРНЕТИКИ АН СССР

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

АНТИПИН Анатолий Сергеевич

УДК 519.85; 617.9

УПРАВЛЯЕМЫЕ МЕТОДЫ РЕШЕНИЯ ПРЯМЫХ И ОБРАТНЫХ ЗАДАЧ ОПТИМИЗАЦИИ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени доктора физико-математических наук

МОСКВА - 1991

Работа выполнена в Институте проблей кибернетики АН СССР

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

профессор Ф.П.Васильев, доктор физико-математических наук, профессор И.И.Ереыин, доктор технических наук, профессор С.К.Коровин

Ведуцая организация: Вычислительный центр АН СССР

Зацита состоится СО_" 1991 года в (^часов на

заседании Специализированного Совета Д 003.78.01 по защите диссертаций на соискание ученой степени доктора наук при Институте проблем кибернетики АН СССР (117312, Москва, ул.Вавилова, 37)

С диссертацией иожно ознакомится в библиотеке Института Автореферат разослан "_£ е- Iе 1991 г.

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

А. Н.Сотников

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

^сйртгАК'т^альность проблемы. Методы оптимизации в настоящее фемя стали мощным средством решения прикладных оптимизационных (адач. Сфера приложений этих методов огромна. Прежде всего это жономика, технология, экология, проектирование сложных систем [ многое другое. Однако растущие запросы практики выдвигают на 1ервый план проблему численного решения не одной задачи оптими-(ации, а их систему, т.е. семейство связанных между собой задач. I качестве примеров можно указать задачи о вычислении седловых ючек, равновесные и игровые задачи, а также системы вариационных неравенств. Не всё из арсенала методов оптимизации может 1ыть использовано для решения сложных систем задач оптимизации, 'ак например, хорошо известные методы оптимизации, построенные ia идеях линейной и квадратичной аппроксимации (градиентные, [ьютоновские и др.),не сходятся к седловин точкам выпукло-вогну-'ых вырожденных функций и тем более они не сходятся к равнове-:ию по Нэшу в простейших играх с ненулевой сумной.

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

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

I. Задача выпуклого программирования. Требуется определить 1ектор I , доставляющий оптимум целевой функции f(l) на юпустимом множестве:

i"eAzgmLntl(ï): 3(1) <0, ieQ}. (1)

1ектор I и выпуклое множество Q принадлежат конечномерному 1вклид0ву пространству, целевая функция |(l) и каждая компо-

нента векторной функции 9(1) - выпуклые скалярные функции.

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

1(х\р) < Кх'.р") < 1<х,р")

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

а(1)<0, хеО).

Здесь выражение J обозначает все множество сед

вых точек функции Лагранжа £(Х,р) = ^(Х)+<р,3(Х)>. Символ БёМпС- • •} обобщает известное выражение Агзш1п{* • •)• Решение задача (2) эквивалентно решению вышеприведенной сист •неравенств.

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

х*еАгатт{|(х,и*): э(х,и*)<0, хеО}, и*еи, С(х*,и*) < 0,

т.е. в задаче параметрического выпуклого программирования требуется выбрать параметр (управление) 11=11 и отвечающий ем: оптимум, такой, чтобы выполнялась система неравенств С(Х,и)< В случае сильной выпуклости целевой функции |(Х,и) и линейно 6(Х,и) система (3) переходит в систему нелинейных уравнени

х* = а*зю'т{?(х,1Г): з(х,и*)<0, хеО), и*еи, = ваМ* ♦ а,

здесь и - также выпуклое замкнутое множество конечномерного эвклидова пространства. Размерности матриц Б! и Бг и переменных Х,и согласованы так, что второе уравнение из (4) описывает непустое линейное многообразие для всех X и р.

Перечисленные задачи расположены по возрастающей трудно* их решения. Соответственно этому перечислению классы задач И1 ют различное алгоритмическое обеспечение. А именно, задача в1 пуклого программирования имеет почти завершенную теорию методов поиска оптимума с огромным набором различных методов, доказательствами их сходимости и оценками скорости сходимост] (Ф.П.Васильев, Ю.Г.Евтушенко, В.Г.Карманов, Б.Т.Поляк и др.) В этом классе задач целесообразно разрабатывать методы с новыми свойствами (например, свойствами допустимости).

Задача о поиске седловых точек имеет небольшой разрозненно набор подходов для ее решения. Это методы модифицирований функции Лагранжа (Б.Т.Поляк, Е.Г.Голыптейн, Н.В.Третьяков, I.Г.Евтушенко, Й.Т.ВОСКС^Б-Каг, Э.М.Вег1^БСаЛ и др.), методы, снованные на идеях прогнозного шага (Г.М.Корпелевич) и итера-■ивной регуляризации (Б.Т.Поляк, А.Б.Бакушинский.Ф.П.Васильев [ др.). Общей концепции, теории или принципов построения методе вычисления седловых точек не существует, поэтому стоит зада-га разработки такой концепции. В отличие от седловых задач, для юшения которых существуют итеративные процессы, сходящиеся к юшениям, для обратных задач оптимизации, напротив, такие не [звестны. Этот важный класс задач не имеет алгоритмической под-(ержки.

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

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

1. Разработка непрерывных и итеративных методов линейной и [вадратичной аппроксимации для решения задач выпуклого програми-ювания. Методы квадратичной аппроксимации имеют свойство допус-•имости (внутренности).

2. Разработка единой теории (схемы) непрерывных и итера-'ивных управляемых вычислительных методов поиска седловых точек 1Ьшукло-вогнутых вырожденных функций.

3. Разработка методов решения обратных задач выпуклого [рограммирования.

Методы исследования. Основным инструментом исследования :лужит аппарат неравенств выпуклого анализа. Классическая сис-

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

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

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

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

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

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

Аппробация работы и публикации. Основные результаты диссертации докладывались на Международной конференции по методам математического программирования (Польша,Закопане,1977), Всесоюзном семинаре по оптимизации и ее приложениям (Душанбе,1986), 1У-м Всесоюзном симпозиуме по методам решения нелинейных уравнений и задач оптимизации (Вильянди.1987), IV Международном симпозиуме "Автоматизация и научное приборостроение" (Болгария,

1арна,1987), 10-м Всесоюзном симпозиуме по системам программно-■о обеспечения решения задач оптимального планирования (Нар-а, 1988), Ш-м семинаре ИФАК по приложениям в нелинейном прог-1аммировании и оптимизации (Тбилиси, 1988), Ш-й школе-семинаре Численные методы для высокопроизводительных систем" (Фрун-е,1988), Всесоюзной конференции по методам математического рограымирования и программного обеспечения (Свердловск,1989), 4-й Международной конференции ИФИП по системам моделирования и птимизации (Лейпциг,1989), а также на семинарах в ИПК АН СССР, НИИСИ, ВЦ АН СССР, факультете вычислительной математики и ки-ернетики МГУ. Аппробация диссертации в целом проведена на семи-аре ИПК АН СССР в 1990 г. По теме диссертации опубликована 21 абота (все без соавторов).

Структура и объем работы. Диссертация изложена на 231 границах машинописного текста и состоит из введения, четырех 1ав, заключения и списка литературы, содержащего 84 работы.

СОДЕРЖАНИЕ РАБОТЫ

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

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

Во-первых, дифференциальные уравнения могут стать источни-1 новых эффективных итеративных процессов в зависимости от "•о, какие конечные разности используются для аппроксимации шзводных: левые, правые, симметрические или многоточечные. >гие из этих процессов нельзя обнаружить, оставаясь в рамках (вычных представлений связанных с градиентным спуском. В пер) очередь это относится к неявым итеративным схемам, эффек-

тивность которых доказана в методах решения уравнений математической физики.

Во-вторых, дифференциальные процессы можно рассматривать в качестве представителей конечно разностных методов с малыми по времени шагами, т.е. методов, которые получаются в результате аппроксимации производной dx/dt разностью (ln+1-In)/Дt, где At - достаточно малая величина. Итеративные процессы, в свою очередь, можно трактовать как методы с большими по времени шагами (т.е. At=l). Первые процессы медленно сходятся вдали от решения, но устойчивы в силу малых шагов к различным возмущающим факторам в окрестности решения; вторые методы, наоборот, быстро сходятся к окрестности решения, но неустойчивы в окрестности решения в силу достаточно большой величины шага. Поэтому для уверенного поиска решений реальных задач необходимо сочетание тех и других методов.

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

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

Применительно к задаче выпуклого программирования (I) в диссертации рассматривается непрерывный метод линеаризации dx/dt = sTH<*>{x - ос vid)} - i, i(to)=i°» M(t) = {z: V3d)(z-x) + a(D < 0, zeQ) (5)

и его итеративный аналог

xn+1 = Яи<п>(1" - avid")).

M(n) = {z: v»(xn)(z-i") ♦ ad") < 0, zeQ}. (6)

Здесь V8(X) - матрица, каждая строка которой - вектор-градиент соответствующего функционального ограничения. Множество h(t) (с точностью до Q) представляет собой многогранное множество, образованное пересечением полупространств <V8»d), z-x> + 3id) < о, 1=1,...,Ш. Оно может быть построено в каждой точке X и на него проектируется вектор

X - OCVfd). Символ Stн<. >{' ' •} - оператор проектирования вектора на множество М(*). Вектор разности

îtM<t>d - avid)) - X определяет направление, с которым должен совпадать касательный вектор траектории X(t). Операция проектирования вектора X - OCV|(X), с одной стороны, является

сильно выпуклой задачей квадратичного програиирования, для решения которой существуют эффективные методы. С другой стороны, это одна из немногих задач квадратичного программирования, для которой можно в явном виде выписать двойственную задачу. Если множество Q совпадает со всем пространством R", т.е. яГа( • )=1 -единичный оператор, то задача, двойственная по отношению к (5) и (6), принимает соответственно вид:

Р = агэтах(-сх/2 | 7|(х)+79т(хЫ2 + <ч, ?(х)>: s»>0], dbc/dt = - a(vf(x)+v3T(i)p), x(t0)=x°. (7)

Pn = агзшах{-а/2 | 7|(х>7 3т(хпЫ 2 ♦ <4, 9(xn)>: a> 0}, xn+1 = xn - aivKx^+va'ix^p"). (8)

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

Если в задаче (I) множество Q не совпадает со всем прост-эанством R", то процессы (7) и (8) можно обобщить соответственно следующим образом:

Р s агзпгах{-1/2а |5ta(x-oc( vf(x)+ 73T(x)y))l2+ l/2oc|x|2+

♦ <4, 3(X) - V3(x)x>: 0},

dl/dt = Sta(X - OC( 7-f(l)+V3T(X)P)) - X,

x(to)=x°. (9)

i

Pn = azgmcn:{-i/2a I jta(xn-cx( vj(x> v3T(xn)3))l M/2ot|xn| 2+

+ <3, 3(xn) - 73(xn)xn>: a>0}» xn+1 = 3Ta(in - a( 7|(хп)*7 3т(хп)р"}). (10)

Поскольку предполагается, что множество Q "простое", напри-iep, положительный ортант, параллелепипед или шар, то вспомога-•ельная задача оптимизации в этих процессах "почти" квадратич-[ая.

Прежде чем привести теоремы о сходимости рассматриваемых [роцессов, сделаем следующие предположения.

А. Задача выпуклого программирования (I) удовлетворяет 'словию регулярности Слейтера (существует вектор Хс 6 Q, акой, что ?(ХС) < 0). Это условие гарантирует выполнение тео-юмы о существовании решения задачи (I).

Б. Скалярная функция ^(Х) и каждая компонента векторной

функции 3(X)=(9i(l).....Э.(Х)) - выпуклые дифференцируемые

функции, причем градиенты всех функций удовлетворяют условию Липшица с константами L0> L=(L 1*...,Lm). .

В. Q - выпуклое замкнутое множество из Rn.

Сформулируем теоремы о сходимости.

Теорема I. Пусть выполняются условия А - В, тогда, если в процессах (5) и (9) параметр ОС выбирается из условия

ч

0< а < , , , ,

где р - множители Лагранжа задачи (I), то множество точек равновесия X систем (5) и (9) асимптотически устойчиво, т.е. l(t) Х*еХ* при t оо ддя всех 1°.

Теорема 2. Пусть выполняются условия А - В, тогда, если в процессах (6) и (10) параметр ОС выбирается из условия

2

0< ОС < -;--— ,

L0+2<L,P >

где р - множители Лагранжа задачи (I), то Xn -» X*gQ при И оо для всех Х°.

Если целевая функция сильно выпуклая, то оценка скорости сходимости рассматриваемых процессов носит экспоненциальный характер для непрерывных процессов

|x(t)-x*|2 < Cexp(-2a(cx)t)

и линейный - для итеративных

|хП+1-хТ < Ч(СС)|хп-хТ.

Вид функций а(0С) и Ч(ОС) приводится в тексте диссертации.

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

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

Изложим идею подхода на примере задачи выпуклого программирования (I). Полагая, что начальное приближение X - строго допустимая точка, т.е. 9(Х°)<0, определим траекторию X(t) с помощью процесса

cfa/dt = srS(t)(x - otvf(x)) - х» Sit) = {z: 1/2 Iz-xl'B + oc(72(x)(z-x)+8(x)) < 0, zeQ),

X(t0)=X°. (Ii)

Здесь ß=(l,l,...,i), параметр OC>0, множество S(t) не пусто (содержит точку X) и является пересечением Ш шаров

{z: |z - (x-ccv3t(x))|2 < tx.(a| V9i(x)|2 - 2з,(х))}, 1=1,2,...,m с центрами X-OCV9t(X) и квадратами радиусов 0C(0C| V? t(X)| 2 - 23i(x)). в силу неравенства 3t(X)<0 задача проектирования в каждый момент времени удовлетворяет условию Слейтера, а если 7?(Х) удовлетворяет условию Липшица» то при некотором ограничении на величину параметра ОС>0 и с учетом выпуклости 9(Х) можно показать, что точка Х+Х, где X = dx/dt, также будет строго допустимой.

Выпишем итеративный аналог процесса (II), заменив производную dl/dt на соответствующую разность х"*1-!":

xn+1 = :гг5<„>(хп - осvf(x")),

S(n) = {х: 1/2 Ix-xl'e + ос( v9(xn)(x-xnM(xn)) < 0, xeQ}.

(12)

При некотором ограничении на длину шага ОС последовательность, порожденная процессом (12), будет допустимой (внутренней).

Задача проектирования в (II) - эта задача минимизации квадратичной функции на квадратичных ограничениях. В вычислительном плане она может оказаться достаточно трудоемкой. Чтобы избежать этого,для каждого момента t можно перейти к двойственной задаче, и если множество Q совпадает со всем пространством R", т.е. 5Та( • ) = I, то получим двойственный процесс

г ос Iv?(x)+v9T(x)»r , , 0i

Р = az9fflOx{- — • ' ' - + <2(х)л>: 0},

2 1+<В,9>

tfa/dt = - a. 'fM*v»'MP 1+<в,р>

x(to)=x°. (13)

Его итеративный аналог имеет вид

р.. агз1т£. г.. ivi(x>T»'n")!ii' 4 a>0)>

2 i+<e,a>

. . ее ' '«W . ,1Ч)

i+<e,p >

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

Приведем теоремы обоснования сходимости. Теорема 3. Пусть выполняются условия А - В, тогда, если в процессах (II) и (13) параметр ОС выбирается из условия

0< а < 4 ,{1f f f ^ . Lo+2<L,p >

где р* - множители Лагранжа задачи (I), траектория p(t) ограничена константой |p(t)UCon6t, то множество точек равновесия X* систем (II) и (13) асимптотически устойчиво, т.е. l(t) X EX при t -> °о для всех 1°. Если при этом параметр ОС выбирается из условия ОС < ШШ{2А>о»iA> 1»• • • »i/Lm}» то траектория является внутренней, т.е. 3(X(t)+X(t)) < 0 для всех t> 0.

Теорема^. Пусть выполняются условия А - В, тогда, если в процессах (12) и (14) параметр ОС выбирается из условия

2 {1+<р»,е>3

0< а < -0.1 о«ч- »

Lo+2<L,p >

где р* - множители Лагранжа задачи (I), траектория рп ограничена константой |р"| < COTlAt, то Хп X*eQ при П <*> для всех Х°. Если при этом параметр ОС выбирается из условия

О < а < nLn{2/L0,i/U.....1Д«3» то траектория является

внутренней, т.е. §(Х("+1)) < 0 для всех П.

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

|x(t)-xT < Cexp(-2a(oc)t)

и линейный характер - для итеративных

|xn+1-xT < Ч(сс)|хп-хТ.

Вид функций а(ОС) и 1(ОС) приводится в тексте диссертации.

Итеративные методы линеаризации имеют достаточно длительную историю развития. Для задач нелинейного программирования первые версии этих методов без доказательства сходимости были сформулированы в работах Р.Гриффита, Р.Стюарта, Г.Зойтендейка, У.Зангвилла. Сходимость своей версии метода линеаризации впервые доказал Б.Н.Пшеничный. Р.П.Федоренко успешно использовал различные варианты метода линеаризации для решения задач оптимального управления. В дальнейшем итеративные методы линеаризации исследовались многими авторами.

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

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

х* = -а7 1,(1к,р*)),

р* = лЛР* ♦ а7 1Л1ж,р*)). (15)

Здесь V £х(Х,р) - вектор-градиент функции £(Х,р) по переменной X, а 7^Р(Х,р) = 3(Х) - по переменной р. 5Га( ' )

и ЭТ +( • ) - операторы проектирования на множество 0 и положительный ортант Точка Х*,р* в (15) является неподвижной точкой, или точкой равновесия.

Если функция £(Х,р) недифференцируема, то необходимые условия задачи (I) естественнее представлять не в форме (15), а форме проксимального оператора, т.е. оператора регуляризации

х* = агзшьпС 1/2 |н-х*|2 ♦ ос£(2,р*): геО),

р* = агдтахС-1/2 1»-р1 2 ♦ акх*,»): (16)

Как следует из (16), если X ,р - седловая точка функции Лагранжа, то она - неподвижная точка проксимального (регу-ляризационного) преобразования:

рг^х.р) = агзштС 1/2 |г-х|2 + а2,(г,р): неО], рг2(х,р) =агдах{-1/2 1з-р|2+ ос2.(х,а): (17)

Разности между правыми и левыми частями (15) и (16) порождают невязки, равные нулю в X ,р* и не равные нулю в произвольных точках X,р.Простейшие дифференциальные системы,на траекториях которых невязки могут убывать пропорционально касатель-

нону к траектории вектору, имеют следующий вид: градиентные системы -

dx/dt = sta(x - av 1«(х,р)) - х, dp/dt = sr+(P + avi„(x,p)) - p,

X(to)=X°» P(to)=P°. (18)

проксимальные системы -

dx/dt = az3nln{ i/2 lz-хГ + txl(z,p): zeQ) - x, dp/dt = агэтах{-1/2 jy-pl* + ocl(x,a): aeRT} - p,

x(t0)=x°, P(t0)=P°. (19)

Если Q = R", а ограничения в задаче (I) - только типа равенств (ограничения такого типа возможны, хотя в постановке (I) они не содержатся), то 5Гв( •)=1иЯ+(,)=1 и система (18) принимает форму хорошо известного непрерывного градиентного метода (К.Дж.Эрроу, Л.Гурвиц, Х.Удзава)

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

£(x,p)=f(x)+<p,3(x)>, отметим его более широкую сферу применимости и более высокую эффективность для решения негладких задач, для которых градиентные методы уже не работают или дают слишком грубое приближение.

Методы (18) и (19), начиная с X(to) = X и для всех t > to» согласно теоремам существования, единственности и продолжимости решения, порождают непрерывные траектории. Простейшие примеры показывают, что траектории этих дифференциальных уравнений не сходятся с течением времени к седловым точкам выпукло-вогнутых функций.

Для решения проблемы сходимости дифференциальных процессов (18),(19) к седловым точкам предлагается рассмотреть эти процессы в рамках представлений, связанных с управляемыми динами-

ческими системами. С этой целью в системы (18) и (19) введем управления U, U

di/dt = sta(x - av £х(х,р + u)) - х, dp/dt = зг+(р + av Х,„(х + u,pj) - р,

x(to)=x°, P(to)=P°. (20)

dx/dt=a2mn{ 1/2 |z-x|2 + a£(z,p + u): zeQ} - x, dp/dt =azgfnai{-l/2 ta-p|2 + al(x + ил): aeR") - p,

x(t0)=x°, P(t0)=P°. (21)

и поставим следующую задачу. В некотором классе обратных связей u=u(x,p,x,p), u=u(x,p,x,p), где iieU, ueV и x=dx/dt, p=dp/dt,

требуется выбрать управления как функции состояния динамических систем, которые обеспечили бы сходимость траектории X(t),P(t) к равновесию, которое описывается задачей выпуклого программирования (I). Другими словами, необходимо синтезировать алгоритм управления, с помощью которого системы (20) и (21) переводятся

„о „о

из произвольного начального состояния X ,р в равновесное -X ,р .

• • • I

Обратные связи U=U(X,P,X,P), U=15(X,P,X,P) можно интерпретировать как положение "рулей" объекта, который перемещается по исследуемой траектории, или как вектор энергии, которую необходимо израсходовать для удержания "рулей" в заданном положении. В точке равновесия объект неподвижен и его скорости X и р равны нулю, поэтому расход энергии в равновесии нулевой: u=u(x\p",x(oo),p(oo))=0, U=U(X*,P*,X(oo),p(oo))=0. Это требование, накладываемое на управление, вытекает из существа ситуации. Во всем остальном управления могут быть достаточно произвольны. Самые простейшие управления имеют вид

a = р, и = х (22)

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

Если системы (20) и (21) замкнуть управлениями (22), то получаются системы дифференциальных уравнений, не разрешенные относительно производных. При переходе к разностным аналогам им будут соответствовать неявные системы уравнений, для решения которых, в свою очередь, потребуются какие-то другие итератив-

ные подпроцессы. Иногда это может оказаться неудобный.

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

u = 51+(р + a v 1Лх,р)) - р, о = х (23)

или симметричную ей:

u = р, и = sra(x - avix(i,p)) - х. (21)

Напомним, что V £„(Х,р)) = f(l), поэтому (23) можно представить в форме

u s згЛр + осз(х)) - р, u = х. (25)

Содержательный смысл новых обратных связей состоит в подавлении не равных нулю невязок (15),(16).

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

A. Множество седловых точек функции Лагранжа £(Х,р) =

= |(Х)+<Р»3(Х)> задачи выпуклого программирования (2) не пусто.

Б. Скалярная функция |(Х) и каждая компонента векторной функции 9(x)=(9i(x),...>9«(Х)) - выпуклые дифференцируемые функции, причем градиенты всех функций удовлетворяют условию Липшица с константами L<>> L=(Li,... ,Lm).

Б1.Скалярная функция |(х) и каждая компонента векторной

функции 9(x)=(9i(x).....2а(Х)) - выпуклые (не обязательно

дифференцируемые), 9(х) на множестве Q удовлетворяет условию Липшица с константой ы.

Б'.Скалярная функция |(Х) и каждая компонента векторной функции 9(х)=(3i(x),...,9»(Х)) - выпуклые (не обязательно дифференцируемые).

B. Q - выпуклое замкнутое множество из Rn.

Теорема 5. Пусть выполняются условия А, Б, В, тогда,

если в процессе (20) и (23) найдется такой вектор С, что для всех t> t0 траектория p(t)=Jt+(P(t)+0l9(X(t))) i С, а параметр ОС, выбирается из условия

_ Ч _

0< a < ((L0+<L,C>)2 ♦ 16Ы2 )1/2 ♦ (L0+<LC>) '

то множество точек равновесия системы (20),(23) асимптотически устойчиво, т.е. X(t) Х*еХ*, p(t) Р*еР* при t оо для всех X°eQ, р°> 0.

Теорема 6. Пусть выполняются условия А, Б, В, тогда,

если в процессе (20) и (22) найдется такой вектор С, что для всех t> to выполняется неравенство p(t)+p(t)<C, а параметр ОС выбирается из условия

2

0< ос < —:—¡-р—,

то множество точек равновесия системы (20),(22) асимптотически устойчиво, т.е. x(t) -» Х*ЕХ", P(t) р"еР* при X -» оо для всех

X°EQ, р°> 0.

Теорема 7.Пусть выполняются условия А, Б , В, тогда, если в процессе (21) и (23) параметр ОС выбирается из условия 0< ОС < 1/Ы» то множество точек равновесия динамической системы (21),(23) асимптотически устойчиво, т.е. X(t) X бХ ,

p(t) -» Р*еР* при t -» оо для всех Х° Е Q, р° > 0.

2

Теорема 8.Пусть выполняются условия А, Б , В, тогда, если в процессе (21) и (22) параметр ОС выбирается из условия 0 < ОС, то множество точек равновесия динамической системы (21),(22) асимптотически устойчиво, т.е.

x(t) х*еХ*,

p(t) Р*еР* при t ^ оо для всех Х° е Q, р° > 0.

Для рассмотрения итеративных аналогов (20) - (24) заменим производные dx/dt и dp/dt в этих уравнениях конечными раз-

„п+ 1 _п _п+ 1 „

ностями X -X и р -р . Полученные соотношения будем трактовать не как разностные схемы для этих уравнений, а как самостоятельные и независимые итеративные процессы, вопрос о сходимости которых всякий раз будет решаться независимо от непрерывного случая. Здесь необходимо подчеркнуть принципиальное различие между аппроксимацией производных dl/dt величиной

(Xn+1-Xn)/At и ее заменой конечной разностью Хп + 1-Хп. В первом случае мы стремимся уменьшить At 0 и тем самый аппроксимировать непрерывную траекторию кусочно-ломаной кривой, во втором (At=i), наоборот, стремимся увеличить At, с тем чтобы быстрее попасть в окрестность решения задачи.

Если в системе (20) управления U и U замкнуть обратными связями (22), а затем производные заменить их конечными разностями, то получим систему нелинейных уравнений, не разрешенную (неявную) относительно переменных Xn+1,pn+1: xn+1 = staix" - av lx(Xn,p"M))» pn+1 = sr+(Pn + OC9(Xn+1)). (26)

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

Если же систему (20) замкнуть обратными связями (23) с последующей заменой их производных конечными разностями, то получим уравнения, разрешенные (явные) относительно пере-

_п+ 1 _п+ 1.

ыенных I ,р :

р" = згг+(рп + <хз(хп)), хп+4 = лв(хп - а7 1,(1п,рп)), Рп+1 = угЛр" + аэ(хп+1)). (27)

В этом процессе коррекция идет по двойственным переменным Р (двойственный процесс); если же воспользоваться обратными связями (24), то получим процесс, в котором коррекция идет по прямым переменным X (прямой процесс).

Первую формулу в (27) можно интерпретировать как прогнозный шаг.

Сформулируем задачу об управлении вычислительный итеративным процессом. В итеративной системе

х"+1 = 5Га(х" - аV 1х(хп,р" + и")),

рп+1 = яЛРп + аэ(хп ♦ о")) (28)

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

и" = и(х",рп,хп+\рп+1), ип = и(хп,рп,х"+1,Рп+1), (29)

которые обеспечили бы при сходимость траектории замк-

нутой итеративной системы к какой-либо одной седловой точке функции Лагранжа задачи выпуклого программирования (I). Обратные связи, 1Г = р"+1-рп, ип = Хп+1-Хп и II" = ЗГ +(рп - ССЗЮ) - Рп, И" = Хп+1-Хп, которым соответствуют замкнутые системы (26) и (27), являются частными случаями (29).

Градиентные методы предполагают дифференцируемость целевой функции и функциональных ограничений. Существует значительное число прикладных задач, для которых это требование не выполняется. Например, во многих прикладных областях, особенно в математической экономике, часто используются функции типа максимумов |(х)=шах{<а 1,Х>-ёь 1=1,2,...го), которые выпуклые, но недиф-ференцируемые и для оптимизации которых градиентные методы не применимы. Для оптимизации негладких выпуклых функций можно использовать проксимальные методы.

Перейдем к итеративным аналогам проксимальных дифференциальных систем. Замкнем систему (21) управлениями (22) и заменим все производные их конечными разностями (аналог (26)), тогда получим

in+1 = cwgmLn{ 1/2 |x-xT ♦ oci(x,pn+1): xeQ)

Pn+1 = агдах{-1/2 |p-pn|2 + ttl(in,1,P): peRT). (30)

Операция минимизации по X в первой формуле приводит к итеративному процессу, когда на каждой итерации необходимо решать обратную задачу оптимизации типа (4). Действительно, (30) можно переформулировать следующим образом:

xn+1 = az3fflin{l/2 |х-х"|2 + a£(x,pn+1): xeQ), (31) pn+1 = 5Г.(РП * аз(хп+1)). (32)

Отметим, что (32) и второе соотношение из (30) в силу линейности функции Лагранжа £(Х,р) по переменной р эквивалентны.

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

Покажем, что неявный процесс (31),(32) очень тесно связан с методом модифицированной функции Лагранжа. Действительно, уравнение (32) разрешено относительно переменной р"+1> поэтому ее можно "подставить" в правую часть (31), тогда можно получить (см. главу 2 диссертации)

xn+1 = azmn{i/2 |x-xT + aJU(x,pn): xeQ)

pn+1 = л+(Рп ♦ a?(xn+1)), (33)

где Л(х,р")=|(х) + 1/2ос |зг+(Р"+ос.з(х))|2 - 1/2оо |pn|2 -

модифицированная функция Лагранжа. Процесс (33) в отличие от (31),(32) является явным процессом и, хотя он получен формальными преобразованиями из второго, тем не менее это разные вычислительные методы с различными объемами вычислений на каждой итерации и с неодинаковыми свойствами сходимости и различной сферой применимости.

Если дифференциальную систему (21) замкнуть обратными связями (23), заменить производные конечными разностями, а переменные - их значениями в фиксированные моменты времени, то придем к итеративной системе:

р" = 5ГЛР" ♦ tX3(Xn)h

xn+1 = azmn{l/2 |х-хТ + al(x,pn): xeQ),

p"+1 = зтЛР" + ссэ(хп+1)). n (34)

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

новое состояние системы хп+1,рп+1.

В процессе (34) используется обычная функция Лагранжа, а не модифицированная, как в (33), что имеет большое значение для задач с блочно-сепарабельной структурой. Дело в том, что функция Лагранжа сохраняет блочно-сепарабельную структуру исходной задачи, а модифицированная функция Лагранжа не сохраняет. Поэтому вспомогательная задача оптимизации в (34) распадается (декомпозируется) на П независимых подзадач, каждую из которых можно решать отдельно друг от друга, а это имеет важное значение для задач большой размерности. На каждой итерации процесса (33) оптимизируется модифицированная функция Лагранжа, которая уже не имеет сепарабельной структуры, а процесс в целом не обладает свойствами декомпозиции, что является одним из его недостатков.

В заключение этого раздела рассмотрена задача об управлении вычислительным проксимальным процессом. В системе

хп+1 = агзш1п{1/2 |х-хпГ + а1(х,рп + ип): хеО), Рп+1 = згЛр" + а*(хп + и")) (35)

требуется выбрать управления

ип=и(хп,рп,хп+1,рп+1), ип=и(хг\рп,хп+\р',+1), (36)

которые обеспечили бы при П->°° сходимость траектории замкнутой системы к какой-либо седловой точке функции Лагранжа. Управления, использованные в задачах (30), (32) и (34), являются частными случаями (36).

Теорема 9. Пусть выполняются условия А, Б, В, тогда, если в процессе (2?) найдется такой вектор С, что для всех П последовательность рп < С, а параметр ОС выбирается из условия

_ 2 _

0< а < «и^ис»2 ♦ 16|зГ )1/2 ♦ (и*<ис>) '

то процесс (27) монотонно, по норне пространства х-р, сходится к седловой точке задачи (2), т.е. ХП-»Х ех , рп-»р ер при п °° для всех Х°еО, р > 0.

Теорема 10.Пусть выполняются условия А, Б, В, тогда, если в процессе (26) траектория р"<С, а параметр ОС выбирается из условия

0< а < , * , г—,

то процесс (26) монотонно, по норме пространства Х'Р, сходится

к седловой точке задачи (2), т.е. Хп-»Х*ЕХ*, р"->р*ЕР* при а оо для всех Х°е£), р°> 0.

Теорема II.Пусть выполняются условия А,Б1,В, тогда, если в процессе (34) параметр ОС выбирается иэ условия 0 < ОС< 1/(2^Ы). то Хп»рп сходится монотонно к некоторому решению исходной задачи, т.е ХП->Х е0 , рп->р*ЕР при для всех Х°Е0, р°> 0.

2

Теорема 12.Пусть выполняются условия А,Б ,В, тогда, ест в процессе (30), параметр ОС выбирается из условия 0 < ОС, то Хп,р" сходится монотонно к некоторому решению исходной задачи, т.е. ХП-»Х*, рп->р* при П-»°о для всех Х°е0, р°> 0.

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

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

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

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

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

Задачу об управлении вычислительным процессом второго порядка можно сформулировать следующим образом. В некотором классе обратных связей: U=U(X,P,X,P,X,P), U=U(X,P,X,P,i',P)> где uell, ueV и x=cbc/dt, p=dp/dt, x=dVdt\ psdtydt2,

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

ßdVdt2 + dx/dt = 5ta(x - otv 1„(х,р + u)) - х, ßdVdt2 + dp/dt = arr +(p + otv£P(x + u,p)) - p,

x(t0)=x°, p(t0)=p°, x(t0)=x1, P(t0)=P1. (37) или проксимальной

ßdVdt2 + dx/dt =az9mln{ i/2 |z-x| 2+ otl(z,p + u): zeQ) - x, ßdVdt2 + dp/dt=azmn{-i/2 Ь-рГ+ а£(х + в,а): И>0) - р, X(t0)=X°, P(to)=P°, x(t0)=x1> Plto)^1. (38)

которые обеспечили бы сходимость траектории X(t),P(t) к к равновесному состоянию систем Х*,Р*. Таким образом, речь идет о синтезе алгоритма управления, с помощью которого система (3?) или (38) переводится из произвольного начального состояния Х°,Р в равновесное - Х*,р*.

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

u« ßp + p, и = £х + х (39)

и = лЛР + а7 1Р(х,р)) - Р, и = Рх + ¿, (10)

ыясняется их содержательный смысл.

При условиях,приведенных в теоремах 5 - 8,и некоторых огра-ичениях на значения параметра Р в работе доказываются теоремы сходимости траекторий процессов (37) - (40).

При переходе к итеративным аналогам систем (37) - (40) юзможны многочисленные варианты, в частности,последовательность :",р" может быть допустимой или недопустимой по отношению к тожеству 0^+. В работе рассматривается процесс, который юрождает последовательность, такую, в которой х"е0 для всех П. >н определяется следующими рекуррентными формулами: р" = зх +(рп ♦ сх9(хп)К хп+1 = 5Га{(хп - [XV + Р(хп-х"-1)},

Рп+1 = ЯГ*{рп + СХЗ(Хп+1)) + £(рп-рп_1). (11)

Здесь при П=0 параметр Р=0. Этот процесс получен следующим )бразом: управляемая система (37) замыкается обратной связью [40) и в полученной системе производные заменяются конечными эазностями. Этот процесс является явным.

Процесс будет неявным, если систему (37) замкнуть управлениями (39): хп+1 = 5Га{(ХП- ОС V X, х(ХП,рП+ £(рп-рп"')) ♦

♦ Р(хп-хп_1)},

рп+1 = зт+{рп ♦ осз(хп+1)3 ♦ £(РП-РП_1). (42)

Здесь при П=0 параметр £=0. Выражения (42) представляют собой систему нелинейных уравнений относительно неизвестных

_п»1 — п + 1 п _п _п-1 _п-1 _

переменных X ,Р . Приближения X ,р и X ,Р предполагаются вычисленными на предыдущих итерациях. Это типичный неявный (нерекуррентный) итеративный процесс с объемом вычислений на каждой итерации примерно таким же, как в методе (26). Можно предполагать, что по эффективности (в смысле необходимого числа итераций и общего объема вычислений для получения решения с заданной точностью) этот неявный процесс превосходит своего рекуррентного (явного) аналога (41).

Если систему (38) замкнуть управлениями (39) и (40), а затем замкнутым системам поставить в соответствие системы итеративные, то получаются методы вида

рп = зг+(рп ♦ аа(х")), хп+1 = агзш1п{1/2 |х-хТ ♦ ос1(х/рп) -

- хп-х"_1>: хеО},

рп+1 = 31 +{рп ♦ аз(хп+1)} + (43)

и соответственно

хп+1 = агзш1п{1/2 |х-хп|2 + а1(х,р"+1- р(рп-рп"1)) -

- £<х-х", х"-хп-1>: хеО}, рп+1 = зх +Срп ♦ аз(хп+1)} ♦ Р(рп-рп_1). (ЧЧ)

Сопоставляя эти системы, видим их существенное различие: система (43) носит рекуррентный характер, а (44) - неявный. Это означает, что на каждой итерации процесса (44) решается система нелинейных уравнений относительно переменных Хп+1,рп+\ Это задача не простая, поскольку правая часть данной системы формируется с помощью задачи параметрического программирования. Этим задачам посвящена четвертая глава диссертации. В ней же обсуждаются и методы их решения.

При условиях, приведенных в теоремах 9 - 12, и некоторых ограничениях на значения параметра £ в работе доказываются теоремы о сходимости процессов (41) - (44).

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

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

Сформулируем управляемый метод модифицированной функции

агранжа второго порядка. В системе

ßdVdt2 + di/dt = az3fflln{ 1/2 |z-x|2+ ocJU(z,p): zeQ} - i, ßdWdt2 + dp/dt = зг+(Р + осз(х + u) - p,

x(t0)=x°, P(t0)=P°, x(to)=x1> pito)^1. (15)

де

<Ai(x,p) = |(x) i/2cc | st +(p + oca(x))|2 - i/2a |p|\ (46)

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

u = u(x,p,x,p,x\p), (47)

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

и = х + ßx (48)

.оказывается сходимость.

Далее в работе рассматривается двухшаговый итеративный ме-од, который не является непосредственным аналогом замкнутой теративной системы, отвечающей управлению (48). Его рекур-юнтные формулы имеют вид

xn+1 = az3iiiLn{l/2 |x-xn|2 + аДКх.р^р""1): xeQ), p"+1 = зт +{pn ♦ ot9(xn+1) + ß(pn-pn_1)}, (49)

де модифицированная функция Лагранжа представляется в форме

Л(х,р",рп_1) = Ux) ♦ 1/2а I?г+(Р" + аз(х) + ^"-Р"'1))!2-

- 1/2сс |р1\ (50)

де ОС > 0, ß < 1. Если П=0, то параметр ß=0. Доказывается ходимость этого метода к решению исходной задачи.

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

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

x*eAz3fflln{f(z,u*): 9(Z,U*)<0, zeQ), u*eU, (51) G(x\u*) < 0. (52)

истема рассматривается относительно переменных X и U, ее реше-ием (если оно существует) является вектор X*,U*. Отметим, то обратная задача оптимизации п форме (51),(52), по-видимому, первые была сформулирована автором этой работы. Из ранних пуо-икаций на эту тему необходимо отметить работы И.И.Еремина и .А.Истомина.

Систему (51),(52) можно трактовать как иерархическую игру,

в которой первый игрок (52) - центр, обладая правом первого хода, выбирает управление U, второй игрок (51) - подсистема, реагируя на управление,вырабатывает ответ J(U). Наилучший гарантированный результат центра заключается в выборе такого управления U , при котором пара I ,U удовлетворяет условию (52). Применение метода штрафных функций к решению иерархических игр можно найти в монографии В.В.Федорова.

Цель этой главы состоит в описании методов решения системы (51),(52), точнее ее, квадратичного случая. Проиллюстрируем на частной, но важной задаче возможные подходы к ее решению. Пусть в (51),(52) функция 3(X,U) s 0, a G(X,U) = X-U, кроме того, множества 0 и U совпадают: Q в U, тогда

x*eAz3mLn{f(x,u*): xeQ), (53)

х* = u", (54)

или

х*еАгзшл{|(х,х*): xgQ). (55)

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

Если в (55) функция Í"(X,U) выпуклая и дифференцируемая по переменной X, то решения этой задачи удовлетворяют операторному уравнению

X* = Ste(x* - (XV ^(Х*,!*)), (56)

где sta( • ) - оператор проектирования некоторого вектора на выпуклое замкнутое множество Q, параметр ОС>0, V ií(X,X) =

= V i-f(X,U)|x=u - частный градиент функции ■fíX.U) по первой переменной X, рассмотренный на диагонали квадрата X=U.

Для решения операторного уравнения (56) можно использовать метод простой итерации

xn+1 = 3tn(xn - av Л(х",хп)). (57)

В отличие от градиентного этот метод имеет две важные особенности, которые в значительной степени ограничивают сферу его применения. Во-первых, оператор V il(X,X) не является потенциальным, т.е., будучи частным градиентом, не является градиентом ни для какой функции; во-вторых, оператор V j|(l,X) почти всегда не монотонный. Эти два обстоятельства чрезвычайно затрудняют анализ проблемы сходимости процесса (57). С целью выяснения возможностей рассматриваемого метода в работе про-

водится исследование его управляемой модификации в предположении, что V i|(X,X) - монотонный оператор.

Отметим, что в литературе имеются публикации ( С.И.Зухо-вицкий., М.Е.Примак, Ю.М. Ермольев, С.П.Урясьев и др.), в которых обсуждаются проблемы сходимости итеративных процессов, близких к (57), при обязательном условии, что частный градиент 7 il(X,X) - монотонный оператор.

Управляемую непрерывную модификацию (57) сформулируем в виде: в некотором классе обратных связей U = U(X,X), где X = dl/dt, необходимо выбрать такую связь, которая обеспечила бы сходимость к равновесию X* траектории дифференциальной управляемой системы

dx/dt = 3ta(x - av íKx+u.x+u)) - i. (58)

где Х° = x(to)•

Для стабилизации траектории используем управление по невязке 15 = Jttt(X - ОС 7 if(X,X)) - X. Управляемая система в этом случае имеет вид

dx/dt = srQ(x - av il(x+u,x+u)) - x,

U = Jta(X - a 7 il(X,X)) - x. (59)

После ее замыкания управлением получим

dx/dt = sTq(x - ос 7 if(x,x)) - х,

X = 3tQ(X - ОС 7 ,1(1,1)), x(to)=x°. (60)

Теорема 13. Если множество точек равновесия задачи (55) не пусто; частный градиент по первой переменной на диагонали квадрата 7 il(X,U)|u=x = 7 il(X,X) является монотонным и удовлетворяет условию Липшица с константой III; множество Q -выпуклое, замкнутое; параметр ОС выбирается из условия 0<ос<1/21/2 |Ц, то множество точек равновесия системы (60) асимптотически устойчиво, т.е. X(t) -> X* при t °° для всех X .

Итеративный аналог системы (60) можно записать в форме

х" = яга(х" - а 7 il(xn,xn)), xn+1 = srQ(xn - а 7 il(xn,x")). (61)

Сходимость процесса устанавливается теоремой.

Теорема 14. Если множество точек равновесия задачи (61) не пусто; частный градиент по первой переменной на диагонали квадрата 7 il(X,U)|u=x = 7 íl(X,X) является монотонным и удовлетворяет условию Липшица с константой III; множество Q -выпуклое, замкнутое; параметр ОС выбирается из условия

0<а < i/21//2 III, то процесс (61) монотонно сходится к равновесию задачи (55), т.е. Xn I ЕХ при П -> оо для всех

i°eQ.

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

Еще раз вернемся к задаче (55), но на этот раз целевая функция будет квадратичная, а множество Q - положительным ортантом:

х* е Агзш1п{1/2 <Ах,х> + <Bx*+S,x>: х>0}. (62)

Здесь матрица А - симметрическая, неотрицательно определенная, т.е. <Ах,1> > 0 для всех XERn, а В - произвольная матрица. Задаче (62) поставим в соответствие квадратичную функцию

Ф(х,р) = 1/2 |(А+В)х - р ♦ 6|2 + <х,р>, (63)

которую будем рассматривать на положительном ортанте {х,р: Х> 0, р> 0). Это невыпуклая по совокупности переменных Х,р, но выпуклая на любом луче р=КХ (где К> 0) квадратичная функция. Кроме того, Ф(Х,р) > 0 для всех Х> 0, Р> 0, а Х*,р* является точкой минимума Ф(Х,Р) на положительном ортанте. Если определитель матрицы А+В не равен нулю, то функция Ф(х,р) -> оо при |х| оо, |р| оо>т,е. растет на бесконечности, что, в свою очередь, обеспечивает существование минимума Ф(Х,р) на положительном ортанте и этот минимум, как несложно убедится, является решением исходной равновесной задачи.

Представим функцию Ф(Х,Р) в векторно-матричной форме

Ф(х,р) = 1/21( V 0 ♦ 1/2 (х,р) (I 0

Введем обозначения

F =(А0В о), z =(р), <* =foj, 3 =(l ol,

тогда

Ф(н) = 1/2 |Рн + чГ + 1/2 <3н,н>. (64)

Рассмотрим задачу

г* е Агяшт{1/2 |Ре + ч1г + 1/2 <Зе,е>: Зг> 0), (65)

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

функцию на положительном ортанте.

Для решения задачи (65) используем метод проекции градиента

гп+1 = 5ГЛ2П - а(Гт(Ргп+я) ♦ Эг")), (66)

где 5Г «■( • ) - оператор проектирования вектора на положительный ортант.

Теорема 15. Если последовательность Нп, которая строится по формулам (66), ограничена, а параметр ос выбирается из условия 0<ОС<2/|РТ+3|, то процесс сходится (в смысле подпоследовательностей) к точке Е , в которой выполняется необходимое условие минимума. Если в этой точке целевая функция равна нулю: Ф(2 )=0, то 2 является минимумом задачи (66) и, следовательно, решением равновесной задачи (55). Точка 2 =

=(СС ,р ) - не может принадлежать внутренности положительного ортанта, т.е. в этой области Ф(2) не имеет ни локального, ни глобального минимума, ни седловых точек.

Из теоремы следует, что оптимум Ф(Е) всегда принадлежит границе положительного ортанта.

Простейшая равновесная задача (62) является эталонной в наших рассуждениях. Этим объясняется детальность доказательства метода ее решения. Анализ других, более сложных задач будет проводится по только что рассмотренной схеме.

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

Пусть

х*еАгчтт{1/2 <Ах,х> + <Вх*+6,х>:

0*х+0ах*-к1 < 0, хеЯ"}, (67)

где 01,02 - матрицы соответствующих размерностей. Введя дополнительную неотрицательную переменную Ш> 0, трансформируем (67) в задачу с ограничениями типа равенств

1*еАгчппл(1/2 <Ах,х>+<Вх*+ё,х>:

0*г+0*е%с1+ю = 0, ш> 0, хеИ"). (68)

Задаче (68) поставим в соответствие вспомогательную квадратичную функцию

Ф(х,и,РьР2) = 1/2 I(А+В)х * И^Р, + 6|2 ♦ 1/2 |РгР2|2 +

+ 1/2 |(0»+02)1 +и Л|2 + <м,р2>, (69)

определенную для всех хей", Ш> 0, р^В™, р2> 0. Эта

функция аналогична (63). Запишем (69) в векторно-матричной форме

Ф(Х.М,РьР2) = 1/2

Di

0 О

1 -I О 0)

'х

ы

1/2 (Х.Ю.РьРа)

p 1 1

IP 11 +

0 0 0

0 0 I

0 0 0

I 0 0

Введем обозначения

/А +B 0 DT 0 x (6 /0 0 0 0

D,+D2 I 0 0 и d 0 0 0 I

0 0 I -I pi 0 0 0 0 0

F = 0 0 0 01 , z = p 2l , 4 = 0 , 3 = i0 I 0 0/

тогда функцию Ф(Х,Ю»Р1»Р2) можно записать в компактной форме:

Ф(и) = 1/2 |Fz + 2 ♦ 1/2 <3z,z>. (70)

Рассмотрим задачу

г* е Агяш1п{1/2 |Fz + ч|г + 1/2 <3z,z>: 3z>0}, (71)

в которой требуется минимизировать невыпуклую квадратичную функцию на положительном ортанте пространства переменных Z2=W, Zч=Р2* Задачи (71) и (65) практически совпадает, различие лишь в том, что в задаче (65) проектирование производится на положительный ортант пространства двух переменных И, р2> а не четырех переменных X,U,Pi,P2- Поэтому для ее решения используем процесс (66)

,п+ 1

= зт +(zn - oc(F (Fzn+q) + Dz")),

(72)

где st +( • ) - оператор проектирования вектора на положительный ортант пространства переменных Z2=W, Zh=P2 • Сходимость этого процесса доказывается в теореме 15.

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

х* е Azamln{ f(x,u*): D^r + Dali* + d < 0, xeR" },

Gic ♦ GjM* ♦ s < 0, (73)

где Di,D2,Gi,G2 - матрицы соответствующих размерностей,

+

a <f(X,U) имеет вид:

( А 1/2В\/х| /х)

f(x,u) = (х,и)\1/2 В С/ \и / + (6,с) ( и /. (74)

Если ввести обозначения

/ А 1/2 В 1 /х| /61 F =[1/2 В С /, z = Ы, 1 = Ы,

где xeRn,UGRK; А, С - неотрицательно определенные матрицы; В - произвольная матрица, то f(Z) = <Fz ,Z> + <4»Z>. Для того чтобы обеспечить выпуклость ?(Z), будем предполагать, что <FZ,Z> > 0 для всех ZGR п.

Задаче (73),(74) поставим в соответствие равновесную задачу

вида

х" е Az3niLn{ ?(x,u): D,x + DjU + d <0,

Gjc* ♦ Gju + з < 0, xeR", ueRn }. (75)

В работе доказывается, что всякое решение равновесной задачи (75) является решением обратной задачи (73),(74).

Теорема 16. Если решение вспомогательной задачи (75) существует, а функция Лагранжа экстремальной задачи из правой части (75) имеет седловую точку, то любое решение задачи (75) является решением (73),(74).

Задача (75) имеет ограничения типа неравенств, ее несложно редуцировать к задаче с ограничениям типа равенств

х* е AzgmLn{ f(i,u):

Dji + DjU + d + töi = 0, Ui>0, xeR",

G,x* ♦ GjU + 3 ♦ Ma = 0, Ma>0}. (76)

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

А х" + ВV ♦ + Dfrl ♦ ~ ♦ ё = 0,

В х* + С u* + + D^p* + G^ia + + с = 0,

р*- р", м = о,

Ра - - Рч =0, Dji* + Dil" + ш* * + d = 0,

GjX* + GaU* ♦ + IÖ2 + +2=0,

<ШьРэ> = о, <Ш 2,Рч> = 0,

м">0, м»>0, Рз> 0, Рч> 0. (77)

Опираясь на систему (77), составим вспомогательную квадра-

тичную функцию, аналогичную (63):

Ф(х,и,м 1>м2»р 1>Р2»Рэ»Рч) = 1/2(|Ах+Вти^1+6|г + + |Вх+Си+01р 1+95=>2+с| 2 + |Р1-Рэ12 + |р2-рч|2 + + 10 ¿1+0 ¿1+Ю 1+Й11 2 + |С ¿Г+С аМ-Иба+Э I 2) +

+ 1/2 <1Й 1»Р э> + <М2,Рч>> определенную для всех хей"» ие{\п, 1й1>0, ш2> 0, Р1б!Г, Р2ЕВт> Рз> 0, Рч> 0.

Эту функцию удобно представить в векторно-иатричной форме

=1/2

,И,Ш 1,М 2>Р 1,Р2>Рэ,Рч) г

(А Вт 0 0 0 0 0 X /ё г

В С о о Ы 0 0 и с

0 0 0 0 I 0 -I 0 1Й1 0

0 0 0 0 0 I 0 -I м2 0

0, I 0 0 0 0 0 Р1 с1

0 I 0 0 0 0 р2 %

0 0 0 0 0 0 0 0 Рз 0

\о 0 0 0 0 0 0 о| 1рч| + 01

/0 0 0 0 0 0 0 0 /X

0 0 0 0 0 0 0 0 и

0 0 0 0 0 0 I 0 и,

0 0 0 0 0 0 0 I (|]2

0 0 0 0 0 0 0 0 Р1

0 0 0 0 0 0 0 0 Рг

0 0 I 0 0 0 0 0 Рз

(х,и,ю 1>И2,РьР2>Рз>Рч) 0 0 0 I 0 0 0 0 | Рч

Введем обозначения: в первом слагаемом функции

Ф(х,и,м 1>Ш2>Р1,Рз>Рз>Рч) матрицу обозначим через С, векторную переменную - через 2, свободный столбец - через Ч. матрицу второго слагаемого - через П, тогда эту функцию можно представить в компактной форме

Ф(н) = 1/2 |Рг + чГ ♦ 1/2 <0н,2>. (78)

Рассмотрим задачу

н* е Агяш1г\{1/2 \?г * ч12 + 1/2 <Эн,г>: 0н> 0}, (79)

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

2ч=Й2» 2 7=Рз, г8=рч. Эта задача аналогична (64), (65), а для ее решения применим процесс (66), сходимость которого обосновывается теоремой 15.

Рассмотрим обратную задачу оптимизации в векторной постановке: требуется определить X ,р »11 ,такие, чтобы они удовлетворяли системе

х*,Р* е ЭДМпС <Г, ?(х,и*)>: з(х,и*)<0, хеО}, С(х*,и*)<0,

Г = Бр" + л. ^ (80)

Здесь I ,р - седловая точка функции Лагранжа £(х,р,11 ,-Е*) = = <1*, |(Х,11*)> + <р, 3(Х,и*)>, определенной для всех ХёО, р> 0 и фиксированных -£*> 0, 11*£и, где |(Х,и) - векторная функция, выпуклая либо по совокупности переменных Х.И, либо по переменной X при любом фиксированном 11; 9(Х,11) - векторная функция, каждая компонента которой - скалярная функция,выпуклая по совокупности переменных; С(Х,11) - векторная функция, каждая компонента которой - скалярная функция, выпуклая по переменной К при любом фиксированном значении X; Б - матрица с неорица-тельными компонентами, размерность которой согласована с размерностью векторов -Е и Р; 6 - фиксированный вектор. Множества 0еВп и иеВ" - выпуклые, замкнутые; Я", В™ - конечномерные эвклидовы пространства. Если значение {¡*=Бр* + Л подставить в выражение целевой функции, то получим <1*, |(Х,и)> =

= «и(х,Ю> + <5р*,?(х,и)> = + <Бр*, ?(х,и)>,

где | (Х,11) = <6, 1(1,11)>. С учетом сказаннного задача (80) представляется в форме

х*,р* е Б(1Мп{Г(х,и*) + <р*, Бт<?(х,и*)>: э(х,и*) < 0, хеО),

С(х*,и*) < 0. (81)

В работе показано, что обратная задача векторной оптимизации (81) может быть сведена к обратной задаче скалярной оптимизации. Доказывается, что всякое решение обратной задачи оптимизации вида

х* е Агтп{?°(х,и*): Бт|(х,1Г) а(1»и*)<0, хеО},

С(х\и*)<0, и*еи, ш*еИ (82)

?вляется решением задачи (81). Отметим, что (82) - задача типа [51),(52).

Теорема 16. Если |°(х,и), |(Х,и), 9(Х,11) - функ-

ции, каждая компонента которых - скалярная функция, выпуклая по совокупности переменных; 0 и I) - выпуклые, замкнутые множества; задача (82) имеет решение Х*,и*,Ш*, такое, что функция Лагранжа вида 1(Х,и*,р,Ш*) =|°(Х,и*) + <р,5Т|(1,и*)-М*>, определенная на множестве й = {х,р: 2(1,11*) < 0, Хб£), р> 0),

мм # * *

имеет седловую точку X ,р , то I ,11 ,р является решением задачи (81).

Таким образом, от задачи (81) можно перейти к задаче (82), а последнюю, в свою очередь, с помощью задачи типа (75) заменить задачей вида

х\и*,ы* е Агтп{?°(х,и): 5т^(х,а)-ш<0,

з(х,и)<0, С(и*,и)<0, хеОиеи, меИ), и*еС1,

х* = и*. (83)

Квадратичный вариант задачи (83) является задачей типа (78),(79), а для ее решения можно использовать итеративный процесс (66), сходимость которого обоснована в теореме 15.

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

ЗАКЛЮЧЕНИЕ

Сформулируем основные результаты, выносимые на защиту.

1. Предложен новый допустимый (внутренний) метод решения задач выпуклого программирования - метод квадратичной аппроксимации. Обоснована его сходимость, приведены оценки скорости сходимости.

2. Развита теория управляемых непрерывных (дифференциальных) и итеративных методов первого и второго порядка для вычисления седловых точек выпукло-вогнутых вырожденных

Функций (на примере функций Лагранжа задач выпуклого программирования). В частности:

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

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

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

к какой-либо седловой точке вырожденной выпукло-вогнутой функции;

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

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

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

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

Т. Антипин A.C. О методе выпуклого программирования, использующем симметричную модификацию функции Лагранжа//Эконо-мика и математ. методы, 1976. Т. XII. Вып. 6. с.1164-1173.

2. Антипин A.C. Об одном методе отыскания седловой точки модифицированной функции Лагранжа//Экономика и математические методы. 1977. т. 13. Вып. 3. с. 560-565.

3. Антипин A.C. Методы нелинейного программирования, основан-

nue на прямой и двойственной модификации функции Лагранжа// Препринт. М.: Изд-во ВНИИСИ, 1979. 74 с.

4. MtlpLn А.5. A FeaôL&lB Method акЬп to GzadLmt Pzojectlon Method |oz SoMLon of Conuei PzoazammLna// Methods of Mathematical PzoazammLna. PWN-PolLah Scientific Puê-flàhezô. Wazàzatua, 1981. à. 7-11.

■3. Антипин A.C. Равновесная форма задач выпуклого программирования и методы их решения//Сборник трудов. Методы оптимизации. М.: Изд-во ВНИИСИ, 1984. Вып. 12. с. 96 - 108.

6. Антипин A.C. Экстраполяционные методы вычисления седловой точки функции Лагранжа и их применение к задачам с блочно-сепарабельной структурой//»!, вычисл.мат. и мат.физ, 1986. Т.26. № I. с.I50-I5I.

7. Антипин A.C. Методы оптимизации прогнозного типа с приложением их к задачам с блочно-сепарабельной структурой// Сборник трудов ВНИИСИ. Модели и методы оптимизации. Выпуск 19, 1986. с.82-92.

8. Антипин A.C. Об одной задаче равновесия и методах ее реше-ния//Автоматика и телемеханика, 1986. № 9. с. 75-82.

9. Антипин A.C. О неградиентных методах оптимизации седловых функций //Вопросы кибернетики. Методы и алгоритмы анализа больших систем. М.: Изд-во АН СССР. Научный Совет по комплексной проблеме "Кибернетика", 1987. с. 4 - 13.

10. Антипин A.C. Методы решения систем задач выпуклого программирования//)«. вычисл.матем. и матем. физ., 1987. Т. 27,

№ 3. с. 368 - 376.

11. Антипин A.C. Линейный оптовый рынок: модели и методы.

В сб. Модели и методы оптимизации. Сборник трудов. Выпуск II, М.: Изд-во ВНИИСИ, 1987. c.IOI-TIO.

Т2. Антипин A.C. Задачи оптимизации со многими участниками. В сб. Численные методы и оптимизация. Таллинн."Валгус", 1988. с.10-14.

13. Антипин A.C. О моделях взаимодействия предприятий-производителей, предприятий-потребителей и транспортной системы. Автоматика и телемеханика. 1989. № 10. с. I05-II3.

14. Антипин A.C. Непрерывные и итеративные процессы с операторами проектирования и типа проектирования// Вопросы кибернетики. Вычислительные вопросы анализа больших систем. М.: Изд-во АН СССР. Научный совет по комплексной проблеме