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

Введение

Классические методы декомпозиции линейных оптимизационных задач.

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

Методы отсечений и декомпозиция оптимизационных задач

1 Теория и практические приложения структурированных задач линейного программирования

1.1 Структурированные задачи линейного программирования

1.2 Динамическая модель "затраты-выиуск".

1.3 Производствспно-трапспортиая задача коксования углей

1.4 Задача двушагового стохастического программирования

1.5 Задача о репликации портфеля рыночных активов.

2 Алгоритм двойственных отсечений (АДО) для двублочных структурированных линейных оптимизациопиых задач

2.1 Теоретическая постановка двублочпой структурированной линейной оптимизационной задачи.

2.2 А, н'орптм двойственных отсечений (АДО)

2.3 Вычислительные аспекты АДО.

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

3.1 Теоретическое обоснованно способов модификации АДО

3.2 Особенности использования алгоритма симплекс-метода для решения подзадач АДО.

3.3 Модифицированный алгоритм двойственных отсечений (МА

3.4 Использование рестарта для решения подзадач АДО

4 Вычислительные эксперименты с МАДО и его параллелизация

4.1 Решение задачи о стационарном распределении температур в двумерной области сложной формы методом конечных элементов

4.2 Теоретические основы параллолнзации МАДО.

4.3 Вычислительные эксперименты с МАДО и параллелизовап-пого МАДО (ПМАДО)

4.4 Вычислительные эксперименты с МАДО для задачи двушагового стохастического программирования

В и]хм 1,(4'со математического моделирования сложных технических, экономических систем постоянно возникают оптимизационные задачи, для решения кото})!,IX предложено значительное количество численных алгоритмов. Развитие электронно-вычислительной техники, появление новых иы-числптельпых'архитектур, распространенно парадигмы параллельных вычислении за. последнее десятилетне позволило подойти к решению задач очень большой размерности, в которых число переменных превышает десятки и сотни тысяч. Появилась возможность решать прикладные4 задачи в экономике, физике, химии, которые рапсе были недоступны из-за своей ч рез в ы ч ail пой сл ож пост и.

Вместе с тем, освоение этих новых возможностей, предоставляемых вычислительной техникой, требует развития новых типов вычислительных алгоритмов. Такие алгоритмы используют то обстоятельство, что проблемы оптимизации большой и особенно сверхбольшой размерности, порождаемые при математическом моделировании сложных экономических, технических и других систем, как правило, имеют структурные особенности, предоставляющие определенные возможности для "крупнозернистого" coai\se-&raiii) представления задачи в виде относительно слабо связанных блоков меньшей размерности.

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

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

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

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

