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

? « 2 ^ ^ РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

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

АЛЕКСЕЕВ Александр Валентинович

ЭФФЕКТИВНЫЕ МЕТОДЫ .ОПТИМИЗАЦИИ ДЛЯ РЕШЕНИЯ ЗАДАЧ ВЫПУКЛОГО ПРОГРАММИРОВАНИЯ С БЛОЧНО-МОДУЛЬНОЙ СТРУКТУРОЙ

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

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

Москва 1993

Работа выполнена в Вычислительном центре Российской - академии наук.

Научный руководитель - доктор физико-математических наук

В.И.Цурков

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

B.И.Ёлкин

кандидат физико-математических наук

C.К.Завриев

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

Зшцита состоится "/" СС^^ЛЯ 199.3г. в_£_" часов на заседании специализированного совета Д 002.32.06 .при Вычислительном центре РАН по адресу: Москва, ул. Вавилова, д.40.

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

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

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

О.Шар

С.М.Швартин

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

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

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

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

Цель работы:

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

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

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

Научная новизна:

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

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

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

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

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

Апробация. Основные положения диссертации рассматривались и обсуждались на семинарах Всесоюзного научно-исследовательского института прикладных автоматизированных систем ГКНТ и АН СССР, на Московской городской конференции "Системы автоматизированного проектирования (САПР-85)", на 5-й Республиканской межведомственной научно-технической конференции "Моделирование и ато-матизация процесов проектирования сложных технических систем", Одесса, 198?, на 14-й конференции IFIP по моделированию систем и оптимизации, Лейпциг (ГДР), 1989, а также на 6-м Международном симпозиуме "Системы - Моделирование - Управление", Закопане (Польша), 1990.

Публикации. По теме диссертации опубликовано семь работ.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы составляет 119 страниц, включая 4 страницы списка цитированной литературы, содержащего 3? наименований.

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

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

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

f(x) - min (1.1)

hj(x) < dj , j=l,..,M

xeB,

где f(x), 1^(х), j=l.....M, - непрерывные, выпуклые функции.

Предполагается, что допустимое множество задачи В с R" имеет непустую внутренность и представляет собой некоторое подмножество декартова произведения N блоков, В = В^.^ХВ*, каждый из которых представляет собой непустой выпуклый ком^ пакт в пространстве размерности n,, i=l,..'.,N и задается системой ограничений В' = { xeR"1 | G,(x')<0}. Соответственно рассматривается разбиение вектора переменных ' х на N частей х = {х1,... ,х"}, где х'е В1 с R"'t n,+.. .+п„=п. Повязывающие ограничения на блоках задаются функциями hj(x), j=l,...,M. Предполагается, что целевая функция, а также ограничения hj(x) являются сепарируемыми, т.е. представимы в следующем виде

f(x) = f'(x) f"(x"),

h,(x) = h/ix1) +...+ h/(x"), j=l.....M.

x'eB', i=l.....N.

Задача (1.1) сводится к задаче следующего вида

d(x) min ' ■ (1.2)

hjixJ/dj < d(x), j=l,...„M xeB. •

где d(x) = max {h,(x)/d,.....ha(x)/da}. -

Эта задача, в соответствии с принципиальной схемой декомпозиции Корнаи-Липтака, заменяется на двойственную

<р(р) = à <р,(р) -+ max (1.3)

1 il-', p +...+P ,= 1

p' > 0, i-1.....M,

где v>i(p) Представляют собой оптимальные при данном р значения целевых функций задач

L,(;х*,р.) = £ pV(xl)/d,- min (1.4)

1 i-> х eß .

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

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

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

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

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

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

Методы потенциальных функций имеют общую схему, которую по аналогии с методом покоординатного спуска.можно назвать схемой поблочного спуска. Задача (1.2) заменяется на задачу минимими-зации некоторой потенциальной функции V(x), такой что min{V(x), хеВ) = min { d(x), хеВ). На каждом шаге метода обеспечивается уменьшение абсолютной погрешности достижения минимума потенциальной функции в некоторое фиксированное число раз.

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

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

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

Определение. Пусть А 6 R" - выпуклый компакт. Назовем дистанцией от А до произвольного компактного выпуклого множества В следующую величину:

АДВ) = min min { k: k>0, В с a+kA}.

вея" k

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

Утверждение. Пусть при работе некоторого метода отсечений на итерации s имеется текущий локализатор области нахождения решения Loc'cP и текущее приближение к решению х5". Тогда достигнутая относительная погрешность не превосходит обратной величины дистанции от Loe5 до исходного допустимого множества Р,

е(хГ) < 1/ ALocS(P).

Предлагается связанная с дистанцией А»(В) псевдометрика р(А.В) = 1п( А4(В) А„(А))

и изучаются ее свойства.

В параграфе 2.2 рассматриваются свойства выпуклых тел и их размеров, в частности, объема д.(А) максимального вписанного в тело А эллипсоида.

Эллипсоид Е задается его центром у„е R" и вещественной симметрической положительно определенной (пХ п)-матрицей Q так, что Е = {ye R" | y=y„+Qw, |w||<l}.

