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

0

1

ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ ПО ВЫСШЕМУ ОБРАЗОВАНИЮ ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ОД

. , -:1 , На правах рукописи

АПЕКИНА Елена Викторовна

НОВЫЕ ВЕРСИИ МЕТОДА СИМПЛЕКСНЫХ ПОГРУЖЕНИЙ В ВЫПУКЛОМ ПРОГРАММИРОВАНИИ И ИХ ПРИЛОЖЕНИЯ

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

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

Иркутск -1995

Работа выполнена в лаборатории "Исследования операций' Сибирского энергетического института СО РАН.

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

академик РАЕН Булатов В.П.

Официальные оппоненты: доктор физ.-маг. наук,

профессор Астафьев H.H.

кандидат физ.-мат. наук, доцент Беликов А.И.

Ведущая организация: Институт математики СО РАН

Зашита состоится " 2 2 - ЩМ^ьЯб^ 1995 г. в 4.0 ~ часов на заседании диссертационного совета Л 063.32.04 по присуждению ученой степени доктора физико-математических наук в Иркутском государственном университете (664003, бульвар Гагарина 20,1-й корпус ИГУ).

С диссертацией можно ознакомиться в Научной библиотеке Иркутского государственного университета (бульвар Гагарина, 24).

Автореферат разослан " 2d " (Упл^Ь 1995 года.

Ученый секретарь спец. совета,

к.ф.-м.н., доцент '^t^y Н.Б. Бельтюков

Общая характеристика работы

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

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

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

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

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

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

Данная работа относится ко второму направлению.

Цель работы. Развитие и модифицирование метода и алгоритма симплексных погружений, который является современным эффективным методом для решения задач выпуклого программирования, идейно близким к широко известным методам Л.Г. Хачияна, Н.Кармаркара и другим полиномиальным на классе задач линейного программирования методам. Получение оценок сокращения объема (скорости сходимости) метода при его модификациях. Тестирование "базового" и "модифицированного" алгоритмов.

Методы исследования. Для обоснования и доказательств основных

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

Научная новизна и практическая ценность результатов.

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

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

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

4. Проведенное тестирование метода показало, что рассмотренные в работе новые версии позволяют ускорить работу базового алгоритма в среднем в 1.4 раза.

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

Апробация работы. Результаты работы докладывались на конференциях "Методы математического программирования и их приложения" (Екатеринбург, 1991, 1995), на международной конференции по исследованию операций (Берлин, 1994), на конференциях молодых ученых СЭИ СО РАН (Иркутск, 1991, 1994) на научных семинарах СЭИ СО РАН.

Структура работы. Диссертация состоит из введения, трех глав, заключения, списка литературы, содержащего 35 наименований. Она содержит 8 рисунков, 9 таблиц. Работа изложена на 74 страницах машинописного текста.

Содержание работы.

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

вании.

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

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

Авторы метода Е.Г.Анциферов, В.П. Булатов.

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

/о(г) min (1)

при ограничениях

fi{x)<0, » = 1,2,..., m, (2)

где х € Еп, fi(x), i = ö,m - выпуклые функции.

Идея метода симплексных погружений состоит в следующем.

Пусть имеется начальный симплекс 5° и х* G 5° - одно из решений задачи (1),(2). Находим центр симплекса точку г^0 и строим плоскость, проходящую через х°и определяем отсекающую неперспективную часть симплекса S0 полупространство. Часть симплекса (усеченный симплекс), содержащую точку х*, погружаем в новый симплекс S1 и повторяем процедуру. Так, последовательно локализуем искомое решение до тех пор, пока объем симплекса, полученного на данной итерации не станет достаточно малым.

Центральным моментом алгоритма является построение симплекса минимального объема, который содержит усеченный симплекс.

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

Обозначим: <р - минимальное найденное до начала 1-й итерации значение функции /о(я); - длина интервала неопределенности, содержащего минимальное значение /ц минимизируемой функции; i - номер итерации; матрица X размеров (rt + 1) * п, строка » которой соответствует i - й вершине симплекса 5°.

Инициализация. При I = 0 полагаем V = 1; (pi = <5| = +оо.

Итерация 1(1 >0).

Шаг 1, Найти центр симплекса S1 по формуле хе = ^-(г1 + ... + zÄ), где х\ » = 1, ...,п, есть »-я строка матрицы X.

Шаг 2. Вычислить значение максимальной невязки ограничений

Л, = т^О,/;(*<)} = /.(*')•

Шаг 3. Вычислить значение минимизируемой функции /0(х) в точке хе: fc = /о(ес); положить yi+i = min{<pi,fc}.

Шаг 4. Найти нормаль отсекающей плоскости по формуле

. = / 3/о(*с), h, = О 1 hi > О,

где dfi - субградиент выпуклой функции fi(x).

Шаг 5. Найти величины а,- = аг(ж' - хс), i = 1,2, ...,п+1, определить индекс р из условия

а„ - min а,,

1<|<Я+1

величины ßi = —i = l,2,...,n + 1, и целое число к, равное числу сохраняемых вершин симплекса S1.

Шаг 6. Найти параметр t € [0,1]. Для этого достаточно решить задачу одномерной выпуклой минимизации.

д'(а) = min{ П (1 + а.*)-1 : 0 < t < -—} i=t "о

Шаг 7. Найти вектор коэффициентов растяжения

т — (г1,..мТр_Ь7>+1,...)гГ1) ребер симплекса S, исходящих из опорной

вершины xv по формуле:

Ti = (l + ßit)~1.

П1аг 8. Перейти от симплекса S1 с матрицей X1 к симплексу Sl+1 с матрицей X,+1

v'+i = \ ХЬ + <xh - » = 1.» + 1,

ij 14.

Шаг 9. Пересчитать объем симплекса, содержащего решение, по формуле V/+1 = Viq*.

Шаг 10. Пересчитать длину интервала неопределенности по формуле

S = - И.Т = (V)*,/= тах/о(х).

Шаг 11. Если длина интервала неопределенности S < е, где е - величина, задающая точность вычислений, то алгоритм заканчивает работу. В противном случае следует перейти к шагу 1, заменив I на. 1 + 1.

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

V(sl) Г ¿/ = 1 т

Vis1-') - \ 2 < к, < n, W

где V(Sl) - объем симплекса на итерации i, a fc - число сохраненных при отсечении вершин симплекса S1'1.

Далее приводится сравнение по скорости сходимости метода эллипсоидов и средней скорости сходимости метода симплексных погружений

где с - константа и с = 0.788791.

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

Раздел 2.3 посвящен результатам тестовых экспериментов, прове-

денных по базовому алгоритму симплексных погружений.

Метод симплексных погружений реализован на персональных компьютерах типа IBM 486 DX4 - 66 Mh на языке Turbo - Pascal.

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

Глубокие отсечения строились следующим образом.

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

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

С помощью реализованного алгоритма проводилось множество тестовых и практических расчетов.

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

Яц+i -+ min (4)

при ограничениях

/о(») - хп+1 < 0 (5)

/,(*)< О, ¿ = Ä (6)

то есть переходить в расширенное пространство £n+1.

Так, при решении тестового примера с функцией Шора в виде (1),(2) потребовалось 123 итерации метода симплексных погружений, а в виде (4)-(6) - 90 итераций. Были проведены и другие расчеты.

Методом симплексных погружений решалась также задача линейного программирования:

/о(г) = я» тах

при ограничениях

0 < xi < 1

ex,_i < Xi < 1 - exi-1, i = 2,n, 0 < e < 0.5.

Как указано в монографии Б.Т. Поляка "Введение в оптимизацию" при решении данной задачи одним из вариантов симплекс-метода для п = 15 число шагов оказалось равным 21402 (то есть требовался перебор значительной части вершин допустимого многогранника); итерационным методом, основанном на модифицированной функции Лагран-жа, потребовалось 556 итераций; методом симплексных погружений -

28 итераций.

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

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

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

G(x)=±(g] + RTln{P:^))xj> (7)

при ограничениях

П IV

Y,aijxj = (8)

3=1 1 = 1

х > О,

где п - количество газов, образующих термодинамическую систему, g°j- стандартные химические потенциалы этих газов, R - универсальная газовая постоянная, Т,Р- соответственно постоянные температура и давление, а(х) = xi + ... + хп, х = (х\,...,хп)т Е Еп - искомый неотрицательный вектор (состояние равновесия), у = (yi, ...,у»)г G Еп -заданный неотрицательный вектор (начальное состояние).

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

Для этой цели дополнительно к (8) задается граф химических реакций с одним узлом-входом, соответствующим начальному состоянию у и с одним узлом-выходом, соответствующим конечному состоянию х. Реакции на ветвях графа должны удовлетворять стехиометрическому соотношению, отражающему равенство количеств атомов каждого вида в левой и правой части каждой из реакций. Если каждой из реакций сопоставить два вектора: L G Е* - вектор веществ, поступивших в реакцию; R£En- вектор веществ, получившихся в результате реакции; то стехиометрическое соотношение можно записать в виде:

AL = AR,

где А = {ау} - матрица веществ, а;;- - количество »- атомов в единице j - вещества.

Далее вводятся неотрицательные переменные Т| - называемые условными потоками вещества по дугам графа. Они отражают интенсивности той или иной реалдии и являются искомыми в данной модели.

Для определения т; формулируется задача выпуклого программирования:

G{x) —+ min,

при условиях

£ TjiRji = £ TijLij, » = 2,...,Л-1 (9)

£ тиЬи=у (10)

3 6Л(1)

£ TjnRjn = г, (11)

1ШЮ

где N - число узлов в цепи, /д(») - множество номеров дуг, входящих в узел t, Ji(t') - множество номеров дуг, выходящих из узла j. Условие (9) - условие баланса масс веществ во всех промежуточных узлах, условия (10),(11) - условия балансов масс веществ в узлах 1 и N соответственно.

После подстановки вместо х его выражения (И) через т в G(x) получим задачу:

F{t) = G(X(r)) min, (12)

при условиях (9),(10) и т > 0.

Для того, чтобы применить метод симплексных погружений необходимо записать систему линейных ограничений задачи (12) в виде неравенств. Для этого с помощью алгоритма Жордана систему условий (9),(10) приводим к виду:

Ti = £ Dijtk + diy i = 1,..., M, (13)

j=i

где M - число дуг графа, К - число независимых переменных, tk - те из переменных г, которые оказались в результате жордановых исключений независимыми, Д-j, - постоянные.

Таким образом, задача трансформируется к требуемому виду:

f(t) = F(r(t)) min,

при условиях

вг + <1>о, * >о.

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

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

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

В разделе 3.1 описывается общая идея модификаций и приводятся некоторые типичные случаи.

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

1) центр симплекса является допустимой точкой;

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

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

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

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

Будем рассматривать секущие плоскости вида

тп л*.

Ег = 1,» = 1,...,т,Л£>0. (14)

¿-1 «>

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

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

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

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

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

У(5'-1) п +1 ~е (15)

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

В базовом методе эта оценка выражалась формулой

_ ( " у>Г " у»-1 ~ 1

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

Поэтому в разделе 3.2 рассмотрена некоторая "компромиссная" идея по реализации рассмотренной модификации.

Пусть на к - й итерации метода симплексных погружений центр симплекса является недопустимой точкой, то есть в нем нарушаются / < тп ограничений задачи. Построим I отсекающих плоскостей, соответствующих нарушаемых ограничениям, и проходящих через центр текущего симплекса. Далее попробуем заменить совокупность плоскостей одной секущей плоскостью. При этом желательно, чтобы определяемое ею полупространство отсекало то же самое число вершин симплекса, что и вся совокупность полупространств. Если удается построить такую плоскость, то можно для реализации алгоритма воспользоваться известным (раздел 2.1) способом построения симплекса минимального объема, содержащего усеченный симплекс. Эта задача может быть решена различными способами, рассмотрим один из них.

Пусть а1, г = ТТ7 нормали отсекающих плоскостей и Л1,...,Лг - вершины, которые ими отсекаются. Будем искать нормаль Ь результирующей плоскости в виде линейной комбинации нормалей о':

6= ¿А,-а' (17)

»"=1

Если существует вектор X = (Х7,..., X/), который является решением системы

1=1

¿А,=1, (18)

¿=1

А,- > О,

где хс - центр текущего симплекса, то отсекающее полупространство

ЬТ(х-хе)< 0, 6= ¿V (19)

1=1

отсекает то же число вершин, что и совокупность полупространств.

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

min тах£АКа'№'-хс),

£А; = 1, (20)

i=i

Аi > 0.

Геометрически, эта задача означает среднее отклонение от отсеченных вершин. Прежде, чем прийти к постановке (20), рассматривались 8 аналогичных задач вида minmin, тахтах, minmax, maxmin относительно отсеченных вершин и те же задачи относительно неотсеченных вершин. Несложный анализ показал, что задача в постановке (20) приближает нас к желаемому результату.

Задача (20) является задачей выпуклого программирования с кусочно-линейной целевой функцией. Если учесть ее специфику: число линейных кусков у целевой функции равно числу отсеченных вершин г. Как показывают практические расчеты г » , где |aj - нал большее целое не превосходящее а. Для решения задачи (20) можно воспользоваться, например, методом опорных плоскостей. Этим методом вспомогательная задача (20) решалась в среднем за 5-7 итераций

Опишем итерационно-вычислительную схему "модифицированного'' метода симплексных погружений.

Как и в базовом методе, при к = 0 полагаем V = 1, tpk = ök = -foo.

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

Шаг 1. Найти центр симплекса

Шаг 2. Проверить, является ли центр х% допустимым, то есть выполняется ли условие /¡(х£) < 0, для всех t = l,m.

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

Шаг 4. Выбрать / ограничений задачи, для которых /,(г£) > 0. Найти нормали а', £ = 177, отсекающих плоскостей по формуле

а1 = dflxck), i = \77,

где - субградиент выпуклой функции /;(з).

Шаг 5. Проверить, какие из вершин симплекса 5* отсекаются совокупностью невязок, то есть для которых выполняется неравенство

Шаг 6. Для поиска нормали результирующей плоскости Ь в виде (17) сформировать специальную минимаксную задачу вида (20).

Шаг 7. Для решения задачи (20) использовать метод опорных плоскостей.

Шаг 8. Найденный с помощью метода опорных плоскостей вектор X = (17, А/) подставить в (17) и определить

«=1

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

Шаг 9. Выполнить шаги 5-11 базового алгоритма симплексных погружений.

В разделе 3.3 приводятся результаты численных экспериментов.

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

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

Модифицированный алгоритм симплексных погружений дает следующие преимущества по сравнению с базовым: количество итераций уменьшается в среднем в 1.4 раза и величина сокращения объема улучшается приблизительно на 0.035. Все расчеты выполнены с точностью 10"®.

В разделе 3.1 была доказана теорема об оценке сокращения объема в виде (15), которая стремилась к 1/е с ростом размерности пространства п. Оценка сокращения объема зависит как от числа отсеченных вершин совокупностью полупространств, так и в связи с изложенной

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

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

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

Поэтому в разделе 3.3.1 рассматривалась задача следующего вида:

/(») -» min, (21)

при ограничениях

a<x<ß,

где f(x) - выпуклая функция, а, ß 6 Ел. Для тестирования рассматривалась задача:

¿¿2(*<-(п + 1))2^т»и, (22)

¡=1

при ограничениях

-J < Xi <i,i= 1,

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

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

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

Рассматривается задача

f(x) min, (23)

при ограничениях

Ах < Ь, (24)

где А — (т*п)- матрица. Допустим, что т = п. Предположим, что А - невырожденная матрица, и существует Л-1. Сделаем замену переменных

у = Ах (25)

и от задачи (23), (24) перейдем к задаче

/(у) min, (26)

при ограничениях

У < Ь, (27)

где f(y) = /(Л-1 у). В задаче (26), (27) допустимое множество имеет простую структуру.

Используя наилучшую эффективность модифицированного метода симплексных погружений для минимизации выпуклой функции на параллелепипеде, предлагается разбить работу алгоритма на два этапа: на первом этапе модифицированным методом симплексных погружений решается задача (23), (24) и на каждой итерации отбрасываются неактивные ограничения, если они есть. Как только число оставшихся ограничений стало равным п, то переходим ко второму этапу. На втором этапе производится замена переменных (25) и формируется задача вида (26),(27), для которой используется упрощенный вариант модифицированного метода симплексных погружений.

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

К основным результатам, полученным в данной работе можно отнести.

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

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

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

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

5. Проведено тестирование метода, которое показало, что:

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

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

в) работа модифицированного алгоритма тем лучше, чем больше невязок в задаче;

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