Во введении сделан краткий обзор теории и практики методов декомпозиции. Можно отметить, что особенно полно развита теория декомпозиции задач линейного программирования, где ее применение может существенно уменьшить вычислительные затраты. Для алгоритма симплекс-метода для решения задач линейного программирования с п переменными и т ограничениями пессемистическая оценка объема вычислений имеет экспоненциальный вид 0(2mm("'m/2)). Однако, алгоритмическая сложность в практических реализациях симплекс-метода имеет вид 0(п3) [32].

В последние годы большое внимание уделялось развитию и песимилек-сных алгоритмов решения задач линейного программирования с заданной точностью типа методов внутренней точки, имеющих полиномиальпую сложность, для которых оценки вычислительной сложности имеют вид 0{п,:). где показатель степени обычно порядка 5. Оценка, сложности итерационных методов имеет вид 0(гг4 In(n/е)), где е - требуемая точность решения. Кроме :ггого в этих алгоритмах существениым являются и требования к памяти ЭВМ (порядка п2). Вместе с тем, даже последняя улучшенная оценка пе оставляет надежд на практическую эффективность применения этих методов для задач большой размерности общего вида. Для практических задач, где п ~ 104, даже полиномиальные оценки вычислительной и алгоритмической сложности предсказывают весьма значительный объем вычислений. Этот объем, однако, существенно снижается при уменьшении размерностей задач, что делает методы типа. Кармаркара весьма перспективными с точки зрения решения локальных и координирующих подзадач, возникающих при декомпозиции исходной задачи.

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

Все вышеперечисленное оправдывает дальнейшую разработку алгоритмов решения задач линейного программирования большого объема, основанных на модификациях симплекс-метода, в частности, для задач с ограничениями специального впда.7для которых удается предложить более экономные алгоритмы решения. Во второй главе структурированные линейные оптимизационные задачи сводятся к двублочному виду, что представляет возможности использования более простых схем декомпозиции. Рассматривается декомпозиционный алгоритм двойственных отсечений, разработанный Е.А. Нурмипскпм для которого была-показана высокая численная эффективность |25|.

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

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

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

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

Классические методы декомпозиции линейных оптимизационных задач

Необходимость использования декомпозиционных методов [G, 7, 13, 20, 21, 22, 29, 31, 33, 35, 47, 50, 63, 68, 77, 78, 83, 84, 85, 86], как правило, связана с большим количеством ограничений и переменных в задачах математического программирования. Иногда применение декомпозиционных методов оправдывается структурными особенностями задачи.

К общеизвестным методам декомпозиции относятся метод Дапцига-Вулфа (генерации столбцов) [37, 38], метод Беидсрса (генерации и релаксации ограничении) 13G, 44, 89] и использование различных функций Лаграпжа [10, 30, 45, 53, 54, 70].

Для задач линейного программирования вида mill сх,

-------Ах-> Ь,

Dx > d, х > 0, где множество {ж : Ах > b, х > 0} - ограниченный многогранник, релаксация Лаграпжа. представляет собой решение задачи maxmin(c.x + v(d — Dx)), ■

Ax > 6, z > 0.

Декомпозиция Беидсрса эквивалентна релаксации Лаграпжа в смысле двойственности решаемых подзадач: maxmax(6u + dv), v>0 » v ' и'A < с - v'D, u> 0, а. декомпозиция Дапцига-Вулфа основана иа том, что для описания полиэдральной области определения достаточна пифо])мацпя о ее крайних точках. Представш} ограниченное множество {х : Ах > Ь, х > 0} в виде выпуклой комбинации крайних точек xll,h 6 Т. получим задачу вида min Е ai,(cxh), he г

Е ah{Dxh) > d, he Т

Е ah = 1, лет оси >0, he Т.

Двойствен ну ю задачу запишем в виде max vq + dv) r>i),c0 ex1' + vDxh > 1>(), h e т, которая эквивалентна задаче maxmin(ca;/l + v(d - Dxh)). u>o her v "

Метод p ал а ксп ц m i, Дою. e оффр и она.

В методе релаксации ограничений для линейных задач (релаксация Дже-оффрпоиа) [29] рассматривается проблема пипсж, агх <b, i е I = {1,2,., т}, x £ X, где X выпуклое множество.

Идея метода основана на утверждении о том. что если х* - решение этой задачи и а'х* =0, г £ / С /, а1х* < 0, г £ /\/, то гс* является решением задачи mill сх, а'х < 6, г £ /, гс 6 X

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

Метод расчленения ограничений.

Метод расчленения ограничений [22, 29] показал свою эффективность для решения сепарабельиых задач с большим количеством переменных вида V min Y, с'хп t=i a%xi < i=1 r, > 0,z = 1,2,.;;.

Вводя m-мерпые векторы y\ удовлетворяющие условию Y, if <b, пред

7 = 1 ставим ограничения исходной задачи в виде а1 х-, < у\ i — 1, 2,., п, тогда исходная задача эквивалентна задаче min jtfi{y% (1) i=i

1у{<Ь, (2) i=i где = min ciXj, alXi < у', Xj >0,2 = 1,2,., п. Таким образом метод расчленения ограничений состоит в последовательном решении подзадачи вычисления fi(y') и координирующей задачи (1)-(2).

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

Теоретической основой для декомпозиционных методов является аппарат выпуклого анализа и иедифференцируемой оптимизации (НДО). Численные методы решения таких задач изложены в работах [3, 8, 25, 28, 35, 40, 41, 4G, 48, 49, 51, 52, 59, G5, 69, 76, 29].

Задачи НДО представимы в виде mjn/W, (3) где / - вещественная, непрерывная, выпуклая функция.

Недифференцируемость (или негладкость) функции f(x) означает, что на некотором подмножестве области определения ее градиент в смысле обычного определения Гато по существует. Одна,ко, выпуклость функции f(x) обеспечивает существование хотя бы одной опорной гиперплоскости к f(x) в каждой точке области определения. Наклоны таких опорных гиперплоскостей 15 некоторой точке а;0 области определения функции образуют множество, называемое субдифференциалом функции в этой точке, обозначаемое df(xl]). Элементы этого множества называют субградиеитами.