Утверждение. Дистанция р(А,Е*) между произвольным выпуклым n-мерным телом А и максимальным вписанным в него эллипсоидом Е* не превосходит величины In п

р(А.Е') < In п.

Заметим, что данная оценка не зависит от вида эллипсоида, а зависит только от размёрности п.

Определение. Вписанный в выпуклое тело А эллипсоид Е, называется i-максимальным для А, если vol Ет > -у цЛк).

Лемма. Пусть Е, - 7-максимальный эллипсоид (7 > 0.5), вписанный в выпуклый компакт А с R". Тогда для расстояния р(А,Е7) между Е, и А справедлива следующая оценка

, ч (1+720^7))

р(А,Е1) < 1п п -.

27-1

Теорема. Для 7-максимального эллипсоида Е, (7 > 0.5), вписанного в выпуклый компакт А справедливо следующее включение

1+27 2(1-7)

Е, с А с п - Е,.

27 - 1

Замечание. При 7 > 0.985 полученная в теореме константа лучше ранее известной константы п(1+зУ(1-7)

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

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

На б-й итерации алгоритма (б>2) в качестве точки отсечения берется центр максимального по метрике В5_, шара, вписанного в локализатор Ьос5. На первом шаге при этом используется стандартная евклидова метрика.

Задача нахождения максимального шара В5", вписанного в выпуклый многогранник Ьос8 сводится к следующей задаче линейного программирования:

г -» шах

C|As.,x5 + rjc,!,,^ < di, i-l,...,n+s.

Здесь xs - центр шара, г - его радиус, A,.i - матрица эллипсоида Bs.,= {xeR° I х = xs + As.,z, ¡z|| < 1 }.

В результате решения этой задачи находится точка х/ и определяется локализатор Locs' = Locs n {х е R°| p(x-xs') > 0}, где р - вектор отсечения в точке х/. Обозначим через rs радиус вписанного в Locs в метрике Bs.¡ шара, а через г/ радиус шара В/ , вписанного в Locs' в той же метрике. Проверяется неравенство

г.' > (1 - 1/6(п+1))г. (2.1)

Если оно не выполнено, то выполняется шаг вида 1: в- качестве

Locs,] рассматривается Locs', а в качестве В5.* берется В,' и осуществляется переход к следующей итерации. Текущая метрика с точностью до растяжения не изменяется.

Если неравенство (2.1) выполнено, то производится шаг вида 2: находится максимальный вписанный в Locs шар в метрике Bs -эллипсоида максимального объема, вписанного в выпуклую оболочку в; и В/.

Шаги вида 2 повторяются до тех пор, пока выполняется, неравенство (2.1), затем выполняется шаг вида 1 и осуществляется переход к следующей итерации. Метод основывается на следующем геометрическом предложении.

Теорема. Пусть s-й итерации выполняется неравенство (2.1). Тогда существует эллипсоид Bsc Locs, объем которого не менее чем на 25% превосходит объем В*

vol Bs > 1.25 vol Bs".

'Получена теоретическая оценка числа итераций, необходимых методу для достижения относительной точности е:

S(e) < С п log2(l/e).

