Содержание к диссертации
Введение
1 Теория п практические приложения структурированных задач линейного программирования 24
1.1 Структурированные задачи линейного программирования . 24
1.2 Динамическая модель "затраты-выпуск" 26
1.3 Произподстпсппо-трапслортпая задача коксования углей . 28
1.4 Задача дну шагового стохастического программирования . 30
1.5 Задача о репликации портфеля, рыночных активов 32
2 Алгоритм двойственных отсечений (АДО) для двублочных структурированных линейных оптимизационных задач 40
2.1 Теоретическая постановка двублочиоп структурированной линейном оптимизационной задачи 40
2.2 Алгоритм двойственных отсечений (АДО) 45
2.3 Вычислительные аспекты АДС) 47
3 Модификация АДО для структурированных линейных оп тимизационных задач с нетривиальным носителем 59
3.1 Теоретическое обоснование способов модификации АДО 59
3.2 Особенности использования алгоритма еимнлекс-мстода для решения подзадач АДО 67
3.3 Модифицированный алгоритм двойственных отсечении (МА-ДО) 68
3.4 Использование рестарта для решения подзадач АДО 71
4 Вычислительные эксперименты с МАДО и его параллелизация 73
4.1 Решение задачи о стационарном распределении температур в двумерной области сложной формы методом конечных элементов ...' 73
4.2 Теоретические основы параллплпзации МАДО 88
4.3 Вычислительные эксперименты с МАДО и пар ал л ел изо ванного МАДО (ПМАДО) 90
4.4 Вычислительные эксперименты с МАДО для задачи двушагового стохастического программирования 94
4.5 Пріїложсміио МАДС) к задачо о репликации портфеля рыночных актииои 98
Заключение 103
Список литературы
- Произподстпсппо-трапслортпая задача коксования углей
- Алгоритм двойственных отсечений (АДО)
- Особенности использования алгоритма еимнлекс-мстода для решения подзадач АДО
- Вычислительные эксперименты с МАДО и пар ал л ел изо ванного МАДО (ПМАДО)
Введение к работе
В процессе математического моделирования сложных технических, экономических систем постоянно возникают оптимизационные задачи, для решения которых предложено значительное количество численных алгоритмов.'Развитие электронно-вычислительной техники, появление новых вычислитель! і ых "архитектур, распространение парадигмы параллельных вычислении за последите десятилетие позволило подойти к решению задач очень большой размерности, в которых число переменных превышает десятки и сотни тысяч. Появилась возможность решать прикладные задачи в экономике, физике, химии, которые ранее были недоступны из-за своей чрезвычайной сложности.
Вместе с тем, освоение этих новых возможностей, предоставляемых вычислительной техникой, требует развития новых типов вычислительных алгоритмов. Такие алгоритмы используют то обстоятельство, что проблемы оптимизации большой и особенно сверхбольшой размерности, порождаемые при математическом моделировании сложных экономических; технических и других систем, как правило, имеют структурные особенности, предоставляющие определенные возможности для "крупнозернистого"
/ (coarse-grain) представления задачи в виде относительно слабо связанных
блоков меньшей размерности.
:'^ --Структурные особенности могут быть связаны как с прострапстпенпы-
ми спецификациями задачи (области сложной формы с относительно узки-'" . ми сечениями в определенных местах для задач математической физики, производствеппо-трапеггортпая специфика для задач планирования производства), так и с динамикой (зависимость будущего поведения системы только от текущего состоянии или небольшой.предыстории), разделением по физическим процессам и т.д. Структурные особенности при моделирова-пии экономических систем возникают вследствие территориальной обособ-ленпостп экономических агентов, ведомственной структуры подразделений
и пр. ''-''''-,.
Возникает целый класс структурированных оптимизационных задач боль-
. той ра-змерпости. для решения которых уже давно предлагаются епециаль-
' . пые вычислительные методы с использованием принципов декомпозиции.
В рамках этого подхода разрабатываются итерационные алгоритмы, сво-
дмщпе решение исходной задачи к решению координирующих и локальных
задач меньшей размерности. В ходе выполнения алгоритмов, основанных
па принципах декомпозиции, как локальные, так и координирующие задачи
.-модифицируются, между этими задачами осуществляется обмен'промежу-
ч точными-результатами.'Применение принципов декомпозиции позволяет . ' уменьшить требования к вычислительным ресурсам: сократить время рс-
.*':"
,-',-_ . шепня задачи, объем' используемой памяти для хранения исходных и про-
межуточных данных и т.п.
Особый интерес вызывают принципы декомпозиции в связи с парадигмой параллельных и глобальных (GRID) вычислений, ставших популярными в последнее время. Концепция параллельных вычислении позволяет организовать расчеты с данными, размещенными в распределенной памяти на разных вычислительных устройствах, и с; использованием большого числа процессоров.
Возможность использования этих двух перспективных направления развития алгоритмов математического программировании оправдывает дальнейшую разработку специальных алгоритмов для решения структурированных задач линейного программирования'большого объема па основе принципов декомпозиции и параллельных вычислений.
Do введении сделан краткий обзор теории и практики методов декомпозиции. Можно отметить, что особенно полно развита теория декомпозиции задал линейного программирования, где ее применение может существенно уменьшить вычислительные затраты. Для алгоритма симплекс-метода для решения задач линейного программирования с п переменными и т ограничениями пессемистическая оценка объема вычислений имеет экспоненциальный вид 0(2mm("'m/2'). Однако, алгоритмическая сложность в практических реализациях симплекс-метода имеет вид 0(п3) [32].
В последние годы большое внимание уделялось развитию и песимплек-сиых алгоритмов решения задач линейного программирования с заданной точностью типа методов внутренней точки, имеющих нолшюмналь-
иую сложность, для которых оценки вычислительной сложности имеют вид 0(пк). где показатель степени обычно порядка 5. Оценка сложности птера-циоипьіх методо» имеет вид 0{п41п(п/е)), где є - требуемая точность решения.Кроме этого и этих алгоритмах существенным являются н требования к памяти ЭВМ (порядка н2). Вместе с том, даже последняя улучшенная оценки, не оставляет надежд па практическую эффективность применения этих методо і! для задач большой размерности общего вида. Для практических задач, где п ~ 104, даже полиномиальные оценки вычислительной и алгоритмической сложности предсказывают весьма, значительный объем вычислении. Этот объем, однако, существенно снижается при уменьшении размерностей задач, что делает методы тина Кармаркара весьма, перспективными с точки зрения решения локальных п координирующих подзадач, возникающих при декомпозиции исходной задачи.
В реальных прикладных задачах матрица, ограничений может иметь нескольких тысяч строк-столбцов. Как правило, она имеют специальную структуру со сравнительно небольшим количеством связывающих переменных пли ограничений. В этом случае; перспективным направлением развития алгоритмов решения таких задач являются схемы декомпозиции, одному из вариантов которых и посвящена настоящая работа. В первой главе рассматривается класс структурированных оптимизационных задач большой размерности, сформулированы постановки широко известных задач линейного программирования и показана их принадлежность этому классу-
. Ben вышеперечисленное оправдывает дальнейшую разработку алгоритмов решения задач линейного программирования большого объема, основанных па модификациях симплекс-метода, и частности, для задач с ограничениями специального вида,-для которых удается предложить более экономные алгоритмы решения. Во второй глапе структурированные линейные оптимизационные задачи сводятся к двублочпому виду, что представляет возможности использования более простых схем декомпозиции. Рассматривается декомпозиционный алгоритм двойственных отсечений, разработанный Е.А. Нурмипским для которого была-показана, высокая численная эффективность |25|.
При декомпозиции задал математического программирования возникает ряд теоретических и практических вычислительных проблем, связанных с пеизбежиоіі вырожденностью подзадач, формулируемых в ходе процесса декомпозиции, желанием быстро получить приближенное решение задачи с заданной точностью, а также численной устойчивостью данных алгоритмов к накапливаемым її процессе вычислении погрешностям.
В третьей главе изучается проблема вырожденности координирующих и локальных подзадач, формируемых в процессе выполнения метода двойственных отсечений с позиции выпуклого анализа и теории двойственности для задач линейного программирования. С учесом этой проблемы этого обстоятельства модифицирован алгоритм декомпозиции и разработан его параллели:ювапиыП вариант. Обсуждаются необходимые модификации симплекс-метода, которые могут эффективно использоваться для решения
формулируемых іі процессе декомпозиции задач линейного программирования.'Доказана теорема сходимости алгоритма двойственных отсечений, использующего е-отсечепня, основанные па попятим е-субградпепта.
Основные преимущества, использования параллельных алгоритмов для декомпозиции болыперазмерпых структурированных оптимизационных задач заключаются в использовании каждым процессом данных меньшего объема, размещаемых її распределенной памяти, и сокращении общего времени выполнения алгоритма за счет параллельной обработки этих данных.
В четвертой главе обсуждается программная реализация и вычислительные :->кепер]шспты с модифицированным алгоритмом двойственных отсечении, его параллелизоваппым вариантом для решения задачи о стационарном распределении температур в области сложной формы методом конечных элементов, диушаговой задачи стохастического, программирования п задачи о репликации портфеля рыночных активов.
Произподстпсппо-трапслортпая задача коксования углей
Рассмотрим классическую модель "затраты-вынуск" рассматривающую п отраслей, каждая из которых производит одпп товар. Пусті» хі - валовой выпуск продукции i-oli отрасли, di - конечный спрос на продукцию г-ой отрасли, Qij количество продукции г-о\\ отрасли, необходимое для производства единицы продукции j-ой отрасли.
Рассмотрим динамический вариант базовой леоптьевской модели, предполагая известными матрицу А в (1.3) и вводя в рассмотрение матрицу Bi элементы которой bij означают затраты продукции г-ой отрасли па увеличение выпуска па одну единицу в j-ой отра-сли. Пустії xt - вектор валового выпуска отраслей ЇЇ периоде , dt - вектор конпчпого спроса па продукцпіа-отра :лем в момсігг времени t. St - запас продукции в конце t-va периода, cfr - ироизводствемная мощность, измеряемая в единицах выпуска продукции, в момент времени Ї, щ - изменение мощности і! периоде t. щ - недоиспользуемая мощность в период І.
Объединяя переменные HiJri2 - -, пт и блок сиязынающнх переменных, получим предстаолепис системы ограничении данной задачи н ішдо (1-2). В качестве функционала может быть пыбрашц например, стоимость хра v Т
неппя суммарных запасов продукции отраслей 22 $и 1.3 Производственно-транспортная задача коксования углей рассмотрена производстислпо-трапепортиаи задача распре-долепим коксующихся углей между коксохимическими заподами. Очевидно, что решение X(UJ) будет зависеть от реализации определенно го события ш. Однако, пели решение этой задачи должно быть определено a priori, иряд ли найдется пектор х) удовлетворяющий ограничениям зада чи для всех событий и) Є Q._BcKTQ\i_5(x}to) = Іі(ш) — S(OJ)X характеризует степень нарушения ограничений исходной модели при выборе какого-то х. В дпушаговон модели стохастического программирования предполагает ся, что па первом шаге мы знаем лишь возможные реализации параметров V модели, на втором шаге мы получаем полную информацию о наступившем с событии ы. В таком случае оптимальный выбор х может проводиться при одновременной минимизации некоторого функционала от вектора 5(X)OJ). Ясно, ччо система ограничений данной задачи является блочной вида (1.2). Однако, вектор связывающих переменных в ДІШНОІЇ задаче входит в минимизируемый функционал. Обозначим новый вектор связывающих переменных за я;. Добавим ограничение х = х и агрегируем его, например, с ограничениями у\—уї+31х = hl. Дальнейшее агрегирование вектора х с векторами У\ ,у позволяет исключить вхождение вектора х в функционал получаемой задачи, сохраняя дпублочпоеть ограничении.
Операции па финансовом (фондовом) рынка представляют собой размещении свободных денежных средств с целью получения дохода путем покупки-продажи рыночных активов. Эти активы обладают различными показателями доходности, определяемой долгосрочным трендом поведения рыночной цепы, а также различной степенью ее волатильпостн. Изменчивость и непредсказуемость будущиэГцсп создает для портфельных инвесторов определенный риск, которым необходимо разумно управлять Традиционными мерами риска являются дисперсия портфеля GG] и кваптильный критерии VaR (Value-at-Risk). В последнее время в качестве меры риска расширяется и использование критерия условных средних потерь CVaR (Conditional Value-at-Risk), Управление рисками характерно не только для финансовых моделей, и частности, кваптильный критерий помимо инвестиционных задач [17] используется в двухэтаппом стохастическом программировании [18], аэрокосмических приложениях [1G] Применительно к задачам инвестирования основным понятием является портфель инвестора, который можно описать вектором х Є X С IR", г-ая компонента которого соответствует количеству единиц актива г в портфеле инвестора, г = 1,... ,п. Стохастическая компонента модели заключается в векторе у рыночных цеп активов, являющегося случайной величиной из множества У С IR,11, на котором задана вероятностная мера V. Экономические потери инвестора описываются функцией /(ж, у), определяющей поте ри при использовании иыбрапиого портфеля х и наблюдаемой реализации котировок у EY.
Более подробно ознакомиться со свойствами критериев VaR, CVaR и их приложениями к задачам финансовой математики можно в работах [79, 80].
Задача о репликации портфеля рыночных активов (см., например [39, 79]) возникнет при желании инвестора зафиксировать ex ante структуру портфеля рыночных активов па некоторый горизонт планирования, так чтобы стоимость портфели в коночный момент при известных будущих цепах этих актшюн была равна заданной. При отом инвестор минимизирует спои потери, под-которыми понимается мира отклонения рыночной стон-мости г го портфеля от стоимости эталонного портфеля, состоящего только и;-! актпва-;-)талопа. ]"$ качестве дополнительного условия может присутствовать желание инвестора ограничить сверху риск как какую либо меру, рассмотренную ранее. В настоящей работе в качестве такой моры используется условная средняя величина, возможных потерь; соответствующая критерию CVaR.
Алгоритм двойственных отсечений (АДО)
В процессе математического моделирования сложных технических, экономических систем постоянно возникают оптимизационные задачи, для решения которых предложено значительное количество численных алгоритмов. Развитие электронно-вычислительной техники, появление новых вычислитель! і ых "архитектур, распространение парадигмы параллельных вычислении за последите десятилетие позволило подойти к решению задач очень большой размерности, в которых число переменных превышает десятки и сотни тысяч. Появилась возможность решать прикладные задачи в экономике, физике, химии, которые ранее были недоступны из-за своей чрезвычайной сложности.
Вместе с тем, освоение этих новых возможностей, предоставляемых вычислительной техникой, требует развития новых типов вычислительных алгоритмов. Такие алгоритмы используют то обстоятельство, что проблемы оптимизации большой и особенно сверхбольшой размерности, порождаемые при математическом моделировании сложных экономических; технических и других систем, как правило, имеют структурные особенности, предоставляющие определенные возможности для "крупнозернистого" / (coarse-grain) представления задачи в виде относительно слабо связанных блоков меньшей размерности.
Структурные особенности могут быть связаны как с прострапстпенпы ми спецификациями задачи (области сложной формы с относительно узки- " . ми сечениями в определенных местах для задач математической физики, производствеппо-трапеггортпая специфика для задач планирования производства), так и с динамикой (зависимость будущего поведения системы только от текущего состоянии или небольшой.предыстории), разделением по физическим процессам и т.д. Структурные особенности при моделирова-пии экономических систем возникают вследствие территориальной обособ-ленпостп экономических агентов, ведомственной структуры подразделений.
Возникает целый класс структурированных оптимизационных задач боль . той ра-змерпости. для решения которых уже давно предлагаются епециаль . пые вычислительные методы с использованием принципов декомпозиции.
Особый интерес вызывают принципы декомпозиции в связи с парадигмой параллельных и глобальных (GRID) вычислений, ставших популярными в последнее время. Концепция параллельных вычислении позволяет организовать расчеты с данными, размещенными в распределенной памяти на разных вычислительных устройствах, и с; использованием большого числа процессоров. Возможность использования этих двух перспективных направления развития алгоритмов математического программировании оправдывает дальнейшую разработку специальных алгоритмов для решения структурированных задач линейного программирования большого объема па основе принципов декомпозиции и параллельных вычислений.
Можно отметить, что особенно полно развита теория декомпозиции задал линейного программирования, где ее применение может существенно уменьшить вычислительные затраты. Для алгоритма симплекс-метода для решения задач линейного программирования с п переменными и т ограничениями пессемистическая оценка объема вычислений имеет экспоненциальный вид 0(2mm(" m/2 ). Однако, алгоритмическая сложность в практических реализациях симплекс-метода имеет вид 0(п3) [32].
В последние годы большое внимание уделялось развитию и песимплек-сиых алгоритмов решения задач линейного программирования с заданной точностью типа методов внутренней точки, имеющих нолшюмнальиую сложность, для которых оценки вычислительной сложности имеют вид 0(пк). где показатель степени обычно порядка 5. Оценка сложности птера-циоипьіх методо» имеет вид 0{п41п(п/е)), где є - требуемая точность решения.Кроме этого и этих алгоритмах существенным являются н требования к памяти ЭВМ (порядка н2). Вместе с том, даже последняя улучшенная оценки, не оставляет надежд па практическую эффективность применения этих методо і! для задач большой размерности общего вида. Для практических задач, где п 104, даже полиномиальные оценки вычислительной и алгоритмической сложности предсказывают весьма, значительный объем вычислении. Этот объем, однако, существенно снижается при уменьшении размерностей задач, что делает методы тина Кармаркара весьма, перспективными с точки зрения решения локальных п координирующих подзадач, возникающих при декомпозиции исходной задачи.
В реальных прикладных задачах матрица, ограничений может иметь нескольких тысяч строк-столбцов. Как правило, она имеют специальную структуру со сравнительно небольшим количеством связывающих переменных пли ограничений. В этом случае; перспективным направлением развития алгоритмов решения таких задач являются схемы декомпозиции, одному из вариантов которых и посвящена настоящая работа. В первой главе рассматривается класс структурированных оптимизационных задач большой размерности, сформулированы постановки широко известных задач линейного программирования и показана их принадлежность этому классу . Ben вышеперечисленное оправдывает дальнейшую разработку алгоритмов решения задач линейного программирования большого объема, основанных па модификациях симплекс-метода, и частности, для задач с ограничениями специального вида,-для которых удается предложить более экономные алгоритмы решения. Во второй глапе структурированные линейные оптимизационные задачи сводятся к двублочпому виду, что представляет возможности использования более простых схем декомпозиции. Рассматривается декомпозиционный алгоритм двойственных отсечений, разработанный Е.А. Нурмипским для которого была-показана, высокая численная эффективность 25. При декомпозиции задал математического программирования возникает ряд теоретических и практических вычислительных проблем, связанных с пеизбежиоіі вырожденностью подзадач, формулируемых в ходе процесса декомпозиции, желанием быстро получить приближенное решение задачи с заданной точностью, а также численной устойчивостью данных алгоритмов к накапливаемым ЇЇ процессе вычислении погрешностям.
Особенности использования алгоритма еимнлекс-мстода для решения подзадач АДО
Во многих постановках область изменения снизывающих переменных неявно ограничена требованиями разрешимости задач вычисления функции /_-1, hjj. Особенно явно это проявляется п декомпозиции задач решения спетом уравнении, где подзадачи неминуемо оказываются либо "пере- либо педоопределенпыми, Это приводит к неявно заданным нетривиальным ограничениям на связывающие .переменные, которые в предыдущей вер сии алгоритма j25 no учитывались. Этот эффект весьма существенен, па. практике во времн работы алгоритма, особенно па начальных итерациях, вероятно, а фактически неизбежно, возникновение недопустимых подзадач (2.9), (2Л1). Характер неразрешимости этих задач может быть двоякой природы: допустимое множество задачи может оказаться пустым, либо ее целевая функция пе ограничена па допустимом множестве задачи, то есть допустимоп мпожеетію зндачп содержит направление бесконечного убывания целевоП функции (для задачи минимизации).
В АДО вычисление./ Є dfn{xk) может привести к задаче с пустым допустимым множеством, а вычисление хк Є с Лд(—р/,:) к задаче, где целевая функция пн.мнлиется ограниченной. Ясно, что в зтпх случаях стаио-пятся неопределенными величины Іів{рк)і їл{їїк) С точки зрения теории двойственности случаи неограниченной задачи может быть сведен к вопросу о коррекции алгоритма в случае возникновения подзадачи с пустым допустимым множеством па некотором ішіго, поэтому рассмотрим сначала первый случаи.
Множество domf описынпется с помощью задачи поиска допустимого Оазиса п задаче линейного программирования. Стшідпртиьіи процесс решения задачи линейного программкропания включает фазу 1 " поиск допустимого базиса. В канонической постановке при этом решается вспомогательная задача с дополнительными искусственными переиоппыми-певязкамн, добавляемыми в ограничения задачи, и искусственным функционалом. Модифицируемым функционал обычно представляет собой сумму мбеолютпых значений невязок, чтобы сохранить линейность задачи. Если оптимум в этой задано равен пулю, то допустимый базис в этой задали суіцсстпуст и"определ5іотся.
Отсюдп следует, что (3,5) - отсечение, отделяющей? хк от dom//j. Задача отделения точки хА от dom/д. как правило, имеет множество решений. По теореме 2.3/2 qk находится как двойственный вектор к ограничению (3-3) в задаче поиска допустимого базиса. Однако, вектор qk7 построенный как двойственный вектор к ограничению (3.3) в ;і ідаче (3.1)-(3.4), обладает гпщшиїьпим свойством оптимальности. Для двойственных переменных гиперплоскость, отделяющая вектор — рк от множества dom/гд, будет задаваться опорным вектором прямых переменных хк. Этот вектор является решением задачи. Однако, и длимом ситуации позможсн более простой метод построения требуемого отсечения. Неограниченность задачи (3.6) означает существование вектора а. что для любого допустимого вектора. Ж(] и скаляра 9 — +со: XQ 4- Ои- -ї —ос)..Тогда отделение недопустимых нектаров р достигается с помощью отсечения ар 0, которое должно быть" добавлено к ограничениям задачи (2.12) аналогично дополнительным отсечениям в прямой задаче {2.10)-. В процессе решения задачи липеПпого программирования симплекс-методом неограниченность задачи (3-6) означает, что будет найден вектор а 0. имеющий размерность количестна нсбазпемых переменных, в В случае неразрешимости задачи 3.7)-(3.11) диопстпеппый вектор к ограничению (3.15) можно использовать для построения отсечения допустимости ішда (3.5), которое должно быть добавлено к ограничениям прямой задачи (2ЛС)-(2Л)). Действительно, если г и,х\ А , А% s оптимальное решение (ЗЛ2)-(ЗЛ0), то двойственный иоктор qk к ограничению (ЗЛ5) по теореме. Для использовании алгоритма симплекс-метода при решении задач линейного программирования, возникающих и ходе ш.шолпеппя алгоритма двойственных отсечении, необходимо приведение соответствующих задач к каноническому виду задачи линейного программировании mine;? при Az — r/3 z 0. При этом используется стандартный прием модификации задам ЛП. когда ограничения типи, неравенств Az d в задачах (2.У), (2,1G)-(2.20), (2.11), (2.22)-(2.20) заменяются па равенства вида Az + s = d путом введении вектора дополнительных искусственных переменных s 0. Переменные Ї;Т неограниченные познаку, представляются і! виде v — s\—s i} s\ 0, 52 0.
Симплекс-метод также позволяет получить вектор двойственных переменных 7г. при этом для канонической постановки задачи ЛП к — с$Ав , где св- An базисные масти вектора с и матрицы А соответственно.
Вычисление обратных бпзпепых матриц па каждом шаге алгоритма симплекс-метода существенно шшяст па скорость его работы. Современное промышленное программное обеспечение для решения задач математического ирогрпммнрошшня (MINOS, CPLEX) использует вспомогательные методы для предварительной факторизации базисной матрицы. Использование LU-разложспия базисной матрицы для ее обращения позволяет сократить вычислительную сложность этой процедуры с 0(п3) до 0{п2).
Вычислительные эксперименты с МАДО и пар ал л ел изо ванного МАДО (ПМАДО)
Одним т источников задач, бол ьшоП размерности являются проблемы вычислительной математической физики. Использование экстремальных принципов в таких задачах имеет давнюю историю и составляет основу как многих теоретических р їиульч І.ГГОЕЇЧ так и вычислительных подходов, В классическом варианте применение вариационных принципов ведет к формулировке необходимых условии экстремума, что переходит в вычислительную форму задачи, каковой является система уравнений -большой размерности. Такая система зачастую имеет ряд особенностей типа ленточной структуры н решастсмспсцнальпыми методами [19, С7, 75," 82J, Мы ироде 73 : мопотрпруем :-л 0"г подход па примере метода конечных элементом 9, 24j. Система ураппеппи метода конечных алемеггпт с точки трепня теории оитпмпчпцпп является вырожденной :-жетремапьноп :їа.дачеіі с трппиальт пым фумкцпопплом, где основная и единственная проблема заключается и удовлетпореппи ограничении. Помимо их вычислительной важности такие задачи представленої1 eofioii и практический интерес.
При декомпозиции исходной задачи па, подзадачи решение системы будет единственной точкой пересечения нетривиальных допустимых областей подзадач. В этом смысле такие задачи являются хорошими тестами для МАДО. Оптимизируемый функционал в таких задачах несущественен и может бып/положеи равным нулю.
Статистика ранения тестового примера приведена в таблице 4,2. Ре-зульчаты решения садами показывают достаточно быструю сходимость но большим" итерациям, оптимальное решение устанавливается ужо после k = 5. что говорит о небольшом обмене данными между задачами (АХ) и (ВР). что способствует разработке параллелнзопаппого алгоритма. На итерациях 1-Г) задача ВР возвращает опорные векторы pj" отсечении допустимости, на С-оп итерации алгоритма вектор рк становится пулевым. Для решения подтлдлч МАДС) использовался епмилеке-метод с: определением двойственных переменных [29]. Суммарное количество итераций симплекс-метода при решении подзадач (АХ) составило 2G5, в подзадачах (ВР) - 1G2.
В качество средства разработки параллелизоваппого варианта МАДО использовался широко распространенный стандарт обмена сообщениями между вычислительными процессами (МРІ, message passing interface)- Механизм параллельных вычислении организуется па оснопе стандарта локальной вычислительной сети (LAMj local area multicomputer), позволяющий производить расчеты па персональных компьютерах, объединенных в есть. ІЗ Институте Автоматики и Процессов Управления ДВО РАН сконфигурирован рабочиП вариант системы LAM/MPI версии G.4.2, позволяющий пользователю самостоятельно задавать моделі» организации вычислении, используя її качество узлов мультикомшлотера любые доступные для LAM компьютеры с;сти [і распределяя выполнение процессов по любым узлам. Вычислительная моделі параллельного алгоритма была представлена в виде двух процессов, обменивающихся сообщениями стандарта МРІ. Уз-ламп мультпкомпыотера служили два персональных компьютера, причем каждый процесс выполнялся на отдельном узле. В кнчестно тестовой также решалась задача нахождения стационарного распределения температур в двумерных областях аналогичных области па рисунке 4.1. Генерируемые двумерные области отличались количеством узлов сетки із основной области и "узком сечении". Будем обозначить размерность вектора связывающих переменных за Nx, количество ограничении в блоках уІ —у\ + Slx — hl и у — УЇ + S2x = h2 исходпої! задачи будем считать одинаковым и равным т.
Для численных расчетов с данной моделью использовались данные о динамике цеп акций 10 активов (АА, GE, JNJ, MSFT, АХР, GM, JPM, PG, BA, HD) п: 30 активов, входящих в индекс Dow Jones Industrial (DJI), за период с 3 февраля но 14 апреля 2003 года (всего 61 котировка по каждому активу), которые достуниы-па http://fmance.yahoo.com. В качестве цен рыночных ЛКТШЮІЇ, входящих н портфель, использоишшеь цепы по закры-ггито торгов,.п качестве эталонного актина рассматривался caw индекс DJI за указанный период. . . Во всех экспериментах терминальная стоимость портфеля v выбиралась равной 1000. уронепь вероятности а для определения CVaR равен 0.9. Задача репликации портфеля решалась как с помощью МАДО, применяемого к структурированной форме задачи {4.5)-(4.8), так н с помощью симплекс-метода, применяемого к задаче (4.5)-(4.8) без разделения па блоки.
Сначала, количество периодом-времени Т выбиралось равным 50. и ис-пользопалось 50 первых котировок указанных 10 актжюи и эталона, начиная с: .3 марта 2003 года, допустимый уровень потерь ш был ранен 0,8. При этом оптимальный вектор х количества активов, включаемых и портфель, равен (1,11,5.15,0.00,458,4.82,0.28,0.00,2.49,2.79,8.03). Ограничение CVaRn(x) и па допустимый уровень CVaR в этом случае оказалось неактивным--поскольку значение GVQ RQ$(X ) = 0.009925. На рисунке 4.9 приведена динамика стоимости портфеля х , то есть величины Ptj j Д 51 I = 1,,.,,50 (пунктирная линия), и величин Bit-, отражающих динамику эталонного портфеля (жирная линия).
В дальнейшем было проведено еще 7 экспериментов, в которых изменялось значение Т, для со = 0.8, Основные характеристики экспериментов приведены в таблице 4.5. m - количество ограничении задачи (4.5)-(4.8). Na + Nh - общее количество внутренних переменных в блоках z и гд} km?iX - число прямых и двойственных задач, решаемых алгоритмом прямо двойственных отсечений, МАДО - время выполнения алгоритма прямо-двойственных отсечений В секундах, СМ - ВрСМЯ выполнения симплекс-метода в секундах в задаче без разделения па блоки, МАДО/СМ - отношение примени выполнения алгоритма прямо-двойственных отсечений и симплекс-метода. При росте! размеров илдачи наблюдается рост выигрыша в использовании декомпозиции задачи по сравнению с решением задачи без использования информации о специальной структуре ограничений.