Формально, вектор р* является субградиептом функции f(x) в точке х°, если для всех х из области определения f[x°) + p*(x-xQ)<f(x). (4)

К основным методам решения задачи (3) относятся субградиеитпые методы и методы отсечений (отделяющих плоскостей).

Субградиеитпые методы сходны с методами градиентного спуска для поиска экстремума дифференцируемой функции. В методе обобщенного градиентного спуска, начиная с некоторой начальной точки, строится последовательность точек, удовлетворяющих следующему рекуррентному соотношению: Л где дк £ df(xk) субградиеит минимизируемом функции f(x) в точке хк.

Последовательность положительных чисел а/с - длин шагов - обычно выбирается так. чтобы ос lim а/. = О, ]Г ак —

А'—»оо jц

Решая задачу mill f'{xk,d),

•'Де f'(xk,d) - производная по направлению d функции f(x) в точке хк, и используя свойство f'(xk,d)= max ad, neOJ(:rk) получим метод наискорейшего субградпентного спуска, где djc = & = arg max И.

Можно вычислять приближенные направления убывания функции f(x) с помощью нахождения ее £-субдифферопциала. то ость множества def(xk) = {£ : f(xk) + £(х - хк) - е < f(x), для любого ж}, получая класс е-субграднеитпых методов.

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

Пусть задан вектор v £ Я" с ||7>|| = 1. Каждый вектора; £ R!1 однозначно представим в виде х = fiv + z, (v, z) — О, где /г= fi{x,v) - некоторое число, z = z(x,v) - некоторый вектор из Rn, ортогональный вектору v. Оператором растяжения пространства R1' в направлении v с коэффициентом /3 > О называется оператор Р, действующий па х = [IV + 2 следующим образом:

Р(х) =0fiv + z= (Р- l)(x,v)v + x = {Е+{Р- l)vvT)x.

Здесь представлено несколько эквивалентных форм записи оператора Р. Е - единичная матрица размерности п х n, Т • знак транспонирования.

В описываемом методе минимизации выпуклой функции f{x) движение в направлении обобщенного градиента па каждом шаге сочетается с операцией растяжения пространства аргументов в этом же направлении. Пусть после выполнения к шагов найдена точка xk (в качестве а;0 может быть выбрана произвольная точка). Определяется субградпепт дк £ df(хк) функции f(x) в точке х1'. Если дк — 0, то хк нскома.я точка минимума и вычисления прекращаются. В противном случае осуществляется линейное преобразование исходного пространства: у^В^х, фк{у) = f{B,,y), где Б/, некоторый, известный к данному шагу оператор (пеособая матрица).

В новом пространстве реализуется шаг обобщенного градиентного спуска для функции f(x) исходя из точки у1' = Bklxk, то есть находится уы = у*-ак^Уедф(хк). (5)

Возвращаясь в исходное пространство (применяя к обеим частям (5) оператор В].), получаем хь+1 = хк akBkv

IIV II

Рассматриваемый (к -f 1)-й шаг завершается нахождением оператора

1 = BjJ\.y где Рк оператор растяжения пространства R" в паправле-иип рк с коэффициентом /? = 1 Д. > 0 - некоторое число. В качестве Bq может быть выбрана любая пеособая матрица, например, единичная матрица Е.

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

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

Методы отсечений и декомпозиция оптимизационных задач