Однако при сравнении с методом вписанных эллипсоидов на ряде тестовых примеров выяснилось, что метод вписанных шаров проиг-

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

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

В параграфе 3.1 формулируется вспомогательная задача и излагаются свойства потенциальной функции, позволяющие находить с ее помощью решение исходной задачи. Для решения задачи (1.2) используется следующая потенциальная функция

» hj(x)

Vt(x) = In 2 exp -,

j.i t

где t > 0 - малый положительный параметр.

Пусть задана некоторая абсолютная погрешность сг>0 решения задачи (1.2) и пусть для некоторой произвольной положительной константы 6 получено приближенное решение х' задачи

Vt(x) -*■ min х е В,

где t = cr/(S + ln M), с абсолютной погрешностью <5. Тогда х' является решением задачи (1.2) с абсолютной погрешностью а. Рассмотрим разность потенциалов в двух точках х и у

д fhj(x) - Myï) V,(x) - Vt(y) = ln ¿ Pj exp --^— ,

где

exp(hj(x)/t) 1

Pj = p,(x,t) = -,--. j= 1.....M. (3.1)

2 exp(h¡(x)/t) i-i

Составленный таким образом вектор peP={p|¿ р} = 1, Pj>0, j=l,...,M} обладает следующим свойством. J1

Утверждение. Для произвольной точки хеВ выпуклая комбинация значений Мх),... ,Ьи(х) с весами (3.1) отличается от значения функции d(x) в этой точке не более чем на величину t ln M, где 0<t<l.

d(x) - i pj hj(x) < t ln M.

Параграф 3.2 посвящен изложению алгоритма решения координирующей задачи, который для заданной абсолютной погрешности ае(0,1/3] находит точку х: d(x) < d" + <т при условии, что известна некоторая точка ХобВ, такая что d(x0) < 1. Доказывается корректность алгоритма. Приводится оценка

числа итераций, необходимых для получения решения задачи (1.2) с абсолютной погрешностью <т.

В параграфе 3.3 описывается алгоритм, который позволяет находить решение задачи (1.2) с относительной погрешностью е>0. Данный алгоритм на каждом шаге решает вспомогательную задачу, используя описанный в предыдущем параграфе алгоритм.

Описывается предварительная процедура нахождения необходимой для работы алгоритма допустимой точки Хо: d(x0) < 1.

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

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

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

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

Пусть х = (xi,...,x„) - набор конструктивных параметров проектируемой системы. Характеристики и - (и,,... ,и„) описывают поведение системы в целом и составляющих ее модулей и блоков. Предполагается, что вектор конструктивных параметров однозначно определяет поведение объекта, т.е. существует функция f: R" R" такая, что Ui - f,(x), i=l,...,N.

Пусть F(x) - показатель качества проектируемой системы.

