Содержание к диссертации
Введение
ГЛАВА I. Блочные задачи со связывающими переменными . 16
I.I. Формулировка проблемы 16
1.1.1. Процессы, приводящие к задачам со связывающими переменными 16
1.1.2. Постановка задачи I?
1.1.3. Процедура расчленения I?
1.2. Координирующая и вспомогательные задачи . is
1.2.1. Определения 18
1.2.2. Условия регулярности 19
1.2.3. Целевая функция координирующей задачи 20
1.2 1. Локальные координирующие задачи . 22
1.3. Декомпозиционный алгоритм для задачи квадратичного программирования со связывающими перемен ными . 24
1.3.1. Процедура решения координирующей задачи Критерий оптимальности 24
1.3.2. Описание алгоритма 26
1.3.3. Рекуррентные формулы 28
1.4. Обоснование конечной сходимости 31
1,5. Случай вырождения 35
ГЛАВА 2. Блочные задачи со связывавдш ограничениями
2.1. Декомпозиция, использующая механизм множителей Лагранжа 38
2.I.I. Реальные процессы, описываемые задачами со связывающими ограничениями . 38
2.1.2. декомпозиция и двойственность . 38
2.1.3. Двойственная координирующая задача. Основные определения 42
2.1.4. Максимизация квадратичной функции в регулярной области 45
2.1.5. Процедура выхода из нерегулярной точки
2.2. Алгоритм для решения блочной задачи квадратич ного программирования со связывающими ограничениями 48
2.3. Обоснование сходимости 50
2.4. Задача со слабо связанными блоками 52
2.4.1. Сведение к задаче со связывающими переменными 53
2.4.2. Исследование координирующей задачи . 55
2.4.3. Построение локальных координирующих задач 57
2.4.4. Процедура решения локальных задач . 59
2.4.5. Критерий оптимальности процесса 63
2.5. Алгоритм для решения задачи квадратичного программирования со слабо связанными блоками 65
ГЛАВА 3. Вычислительные аспекты решений задач специально; структуры 69
З.І.- Компактное хранение информации при решении больших задач 69
3.1.1. Задачи со слабо заполненными матрицами ограничений 70
3.1.2. Задачи с двусторонними ограничениями 74
3.1.3. Задачи с блочно-диагоналъной структурой ограничений 76
3.2. Возможности организации параллельных вычисле ний на многопроцессорных ЭВМ 80
3.2.1. Распараллеливание процесса вычислений при реализации декомпозиционных алгоритмов 80
3.2.2. Ооращение симметричной матрицы специального вида 83
3.2.3. Естественный- параллелизм и параллелизм смежных операций процесса (1.8) 89
3.3. Вычислительный опыт решения задач специальной структуры 90
Заключение
Список основное литературы 114
- Координирующая и вспомогательные задачи
- Максимизация квадратичной функции в регулярной области
- Задачи с блочно-диагоналъной структурой ограничений
- Естественный- параллелизм и параллелизм смежных операций процесса (1.8)
Введение к работе
В последние годы все чаще возникает необходимость в интегрированном исследовании объектов 'И явлений в целом, в то время как раньше изучались модели элементов или отдельные стороны тех или иных явлений. Изучаемые объекты обладают большими размерами.
Поскольку большие задачи возникают обычно в результате учета связей, существующих между независимыми подсистемами во времени или в пространстве, то в них почти всегда обнаруживается некоторая специфическая структура. Создание специализированных алгоритмов решения, учитывающих эту структурную специфику, позволяет достичь значительного выигрыша в вычислительной эффективности. Подобные алгоритмы открывают путь к решению действительно больших задач, которые не поддаются стандартным методам в силу ограничений по времени или объему памяти.
В настоящей работе рассматриваются большие задачи математического программирования. К экстремальным задачам сводятся очень многие проблемы прикладного характера и они зачастую обладают специальной структурой. Так, в задачах с линейными ограничениями ненулевые элементы матриц ограничений могут появляться лишь в диагональных блоках и в относительно малом числе связующих строк или столбцов Гз5 , 74].
За последние два десятилетия было осуществлено выделение многих характерных структур и создано большое число алгоритмов для их решения. Определились два основных подхода к решению задач большой размерности: прямые методы и методы, основанные на идеях декомпозиции /разложения/.
В первом случае для решения задач специального вида используются общие методы математического программирования. При - є - этом основные вычислительные трудности связаны с хранением больших массивов информации и с операциями над ними. Большие разреженные матрицы /матрицы, имеющие малый процент ненулевых элементов/ обычно хранятся в ЭВМ в упакованном виде, т.е. хранятся только ненулевые элементы вместе с необходимой информацией об их положении в матрице ГбзТ. Например, при использовании симплекс-метода для решения линейных задач большой размерности основные вычислительные трудности связаны с обращением матрицы базиса ГбЗ , 88J. Если матрица условий задачи имеет специальную структуру, то необходимые вычисления могут быть выполнены с использованием матрицы меньшей размерности. Такой подход, к примеру, реализуется при применении метода учета двусторонних ограничений [82 J_ или метода приведения базиса к треугольному виду [351.
Методы, принадлежащие ко второму классу, основаны на разложении системы на подсистемы меньшей размерности. Обычно выделяются подсистемы первого и второго уровня таким образом, что подсистемы второго уровня определяют соответствующие изменения в подсистемах первого уровня. Задача второго уровня состоит в координации функционирования элементов первого уровня с целью получения общего решения исходной задачи. два основных декомпозиционных подхода были выдвинуты в начале шестидесятых годов нашего столетия при исследовании больших задач линейного программирования Дж. Данцигом, Ф. Вул-фом [21], И. Корнай, Т. Липтаком [_331* Принцип Данцига - Вул-фа повлек за собой многочисленный поток работ, развивающих центральные идеи в различных направлениях. Если в исходном варианте решение координирующей задачи основано на методе улучшения плана в линейном программировании /см., например, Г?8І /, то в последующих работах исходили из метода одновременного решения прямой и двойственной задачи [35], сокращения невязок [4-IJ, обобщенного градиентного спуска [75], использования модифицированных функций Лаграіша [52^ и других процедур. Применялись также игровые подходы [53* с помощью линеаризации и аппроксимации принцип Данцига-Вулфа распространялся на нелинейные задачи [35 , 92J. Техника разложения Данцига-Вулфа была перенесена и на некоторые специальные экстремальные задачи [37, 79, 86, 95].
В подходе Данцига-Вулфа за основу принимается разбиение условий задачи линейного программирования по строкам. Разбиение линейных ограничений задачи по столбцам положено в основу подхода Корнай-Липтака. В первоначальном варианте [.33 J координирующая задача сводилась к отысканию седловой точки, или к решению максиминной задачи, для которой использовались методы теории игр. В последующих работах для решения главной задачи применялся метод возможных направлений L^j, использовались множители Лагранжа при организации спуска по градиенту [9М» выравнивание двойственных оценок [60J и другие. Декомпозиция Корнаи-Липтака была развита для нелинейных блочно-сепарабель-ных задач математического программирования / [_39j, |_65j, |_93j и др./.
В дальнейшем была разработана декомпозиция на основе разделения переменных, релаксации ограничений, разложение, связанное с агрегированием переменных, параметрическая декомпозиция и т.д. Эти подходы подробно изложены в [35], [73J.
Различные конкретные модели приводят к определенным приемам разложения, не имеющим аналогий с основными схемами. К настоящему времени разработано довольно много различных подходов для декомпозиции специальных классов задач выпуклого программирования и оптимального управления /см., напр., монографии - Я - W, [ад], [ад], [бі], [«.] /.
В последние годы появился ряд работ обзорного характера с обширной библиографией / Н, [i^], [35], [?з], [74], [?7], [87] и др./.
Таким образом, аппарат математического программирования насчтывает немало алгоритмов для решения специальных задач. Однако интерес к разработке новых эффективных методов не ослабевает и сейчас. Это в особенности касается методов решения нелинейных задач большого объема. Во-первых, нелинейные модели все чаще становятся объектом изучения в экономике и технике. Во-вторых, область реальной применимости существующих методов еще недостаточно широка, что объясняется, в основном, сложностью программной реализации и большими затратами машинного времени на их испытания.
Диссертационная работа посвящена построению и исследованию методов решения больших задач нелинейного программирования. При разработке алгоритмов уделялось внимание возможности достаточно простой их программной реализации. Предложенные методы базируются на хорошо разработанном аппарате квадратичного программирования.
В основу предлагаемого подхода положен метод линеаризации 55 , 58J. Это метод решения общей задачи математического программирования. Метод носит итерационный характер. Для нахождения очередного приближения используется линеаризованная задача. Хотя метод линеаризации имеет наибольшее значение для нелинейного случая, его применение для задачи линейного программирования также не лишено смысла.
Глобальная сходимость метода доказана и получены оценки скорости сходимости в окрестности точки оптимума. Для задачи линейного программирования алгоритм сходится за конечное число _ Q _ шагов. При естественных условиях в общем нелинейном случае алгоритм имеет геометрическую скорость сходимости. Метод линеаризации [55J - это метод первого порядка, т.е. он требует вычисления лишь первых производных. В то же время при некоторых благоприятных обстоятельствах алгоритм имеет квадратичную скорость сходимости.
Он применим к решению задач дискретного минимакса.
Существенной особенностью метода является возможность учета нелинейных ограничений типа равенств.
Многолетнее успешное применение метода для решения практических задач [_57j обусловило интерес к нему со стороны исследователей и появление многочисленных модификаций I 1,12,18,23, 44-47,59].
Рассмотрим-подробнее идею метода линеаризации /см. [.55 J , L58J, [57J /. Пусть^гребуется минимизировать функцию i0 ( X) , ОС Е при ограничениях ;(осЬО, ге Л, где J - конечное множество индексов. Предполагается, что все функции 4-0vXj , І і 1.^-) непрерывно дифференцируемы. /Более полно ограничения, при которых применим метод линеаризации, приведены, например, в Г 58 [ / Все ограничения и і0 IxJ заменяются на линейные путем линеаризации их в некоторой точке Q?0 . Линейная аппроксимация является наиболее грубой. Для того, чтобы решение линеаризованной задачи в точке Х0 не уходило слишком далеко от ОС о » к линеаризованной целевой функции добавляется квадратичный член.
Итак, в методе линеаризации I 55J для определения направления движения из точки Хо используется воспомогательная задача квадратичного программирования тЦ<,(:(*0),р>+і|[р|[г], ({(*.),p>+{t(*.)<0, i^(*.), где ^(J1 \0б0) - множество индексов ограничений, существенных в точке Х0 . Обзор литературы по методам, использующим другую структуру линеаризованной задачи можно найти в [^26,57,69, 7 о].
Для решения вспомогательной задачи в Г581 рекомендуется метод сопряженных градиентов, сходящийся для задачи квадратичного программирования за конечное число шагов. Возможно использование и других конечных методов решения задач квадратичного программирования [ 22,34,57,58,74-J .
Если исходная задача описывает достаточно сложную систему, то вспомогательная задача будет задачей большого объема. Возникает вопрос о специальных алгоритмах для решения вспомогательной задачи метода линеаризации. При наличии таких алгоритмов метод линеаризации может быть применен к достаточно широкому классу нелинейных задач большой размерности.
В существующих методах решения нелинейных задач большого объема требуется определенная структура расчленяемой задачи [_94J . В частности, существенными условиями оказываются выпуклость 1 38 J и аддитивная сепарабельность |_36 \ функций, определяющих критерий и ограничения. Поскольку расчленению в нашем случае будет подвергаться вспомогательная задача, которая обладает этими свойствами, то нет необходимости предъявлять подобные требования к исходной задаче. Таким образом, расширяется класс задач нелинейного программирования, которые могут быть решены с применением специальных приемов.
Следуя I 35 I , под задачами большого объема будем понимать задачи в которых а/ функциональные связи описываются набором большого числа уравнений и неравенств с большим числом переменных, б/ в структуре функциональных связей имеется специфика, указывающая на возможность более или менее полного расчленения задачи на подзадачи меньшей размерности.
Итак, целью диссертационной работы является создание алгоритмов решения вспомогательной задачи метода линеаризации, в которых используется специфика структуры связей, и, в частности, специфика критериальной функции. Поскольку задача вспомогательная, то при построении алгоритмов учитывается, что ее решение должно быть получено за конечное число шагов.
Диссертация состоит из трех глав.
В главе I рассматриваются блочные задачи со связывающими переменными.
В I.I перечисляются некоторые классы практических задач, которые приводят к подобным математическим моделям, а также кратко излагается метод разделения переменных /см., напр.,[35_|/ применяемый для решения задач подобного типа.
В 1.2 формулируются подзадачи, на которые распадается вспомогательная задача метода линеаризации при фиксированных связывающих переменных, и строится координирующая задача с неявной целевой функцией. В l_32J, [35], L^i» [74-] и других работах описываются методы решения подобных координирующих задач, основанные на исследовании структуры целевой функции и ее производных в очередной допустимой точке.
Для задачи квадратичного программирования с единичной мат-трицей квадратичной формы удается уточнить структуру целевой функции координирующей задачи в целом. С этой целью вводятся определения регулярной точки, регулярной области и доказывается следующий факт /лемма 1,1/: в каждой регулярной области целевая функция координирующей задачи является квадратичной.
В п.1.3.1 предлагается процедура замены координирующей задачи с неявной кусочно-квадратичной целевой функцией последовательностью задач квадратичного программирования, которые мы назвали локальными координирующими задачами /MS/, Принцип построения МЪ изложен в п. 1.2.4.
Подробно декомпозиционный алгоритм для блочной задачи квадратичного программирования со связывающими переменными сформулирован в п.1.3.2. Приведен критерий оптимальности /теорема I.I/, выведены рекуррентные формулы для облегчения пересчета ЖЗ /лемма 1.2/.
В 1.4 приводится подробное обоснование конечной сходимости алгоритма.
В 1.5 исследован случай вырождения /в очередной допустимой точке не выполняются условия регулярности/. Приводятся соответствующие рекомендации и обосновывается конечная сходимость алгоритма для этого случая.
В главе 2 рассмотрен второй основной тип блочных задач -задачи со связывающими ограничениями. Построен декомпозиционный алгоритм для блочной задачи квадратичного программирования со связывающими ограничениями / 2.2/. При разбиении этой задачи на подзадачи используются двойственные оценки связывающих ограничений / L35J, \7^[ /. Исходной схемой подобного рода является принцип декомпозиции Данцига-Вулфа [2*1 Однако» в отличие от линейных задач, в задачах с нелинейными целевыми функциями возможна полная децентрализация принятия решений, т.е. оптимальная точка находится непосредственно при решении вспомогательных подзадач.
В функцию Лагранжа, ассоциированную с исходном задачей, включаем только связывающие ограничения. Строим двойственную за- - із - дачу, размерность которой определяется числом связывающих ограничений. Б \S5\ продемонстрировано применение для решения двойственной задачи такой структуры алгоритма наискорейшего спуска, модифицированного с учетом простых ограничений. Эта градиентная процедура рассматривается как координирующий механизм для координатора верхнего уровня, задача которого состоит в решении двойственной проблемы при заданных значениях двойственной целевой функции и ее градиента. На нижнем уровне решаются подзадачи и находятся эти значения. В [50] использован прием "усредненного градиента". В случае произвольных выпуклых функций для решения таких двойственных задач- применимы обобщенные градиентные методы минимизации негладких функций [ув\.
Чтобы избежать многократного решения вспомогательных подзадач, в п.2.1.3 настоящей работы исследуется структура построенной нами двойственной задачи /мы назвали ее двойственной координирующей задачей/. Вводится определение регулярной области и при решении двойственной координирующей задачи используется ее явное представление внутри регулярных областей.
В 2.3 исследована скорость сходимости алгоритма.
В главе 2, кроме того, приведена процедура решения задачи квадратичного программирования со слабо связанными блоками, основанная на сведении задачи со связывающими ограничениями к задаче со связывающими переменными и использующая результаты главы I. Локальные координирующие задачи в данном случае имеют более сложную структуру, чем описанные в главе I, поэтому в п.2.4.4 подробно рассматривается процедура их решения.
Третья глава посвящена вычислительным аспектам решения специальных задач описанной структуры.
В 3.1 рассматриваются вопросы компактного хранения информации при применении метода линеаризации и приводятся модиюика- ции метода сопряженных градиентов для различных структур матрицы ограничений квадратичной задачи,
В 3.2 на примере алгоритма 1.3 анализируются возможности организации параллельных вычислений на многопроцессорных ЭВМ.
В заключение приводятся результаты решения тестовых примеров и практических задач с использованием описанных процедур.
В 3.3 мы касаемся вопроса целесообразности применения структурного программирования при реализации декомпозиционных алгоритмов. В качестве примера .в приложении приведена схема &ЕС LA6 реализации алгоритма 2.2. При составлении схемы использовался псевдокод, описанный в [l5J.
Изложенные результаты докладывались на семинарах "Выпуклый анализ и экстремальные задачи", "Теория оптимальных решений" в Институте кибернетики АН УССР, на семинаре кафедры теории оптимальных процессов Львовского государственного университета, на Ш Республиканской конференции "Вычислительная математика в современном научно-техническом прогрессе" /г. Канев/ и опубликованы в работах ^96-IOOJ.
Для упрощения изложения ниже полагаем, что в рассматриваемых структурах имеется только два диагональных блока. Несколько слов о декомпозиции задач с произвольным количеством блоков в матрице ограничений сказано в заключении.
Рассмотрение ведется в конечномерном евклидовом простран-. Компоненты векторов обозначаются индексами сверху. Нижние индексы обозначают элементы некоторой последовательности. Скалярное произведение двух векторов обозначается 4 0(1,^/ , т.е. (х,цУ - ХгЦ{ .
Под нормой вектора понимается его евклидова норма
I х И = J(x,x.>
Звездочка сверху обозначает транспонирование. Под вектором X будем понимать вектор-столбец. Тогда %> обозначает вектор-строку. Соответственно, А - транспонированная матрицаЛ .
Нумерация формул, теорем, лемм, определений двойная. Первое число означает номер главы.
В заключение автор выражает глубокую и искреннюю благодарность научному руководителю профессору Б.Н.Пшеничному за постоянное внимание к работе. - 1Є -
Координирующая и вспомогательные задачи
. Основная идея метода разделения переменных, применяемого для решения задач со связывающими переменными состоит в следующем /см., напр., { 32,35J /. Фиксируются связывающие переменные и решается задача относительно остальных переменных, которая в силу блочной структуры задачи распадается на независимые вспомогательные подзадачи меньшей размерности. Экстремумы целевых функций зависят от фиксированных переменных как от параметров. При подстановке их в неявном виде в исходную, получают координирующую задачу только от фиксированной части переменных. Основная трудность состоит в то:.:, что лишь для ограниченного количества функций монно получить явный вид этой координирующей задачи. на множестве допустимых точек рз . Функции /1ЛІ - неявные и в общем случае оценка / Ь = 1,2/ в некоторой точке рз требует решения задач /1.2/. Однако эти задачи имеют меньшую размерность, чем исходная, и решаются независимо, что монет оказаться удобным.
Определениеэквивалентная исходной, называется координирующей задачей, а задачи /1.2/ - вспомогательными.
Вспомогательные задачи дают информацию, касающуюся субградиентов функции /1.3/. Будем рассматривать П{, как выпуклые многогранные многозначные отображения. Поскольку целевые функции задач /1.2/ выпуклые и собственные, то (рз) являются выпуклыми функциями и, воспользовавшись теоремой о вычислении субдифференциала через отображение, локально сопряженное к многозначному получим:
Поскольку доступны средства для оценки и их суб-градиентов, то для решения задачи /1.5/ можно воспользоваться каким-либо методом выпуклого программирования [_3,30,58j. Но для получения конечного алгоритма требуется выполнение некоторых дополнительных условий.
Условия регулярности. Пусть при некотором фиксированном рз = Рз задачи /1.2/ решены и найдены оптимальные значения Di С рз) Обозначим - множество номеров активных ограничений й задачи /1.2/ в точке рз ,
Верхний индекс в массивах обозначает соответственно строку матрицы или компоненту вектора. Через А а: обозначим матрицы, состоящие из строк соответствуют блоки и составляющие Я{ и $ векторов множителей Лагранжа и свободных членов.
Определение 1.3. Точка р3 называется регулярной, если а задачи /1.2/ при фиксированном ps = рз разрешимы; б строки матриц А {а линейно независимы; в соответствующие активным ограничениям множители Лагранжа строго положительны: Ліц U .
При небольшом отклонении р3 от П3 набор активных ограничений и знаки множителей Лагранна вспомогательных задач могут остаться неизменными.
Определение 1.4. Подмножество множества изменения рз і состоящее из регулярных точек, которым соответствует одна и та же матрица активных ограничений /\i t со строго положительными множителями Лагранжа АІЯ J называется регулярной областью для функции Ці (рз) .
Целевая ФУНКЦИЯ координирующей задачи. Лемма І.І. В каждой регулярной области функции Ц{ (рз) являются квадратичными. Доказательство. В регулярной точке р3 множители Лагранжа определяются однозначно. В этом случае состоит из единственного вектора
Необходимые условия экстремума для Ь -ой задачи /1.2/ в этой точке выполняются в следующей форме:
Поскольку формула /1.7/ была выведена в предположении, что/t является матрицей активных ограничений задачи /1.2/, то для тех рз , для которых это условие сохраняет силу
Таким образом, в регулярной области градиент функции іі является линейной функцией рз . Сама же функция tfi на этом участке будет квадратичной: где в{, - некоторая константа, которая может быть найдена из определения функции 4 /формула /1.4//: Лемма доказана.
Каждая регулярная область для Ч? ( рз) образуется пересечением регулярных областей функций tfi( рз) и 4 Cpj) Таким образом, функция Ч? (рз) состоит из "кусков" квадратичных функций, причем переход от одной квадратичной функции к другой осуществляется при переходе от одной регулярной области к другой. Функция ФСр ) непрерывна, но в местах переходов возможны разрывы ее производных. Из-за возможного разрыва градиента конечношаговые градиентные методы для минимизации Ог(Рз) неприменимы. Поскольку же нашей целью является построение ко-нечношагового алгоритма, то вместо минимизации неявной функции будем проводить последовательную минимизацию конкретных квадратичных функций, построенных таким образом, чтобы в конце итерационной процедуры добиться совпадения полученного решения с точкой минимума функции
Определение 1.5. Если имеется многогранное множество, описываемое системой неравенств, то гранью этого множества называется подпространство, заданное подмножеством ограничений, удовлетворенных как равенства.
Максимизация квадратичной функции в регулярной области
Реальные процессы, описываемые задачами со связывающими ограничениями. Мы рассмотрели в предыдущей главе структуры со связывающими переменными. Еще один распространенный вид блочных структур - со связывающими ограничениями.
Пусть имеется производственное объединение в составе нескольких предприятий. Каждое предприятие для производства продукции использует свои внутренние, локальные ресурсы. Предприятия связаны между собой, совместно потребляя некоторые лимитированные ресурсы, например, сырье. Возникает задача, общая система ограничений которой состоит из двух подмножеств ограничений, соответствующих условиям производства на каждом предприятии, и связывающих ограничений на использование общих ограниченных ресурсов L35_[.
Еще один пример. Некоторый производственный процесс, протекающий в дискретном времени, подчиняется ряду ограничений, одни из которых относятся к отдельным тактам анализируемого периода, а другие ко всему периоду в целом.
В обоих случаях матрица ограничений имеет вид Структуры этого типа называются блочно-диагональными со связывающими ограничениями.
Если число общих связывающих ограничений системы невелико, то такую систему называют слабо связанной. Часто такая структура возникает, когда изучаемая система представляет совокупность однотипных, многократно повторяющихся /во времени или пространстве/ подсистем, слабо связанных между собой. Такая структура типична для различных транспортно-производственных задач, в которых предприятия-поставщики связаны ограничениями на общие ресурсы и удовлетворение потребительского спроса [35J .
Декомпозиция и двойственность. Если матрица условий вспомогательной задачи метода линеаризации имеет описанную выше структуру, то при разбиении этой задачи на подзадачи можно использовать двойственные оценки связывающих ограничений
Исходной схемой такого рода является принцип декомпозиции Данцига-Вулфа [21 [. Там задача включала в себя ряд независимых линейных подзадач, связанных ограничениями на распределяемые ресурсы. Эта задача разделялась путем установления цен на общие ресурсы и добавления затрат на эти ресурсы к целевой функции каждой подзадачи. Цены вычислялись как двойственные переменные в координирующей задаче. Координирующая задача находила оптимальное решение, как выпуклую комбинацию предложений, выработанных подзадачами, а также определяла новые цены, направляемые к подзадачам. Таким образом, процесс принятия решений был только частично децентрализован.
В задачах линейного программирования решения вспомогательных подзадач являются крайними точками множеств ограничений. Составляющие не оптимального вектора исходной задачи, соответствующие делению ограничений на блоки, могут оказаться внутрен - 40 ними точками соответствующих подсистем ограничений. Внутренние точки находятся только как комбинации различных крайних точек, этим и объясняется возможность лишь частичкой децентрализации принятия решений в линейных задачах. В задачах с нелинейными целевыми функциями могут быть реализованы условия полной децентрализации, т.е. оптимальная точка находится непосредственно при решении вспомогательных подзадач
Задачи с блочно-диагоналъной структурой ограничений
При этом операции производятся только над массивом Б , по ъ на вектор соответствует и скольку умножение матриц вычеркиванию из него компонент с индексами, не входящими соот-ветственно в множества 3 и J . Если при реализации метода сопряженных градиентов учитывать эту особенность матрицы квадратичной формы двойственной задачи, то вместо массива ДА размеріюоти(іТІо+ і+ г)х(г о+ІГЛі.+ г) достаточно хранить массив В В размерности Wlo Wlo.
Таким образом, несмотря на то, что размерность двойственной задачи равна общему числу ограничений /в том числе простых/ модификация процедуры сопряженных градиентов позволяет оперировать с массивами существенно меньшей размерности. Помимо исходной матрицы D и векторов С! и Ь0 достаточно хранить в памяти матрицу Р Б , векторы нижних и верхних границ переменных, а также массивы, соответствующие индексным множествам. Некоторое усложнение вычислительной процедуры за счет дополнительных проверок и операций дает выигрыш в требуемой памяти, который оказывается тем существенней, чем больше простых ограничений наложено на переменные. Задачи с блочно-диагональной структурой ограничений. методы компактного хранения применимы и в том случае, когда матрица ограничений имеет блочно-диагональную структуру, из-за наличия связывающих строк или столбцов при перемножении двух блочных матриц число некулевых элементов увеличивается. Если не хранить матрицу А А" в явном виде, а операцию % = АА Х разбить на два этапа и выполнять эти операции с учетом блочной структуры матрицы / , то маяно построить модификацию метода сопрякенных градиентов, включающую операции только над ненулевыми блоками.
Разобьем все используемые векторы на составляющие, соответствующие делению матрицы ограничений на блоки. Пусть &е, k -Ь -я составляющая вектора & на & -ой итерации. Распараллеливание процесса вычислений при реализации декомпозиционных алгоритмов. Декомпозиция тесно связана с распараллеливанием вычислений. Более того, по-настоящему эффективная декомпозиция без параллельной организации вычислений, по-видимому, не возможна.
Существует два способа распараллеливания вычислений. Первый состоит в распараллеливании известного последовательного алгоритма. Второй - в построении нового, по своей структуре параллельного алгоритма /см., напр., [?] /.
Декомпозиционный подход по самой сути своей является параллельным. Исходная задача разбивается на несколько подзадач, которые могут решаться независимо, а значит и параллельно. Но, кроме того, как при решении этих подзадач, так и координирующей задачи монет быть осуществлено распараллеливание различной глубины, вплоть до параллельной организации матрично-векторных преобразований.
В качестве примера рассмотрим алгоритм 1.3. Поскольку мы не ориентируемся на какую-либо конкретную вычислительную систему, то ограничимся лишь некоторыми общими соображениями и ре - 81 комендациями.
Наиболее трудоемкими операциями алгоритма являются: решение набора однотипных вспомогательных задач, требующее многократного применения процедуры сопряженных градиентов; построение квадратичных форм локальных координирующих задач, поскольку оно предполагает нахождение обратных матриц; пересчет квадратичной формы локальной координирующей задачи при.расширении одного из индексных множеств.
Остановимся на каждом из этих пунктов подробнее, учитывая возможность параллельных вычислений.
Прежде всего, вспомогательные задачи могут решаться независимо друг от друга, лишь после окончания вычислений объединяя полученную информацию. Этот, так называемый, параллелизм независимых ветвей задачи [31j реализуется многопроцессорной системой с раздельным управлением, где каждый процессор имеет в своем составе автономное устройство управления и работает по своей независимой программе. В данном же случае программа для всех вспомогательных задач одна и та же, задачи полностью идентичны и различаются только входными данными, поэтому возможна организация системы конвейерного /магистрального/ типа содержащей столько устройств управления в конвейере, подключающихся поочередно /по кольцу/ к разным ступеням конвейера, сколько задач в конвейере. После того, как закончено решение одной из задач, она исключается из конвейера и запускаются для решения оставшиеся задачи. Таким образом удается избежать простаивания процессоров при неодновременном завершении решения задач, входящих в данную группу.
Естественный- параллелизм и параллелизм смежных операций процесса (1.8)
При решении аналогичной задачи с 48 переменными, 96 простыми ограничениями на координаты и 24 ограничениями-равенствами потребовалось: а при использовании стандартной процедуры для решения вспомогательном задачи - 23 сек. работы процессора, 21.385 слов І.Ї03У для хранения данных; б при использовании модифицированной процедуры - 73 сек. работы процессора, 3.029 слов МОЗУ для хранения данных.
При использовании модифицированной процедуры время счета несколько увеличивается из-за усложнения вычислительных операций, однако экономия памяти тем существенней, чем больше размерность задачи. Это особенно важно при решении задач, которые не помешаются в оперативную память ЭВМ. Если задача не помещается в УОЗУ, то часть информации долина сохраняться во внешней памяти /на дисках, лентах и т.д./. Перенос информации из внешней памяти в МОЗУ является операцией значительно более медленной, чем арифметическая. Таким образом, для больших задач специальные процедуры экономят не только память, но и затраты времени.
При использовании компактной формы метода сопряженных градиентов задача с 120 переменными, 60 ограничениями-равенствами и 240 простыми ограничениями на переменные была целиком решена без обращения к внешней памяти ЭВы БЭ&л-б, имеющей объем ьіОЗУ в 30464 слов. Время счета - 14 мин. Та же задача с использованием стандартной процедуры сопряженных градиентов потребовала слов только для хранения массивов.
Для простоты изложения мы полагали, что в матрицах блочных задач имеется по два диагональных блока. Все результаты естественным образом распространяются на случай задач с произвольным количеством блоков. Если число блоков в ограничениях равно /V , то при фиксированных связывающих переменных /алгоритмы 1.3 и 2.5/ или при преобразовании задачи минимизации со связывающими ограничениями в задачу минимизации функции Лаг-ранка /алгоритм 2.2/ получаем не 2, а /V независимых подзадач. Целевые функции координирующих задач /1.5/ и /2.7/ состоят в этом случае из /V "" " 1 составляющих и имеют вид N соответственно.
В схемах 3.1, использующих компактное хранение при решении задач минимизации, на каждом этапе происходит параллельное преобразование не 2, а N векторов, где А/ - количество блоков исходной задачи.
Приведенные в главах I и 2 результаты легко распространи - 112 ются на случай, когда в числе ограничений исходной задачи есть равенства. Возможность учета нелинейных ограничений типа равенства является существенным достоинством метода линеаризации. Так же как и для общей задачи математического программирования [58] , в случае задачи специальной структуры учет ограничений типа равенства сводится к анализу знаков множителей Лагранжа: если некоторое ограничение имеет вид равенства, то множитель Лагранжа, соответствующий этому ограничению, может иметь произвольный знак. Очевидно, что это уточнение не нарушает сущности изложенных подходов.
Что касается вычислительной эффективности предложенных методов, то преимущество процедур, учитывающих специальную структуру задач, с точки зрения затрат памяти ЭВМ и времени счета очевидно.
Если сравнивать методы декомпозиции и методы компактного хранения, рассмотренные выше, то в некоторых случаях методы компактного хранения предпочтительнее как менее трудоемкие.
Выигрыш во времени, вообще говоря, выше при использовании декомпозиционных методов. Кроме того, при декомпозиционном подходе организация вычислительного процесса естественным образом отражает иерархическую структуру принятия решений, а методы декомпозиции служат моделями разложенных систем принятия решений. Существенным достоинством оказывается возможность использования специальных алгоритмов для решения вспомогательных подзадач /в том числе и процедур.компактного хранения/, создания и отладки программ для каждой из них /или групп задач/ независимо.