Методы отсечений пли отделяющих плоскостей, используемые для решения задач математического программирования, основаны на идее последовательного сужения области локализации искомой точки минимума х*. На каждом шаге от множества X отсекается некоторое подмножество таким образом, что в оставшейся части множества X заведомо содержится хотя бы одна точка минимума функции f(x). Отсечениями ситу жат опорные гиперплоскости к /, построенные в различных точках х. Большое количество таких отсечений лучше аппроксимирует функционал.

Рассмотрим задачу min /(.т), д{х) < О, где функции f(x),g(x) являются выпуклыми, дифференцируемыми и непрерывпымп, множество значений х, удовлетворяющих неравенству д(х) < О, будем обозначать через X, пусть х некоторая внутренняя точка этого

Введем в рассмотрение гиперплоскость (/'(£), х — х) = 0 и обозначим через Л' множество всех точек из X, удовлетворяющих условию (/'(х), х — х) < 0. В случае педифферепцнруемоп функции f(x) использование се субградпопта заменяет данное неравенство па субградпептное неравенство (4) для внешней аппроксимации функции f(x).

Этот прием позволяет свести исходную задачу минимизации f(x) на множестве .Y к задаче минимизации /(;х) па множестве X, объем которого

V Л меньше исходного. Выбираясь качестве X множество Х) можно провести тс же рассуждения относительно вновь полученной задачи и так далее, пока точка х* по будет локализована во множестве достаточно малого объема, определяемого заданной точностью решения исходной задачи.

Методы отделяющих плоскостей решают задачу множества, то есть д(х) < 0. min max f(xl) + щ(х — х,) J max д (а:-7) + аЦх — ж7) < 0 которая эквивалентна задаче nun v и,.с f{xl) + а{ {х - Xi) <v, iel J g(x3) + ot$(x - x3) < 0, j G J, а{ Е df(xi), а<} <Е dg{xj). Для некоторого приближения vk "локализованное"' пространство х, v) : v < vf'\ n-W) = + а/(х - X,) < v, г G //,, g{xi) + 0Cj{x — х-*) <0,je J&, содержит оптимальный вектор.

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

Классический метод Колли выбирает в качество очередной точки хк решение задачи (G).

Если в качестве точки х на каждом шаге выбирать центр тяжести очередного множества Л", будет отсекаться но менее чем (п/(п+ 1))" часть объема предыдущего множествах. Такой метод, получивший название метода централизованных отсечений, обеспечивает убывание объема области локализации точки х* со скоростью не меньшей, чем скорость убывания геометрической прогрессии со знаменателем 1 — (п/(п + 1))" при больших п. К сожалению, нахождение центра тяжести множества X в большинстве случаев (даже когда, например, Л' многогранник) является весьма трудоемкой за,дачей. В то же время, если X - шар, эллипсоид, ортогональный симплекс (то есть множество точек х 6 R11, удовлетворяющих п неравенствам £ Xj < п + 1, Xj > 0, j — 1,1,., п ) и т.п., то нахождение з=1 центра тяжести множествах не вызывает затруднений, что приводит к созданию достаточно эффективных методов решения задач математического программирования. На, каждом шаге множество X погружается в некоторое более "простое" подмножество и проводится центрированное сечение последнего.

Так в методе эллипсоидов исходное множество X или часть его, заведомо содержащая ж*, погружается в некоторый эллипсоид, обычно в шар. При решении практических задач это нетрудно сделать, поскольку, как правило, известны "разумные" границы изменения переменных. Проводится центрированное сечение эллипсоида и та часть его, которая заведомо содержит х*у погружается в новый эллипсоид возможно меньшего объема. Проводится центрированное сечеипс нового эллипсоида, и так далее, пока не будет получен эллипсоид достаточно малого объема. Центр его и выбирается 15 качестве х*.

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

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

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

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

Заключение

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

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

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

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

1. Васильев Ф.П. Численные методы решения экстремальных задач.- М., 1980.

2. Величко А.С., Нурминскип Е.А. Прямо-двойственная декомпозиция задачи о репликации портфеля рыночных активов. Автоматика и телемеханика, 2003, No. 12.

3. Гловипски Р., Лионе Ж.-Л., Тремольср Р. Численное исследование вариационных неравенств.'-М.: Мир, 1979.