S(e) = 0(N (In M) (e"2 + In N)).

Для задач проектирования характерен случай F(x) = ip(u(x)), где функция <р(и) определена на множестве' UcR" всех возможных характеристик системы.

Задача оптимального проектирования системы формально может быть записана в виде задачи оптимизации

max {p(u)| u=f(x), ueU, xe£), (4.1)

x

где í с R' - множество технически реализуемых конструктивных параметров системы.

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

Обозначим через G(x)={g,(x) ..... g»(x)} m-мерную вектор-функцию, задающую ограничения как на физические связи между конструктивными параметрами хеХ, так и на характеристики проектируемой системы usU. Тогда задачу (4.1) формально можно переписать в следующем виде: ,

F(x) max (4.2)

' G(x) <0.

Будем считать, что для задачи оптимального проектирования выполняются следующие условия монотонности:

V х',х" б Х- { х| G(x) <0 }, из U(x') > fs(x"), i=l.....N,

следует, что F(x')> F(x"). Это условие означает, что если один из вариантов проектируемой системы не хуже другого по всем частным характеристикам f,, ■ i=l,... ,N, то значение показателя качества F(x)' на этом варианте системы также будет не меньше.

Пусть система в целом состоит из N подсистем и каждый из проектировщиков подсистем имеет в качестве целевой функции одну из характеристик системы f,(x). Далее будем предполагать, что множество компонент вектора х можно разбить на непустые подмножества х1, i=l,...,N и v. Здесь х1 - множество параметров, которыми распоряжается только проектировщик i-й подсистемы, а V - множество конструктивных параметров, с которыми имеют

ю

дело двое или более проектировщиков подсистем. Тогда вектор х={х,,... ,хп} представим виде х={х\..., x",v), где

x'n xJ=0 i^j, x'nv =0, i=l,... ,N,

x'e Rn", ve Rn\ Sn,+n,=n, i-i

и при этом f,(x) = f, (x',v), а система ограничений задачи (4.2) распадается на системы ограничений подзадач

G(x) = { G1 (х1,v)..... G"(x",v),H(v)},

где G'(x',v)= {g,' (x',v)..... gi,', (x',v)),

H( v)= (h,(v).....h„( v)},

»

Em, + M = m.

i-i

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

В параграфе 4.2 для декомпозиции задачи (4.2) определение подмножеств х', i=l,...,N и v на основе анализа графа задачи. Формулируется следующая

Задача оптимальной декомпозиции. Пусть дан связный, неориентированный граф r=(Q,E), в котором имеется N подграфов

Г, = (Q,,E,), i=l.....N, для которых Q, nQj=0, Требуется

найти такое подмножество vCQ минимальной размерности, после удаления которого граф Г распадается на N,компонент связности

7,= (х',Е,'), где x,nQ, ф 0, x,nQj= 0, i,j,=l.....N, i^j.

При N=2 задача решается при помощи построения минимального разреза. В случае N>2 доказыается NP-трудность задачи. Предлагаются приближенные алгоритмы ее решения. Первый из ' них основан на последовательном разделении графа на две части. Второй основан на решении известной задачи об атаке

S(А-) - b k(А) min ACE

k(A)>0,

где k(A) - число компонент связности, на которое распадается граф Г' после удаления подмножества ребер А, S(A) - суммарный

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

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

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

Б < 5.89 N 1п(1/с).

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

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

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

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

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

По теме диссертации опубликованы следующие работы:

1. Алексеев A.B. Приближенный алгоритм декомпозиции в задачах оптимального проектирования // Проблемы теориии и практики построения САПР. - М.:ВНИИПАС, 1988. - Вып.4. - С.18-22.

2. Алексеев A.B. Метод вписанных шаров с изменяемой -метрикой // Интеллектуальная обработка данных в программных системах телеинформатики. - М.:ВНИИПАС, 1989. - Вып.2. - С.3-5.

3. Алексеев A.B. О вычислительной сложности процедуры принятия решений, основанной на методе вписанных эллипсоидов // Программное, алгоритмическое и методологическое обеспечение систем интеллектуальной обработки информации.- М.: ВНИИПАС, 1990. - Вып.5. - С.24-31.

4. Алексеев A.B., Хачиян Л.Г., Эрлих И.И. Метод вписанных эллипсоидов в многокритериальных задачах выбора // Методы и алгоритмы управления, информационными и вычислительными процессами в автоматизированных системах. - М. : ВНИИПАС, 1987. Вып.5. - С.58-66.

5. Алексеев A.B., Эрлих И.И. Декомпозиция модельного описания задачи оптимального проектирования // Автоматизация проектирования и научных исследований.- М. : ВНИИПАС, 1986. Вып.1. -С.3-9.

6. Алексеев A.B., Эрлих И.И. Оптимальная декомпозиция и координация в задачах коллективного проектирования // Proc. of the 6th International Symposium on System-Modelling-Control. -1990. - T.l - c.3-8.

7. Alekseyev A.V., Erlikh I.I. and Khachiyan L.G. An interactive procedure based on the inscribed ellipsoid method. In: System modelling and optimization, Proc. 14th IFIP Conference. -Springer-Verlag. - 1990. - p.67-72.

Подписано в печать Формат 60x90 1/16 Уч.-изд. л. 1

Тираж 100 экз. Усл. печ. л. 1 Бум. офс.

Институт автоматизированных систем 103009, Москва, ул. Неждановой, 2а, ?ИО, тел. 132-70-00

Ап "Шанс", 127412, Москва, ул. Ижорская, Д. 13/19