6. Применение метода симплексных погружений для расчетов термодинамических цепей химических реакций в Сибирском энергетическом институте СО РАН было успешным: во-первых, была подтверждена на тестах правильность математической постановки задачи при переходе от термодинамической равновесной модели к модели поиска промежуточных состояний термодинамической системы, проведено множество

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

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

1. Апекина Б.В. Вычислительный аспект метода симплексных погружений в выпуклом программировании.// Тез. конференции "Математическое программирование и приложения", Екатеринбург, ИММ УрО РАН, 1991, с. 5-6.

2. Апекина Е.В. Алгоритм и программа метод* симплексных погружений в выпуклом программировании и их приложения.// Материалы XXII конференции научной молодежи СЭИ СО РАЗ, Дел. в ВИНИТИ 28.07.91, с. 10-24.

3.Ап<зкина Е.В. Применение метода симплексных погружений для решения прикладных задач термодинамики.// Тез. конференции "Математическое программирование и приложения", ЕьС*ринбург, ИММ УрО РАН, с.17.

4. Апекина Е.В. О некоторых быстро сходящихся модификациях метода симплексных погружений в выпуклом программировании.// Материалы XXIV конференции научной молодежи СЭИ СО РАН, Деп. в ВИНИТИ 30.08.94, 2129-В94, с.2-13.

5. Apekina E.V., Bulatov V.P. The modifications of Simplicial Embeddings Method and its Applications.-Abstracts of International Conference on Operation Reseach, Berlin, 1994.

6. Апекина Е.В. Об ускорении метода симплексных погружений в выпуклом программировании.// Тез. конференции "Математическое программирование и приложения", Екатеринбург, ИММ УрО РАН, 1995, с. 28-29.

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

Отпечатано в СЭИ Заказ № 410. Тираж 85 экз.