4. Гольштейп Е.Г., Третьяков Н.В. Модифицированные функции Лагран-жа п их применение. Экономика и математические методы, 1983, т. 19, No. 3, с. 528 -547.

5. Еремин И.Я., Мазуров В.Д., Астафьев Н.Н. Несобственные задачи линейного и выпуклого программирования.-М.: Наука, 1983.

6. Иоффе А.Д., Левин В.Л. Субдифференциалы выпуклых функций. Труды ММО, 1972, т. 2G, с. 3-73.

7. Иоффо Л.Д., Тихомиров В.М. Теория экстремальных задач.-М.: Наука, 1974.1G. Каи К).С. Оптимизация управления по кваптпльпому критерию. Автоматика и телемеханика, 2001, No.5, с.77 88.

8. Кибзуи А.И., Кузнецов Е.А. Оптимальное управление портфелем ценных бумаг. Автоматика и телемехапнка, 2001, No.9, с.101- 113.

9. Кутиков J1.M. Декомпозиция-блочных задач линейного программирования с слабо связанными блоками, ЭММ, т. XVI, No. G, 1980.

10. Левин Г.М., Тапасв B.C. Декомпозиционные методы оптимизации проектных решений. Минск, 1978.

11. Лэсдоп Л.С. Оптимизация больших систем.-М.: Мир, 1975.

12. Немировский А.С., Юдин Д.Б. Сложность и эффективность методов оптпмизацни.-М.: Наука, 1979

13. Норрп Д., де Фриз Ж. Введение в метод конечных элемсптов.-М.: Мир, 1981.25| НурмппскпП Е.А. Численные методы выпуклой оптимизации.-М.: Наука. 1991.

14. Пшеничный Б.Н. Выпуклый аиализ и экстремальные задачи.-М.: Наука, 1980.

15. Рокафеллар Р.Т. Выпуклый анализ,-М.: Мир, 1973.

16. Сергиоико И.В. Математические модели и методы решения задач дискретной оптимизации. Киев, 1985.

17. Тапаев B.C. Декомпозиция и агрегирование в задачах математического программирования. Ми.: Наука и техника, 1987.

18. Телле Н. Применение модифицированной функции Лаграижа в блочном программировании. Экономика и математические методы, 1975, т. 11. No. 3, с. 525 534.

19. Тенев Т.П. Декомпозиция задач линейного раскроя. Известия АН СССР, Техн. кибернетика, 1978, No. 5, с. 56-G1.

20. Хачиян Л.Г. Сложность задач линейного ирограммпровапия.-М.: Знание, 1987, No. 10.

21. Цурков В.И. Декомпозиция в задачах большой размерности.-М.: Наука, 1981.

22. Шор Н.Э. Методы минимизации недиффсрспцирусмых функций и их .приложения. Киев: Наукова, Думка, 1979.

23. Dantzig G.B., Wolfe P. Decomposition principle for linear programs. Operations Research, 19G0, vol. 8, pp. 101-111.

24. Dantzig G.B. Wolfe P. The decomposition algorithm for linear programming. Econometrica, 1961, vol. 29, No. 4, pp. 7G7-778.

25. Dcnibo R.S., Rosen D. The practice of portfolio replication: a practical oveiview of forward and inverse problem. Annals of Operations R.esearch, 1999, No.85, pp. 267-284.

26. Fragniere E., Gondzio J., Vial J.-P. Building and solving large-scale stochastic programs on an affordable distributed computing system. Annals of Operations Research, 2000, vol. 99, No. 1/4, pp. 167-187.

27. Geoffrion A.M. Generalized Benders decomposition. Journal of Optimization Theory and its Applications, 1972, vol. 10, No. 4, pp. 237 260.

28. Gcoffiion A.M. Lagrangean relaxation for integer programming. Mathematical Programming Study, 1974, No. 2, pp. 82-114.

29. Goffin J.-L., Hauric A., Vial J.-P. Decomposition and nondifferentiable optimization with the projective algorithm. Management Science, 1992, vol. 38, pp. 284-302.

30. Goffin J.-L., Haurie A., Vial J.-P., Zhu D.L. Using Central Prices in the Decomposition of Linear Programs. European Journal of Operational Research, 1993, vol. 64, pp. 393-409.

31. Golstein E. On a dual block linear programming technique. Automation and Remote Control, 1994, vol. 55, No. 12, pp. 1733-1739.

32. Gondzio J., Grothey A. Re-optimization with the primal-dual interior point method. Tech. Report MS-01-004, Department of Mathematics and Statistics, The University of Edinburgh, 2002. To appear in SIAM Journal on Optimization.

33. Gondzio J., Komvenbcrg R. High performance computing for asset liability management. Operations Research, 2001, vol. 49, No. 6, pp. 879-891.

34. Gondzio J., Sarkissian R. Parallel interior point solver for structured linear programs. Tech. Report MS-00-025. Department of Mathematics• and Statistics, The University of Edinburgh, 2000, revised 2002.

35. Gondzio Л. Warm start of the primal-dual method applied in the cutting plane scheme. Logilab/HEC, Tech. Report 96.3, 1997, also Mathematical Programming 1998, vol. 83, No. 1, pp. 125-143.

36. G2. Grigoriadis Ы., Khacliiyan L. Coordination complexity of parallel priccdireetive decomposition. Department of computer science, Tech. report94.19, Rutgers University, USA, 1994.

37. Himmclblau D.M. Decomposition of large-scale problems.- Amsterdam: • North-Holland, 1973.

38. G4. Hughes D., Nurminski E., Royston G. Use of nondifferentiable optimization in a health care problem. Behavioral Science 25 (5), 1980.

39. G5. Larsson Т., Patriksson M., Stromberg A.-B. Ergodic, primal convergence in dual subgradicnt schemes for convex programming, Mathematical Piogramming, vol. 86, 1999, pp. 283-312.

40. Markowitz H.M. Portfolio-Selection // J. Finances. 1952. No.7(1). pp. 7791.

41. Mandel ,J. Balancing domain decomposition, 1992. http://www.mgnct.org/mgnct/papers/Mandel/bdd.ps.gz

42. Medlii D. Bundle-based decomposition for large scale convex optimization: error estimate and applications to block-angular linear programs. Mathematical Programming, 1994, vol. 66, pp. 79-101.

43. Mehrotra S. Volumetric center method for stochastic convex programs using sampling. IE/MS Tech. Report, Department of industrial engineering and management science. Northwest University, USA, 1999.

44. Pinar A., Catlyiirck U., Aykanat C., Pinar M. Decomposing linear programs for parallel solution. Industrial engineering department, Bilkcnt University, Turkey, 1996.

45. Rockafcllar R.T., Uryascv S. Conditional value-at-risk for general loss distributions // Journal of Banking & Finance. 2002. No.26. P.1443 1471.

46. Rockafellar R.T., Uryascv S. Optimization of conditional value-at-risk // Journal of Risk. 2000. No.2. P.21 41.

47. Schultz G. Barrier decomposition for the parallel optimization of block-angular programs, University of Wisconsin-Madison, PhD thesis, 1991.

48. Sliao J.-P. Domain decomposition algorithms, University of California, Los Angeles, PhD thesis, 1993. http://www.mgnet.org/mgnet/papers/Shao/jpshaol.ps.gz

49. Soewandi H. Column generation and decomposition for linear programming: a review, http://www.ie.ncsu.edu/fangroup/ps.dir/colgen.ps

50. Tind J. Decomposition principle of linear programming. University of Copenhagen, Denmark, 1998.

51. Tomlin J.A. Large scale mathematical programming systems. Comput. and Chem. Eng., 1983, vol. 7, No. 5, pp. 575-582.

52. Wismer D.A. (editor) Optimization methods for large-scale systems with application-New York: McGraw-Hill, 1972.

53. Yildirim E., Wright S. Warm start strategies in interior-point methods for linear programming. Advanced Scientific Computer Research, US Department of Energy.

54. Zakeri G. Multicoordination methods for parallel solution of block-angular programs, University of Wisconsin-Madison, PhD thesis, 1995.

55. Zakeri G., Philpott A., Ryan D. Inexact cuts in Benders' decomposition. Department of engineering science, University of Auckland, New Zealand, 1997.