Обобщенный метод уровней с приложением к декомпозиции тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

СОКОЛОВ Николай Александрович

ОБОБЩЕННЫЙ МЕТОД УРОВНЕЙ С ПРИЛОЖЕНИЕМ К ДЕКОМПОЗИЦИИ

Специальность 01 01 09 — дискретная оптимизация и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Москва-2008 003 169928

003169928

Работа выполнена в Центральном экономико-математическом институте РАН

Научный руководитель

Официальные оппоненты

доктор физико-математических наук, профессор ГОЛЬШТЕЙН Евгений Григорьевич

доктор физико-математических наук ГРИШУХИН Вячеслав Петрович

доктор физико-математических наук АНТИПИН Анатолий Сергеевич

Ведущая организация

Институт проблем управления им В А Трапезникова РАН

Защита состоится 23 июня 2008 г в 10 часов на заседании Диссертационного совета Д002 013 02 при Центральном экономико-математическом институте РАН по адресу 117418, Москва, Нахимовский проспект, д 47, аудитория 520

С диссертацией можно ознакомиться в библиотеке ЦЭМИ РАН

Автореферат разослан « / 'у» мая 2008 г

Ученый секретарь диссертационного совета, кандидат физико-математических наук

С В Борисова

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

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

Этим свойством обладает предложенный К Лемарешалем, А Немировским и Ю Нестеровым в начале 90-х годов метод уровней (в дальнейшем называемый классическим), гарантированная скорость сходимости которого оптимальна с точки зрения теории информационной сложности количество итераций к, необходимое для нахождения приближенного решения с заданной точностью £ > 0, имеет неулучшаемую теоретическую оценку вида к = О (е-2) при невысоких требованиях к точности

Отметим два момента, теоретический и практический, побудившие к дальнейшей разработке методов уровней

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

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

Основные дели работы:

• обобщение классического метода уровней, разработка и исследование семейства обобщенных методов уровней для задач минимизации и семейства седловых вариантов

(

обобщенного метода уровней, а также установление теоретической скорости сходимости методов из этих семейств,

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

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

Все основные результаты (леммы, теоремы и следствия) глав 1 и 2 получены автором лично и являются новыми Предложенные в главе 3 блочные методы разработаны в соавторстве и также являются новыми, численное тестирование этих методов также произведено автором

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

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

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

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

Апробация результатов исследования. Основные результаты и выводы работы докладывались на конференциях «Математическое программирование и приложения» (Ека-

теринбург, 1995, 1997, 1999, 2007 гг), 1-м и 2-м Американо-Украинском рабочем совещаниях «Recent advances in non-differentiable optimization» (Киев, 2000, 2001 г), Международной конференции «Дискретный анализ и исследование операций DAOR'2000» (Новосибирск, 2000 г), Международной конференции «Распределенные системы оптимизация и приложения в экономике и науках об окружающей среде DSO'2000» (Екатеринбург, 2000 г), 1-ой Московской конференции «Декомпозиционные методы в математическом моделировании» (Москва, 2001 г), ХП-й Байкальской международной конференции «Методы оптимизации и приложения» (Иркутск 2001 г), Международной конференции по оптимизации (PfalzAkademie Lambreht (Germany), 2002 г), VII-м и VIII-м Всероссийских симпозиумах по прикладной и промышленной математике (Кисловодск, 2006 г, Адлер-Сочи, 2007 г)

Публикации По теме диссертации опубликовано 25 научных работ (в том числе 14 основных работ) общим объемом 10,0 п л , личный вклад автора — 6,2 п л , 10 работ опубликовано в журналах, рекомендованных ВАК

Структура и объем диссертации Диссертация состоит из введения, трех глав, заключения, списка литературы из 112 наименований, 22 таблиц, 3 рисунков

II Основное содержание работы В работе решаются две основные задачи

Задача оптимизации V f(z) min, z 6 G С G С E, где / — выпуклая, вообще говоря, недифференцируемая функция, определенная на выпуклом многограннике G конечными значениями (на множестве G = dorn/ = {z 6 G f(z) < oo}) либо значениями, равными оо (вне G), где Е — некоторое конечномерное пространство Будем предполагать, что G — непустой компакт, содержащий внутренние точки, а функция / является липшицевой на G (с константой Липшица L) При этом функция / субдифференцируема в любой точке множества G Если df(z) — субдифференциал / в точке z, а под l(z) С df{z) понимать некоторый субградиент (элемент из множества df(z)), то для z е mtG любой элемент df(z) имеет норму, не превышающую L, а при z £ G\intG существует такой субградиент l(z), что ||/(г)|| ^ L Обозначим Z' = {z'&G Г = /(*') = min2e3 J(z)} * 0

Задача равновесия (отыскания седловых точек) <S' поиск на множестве G = Gx х Gy седловых точек функции f(z) — f(x,y), z = (х,у), те таких точек z* = (х',у') 6 G, для которых выполнены неравенства

f(x',y) ^ f(x',y') ^ f(x,y') для любых точек a = (i,y)eG

Здесь функция f(z) определена конечными значениями на множестве G, содержащемся в G — декартовом произведении многогранников С, х G, С Б = Е, х Е, Множество седловых точек обозначим Z' (оно может быть пустым)

Пусть функция / выпукло-вогнута на G и удовлетворяет условию Липшица (с постоянной L) по каждой из переменных х, у Тогда множество Z' = {{х',у')} ф 0, обозначим

/* = f(x',y') Кроме toro, функция / субдифференцируема по х и супердифференци-руема по у в каждой точке (г, у) 6 G Для произвольной точки у £ Gy (х £ Gx), если х 6 int Gx (у 6 int Gy) и iz (¡y)— произвольный элемент множества dfx(x,y) (dfv(x,y)), то ||fz|| < L (||íj| ^ L), для граничных точек существует субградиент (суперградиент 1у), норма которого не превосходит L

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

Далее предполагается, что многогранники G (для задачи V), Gx и Gy (для задачи S) заданы системой (двумя системами) линейных неравенств Что же касается выпуклого компакта G и функции /, определенной на нем, то они задаются неявно с помощью специального алгоритма — оракула

Во ВВЕДЕНИИ рассмотрены основные декомпозиционные подходы, выявлены их достоинства и недостатки, обсуждены оптимальные методы, описаны классические методы уровней для задач оптимизации и равновесия

Выбор метода Применение декомпозиции приводит к задаче минимизации (либо нахождения седловой точки) функции f(z), неявно заданной на неявно заданном компакте G Для точек z е G даже установление либо отрицание того факта, что z 6 G, и остальные действия, осуществляемые оракулом, могут быть достаточно трудоемкими Поэтому желательно, чтобы метод решения задачи (V или S) требовал как можно меньше итераций

Как известно из теории информационной сложности алгоритмов, теоретическая скорость сходимости оптимального метода имеет вид

где п — размерность пространства Е для задачи V (Ех х Еу для задачи й), а е > 0 — заранее заданная относительная погрешность решения задачи, к — количество итераций, понадобившихся методу для достижения заданной точности Первая часть оценки указывает на медленную скорость сходимости, не зависящую от размерности пространства (она справедлива для больших п) Примером метода, для которого имеет место такая оценка, является метод субградиентного спуска Н 3 Шора Во второй части оценки (т е к ~ ¡т 1п(1/е)) утверждается геометрическая скорость сходимости

к =

(1 /е2), п~1/2 <£ < 1 («низкая» точность), (п 1п(1/е)), 0 < е < п-1/2 («высокая» точность),

£ ~ exp{-fc/(H> ~ (1 - 1/М)'

i*

(1)

Примером оптимального метода с геометрической скоростью сходимости (со знаменателем 1 - 0(п~1)) является практически не реализуемый из-за своей трудоемкости метод центров Идея метода центров лежит в основе метода эллипсоидов, имеющего скорость сходимости типа О (п21п(1/е)), т е геометрическую скорость сходимости со знаменателем порядка 1 — 0 (гс-2)

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

Классические методы уровней. Метод уровней (в дальнейшем называемый классическим, G = G) был разработан в начале 90-х годов К Лемарешалем, А С Немировским и Ю Е Нестеровым [Math Programming, 1995] для решения общих задач негладкой выпуклой оптимизации на основе хорошо зарекомендовавших себя в вычислительной практике bundle-методов, являющихся развитием метода Келли (оценка трудоемкости последнего имеет вид к = О (г-1/'"-2')) Для классического метода уровней авторами остановлена оценка скорости сходимости к = О (е-2) Метод может быть применен для решения различных задач, в том числе для задач V и S

Схема классического метода уровней для задачи V.

О Задаются параметр А £ (0,1), число е > 0 и произвольная точка z¡ € G, к =1

1. Обращение к оракулу в точке zk 6 G, получение значения ¡(zk) и субградиента l(zk)

_к

2. Вычисление fc-ro рекорда по функции / / = mm{/(z,) i — 1, ,к} = f(zk)

3. Решение задачи ЛП оптимальное значение к-й модели на G /* = шт{/'(г) z 6 G}, где fk[z) = max1<lík{(/(zt), z-z,)+ f(zt)}

4 Вычисление «зазора» к-й модели Д* = / — /*, и к-го >ровня Lk = }к + (1 — A)A¡t

5. Критерий останова если выполнено условие Ак ^ е, то рекордная точка ;к является £-решением исходной задачи, STOP

6 Решение задачи КП zk+1 = argmm.,eGlW ||г - ;t||2, где Gk(А) = {гб5 fk(z) ^ Lk}

7. к = fc + 1, к 1

Для классического метода уровней, примененного к задаче V, верна оценка меры близости точки z¡¡ к множеству Z*

A(zk) = f(zk)-imnf(z)^Ak^Qk^2, Q = Д(1 _¿¿2)1/2. (2)

где d — диаметр компакта G, L — константа Липшица функции / Приближенное (по функционалу) е-решение задачи V отыскивается за ке итераций, kz 1 + (Q/e)2

Классический седловой вариант метода уровней. К Лемарешалем, А С Немировским и Ю Е Нестеровым [Math Progr , 1995] оптимизационный вариант метода уровней был обобщен на седловой случай для решения задачи S при G = G, для которой мера близости точки z = (х, у) е G = Gx х Gy к множеству седловых точек Z" определена по аналогии с (2) как A(z) = <р(х) — тр(у), где двойственная пара задач задается формулами

V >р(х) = max }{х,у) —> mm, х е Gx, V ф(у) = mm f(x,y) —> max, у 6 Gy

yeGy x sa,

Пусть уже построена последовательность точек {z, = (х„у,) е G г = 1, , к}, для которой вычислены значения, субградиенты и суперградненты функции {/(г,), lx(z,), ly(z,), г = 1, , к} Определим функции и задачи

Vk <рк{х) = ma {(/i(^), х - х3) + f{z,)} min, x e Gx, Vk у € Gs,

выпуклые ¿-модели ipk(x), —фк(у), являются минорантами функционалов f[x), -тр(у), соответственно, они монотонно не убывают по к Обозначим V1*'* — оптимальные значения задач Vk, Vk, им соответствуют наборы множителей Лагранжа (а*, /?,*)

к

i = i, A 2>i = 1}' f1

i=i

При этом ^ Afc = /'* - V*'*, где точка zk = (х*,2/*) = (E,=i Ä**.. Ef=i € <5

Схема классического метода уровней для задачи 5.

0. Задаются параметр А € (0,1), число е > 0 и произвольная точка z\&G, к =1

1 Обращение к оракулу в точке zk 6 G, оракул выдает тройку f{zk), lx(zk), ly{zk)

2. Решение задач ЛП определение оптимальных значений <£>*•* и "фк'* задач Vk и Vk

3. Вычисление «зазора» к-й модели Ак = </>'■* - ipk'', и fc-ro уровня Lk = -(1 - A)Ajt

4 Критерий останова если выполнено условие Ак е, то вычисляется точка Zk = (хь,Ук), которая является £-решением задачи S, STOP

5 Решение задачи КП z*+1 = arg minieGt(A) \\z - zkf, где Gk( A) = {z e G <pk( x) -4>k{y) ^ Lk}

6. к = k+ 1, к 1

Классический метод уровней неприменим для задач, в которых G Ф G, в частности, в случае, когда G не является многогранником Он также не может быть применен к задачам, полученным при помощи прямой либо прямо-двойственной декомпозиции Эти задачи решаются обобщенными методами уровней, разработанными в 2000-2001 гг (см [8], [9]1) В ГЛАВЕ 1 диссертации предлагается общая схема таких методов, использующих обобщенный оракул, их частным случаем является семейство методов уровней для решения задачи V

Обобщенный оракул. Пусть в многограннике G С Е (Е — конечномерное пространство), содержится выпуклый компакт G, который, в свою очередь, содержит произвольное выпуклое множество Z" ф 0 (например, точку) Нашей целью является нахождение какой-нибудь точки из Z' либо приближение к множеству Z* с некоторой точностью Каждой точке z = Zk S G приписано непустое множество ответов (откликов) оракула B(~it) = {(b{zk),ß{zk))}, ответом оракула считается пара (b(z),ß(z)), где b(z) — вектор, ß{zk) — число Множество В(гк) содержит набор b{zk) = 0, ß(zk) = 0 лишь для точек

'См список работ автора в конце автореферата

= min V ak{f(z,) + (lx(z,),x- х,)), {of ^ 0

х£Х J I.

= max £ ßk(f(z,) + (ly(zt), у - у,)), > 0 1=1

гк 6 2' Для остальных наборов ||Ь(г(;)|| ф 0, и множество 2' содержится в каждом полупространстве Е точек у £ Е, для которых выполнено неравенство

(Ъ(гк),у - гк) + р{хк) ^ 0, (3)

В точке г = гк £ (7 множество откликов оракула ./ = ]к разделим на два непересекающихся подмножества ]к — Ук и Л Зк = 0 Это разделение производится по принципу принадлежности точки гк множеству б К первому типу отнесем точки гк £ тЬй, для них любой отклик оракула гарантирует лишь то, что множество Z' содержится в Е Отклик оракула для задачи минимизации V — пара (1{гк), /(гк)), где /(г*) и 1(гк) 6 д/(гк) — значение функции и ее субградиент, вычисленные в точке гк Для задачи равновесия 5 откликом оракула является набор {1{гк), /(гк)), где 1(гк) = (1х{гк),—1у(гк)), }{гк) = }{хк, Ук), М2*) 6 д/х(гк) и Цгк) £ д/у(гк) — значение функции, ее субградиент и суперградиент, вычисленные в точке гк

Ко второму типу (отнесем точки гк 6 (7 \ (7, для них любой отклик оракула гарантирует, что полупространство Е, задаваемое неравенством (3), отделяет точку гк от й Для задачи V при гк £ (7\<7 отклик оракула — вектор Ь(гк) = а(гк) (||а(г4)|| ф 0), и число /3(г) = а{гк) ^ 0, удовлетворяющие неравенству (3) Для задачи 5 при гк = {хк,ук) £ <7\0 отклик оракула может быть трех видов если хк £ вх, ук £ ву, то откликом оракула является вектор Ь{гк) = (а(хк),0у), а{хк) £ Ех (||а(х*)|| ф 0) и число Р{гк) — а(хк) ^ 0, аналогично, при хк £ С„ ук & С?, отклик оракула — вектор Ь(гк) = (0х,а(уь)), а(ук) £ Еа (Иа(уОН Ф 0), и число /3(хк) = а(ук) ^ О, 0Х,0У —нулевые векторы в Ех и Е, соответственно Если одновременно хк $ и ук £ йу, то откликом оракула является одна из двух гиперплоскостей, отделяющая точку хк от Ох или точку ук от ву, либо линейная комбинация этих двух гиперплоскостей (можно взять обе гиперплоскости, считая их различными откликами оракула)

Для граничных точек гк £ ОС оракул может выдавать отклики как первого, так и второго типов «Классический» оракул выдает отклики только первого типа {Зк = 0)

Схема обобщенного метода уровней Опишем вариант обобщенного метода уровней, использующий введенный оракул Зададим множества 5о = 0, Л0 = 0 и число щ = 0 Выберем положительно определенную симметричную матрицу Я с собственными значениями 0 < Лт1П ^ ^ Лт1Х и произвольную точку ¿1 £ (7

Пусть уже построено к (к ^ 1) точек г, € Д, г = 1,2, , к, определено множество Зк-1, |5*-1| = пк_1 С точкой гк свяжем тк (тк ^ 1) откликов оракула, т е зададим тк наборов векторов Ь} = Ь.,{гк) и чисел /3]<к = Р]1к(гк), ] £ Зк = {пк,х + 1, ,пк_х + тк}, для каждого набора выполняется условие (3) Положим Бк = и ]к, где = тпк, 15*1 = пк = + тпк Будем считать, что среди тк чисел /3^, ] £ ,4, хотя бы одно неотрицательно

Далее будем предполагать, что Ф 0 для всех ] £ ]к (иначе точка гк 6 2*) и что многогранник йк = {г 6 в (Ь},г — г,)+0]:к ^ 0, ] £ ./,, I = 1, ,к}, где числа &1<к ^ Р,,к~\ для всех 7 6 ■/„ » = 1, ,к — 1, является непустым множеством и содержит 2'

Поиск точки zk+i в обобщенном алгоритме уровней начинается с решения задачи ЛП

Л t -+ шах, {b},z~ 2,) + P}tk + t < 0, j £ J„ г = 1, ,к, zeG, (4)

относительно переменных zut Обозначим Д* ^ 0 ее оптимальное значение

Если Д* = 0 (либо выполнен некоторый критерий прерывания счета), то итеративный процесс прекращается В противном случае к множеству Л*_1 добавляем m* ^ 1 чисел б (0,1), ] 6 Jk, полагаем Л* = Ajt-i U {А;, ] 6 Л} и определяем многогранник

Gk{A.k,Ak) = {zeG (b}lz-z,)+P},k + А,Д*«:0, j е J„ г = 1, ,к} (5)

В заключение к-й итерации, новая точка z*+i находится как проекция (в метрике Я) точки zk на многогранник C/tfA^, Д*), т е решается задача КП

В* (Н(г - г*), z - z*) -> min, геС*(Л*,Д0 (6)

Далее процесс повторяется для новой точки z/t+i

Вместо последовательности {Д*} оптимальных значений задач Лк в методе уровней можно использовать невозрастающую последовательность {Д*} (ненулевых) приближенных значений задачи Лк 0 < Д* — Д* ^ 6к, Д*+1 < Д*, к ^ 1 В диссертации доказаны две основные леммы.

Лемма 1. Пусть исследуемый вариант обобщенного метода уровней имеет следующие параметры 0<А^А;^А<1 для всех А; 6 Л* и |[63|| ^ В дм всех j € Sk, к = 1,2, , где ответы оракула порождают систему неравенств (3) Пусть также d — диаметр G, ¡1 = hmix/hmm — число обусловленности положительно определенной симметричной матрицы H Тогда для последовательности {Дк) оптимальных (либо {Дк} невозрастающих приближенных) значений задачи Лк, вырабатываемой методом уровней, имеет место неравенство

Д k^Qk'l/2, к = 1,2, , где Q = Шм1/2/[А(1 -À2)1/2] (7)

Задачу Вк также можно решать приближенно Пусть \ 6 G — приближенное решение задачи КП Вк, те такая точка из множества Q* (Ajt> Ajt), для которой

{H{zk-Zku),^-Zk+i)^(H(zk-zM),Zk-zM)^{H(zk-Zk+i),Zk-zw}{l+T^), (8)

где тЦ (к ^ 1) — относительная погрешность по функционалу решения задачи КП Вк, гш — ее точное решение

Пусть последовательность {rt} такова, что

оо оо

г к < оо, положим S = y~](2rt + тк) (9)

t=l lt=l

Лемма 2. Пусть выполнены все предположения леммы 1, задача. Вк решается приближенно с погрешностью Тк, к ^ 1, а также выполнены условия (8), (9) Тогда последовательность {Д*} (оптимальных или невозрастающих приближенных) значений задач

Ак, вырабатываемая методом уровней, удовлетворяет неравенству (7) при замене В на

Если (9) заменить на условие 0 ^ тк ^ С[(Я(гк - — г^)]1/2, где О ^ С <

С = (\/2 — то последовательность {Д*} (точных или невозрастающих

приближенных) значений задач Ак, вырабатываемая методом уровней, удовлетворяет неравенству (7) при замене В на В/( 1 — 5), где 5 = 2СУ\/Лтах + С2сР/гтах £ [0,1) Леммы 1-2 являются основой всех результатов глав 1 в 2

Обобщенный метод уровней для задачи V и его основные модификации К Бэром, Е Г Голыптейном и Н А Соколовым в работе [8] было предложено несколько вариантов обобщенного метода уровней, согласно которому в процессе минимизации функции / на многограннике й строится последовательность точек 2, 6 (7, г = 1,2, (в качестве начальной точки г\ принимается любая точка из б) Многогранник (7 задается аналитически в виде системы линейных неравенств, а множество С? и функция /(г) задаются неявно с помощью обобщенного оракула Оракул выдает информацию о том, принадлежит ли 2, множеству в или нет, а также (только один) субградиент и значение функции в точке г, 6 б либо (одну) отсекающую гиперплоскость при г, 0 6"

Пусть /£ = тт^^ Л^,) — рекорд по функции /, полученный на к точках , г*, (вначале этот рекорд полагается равным оо), и для к = 1,2, множество 4 = {1,2, , к} разбито на два подмножества по признаку, попали ли точки , ^ в множество О или нет Гк = {1 ^ I ^ к г, 6 Щ, = г, £ 5}

Допустим, что уже найдено к (к ^ 1) точек г, 6 б С каждой точкой г,, 1 ^ г ^ к, связывается неравенство (ответ оракула) (6„ г — г,) + Д* ^ 0, где

Здесь число р = 1 определяет метод с глубоким отсечением, р = 0 — метод без глубокого отсечения, 7, = 1 задает ненормированный, 7, = ||/(г,)|| — нормированный метод уровней Ненормированный метод уровней с глубоким отсечением в случае в = С? совпадает с классическим методом уровней В нормированных вариантах метода и вектор /(2,), и вектор а, (г,) нормированы одинаково Отклики оракула и исходный многогранник (7 порождают многогранник = {г € С (Ь,,2 — г,) + Д* ^ 0, 1 ^ г ^ к} ф 0, т к он содержит все точки г 6 С, для которых /(2) ^ /£

Согласно схеме, отдельная итерация метода, связанная с вычислением очередной точки гк+1 6 <7, сводится к решению одной задачи ЛП и одной задачи КП (задач и В к)

Для всех вариантов обобщенного метода уровней получены оценки скорости сходимости, имеющие порядок О (к'1/2)) при к ^ К и достаточно большом К, для случая, когда компакт О имеет непустую внутренность Приведен пример, в котором С не имеет внутренних точек и нет сходимости ни /£ к /*, ни г* к С

Семейство обобщенных методов уровнен для задачи ~Р В [4|, [И], [13] рассмотрено семейство методов уровней для задачи V, содержащее все ранее встречавшиеся (классические и обобщенные) варианты метода уровней Обобщение производится в

5(1 + 5)

*.), ' € II

нескольких направлениях параметризация «глубины отсечения», произвольное нормирование векторов, определяющих вспомогательную задачу ЛП, вместо одного числа Л, постоянного для всех итераций алгоритма, используется набор, вообще говоря, различных чисел А,, г = 1,2, , разрешено добавлять на каждой итерации несколько линейных ограничений, вместо единичной матрицы в задаче КП используется произвольная симметричная положительно определенная матрица, вспомогательные задачи ЛП и КП решаются приближенно Отметим особо, что ранее не рассматривался вопрос о точности приближенного решения вспомогательных задач, необходимой для сохранения скорости сходимости методов уровней

Опишем новые варианты метода уровней для нахождения минимума, использющие обобщенный вариант оракула Разделим множество откликов оракула Sk = Uiна два подмножества S'k = Ui^* J[ и S¡¡ = Ui^* J'k Дополнительно к уже введенным множеству чисел Ак = {Aj 0 < Aj < 1, j G Sk} и положительно определенной симметричной матрице Я (с числом обусловленности д = hmax/hmm) рассмотрим еще три множества чисел {/?;}, {F,}, {А,} 0 < р, < 1, F,(zt) > О, j € j; ф 0, A,(z.) > 0, ) е J," ф 0, 1 ^ г s: к, к > 1

Отклики оракула для точки zk Ç.G { те m¡t наборов векторов Ь3 и чисел j 6 Jt) определяются формулами

{ A}{zk)a,{zk), j е J'¿, { A}(zk)a,(zk), j S

Здесь, как и ранее, l¡ (zk) С df{zk) — субградиент функции f(z) в точке zk, числа p¡ (p¡ € [0,1]) задают «глубину отчечения» (при условии, что J'k ф 0), векторы b3 = A](zk)aJ(zk) (l|ij(zi)|| = 1) нормированы по-новому и их новые нормы есть числа Aj(zk) > 0, «нормировка» векторов l3{zk)l||Zj(zjfc)|| определяется положительными числами Fj(zk) Как и ранее, числа ¡3hk положительны и монотонно не убывают по к

Теорема 1 Пусть f(z) — собственная выпуклая функция на многограннике G, диаметр G равен d, компакт G — [z 6 G f(z) < со} содержит шар радиуса г > 0, функция f на G удовлетворяет условию Липшица с постоянной L, пусть также исследуемый вариант обобщенного метода уровней задается положительно определенной симметричной матрицей H с числом обусловленности fi > 0 и последовательностями чисел {А3} (0 < A sC_A, ^ Â < 1, j 6 S»). (M (0 < Р, < 1, 3 G Si), {ВД} и {Л,(г,)} (0 < F3(zt) ü F и ^ F, j ф 0, 0 < А < A,{z,) ^ A, j 6 J" ф 0,

i = l, ,k, k = 1,2, ) Пусть {Д/t} и — последовательности оптимальных и невозрастающих ненулевых приближенных значений задачи ЛП Ак 0 ^ Ак — Ак ^ Sk Тогда при 6к < Аг и к > К(Аг - â/,) множество З'кф 0 и

A(zk) = Д* - /• < С(Лк + 6к) < C(Qk~1'2 + 5к), где /* — минимальное значение / на G, fk = miiii^ f{zt) = f{zk), константы

C = BÍzA+f, В = max(F,Â), Q = ^f , K(z) = {Q/z)2

Для любого е > 0 при 0 ^ 5к < тш{Лг, е/С} можно найти е-мингшум функции f(z) на G за кс итераций, причем к€ ^ 1 + тах{К(е/С — Sk),K(Ar — 6k)} При приближенном решении задачи КП ßk константы В и Q увеличиваются в соответствии с леммой 2

Для нахождения г-минимума функции /(х) на G одновременно с задачей Ак рекомендуется решать (например, через каждые 10 итераций) задачу ЛП

(t1 -)• max, г £ G,

{aj(z,),z-z,) + а, (г,) $0, 1

Теорема 2. При выполнении условий теоремы 1 имеют место неравенства

Д(г*) = /**-/•< AU СДь

где — максимальное значение линейной формы задачи А'к

В ГЛАВЕ 2 описаны два седловых варианта метода уровней и предложена схема построения семейства таких методов для задачи равновесия S

В 2001 г было предложено два способа распространения обобщенного метода уровней для задачи минимизации V на задачу равновесия S

В методе первого типа [9j задается значение параметра Л € (0,1) и в процессе отыскания седловой точки функции f(z) на G строится последовательность точек z, € G, г = 1,2, (с любой точкой z\ 6 G) Пусть для к = 1,2, множество 1к = {1,2, , к} разбито на два подмножества по признаку, попали ли точки zx, ,zk в множество G или нет Д = {1 < « < fc z, € G}, Гк={1^г^к z, £G)

С каждой точкой z, = (х„у,) е G, 1 ^ г ^ к, связывается (одно) неравенство (3), где

>. = ( P(är teIi' А* = А = { °а(2} leJ;

{ e(2,), teil I аЫ' ге1к'

l(zt) = a{z,) = {ах(х,),ая{у,)), ||а(г,)Ц = 1, a(z,) > 0 Величины ||/(г,)||

можно считать не равными нулю (иначе точка z, является искомой седловой точкой) Оракул для точки zk 6 int G вычисляет f(zk) и находит некоторые субградиент lx(zk) 6 dxf{zk) и суперградиент ly{zk) 6 dyf(zk) (при этом f(zk) не используется) Если хк & Gx, Iк £ Gx, то оракул выдает набор ах(х,) ф 0, ах(х,) > 0 (ау(у,) = 0), если ук g Gy, ук е Gy, то откликом оракула является пара ау(у,) ф 0, ау(у,) > 0 (ах{х,) = 0), если эти два условия выполняются одновременно, то оракул выдает набор 0i(zt),a1(;,),0j,(r,),a,j(cl), по которому строится гиперплоскость (as(z,),z — г,) + as(zt) < 0, где для произвольных неотрицательных чисел кх = kx(z,), ку = Ky[z,), таких, что к, = + к2)1/2 ф 0, az(z,) =

«["'ММ2").0?) + S(°i>av(2'))]> аЛг.) = кГ1!**0^) + гДе О*, 0У - нулевые

векторы в Ех и Еу, соответственно

По получении отклика оракула решается задача ЛП А^ вида (4) относительно [z, t) и двойственная ей задача Л'^ Обозначим Д* максимальное значение линейной формы задачи Д1' Если I'k ф 0 и Ак «мало», то вычисляется точка zk = w,z,/ w, € G,

42)

где ш, ^ 0 — соответствующие компоненты оптимального плана задачи и итерационный процесс прекращается при Д(zk) ^ е, иначе отыскивается точка zk+1 — решение квадратичной задачи вида (6) при Ajt = Л, Н = и итерационный процесс продолжается ДЛЯ НОВОЙ ТОЧКИ Zfc+i

Е Г Голыптейн [Ж вычисл матем и матем физики, 2001] предложил седловой вариант метода уровней второго типа В нем также задается значение параметра А £ (0,1), и в процессе отыскания седловой точки / на G строится последовательность точек г, 6 G, г — 1,2, (zi € G произвольная) Пусть для к ^ 1 множество Ik = {1,2, , fc} разбито на три подмножества Гк = {г € 1к г, £ int (?}, ZJ'fc = [i Е Ik x,eGx\ int Gx}, Iyk = {i £ Д í/, £ Gy \ mt Gy}, при этом Ik = Гк U П = 0, где = I»k U I«k

Введем задачу ЛП А^ (относительно неизвестных вектора z = (х, у) и чисел tx, ty)

ty — i» max, (x, y) 6 G, +{lx{z,), x - X.) + /(г,) - ix ^ 0, геГкф0, -(1у(ь),у- У.) ~ /(*.) + iy < о, хегкф0, (ах(х,), х-х,)+ ах(х,) + tv - tx < 0, г € 1"к ф 0,

(ay(z,),2/ -!/.) + а„(у,) + íy - tx < 0, г £ 1Цк ф 0,

Ее отличия от задачи А^ очевидны Тем не менее, ее можно привести к виду (4)

Поиск точки zk+i £ G начинается в методе второго типа с решения задачи Af^ и задачи Af\ ей двойственной Пусть Ак — максимальное значение линейной формы задачи А^ Если множество Гк ф 0 и Ак «мало», то вычисляется zk = (х'к, у'к) £ G с компонентами хк = Е.ei'k v'x'/ Ук. = E,s/í "■?/■/ Е,eií u" где > 0> v. > 0, г е Гк — компоненты

7(2)

оптимального плана задачи Ак , соответствующие первым двум группам неравенств в задаче 42>, при A(z£) ^ е итерационный процесс прерывается В противном случае для нахождения новой точки zk+1 решается задача КП Ввида \\z — zt|¡2 min, z £ Gk\^Ak), где непустой при фиксированном t ^ Ак выпуклый многогранник Gf\t) С Е является проекцией на Е многогранника, определяемого условиями задачи А¡j.2' и дополнительным условием tv-tx^t Далее итерационный процесс повторяется для новой точки

Для методов обоих типов отдельная итерация алгоритма, связанная с вычислением очередной точки zk+i 6 G, заключается в решении одной задачи ЛП и одной задачи КП Получены оценки скорости сходимости этих методов (порядка О (А;-1'2)) при условии, что компакты Gx и Gy имеют непустые внутренности

Семейство седловых вариантов метода уровней. В описанном в [12] седловом варианте обобщенного метода уровней обобщение методов первого и второго типа производится в нескольких направлениях (подобно семейству методов уровней для задач оптимизации) «гибрид» методов первого и второго типа, т е в случае г € Гк можно строить отсечения как первого типа, так и второго типа, можно произвольным образом нормировать векторы l(z,) и a(z,), вместо одного числа А, постоянного для всех итераций алгоритма, используется набор, вообще говоря, различных чисел А„ t ^ 1, разрешено добавлять на каждой итерации несколько линейных ограничений любого типа, вместо единичной матрицы в задаче КП используется произвольная симметричная положительно определенная

матрица, вспомогательные задачи ЛП и КП можно решать приближенно

Выберем произвольные точку г^ £ G, числа Ао £ (0,1) и Fo > 0 (например, До = 1/2. Fq = 1), симметричную положительно определенную матрицу H (с собственными числами О < ЛтЦ1 ^ < /¡тах и числом обусловленности ¡1 — "тах/ '»min ), множество Ло = 0

Пусть уже построено к (к ^ 1) точек г, 6 G, г = 1,2, , к Уже накопленное множество откликов оракула Sk~ь nt_] = |5/t_i| (So полагаем равным 0, щ = 0), в точке zk пополним m* ("I* ^ 1) откликами оракула Jk = {nt_i + 1, .nt-i + mt}, |J;t| = mk, положим Sk = S*-! U Jk = {1, ,71*}, где nk = пк.1 + 1Щ

Отклики оракула первого вида (zk £ int G и частично zk б dG) обозначим J'k, они порождают два подвида неравенств К первому подвиду J'ak, = т'ок, отнесем неравенства

jj^î[Сч(**).*- - (ly,(zk),y-yk)]+tv-tx^ О,

ко второму подвиду J'lk, = т[к, отнесем, соответственно, пару неравенств

+F0[(l4(zt), х - хк) + /Ы] - tx < 0, -F0[(iw(zO, у - ук) + /Ы] +1, ^ О

Здесь Fj[zk) [] € Jôk), F0 — положительные числа (задаваемые пользователем), }(zk), lj{zk) = {lxj(zjc), ~'w(z*)) Ф (0> >0) ~ информация, выдаваемая оракулом

Итак, множество J'k разбито на два взаимно непересекающиеся подмножества J'ok, J[k, = т'к = т'ак + т\к Оставшиеся отклики оракула обозначим Jk s Jk \ J'k, |JJ.'| = тк Они определяют неравенства вида

Aj(zk)[{aXJ(xk),x - хк) + {ау]{ук),у - у,) + a3{zk)] + ty-tx^ О,

где числа A}(zk) > 0, j £ Jk, задаются пользователем (это масштабирующие множители), a,{zk), a,{zk) = (аХ]{хк),аю(ук)) (||а,(г*)|| = 1), j е Jk, — отклик оракула Обозначим Jok ~ Jk\{Jxk^Jyk) множество таких откликов Тем самым, множество Jk разбито на три попарно непересекающихся подмножества J'Jk и J'^k В итоге имеем тк = т'к + тк Положим S'k = U J'k, S'I = U J'i

Поиск точки zk+x 6 G начинается с решения задачи

Л,

ад

У) 6 С,

(lj(z,),z-z,) + ty-tx^o, ] е J'üv

+F0[{lXJ{z,),x - X.) + f{z,)} -txií 0, je J[„ -Fo [(¿„(г,), y - y,) + f{z,)] +ty^ 0, je J[„ A,{zt) [(aj(z,), z-z,) + a,(z,)] + ty-txÇ 0, J,",

1 ^ Î ^ k, (10)

переменными которой являются точка г = (х, у) и два числа tx и ty Обозначим Лк максимальное значение линейной формы задачи Лк

Если множество J'k ф 0, то вычисляется к-е приближение z£ к Z'

1 * Г 1 * Г *

1=1 l£JL JC-^U 1=1 J 1=1 Lj€j;, iZJ'n

где ^ 0, у Е Г^, и, ^ 0, у} > 0, ] 6 1 ^ % < к — компоненты оптимального плана задачи Лк, соответствующие первым трем группам неравенств в задаче Аь Начиная с некоторого номера к, при к ^ к множество З'к ф 0 и -у^ > 0 Итерационный процесс оканчивается, если точка Д(г£) ^ е, в противном случае доопределяется множество Ак = Л*_1 и {А; 6 (0,1), з 6 Гок и ■/£'}, вводятся масштабирующие множители > О,

] 6 к, ^(г*) > 0, ^ € и для нахождения точки решается задача КП

(#(г-;г*),г-г*)-+тт, г 6 (^(Д*,Л*), где £?*(<, Л*) = {г = (*, у) £ С ¿„ - и > А0(, ф 0,

-^[{/„(гО.у-у.НДг^+^О, ] € 1 5$ г ^ Л, ^(^[(а^^.г-^ + а^г.Ц+^КО, ) € 7,", 1 < ( ^ А;}, непустой при фиксированном Ь ^ Д* многогранник Л*) С Е является (при ф 0) проекцией на Е многогранника, определяемого при помощи условий задачи Л* и дополнительного условия (у — ^ Ло4 Далее итерационный процесс повторяется для Положим для к ^ 1

I и, Ь1к-0, ^ о, =

_ Г тахЛ,(г,). Г,'ф0, ( тшЛ,(г,), 7," ф 0,

Л* = тах < №. = тт {

[ 0, 7," = 0, \ +со, ^ = 0,

В = Бир^^В*}, Л = т^^/Ц}, где -Ро, -^(г,), АДг,) определены в (10), £ — постоянная Липшица функции /(г, у) на б по каждой из переменных зг, у

Теорема 3 Пусть }(х,у) — выпукло-вогнутая функция, определенная конечными значениями на выпуклом компакте й = х и удовлетворяющая на нем условию Липшица с константой Ь по каждой из переменных х, у, каждый из компактов йх и Оу содержит шар радиуса г > 0 Пусть также С» содержится в многограннике (? = йх х(7у, причем максимальный диаметр многогранников С?* и йу есть й, а седловой вариант метода уровней задается с помощью симметричной положительно определенной матрицы Я с числом обусловленности ц, трех последовательностей чисел

А* = {А, 0<А^А^А<оо, Ак = {А3 0<А^А^А<1,

и двух чисел А0 и где А0 € (А, А) и ^ ^ < если ^ 0

Тогда седловой вариант метода уровней вырабатывает при к > К(Аг) точку гк, мера близости которой к седловому множеству допускает оценку Д(г£) ^ С<2Атгде В = шах{Л,Р}, константы С = 2Щ-г)/{Аг) + Р, О. = 5^(2^)1/2/[А(1-А2)1/2], функция К(г) = (2/г)2 Для любого е > 0 можно найти е-седловую точку /(г) на б за кс итераций, причем ке ^ 1 + тах{К'(£/С),К"(Лг)}

Как н в главе 1, задачи .4* и Вк можно решать приближенно Для седлового варианта обобщенного метода уровней верны леммы 1 и 2, доказанные для общей схемы оракула, и имеет силу аналог теоремы 2 Для нахождения е-седловой точки можно дополнительно (например, через каждые 10 итераций) решать некоторую вспомогательную задачу ЛП (в диссертации рассмотрены две такие задачи — аналоги задачи А'к главы 1)

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

ГЛАВА 3 диссертации посвящена применению обобщенного метода уровней к задачам ЛП, имеющим блоки простой структуры Для пяти линейных моделей построены новые методы их решения, основанные на классическом и обобщенном методах уровней, проведено их численное тестирование Для всех методов использовался прием «обновление» когда величина Л^ уменьшается, скажем, в два раза, то вместо всех ограничений-неравенств определенных точками 21, ,гк (к моменту проведения к-й итерации их накопилось бы пк штук), задающими модель, оставляются только те ограничения, которые входят в оптимальный базис задачи Ак При этом теряется часть накопленной информации о функции / и множестве б, однако вспомогательные задачи становятся меньшего размера, и суммарный выигрыш во времени значителен В качестве решателя задач ЛП и КП во всех тестах была использована программа К Шитковского, основанная на методе Пауэлла Для каждого набора параметров решалась серия из 15 задач, и результаты усреднялись

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

— двойственный блочный метод (ДБМ) Т\ для трехиндексной транспортной задачи с аксиальными суммами [о],

— ДБМ 7г для многопродуктовой задачи снабжения с промежуточными базами, имеющими ограниченные пропускные способности [6],

— прямо-двойственный блочный метод (ПДБМ) % для многопродуктовой транспортной задачи при наличии дуг с ограниченными пропускными способностями и производством [7]

Проведенные вычислительные эксперименты, описанные и проиллюстрированные в диссертации таблицами, показали высокую эффективность и надежность классических ДБМ 71, Тг и ПДБМ 7з при решении всех тестовых задач

Прямой блочный метод (ПБМ) [2], [8J и прямо-двойственный метод (ПДБМ) [9j, [Ы| были разработаны для решения задач ЛП с блочно-диагональной структурой при наличии вертикального либо вертикального и горизонтального связующих блоков к

(с, х) + и*) -+ max, 0 < х < х, 0 < ик < щ, k = 1, ,К,

<р *=i I Н

А00х + АокЩ £ Ьо, Акох + ВКик ^Ьк, к = 1, , К,

I *=i

где векторы с,х,х е ENo, дк,ик,йк € к = 1, ,К, bk 6 ЕМк, к = О,. ,К, Лоо, А)ь Лю — матрицы размера MaxN0, M0xNk, MkX.N0, соответственно, Bk — матрицы размера Mk х JV*, k = 1, , К

Случай Mo = 0 (отсутствуют связующие ограничения) Вычислительный эксперимент был проведен на множестве генерируемых тестовых задач при трех значениях К £ {5,20,128}, М, = 10, JV, = 15, г = 1, ,К {те блоки одного размера 10 х 15), No S {5,10,20,30, ,200} Задача считалась решенной, если удавалось найти ее приближенное решение с заранее заданной относительной точностью е = 10~% s £ {3, , 7}

Сравнение нормированного (М) и ненормированного {М) ПБМ на наборе тестовых задач выявило явное превосходство М даже для небольших задач ЛП

Таблица 1. Сравнение ПБМ М и М для К = 5, Л'о = 10

ПБМ £ ~ ю-3 е = 10~5 е = 10~7

к Mjom к ■fcdom к &dom

М 15,1 11,0 34,4 28,0 54,1 47,5

М 677,1 673,9 924,1 916,3 1204 5 1192,8

Случай М0 ф 0 (горизонтальное и вертикальное окаймление) Рассмотрен обобщенный седловой метод уровней (ПДБМ) 77\ (нормированный, первого типа) для генерируемых задач с матрицей В блочно-диагональной структуры {К = 5 или 20 блоков размера 10 х 15), который оказался лучшим среди других типов ПДБМ Числа М0 и Na выбирались из набора {0,10,20, , 60} Задачи решались с относительными точностями е = 10-i, 3 ^ s < 7 Конец счета определялся при помощи решения на каждой десятой итерации задачи А'к В ПДБМ 77 х значения параметра Л = 1/2 и штрафного параметра R = 103

Было проведено сравнение трех ПДБМ 771, и 1С2 (Л^ уже определен) Два остальных — классические седдовые методы уровней {¡С? — ненормированный вариант второго типа, К\ — нормированный вариант первого типа), примененные к выпукло-вогнутой функции f(x,y), к которой добавлен негладкий (модульного типа) штраф за нарушение связующих ограничений Скорость сходимости остальных ПДБМ (yVb Л/г — ненормированные обобщенные варианты первого и второго типа, К\ — ненормированный классический вариант первого типа) оказалась значительно медленнее, чем у первых трех ПДБМ Анализ полученных численных результатов позволил сделать следующие выводы — ПДБМ 771, К.\ и К.2 работают надежно, позволяя достаточно быстро находить решение исходной задачи с высокой относительной точностью е ~ Ю-7,

— скорость сходимости этих ПДБМ почти линейна (как правило, увеличение точности в 10 раз происходит за «примерно одинаковое» число итераций),

— зависимость числа итераций к{Мо, Nо) от М0 + Л^ не является линейной, она скорее имеет вид «параболы» ,

— наилучшим по числу итераций оказался ПДБМ К^, два других имеют примерно одинаковую скорость сходимости

к

Распараллеливание Блочные методы допускают естественное распараллеливание (1), [3) В главе 3 рассмотрен ПБМ М с К = 128 блоков 10 х 15, N0 6 {10,20, ,60} Целью эксперимента явилось не только тестирование алгоритма, но и выявление целесообразности использования для его реализации параллельной ЭВМ

Как показали результаты вычислительных экспериментов, для всех значений связующих переменных с увеличением числа доступных процессоров время решения соответствующих задач уменьшается примерно одинаково (в 1,35 раза при увеличении числа процессоров в два раза)

Сравнение с симплекс-методом При проведении вычислительных экспериментов неоднократно приходилось сравнивать результаты решения задач ЛП методом уровней и симплекс-методом Так, был проведен сравнительный анализ [6] решения двух многопродуктовых транспортных задач методом уровней 7г (с относительной точностью е = Ю-5) и симплекс-методом (с помощью программы MINOS) Для MINOS приведены размеры задачи ЛП число строк М, число столбцов N, число строк записей L в MPS-формате, 77 — отношение времени вычислений, полученного с помощью программы MINOS, ко времени, которое затрачено ПДБМ 75 Для первой задачи наблюдался выигрыш r¡ по времени больше, чем в 12 раз, для второй — более, чем в 42 раза (см с 20)

Аналогично, был проведен сравнительный анализ результатов решения многопродуктовых производственно-транспортных задач с помощью алгоритма ПДБМ 7з и симплекс-алгоритма (программа MINOS) для четырех задач при m = п = 20, р = t = 10, s 6 {10,20,30,40} (здесь тип — количество пунктов отправления и назначения соответственно, s — количество различных продуктов, t — суммарное количество технологических способов производства) [7] Преимущество 7з над MINOS возрастает с ростом s

и при s = 40 ПДБМ решает задачу в 97,7 раза быстрее, чем MINOS

Таблица 2 Численное сравнение MINOS и ДБМ Т2, е = 10~5

m п Р s MINOS ДБМ Тг V

М N L к time к time

20 30 15 5 416 4242 12300 3045 645 86 52 12,4

30 50 25 10 1326 20250 63600 17509 17305 119 412 42,0

Также было проведено сравнение вычислительной эффективности метода уровней и принципа разложения Данцига-Вульфа (DW) [10], который, как и метод уровней, учитывает специфику решаемой задачи Размеры задач п = 50, m = 30, количество баз р е {10,30}, s 6 {10,20,30,40} Размеры общей задачи ЛП М = s(m + п + 2р) + р, N = ps(m + n + l) Для алгоритмов 7г, DW, MINOS приведены требуемое количество итераций к и время решения time (в сек) задач ЛП с точностью по функционалу е = Ю-5 (С помощью MINOS на маломощном компьютере удалось решить только 4 первых задачи)

Для больших реальных блочных задач (3000 х 240000 и более) 7г обгонял принцип разложения на порядок и выиграл у MINOS более, чем на два порядка

Таблица 3 Численное сравнение DW, MINOS и ДБМ Тг, е = Ю-5

Размеры ДБМ Г2 DW Размеры MINOS

Р s к time к time М N к time

10 68 4,0 197 15,6 1010 8100 6414 129

10 20 57 6,4 184 27,4 2010 16200 13744 544

30 55 10,1 205 43,9 ЗОЮ 24300 21226 1849

40 53 10,0 205 58,1 4010 32400 29238 3473

10 147 30,1 1806 354,5 1430 24300 - -

30 20 159 58,3 1716 669,8 2830 48600 - -

30 126 62,1 1915 1100,3 4230 72900 - -

40 137 107,3 1559 1128,5 5630 97200 - -

III Основные выводы по результатам исследования

1 Обобщен классический метод уровней оракульного типа для решения задачи минимизации выпуклой липшицевой функции /(г), определенной на непустом выпуклом компакте G, на случай, когда функция / доопределена значением +оо на многограннике G, содержащем этот компакт В обобщенном множестве уровней для точки z 6 G \ G оракул строит гиперплоскость, отделяющую z от G Получена оценка скорости сходимости обобщенного метода уровней, близкая к аналогичной оценке для классического случая Показано, что для сходимости обобщенного метода уровней, в отличие от его классического варианта, необходимо наличие непустой внутренности у множества G

Разработано семейство обобщенных методов уровней оракульного типа для решения задачи V минимизации выпуклой липшицевой функции f(z), определенной на имеющем непустую внутренность выпуклом компакте G, содержащемся в многограннике G Это семейство включает в себя все предлагавшиеся ранее классические (G = G) и обобщен-

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

2 Обобщен классический седловой вариант метода уровней оракульного типа для задачи отыскания седловой точки выпукло-вогнутой лишпицевой функции /(г) = }{х,у), определенной на непустом выпуклом компакте й = х Оу, на случай, когда б содержится в многограннике в = СххОу Получена оценка скорости сходимости обобщенного седлового варианта метода уровней, близкая к аналогичной оценке для классического случая, при наличии непустой внутренности у множества (3

Разработано семейство обобщенных седдовых методов уровней оракульного типа для задачи отыскания седловой точки выпукло-вогнутой липшицевой функции /(г,у), эффективное множество которой есть имеющий непустую внутренность выпуклый компакт в = Схх Су, содержащийся в многограннике б = (?х х Это семейство также включает в себя все ранее известные классические (С = б) и обобщенные (б С С) седловые варианты метода уровней Для методов предлагаемого семейства также получена теоретическая оценка скорости сходимости вида О (к-1'2)

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

4 Проведен широкомасштабный вычислительный эксперимент по определению практической скорости сходимости методов уровней (классических и обобщенных) применительно к решению задач ЛП блочной структуры, допускающих декомпозицию

Разработаны и протестированы три (новых) оптимизационных метода уровней для решения задач ЛП специального (блочного) типа 1) двойственный (классический) метод уровней для решения трехиндексной транспортной задачи с аксиальными суммами 2) двойственный (классический) метод уровней для решения многопродуктовой задачи снабжения с промежуточными базами, имеющими ограниченные пропускные способности, 3) прямой (обобщенный) метод уровней для решения задачи ЛП при наличии диагональных блоков и вертикального связующего блока Проверялась и на тестовых примерах нашла подтверждение гипотеза о (почти) линейной скорости сходимости метода уровней которым надежно решались все тестовые задачи с относительной точностью до 1СГ7

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

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

IV Основные публикации по теме диссертации

1 Beer К, Gol'stejn Е G, Sokolov N A Utilization of the level-method for primal decomposition m linear programming problems / Chemnitz Technische Universität Chemnitz, Fakultat fur Mathematik, 2000, Preprint 2000-13 - 1,0 п л / 0,35 n л 2

2 Соколов H А Программа прямой декомпозиции (PDLEV) задач линейного программирования, основанной на методе уровней / М ЦЭМИ РАН, 2001, препринт #WP/2001/114 - 1,5 п л

3 Beer К , Gol'stem Е G , Sokolov N A Minimization of a nondifferentiable convex function defined not everywhere // Optimization, 2002, v 51 (6) — 1,0 п л / 0,35 n я

4 Sokolov N A New variants of the generalized level method for minimization of convex nondifferential functions taking infinite values // Comput Math and Math Physics, 2007, v 47, № 12 — 1,0 n л

В том числе публикации в журналах, рекомендованных ВАК

5 Гольштейн Е Г, Немировский А С, Соколов Н А Новый алгоритм двойственной декомпозиции с приложением к задачам транспортного типа // Экономика и матем методы, 1994, т 30, в 2 — 0,5 п л / 0,15 п. л

6 Гольштейн Е Г, Соколов Н А Новый метод решения многопродуктовой транспортной задачи // Экономика и матем методы, 1995, т 31, в 2 - 0,8 п л / 0,4 п л

7 Гольштейн Е Г , Соколов Н А Декомпозиционный метод решения производственно-транспортных задач // Экономика и матем методы, 1997, т 33, в 1 — 0,5 п л / 0,85 п л

8 Бэр К , Гольштейн Е Г, Соколов Н А Об использовании метода уровней для минимизации выпуклых функций, не все значения которых конечны // Экономика и матем методы, 2000, т 36, № 4 - 0,7 п л / 0,25 п л

9 Бэр К , Гольштейн Е Г, Соколов Н А Метод отыскания седловой точки функции, область определения которой содержится в многограннике // Экономика и матем методы, 2001, т 37, JV» 3 - 0,5 п л / 0,15 п л

10 Малков У X , Гольштейн Е Г, Соколов Н, А Результаты экспериментального сравнения метода уровней и принципа разложения Данцига-Вульфа // Экономика и матем методы, 2003, т 39, № 2 - 0,4 п л / 0,15 п л

11 Соколов Н А Новые варианты обобщенного метода уровней для минимизации выпуклой недифференцируемой функции, не все значения которой конечны // Обозрение прикл и промышл матем , 2006, т 13, в 4 — 0,2 п л

12 СоколовН А О новых модификациях обобщенного седлового варианта метода уровней // Обозрение прикл и промышл матем , 2007, т 14, в 3 — 0,3 п л

13 Соколов Н А Новые варианты обобщенного метода уровней для минимизации выпуклой недифференцируемой функции, не все значения которой конечны // Журнал вычисл матем и матем физики, 2007, т 47, № 12 — 1,0 п л

14 Соколов Н А Сравнение вычислительной эффективности седловых вариантов метода уровней // Обозрение прикл и промышл математики, 2008, т 15, в 3 — 0,2 п л

3 Курсивом отмечен личный вклад автора.

СОКОЛОВ Николай Александрович

ОБОБЩЕННЫЙ МЕТОД УРОВНЕЙ С ПРИЛОЖЕНИЕМ К ДЕКОМПОЗИЦИИ

Специальность 01 01 09 — дискретная оптимизация и математическая кибернетика

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

Заказ № 39

Объем 1,0 п л Тираж 100 экз

ЦЭМИ РАН

Введение.

Глава 1. Обобщенный метод уровней для минимизации выпуклой недифференцируемой функции.

§ 1.1. Описание обобщенного метода уровней и его основных модификаций.

§ 1.2. Общая схема метода уровней.

§ 1.3. Описание новых вариантов метода уровней.

§ 1.4. Критерий окончания счета.

§ 1.5. Метод уровней с приближенным решением вспомогательных задач.

1.5.1. Приближенное решение задачи линейного программирования Лк.

1.5.2. Приближенное решение задачи квадратичного программирования В*

Глава 2. Обобщенный седловой вариант метода уровней и его новые модификации

§2.1. Описание обобщенного седлового варианта метода уровней и его основных модификаций.

§2.2. Описание новых седловых вариантов метода уровней.

§ 2.3. Обоснование седлового варианта метода уровней.

§ 2.4. Критерий окончания счета в седловом варианте метода уровней.

§ 2.5. Седловой вариант обобщенного метода уровней с приближенный решением вспомогательных задач.

2.5.1. Приближенное решение задач линейного программирования Лк и Лк в седловом варианте обобщенного метода уровней.

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

Глава 3. Применение обобщенного метода уровней к декомпозиции линейных задач.

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

§ 3.2. Прямой блочный метод решения задач линейного программирования.

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

§ 3.4. Распараллеливание в методе уровней; численное сравнение метода уровней с другими вычислительными методами.

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

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

• децентрализация процесса управления объединением (разбиение на отдельные подзадачи для каждого предприятия, входящего в объединение);

• распараллеливание вычислительного процесса с использованием многопроцессорных систем;

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

Анализу различных декомпозиционных методов посвящена обширная литература (например, [4], [31], [45], [49, глава 4], [55], [80] и многие др.).

Большинство декомпозиционных методов сводятся к одному из двух принципиальных подходов — прямой и двойственной декомпозиции.

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

V : f{z) min, g(z) ^ b, z е Z, где функции /: En —Еь g: En —у Еот, вектор b G Em, множество Z С E„, Es — s-мерное евклидово пространство, и пусть переменные разбиты на две группы 2: = (х,и), Z = X х U С Еп, х G X С ЕЯ1> и € U С Е„2, ni + n2 = п.

В прямой декомпозиции отыскание минимального значения /* задачи V производится сначала на нижнем уровне: отыскивается минимум по одной группе переменных, например, по и £ U, при фиксированном значении х G X, т. е. решается задача

V(x) : f(x) = min {/(ж, и): g(x, и) ^.b, ие U}, а затем — на верхнем уровне, по второй группе переменных, х G X:

Г = min Q(x), хеХ}.

Таким образом, для нахождения значения неявно заданного функционала 7(ж) в каждой точке х £ X последовательности поисковых точек приходится заново решать (блочную) задачу V(x), т.е. для решения исходной задачи размерности п решается серия задач размерности п2. Обычно эта процедура эффективна при щ п.

Важнейшим представителем прямых декомпозиционных методов является метод распределения ресурсов (Корнаи-Липтака) [41]. Он применим к адцитивно-сепарабельным функциям

S S f(u) = X9= и = Ui X U2 X • • • х Us, г'=1 г=1 для которых вводится в рассмотрение задача вида V: s mm gi(ui)^xu щеЩ, i = l,.,S, У^х{ ^ Ь L i=i i=1 J

Прямая декомпозиция состоит в распределении ресурса b таким образом, чтобы обеспечить минимум задачи s s

J(x) = ^2fi(xi) -)• min, ац^Ь, i=l г=1 где значения неявно заданной функции f(x) отыскиваются в результате решения S независимых оптимизационных подзадач

V(x) : Ji(xi) = min {/{(щ), д^щ) < х{, щ G Щ, г = 1,., S.

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

• при некоторых х 6 X задача Т(х) может оказаться несовместной;

• целевая функция f(x) задана неявно и оказывается негладкой, даже если f(z) и g(z) обладают высокой гладкостью.

1.2. Двойственная декомпозиция используется тогда, когда неучет некоторых ограничений задачи делает ее легко разрешимой. Вводится (обычная) функция Лагранжа (ОФЛ) вида z,y) = f(z) + (y,g(z)-b), определенная для z G Z, у € Y = Е+ = {у = (yi,., ут): у» ^ 0, г = 1,., т} (заметим, что множество Z также может содержать ограничения-неравенства, т. е. в ОФЛ переводится, возможно, только часть ограничений). При помощи ОФЛ определяется двойственная задача

V : -ф(у) = min{£(jz,у): z G Z} max, у <E Y.

При выполнении определенных условий оптимальные значения /* задачи V и ф* = max{ф(у): у G Y} совпадают. Поэтому на нижнем уровне при фиксированном у е Y решается задача нахождения значения функции ф(у), а на верхнем уровне — задача V.

Как и при прямой декомпозиции, сохраняется свойство аддитивной сепарабельности, и задача V распадается на S независимых подзадач: s (У,ь), Му) = min{/i(zi) + (y,gi(zi)): ъ Е ZJ, i = l,.,S. i= 1

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

Достоинства двойственных декомпозиционных методов:

• задача V имеет меньшую размерность, чем задача V]

• множители Лагранжа находятся автоматически;

• можно оценить сверху влияние изменения вектора ресурсов b на оптимальное значение задачи.

Недостатки двойственной декомпозиции:

• задачи V и V эквивалентны лишь тогда, когда ОФЛ имеет седловую точку, а это имеет место не для всех задач; возможно /* ф ф* (невыпуклый случай);

• могут потребоваться значительные вычислительные усилия, чтобы по найденному оптимальному значению у* задачи V восстановить оптимальное решение задачи V, т.е. найти решение задачи (при /* = ф*).

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

1.3. Прямо-двойственная декомпозиция заключается в одновременном применении к исходной задаче V и прямой, и двойственной декомпозиции. При этом задача должна иметь определенную структуру вида

V : min{/i(a;)+/2(и): gi (х) + д2 (и) ^ h, hi{x) + h2{u) ^ b2, х Е X, uEU}, т. е. отличается от рассмотренной ранее тем, что все функции, в нее входящие (f(z), g(z), h(z)), адцитивно-сепарабельны; ограничения-неравенства поделены на две группы: g(z) — mj-мерная, a h(z) — тг-мерная вектор-функции, mi + т2 — т\ переменные z, как и раньше, разбиты на две группы переменных меньшей размерности z = (х, и) Е Z — X х U, щ + п2 = п.

При прямо-двойственном подходе на нижнем уровне отыскивается решение и(х, у) (при фиксированных значениях х € X, у G Y) вспомогательной (блочной) задачи

Ф(х,у) = fi{x) + (y,gi(x) - bi) +min{/2(u) + (y,g2(u)): и e U, h2(u) ^ b2 - /ii(a:)}, а на верхнем уровне отыскивается седловая точка (х,у) функции ^(ж, у) на множестве х Е X, у G У. Данный подход эффективен при rrii <С т и щ <С п. Примером подобного подхода могут служить методы, описанные в [49], примененные к задаче со структурой окаймления и использующие в качестве отыскания седловых точек метод Эрроу-Гурвица (см. [19], [85]) либо вариант прокс-алгоритма [103], [104]).

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

1.4. При декомпозиционном подходе вместо обычной функции Лагранжа можно использовать модифицированные функции Лагранжа (МФЛ). С теорией МФЛ и численными методами на их основе можно ознакомиться, например, по работам [1], [2], [5], [13], [30], [36], [47], [97], [102] и др. Наиболее употребительной (ставшей стандартной) для решения задачи V является МФЛ ffl(z, у, 7) (при 7 > 0) вида

1 5

1) = № ~ щТ, {v2i ~ [max{0,W + 7Ы*) - bi)}]2}.

Для выпуклых задач аналог функции ф(у) вида ф(у; 7) = max {Ш(г, у, 7): z G Z} является гладкой функцией, сильно вогнутой по у, множество седловых точек функции У> 7) совпадает с множеством седловых точек обычной функции Лагранжа £(z, у) и устойчиво по г (см., например, [19], [46]). Поэтому для максимизации ip(y, 7) на У можно применять градиентные методы. К сожалению, для МФЛ свойство сепарабельности не сохраняется. Различные приемы преобразования задач к сепарабельному виду в случае МФЛ приводит к серьезному усложнению алгоритмов (см., например, [49]).

1.5;. С помощью МФЛ можно строить различные декомпозиционные методы первого порядка. Так, в [76], [НО] разработаны итеративные алгоритмы, делящие задачу на вертикальные блоки. В [28] предложен итеративный алгоритм для решения линейной двухуровневой распределительной задачи, а в [69] — итеративный алгоритм для решения общей задачи линейного программирования, в которой каждый ненулевой элемент матрицы ограничений трактуется как отдельный блок. Все эти алгоритмы являются частными случаями общего декомпозиционного подхода [14], [15], [16], [21]: оказывается, можно применять разбиение задачи произвольным образом, а не только на горизонтальные или (и) вертикальные блоки и получать алгоритмы, сходящиеся не только по функционалу, но к некоторой седловой точке задачи, при условии, что прямая и двойственная задачи разрешимы. На каждой итерации решаются задачи оптимизации симметричных МФЛ, построенных для каждого непустого блока.

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

2. Поскольку задача нахождения значения целевого функционала f(z) (или ip(y)) и/или его производных (в гладком случае) либо субградиентов (в выпуклом недифференциру-емом случае) требует значительных вычислительных усилий, то эффективный декомпозиционный метод решения задачи V (V) должен быть экономным по количеству этих вычислений. [

Теории и построению численных методов дня негладких задач посвящено много работ (см., например, монографии [9], [34], [35], [39], [56], [62], [63], [65], [77], [81] и др.).

В [51] разработана теория информационной сложности и оптимальности методов (ора-кульного типа) решения задачи вида

V : f(z) min, г € G, где f(z) — выпуклая липшицева функция, определенная на непустом выпуклом компакте G С Еп, Еп — n-мерное евклидово пространство. Не вдаваясь в подробности, отметим, что оптимальный метод невозможно существенно улучшить по числу вычислений значений и субградиентов минимизируемой функции f(z) для достижения заранее заданной относительной погрешности е > 0. В [51] найдены достаточно близкие друг к другу верхние и нижние оценки для информационной сложности и указаны алгоритмы, имеющие сложность, близкую к теоретической. Так, для шара в Е„ оценка информационной трудоемкости имеет вид к ) I n~ll2 < е < 1 («низкая» точность),

1 О (nln (1/ег)), 0 < е < п-1/2 («высокая» точность).

Среди известных оптимальных методов для низких точностей следует отметить метод субградиентного спуска [83], [81], реализующий равномерную по размерности оптимальную скорость сходимости 0(к~1/2). Метод очень простой (стоимость одного шага метода порядка 0'{п)), описывается рекуррентной формулой zk+1 = argmin \\zk - rkl(zk) - z\\, k = 1,2,., в которой т* > 0 — некоторые шаговые множители, /(гг) — субградиент функции /(г), вычисленный в точке z Е G.

Имеется много разных способов выбора шаговых множителей тк, обеспечивающих оптимальность метода для невысоких требований к точности е (наилучшим признано правило Б.Т.Поляка [56] тк = [Kzk)TKzk)]~l(fizk) — /*)» где /* = min,£g/(z)). К сожалению, метод неприемлем при отыскании приближенных решений с высокой относительной погрешностью е < п-1/2, поскольку его практическое поведение соответствует его теоретической оценке.

Для высоких точностей оптимальным является метод центров [44], [106], строящий стягивающуюся последовательность множеств {Zk}, Z\ — G,

Zk+1 = Zkf){ze En: (l(zk),z-zk) ^ 0}, k = 1,2,., где zk — центр тяжести множества Zk. Метод сходится со скоростью геометрической прогрессии со знаменателем 1—0 (1 /п), но практически непригоден из-за огромной трудоемкости итераций. Среди других методов следует отметить метод вписанных эллипсоидов [74], [75] и метод волюметрических центров [108], [111], которые имеют оценку информационной сложности вида 91(e) = О (nln(n/e)), на каждом шаге которых однократно вычисляются значение функции и субградиент и дополнительно тратится Q арифметических операций на организацию метода, причем

О (п7/2), для метода вписанных эллипсоидов, О (п3), для метода волюметрических центров.

Их основным недостатком является достаточно высокая арифметическая стоимость Q одного шага. От этого недостатка свободен метод эллипсоидов [51] с Q — O (га2), к сожалению, не являющийся оптимальным (к = У1(е) = 0 (п21п(1 /ег))). Он сходится со скоростью геометрической прогрессии со знаменателем 1 — 0 (1/п2). Метод совпадает с r-алгоритмом Шора [82], в котором осуществляется растяжение пространства вдоль очередного субградиента, при определенном способе выбора коэффициента растяжения pi шагового множителя.

3. Метод уровней для задач оптимизации и равновесия.

311. Метод уровней, различные варианты которого будут разработаны и исследованы в дальнейшем, имеет немало предшественников. В их основе лежит минимизация /^-модели функции f(z), определяемой как fk(z) = max{f(zi) + (l(zi), 2 - г,», где {zi € Z: i — 1,., к} — множество уже построенных методом точек. В качестве следующей точки Zk+\ естественно было бы взять точку zk+i минимума модели fk(z), что приводит к методу секущей плоскости Келли [89], [94]. Как оказалось, в методе Келли точка минимума модели ведет себя крайне неустойчиво и далека от истинного минимума. Хотя метод Келли и сходится, но гарантированая теорией скорость сходимости крайне низка, его е-трудоемкость не лучше, чем О для п > 2 (см. [51]). Практический опыт демонстрирует не столь безнадежно плохую, но все же неприемлемо медленную скорость сходимости.

3.2. Существенный прогресс был достигнут так называемыми bundle-методами (bundle — пучок), см. [95], [96], [98], [101], [105], [109] и др., хорошо зарекомендовавшими себя в вычислительной практике. К. Лемарешалем в [98] было предложено правило пересчета вида zk+1 = argmin j/*(z) + ~\\z - £fc||2}, в которой производится стабилизация вычислительного процесса с помощью введения квадратичного члена — штрафа за уклонения от текущей «перспективной» точки zk. (Формула напоминает о ргох-алгоритме [103], [104], zk+i = argmin,e£{/(2:) + \\z — z&||2}, примененном не к исходной функции f(z), а к ее А;-модели fk(z).) Bundle-алгоритмы (при удачно выбранных правилах подстройки штрафного коэффициента и пересчета центра регуляризации zk оказываются весьма эффективными на практике. Однако их эффективность существенно зависит от этих правил, причем правила, успешные для одних задач, могут, как отмечают сами авторы, оказаться неподходящими для других.

3.3! Метод уровней был разработан в начале 90-х годов для решения общих задач негладкой выпуклой оптимизации [99], [100] на основе bundle-методов.

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

0. Задаются параметр Л £ (0,1), число е > 0 и произвольная точка zi £ G. Полагаем к = 1.

1. Обращение к оракулу в точке zk £ G, получение значения f(zk) и субградиента l(zk). к

2. Вычисление к-го рекорда по функции /: / = min{f(zl)\ i = 1,.,к} = f(zk).

3. Определение оптимального значения к-й модели на G: fk = тш{/^(г): z £ G}. '

4. Вычисление «зазора» к-й. модели: Д^ = fk — fk и к-го уровня: Lk = fk (1 — Л)Д^.

5. Если выполнено условие Ак ^ е, то рекордная точка zk является ^-решением исходной задачи; STOP.

6. Вычисление очередной точки процесса zk+1 = argmin„eGi \\z — zk||2, где Gk = {z £ G: fk(z) < Lk}.

7. к := fc + l, к 1.

При Л —> 1 метод уровней превращается в метод Келли.

3.4. В [99], [100] метод уровней для задач безусловной оптимизации обобщен на случай решения задачи оптимизации при наличии системы ограничений и на случай поиска седловых точек выпукло-вогнутой липшицевой функции, заданной на декартовом произведении двух непустых компактов.

Пусть Gx и Gy — непустые выпуклые компакты в евклидовых пространствах Еп и Ет соответственно; f(z) = f(x,y): Gx х Gy Ei — липшицева функция, выпуклая по переменной х £ Gx при каждом фиксированном у € Gy и вогнутая по переменной у £ Gy при каждом фиксированном х £ Gx. Задача состоит в отыскании седловой точки функции /, т. е. такой точки z* = (х*, у*) £ G = Gx х Gy, что

S: f(x,y*)^f{x*,y*) = f*^f(x*,y) для любых xeGx, у eGy.

Хорошо известно, что задача отыскания седловых точек на произведении компактов функции f(z) (лемма фон Неймана) эквивалентна паре задач выпуклой оптимизации с неявно заданными целевыми функционалами и равными оптимальными значениями, именно

V : |р(х) = max f(x, у) —> min, х G Gx, yeGy

V : ф(у) = min f{x,y) -f max, у £ Gy; если X*, Y* — оптимальные множества этих задач, то Z* = X* х У* есть множество седловых точек функции f(x,y) на G, f(z*) = /* для z* G Z*.

Мера погрешности точки z = (х,у) £ G (мера близости к множеству Z*) определяется как v{z) = их(х) + иу(у) = <р(х) - ф(у), где их(х) = <р{х) — /*, vy(y) = f* ~Ф(у) — меры погрешностей двойственной пары задач V и V. Функция v(z) выпукла по г = (х, у) G G и u(z) ^ 0 для всех г£(?,а также u(z) = О тогда и только тогда, когда z G Z*. Поэтому исходная задача S отыскания седловой точки (равно как и пара задач V, V) эквивалентна задаче выпуклого программирования с неявно заданным целевым функционалом v(z) —> min, z £ G, K-z*) = 0 для всех г* G Z*.

Пусть задано число е > 0. Точку г £ G назовем е-седловой точкой задачи «S (или е-решением задачи S), если u(z) ^ е. При этом их{х) ^ £, vy(y) ^ е, т.е. компоненты (х, у) е-седловой точки S являются также и е-решениями задач V и V соответственно. Обратно, если х, у — е-решения задач V, V, то z = (х,у) — 2е-решение задачи S.

Предположим, что в каждой точке z G G вычислимы значение f(z) функции / и пара (lx(z), ly(z)), образованная субградиентом lx(z) выпуклой функции f(-,y) в точке х и суперградиентом ly(z) вогнутой функции f(x, ■) в точке у,'и пусть (в силу предположения о липшицевости /) ||/х(z) ||, ||^(г)|| ^ L < оо для любых z G G, где L — константа Липшица.

Пусть уже построена последовательность точек {zi = (xi,yi) G G: г = 1,.,A;}, для которой вычислены значения, субградиенты и суперградиенты функции: {f(zi), lx(zi), ly(zi), г — 1,., к}. Определим функции и задачи ,

Vk : <Pk(x) = max {/(г,) + (lx(zj),x - хМ -»• min, x G Gx,

Pk • Фк{у) = min {/(Zj) + (1у&),у - yj}} max, у G Gy,

Sk : vk(z) = yk(x) - ipk(y) min, z E G, k- 1,2,.; выпуклые ^-модели <pk(x), —ipk(y), vk(z) являются минорантами функционалов ip(x), —ip(y) и v(z) соответственно, они монотонно не убывают по к. Обозначим ipk'*, фк'* — оптимальные значения задач Vk, Vk, им соответствуют наборы множителей Лагранжа: а? 2*0: г = 1,.Л £a? = l}, {fi > 0: i = l,.,k, = Х}> для которых к к рк'* = min Y^ + (kte), я - ®i>), ^ = max V #(/(*) + (*„(*,•), у - Vi)). xeG1 j=l »6G» fcl

Легко показать, что ^ А^ = <£>fc'* — ■0*'*, где точка к к Zk = {хк,Ук) = ( 2 G

1=1 г=1

Схема (классического) седлового варианта метода уровней, основанного на идеях метода уровней для безусловной минимизации, такова.

0. Задаются параметр А Е (0,1),число е>0и произвольная точка zy G G.

1. Обращение к оракулу в точке Zk € G, получение значения f(zk), субградиента lx(zk) и суперградиента ly(zk).

2. Определение оптимального значения (рк■* задачи Vk

3. Определение оптимального значения фк>* задачи Vk

4. Вычисление «зазора» Ar-й модели: Д& = <рк'* — фк'* и к-го уровня: Lf. = —(1 — А)Д&.

5. Если выполнено условие Ak ^ е, то вычисляется точка zk = (xk,Tjh), которая является г-решением исходной задачи; STOP.

6. Вычисление очередной точки процесса zk+1 = argmin.6Gfc \\z — zk||2, где Gk — {z G G: uk{z) ^ Lk}.

7. к := k + 1, к 1.

3.5. В [99], [100] получена оценка скорости сходимости классического метода уровней вида к = О (е-2), которая соответствует оптимальному алгоритму для «низкой» точности (тГ1/2 <£< 1).

Если G — многогранник, то шаги 2, 3 метода уровней соответствуют решению одной задачи ЛП (для безусловной минимизации) либо двух задач ЛП (для седлового варианта), а шаг 6 — решению одной задачи КП (квадратичного программирования). Для эффективности метода уровней необходимо, чтобы эти задачи решались надежно и эффективно.

Для создания эффективных декомпозиционных» алгоритмов необходимо также, чтобы эффективно решались задачи нижнего уровня («простые» задачи), на долю которых обычно выпадает наиболее значительная часть вычислений и времени. В качестве «простых» задач чаще всего выступают задачи ЛП или КП либо задачи, имеющие специальную блочную структуру: транспортные задачи, двухкомпонентные задачи, многоиндексные транспортные и производственно-транспортные задачи, комбинаторные задачи. Выбор оракула зависит от конкретного вида решаемой задачи {V или S).

Нет необходимости много говорить о теории и методах ЛП. Этой теме посвящена многочисленная литература (см., например, [3], [6], [10], [11], [31] [32], [66], [86] и др.). Наибольшую известность имеют конечные методы симплексного типа (методы последовательного улучшения плана, уточнения оценок, сокращения невязок, модифицированный симплекс-метод и др.). Для задач ЛП большого размера с сильно разреженной матрицей используются мультипликативные алгоритмы; при заполнении места, предназначенного для хранения мультипликативного представления обратной базисной матрицы используются различные схемы «повторения» ([48]). Имеются многочисленные реализации симплекс-алгоритма (MINOS, ЛП АСУ, СПО МПР-2, ЛП/БЭСМ-6, ПАОЭМ, Омега, Оптима-2 и другие пакеты (см., например, [40], [50], [53], [54], [59]). Также разработаны итеративные алгоритмы ЛП, основанные на игровых идеях (типа фиктивной игры), методе штрафов [78], МФЛ [58], методах внутренней точки и др.

Имеется множество методов для нахождения оптимума квадратичных форм без ограничений: метод Ньютона, сопряженных градиентов, переменной метрики (квазиныотонов-ские, сопряженных направлений) и др. (см., например, [56], [62], [64]).

Среди методов КП следует отметить методы симплексного типа, сопряженных градиентов, возможных направлений и др. (см., например, [38], [43], [57], [79], [91], [112] и др.). Нами в дальнейшем для решения задач ЛП и КП активно используется разработанный

К. Шитковским алгоритм Пауэлла [92], [107] — при работе с ним в течение нескольких лет не было отказов. Тем не менее, следует отметить, что в отличие от линейных задач, нет надежных программных реализаций для решения задач КП большой размерности.

3.6. Если компакт G не является многогранником, то обычно его можно легко вписать в некоторый многогранник G (например, в n-мерный куб). Поскольку при этом функция f(z) не определена для точек z £ G\G, для сохранения выпуклости ее значения в этих точках следует принять равными +оо. Для минимизации таким образом определенной функции применяется обобщенный метод уровней (см., например, [8]). При этом для точки z € G оракул, как и в классическом методе уровней, выдает значение и субградиент функции /. Для точки z Е G\G оракул строит гиперплоскость, отделяющую z от G.

Аналогично, классический седловой вариант метода уровней может быть распространен на случай, когда компакт Gx и/или компакт Gy не является многогранником, но вписан в соответствующий многогранник Gx и/или Gy. Получающийся метод носит название обобщенного седлового варианта метода уровней (см. [20], [7]).

В литературе имеется несколько различных модификаций метода уровней (нормированный, ненормированный, с глубоким отсечением, без глубокого отсечения) для задач минимизации; также имеется несколько различных модификаций седлового варианта метода уровней. Для каждого варианта приходилось заново доказывать, что оценка скорости сходимости имеет вид v(z£) — О (А;-1/2) (в обобщенных вариантах для достаточно больших к при наличии внутренности у G). В то же время, эти модификации могут быть включены в некоторое семейство методов (отдельно для задач оптимизации и для задач отыскания седловых точек), такое обобщение можно провести в различных направлениях.

Полученная в [100] теоретическая оценка скорости сходимости классического метода уровней не слишком оптимистична, однако там же приведены результаты проведенных численных исследований классического метода уровней для задач минимизации и его седлового варианта. Эти результаты позволили предположить, что практическая скорость сходимости этих методов более высокая (близка к оптимальной оценке для высоких точностей).

4. Целью настоящих исследований являлись:

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

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

В диссертации три главы и заключение.

В главе 1 построено семейство методов уровней для решения задачи минимизации выпуклой липшицевой функции f(z), эффективное множество G которой является непустым компактом, содержится в многограннике G и, вообще говоря, не совпадает с ним. Это семейство содержит все ранее встречавшиеся (классические и обобщенные) варианты метода уровней и строит новые варианты. Обобщение производится в нескольких направлениях: параметризация «глубины отсечения»; произвольное нормирование векторов, определяющих вспомогательную задачу ЛП; вместо одного, постоянного для всех итераций алгоритма числа Л используется набор, вообще говоря, различных чисел Аг, г = 1,2,.; разрешено добавлять на каждой итерации несколько линейных ограничений; вместо единичной матрицы в задаче КП используется произвольная симметричная положительно определенная матрица; вспомогательные задачи ЛП и КП решаются приближенно. Получена теоретическая оценка скорости сходимости для методов построенного семейства.

В главе 2 производится аналогичное построение семейства седловых вариантов метода уровней для случая, когда выпукло-вогнутая липшицевая по каждой группе переменных функция f(x,y) определена на декартовом произведении непустых компактов G — Gxx Gy, каждый из этих компактов содержится в своем многограннике (т.е. Gx С Gx, Gy С Gy), но, вообще говоря, G Ф G = Gx х Gy. Построенное семейство методов содержит все ранее встречавшиеся (классические и обобщенные) варианты метода уровней (их два типа), а также содержит новые варианты. Обобщение производится в нескольких направлениях: гибрид методов первого и второго типа; произвольное нормирование векторов, определяющих вспомогательную задачу ЛП (с некоторыми ограничениями); вместо одного, постоянного для всех итераций алгоритма числа Л используется набор различных чисел Aj, г — 1,2,.; разрешено добавлять на каждой итерации несколько линейных ограничений; вместо единичной матрицы в задаче КП используется произвольная симметричная положительно определенная матрица; вспомогательные задачи ЛП и КП решаются приближенно. Получена теоретическая оценка скорости сходимости для методов построенного семейства.

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

В §3.1 построены двойственный блочный метод (ДБМ) Т\ для трехиндексной транспортной задачи с аксиальными суммами и ДБМ 72 для многопродуктовой задачи снабжения с промежуточными базами, имеющими ограниченные пропускные способности. Проведенное тестирование этих методов (классического типа) с помощью специально написанных программ на широких наборах сгенерированных случайным образом тестовых задач выявило линейную скорость сходимости исследованных методов.

В §3.2 построен прямой блочный метод (ПБМ) Л4 для нахождения решения общей задачи линейного программирования, разбитой на два вертикальных блока, один из которых состоит из нескольких диагональных блоков. Проведенное тестирование (обобщенного) ПБМ для набора построенных случайным образом тестовых задач также подтвердило высокую эффективность (линейную скорость сходимости) исследованного ПБМ.

В §3.3 построены прямо-двойственный (классического типа) метод (ПДБМ) 7з для решения производственно-транспортной задачи при наличии производства и баз с ограниченными пропускными способностями и (обобщенный) ПДБМ J\f решения задачи ЛП блочно-диагональной структуры при наличии горизонтальных и вертикальных связующих блоков. Оба алгоритма протестированы. Получены результаты, которые не столь внушительны по сравнению с ПБМ и ДБМ, но все же значительно превышают теоретическую скорость сходимости тестируемых алгоритмов.

В §3.4 приведены численные результаты по распараллеливанию ПБМ ЛЛ. Показано, что увеличение в два раза количества используемых процессоров примерно в 1,35 раза уменьшает время, требуемое для получения решения исходной задачи (при прочих равных условиях). Проведено сравнение по числу итераций и по времени счета нескольких блочных методов и симплекс-метода общего (MINOS) и специального вида (с использованием разложения Данцига-Вульфа). Полученные результаты демонстрируют преимущество предлагаемых методов, которое возрастает с увеличением количества блоков в тестируемой задаче.

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

Все основные результаты (леммы и теоремы) глав 1 и 2 получены автором и являются новыми. Предложенные в главе 3 блочные методы получены в соавторстве и также являются новыми, численное апробирование этих методов также произведено автором.

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

1. Классический метод уровней оракульного типа для решения задачи минимизации выпуклой липшицевой функции /(ж), определенной на непустом выпуклом компакте G — domf, обобщен на случай, когда f(x) доопределена на многограннике G D G как +оо. В обобщенном множестве уровней для точек х G G \ G оракул строит гиперплоскость, отделяющую х от G. Получена оценка скорости сходимости обобщенного метода уровней, близкая к аналогичной оценке для классического случая. Для сходимости обобщенного метода уровней, в отличие от его классического варианта, необходимо наличие непустой внутренности у множества G.

2. Классический седловой вариант метода уровней оракульного типа для задачи отыскания седловой точки выпукло-вогнутой липшицевой функции f(x,y), эффективное множество которой есть выпуклый компакт G = Gx х Gy, обобщен на случай, когда G содержится в многограннике G = GxxGy. Для точки (ж, у) из многогранника G, не содержащейся в G, оракул строит гиперплоскость, отделяющую (х, у) от G. Получена оценка скорости сходимости обобщенного седлового варианта метода уровней, близкая к аналогичной оцен-, ке для классического случая, при наличии непустой внутренности у множества G.

3. Разработано семейство обобщенных методов уровней оракульного типа для решения задачи минимизации выпуклой липшицевой функции f(x), определенной на имеющем непустую внутренность выпуклом компакте G, содержащемся в многограннике G. Это семейство включает в себя все предлагавшиеся ранее классические (domf = G = G) и обобщенные (G С G) методы уровней. Каждая (к-я) итерация метода содержит:

• одно обращение к оракулу (в точке хк 6 G) и получение отклика от него (в виде > некоторого набора линейных ограничений);

• -решение одной задачи ЛП и одной задачи КП, построенных при помощи информации, * полученной от оракула.

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

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

• вводится параметризация глубины отсечения (ранее этот параметр задавался одним фиксированным числом, равным 0 или 1);

• отклик оракула может представлять собой не одно линейное ограничение, а сразу несколько, причем различного типа (в зависимости от того, принадлежит ли точка х\t е G внутренности множества G, или границе G, или не принадлежит G);

• допускается произвольное нормирование векторов, задающих отклик оракула (обычно эти векторы либо совсем не нормируются, либо приводятся к векторам единичной длины);

• вместо одного числа (уровня) А 6 (0,1) можно использовать набор различных на разных итерациях чисел Аг, г ^ 1;

• вместо единичной матрицы в задаче КП может использоваться произвольная симметричная положительно определенная матрица;

• все вспомогательные задачи ЛП и КП можно решать приближенно.

Для всех методов предлагаемого семейства получена теоретическая оценка их скорости сходимости вида min f(xt) — min f(x) ^ Ck~1^2 при к ^ ко, где к — номер итерации, а константы, С и ко зависят как от параметров задачи, так и от параметров метода.

4. Разработано семейство обобщенных седловых методов уровней* оракульного типа для задачи отыскания седловой точки выпукло-вогнутой липшицевой функции /(ж,у), эффективное множество которой есть имеющий непустую внутренность выпуклый компакт G = Gx х Gy, содержащийся в многограннике G = Gx х Gy. Это семейство также включает в себя все предлагавшиеся ранее классические {G = G) и обобщенные (G С G) методы уровней. Каждая итерация седлового метода уровней содержит одно обращение к оракулу, решение одной задачи ЛП и одной задачи КП; для определения момента окончания итерационного процесса время от времени решается еще одна вспомогательная задача ЛП.

Методы седлового семейства имеют ряд отличий от предлагавшихся ранее:

• имеется два типа седловых методов уровней, отличающихся видами откликов оракула; в предлагаемом семействе рассматривается их «гибрид», когда на итерации можно применять отклики оракула первого или второго вида (либо оба сразу);

• может быть рассмотрен не один, а несколько откликов оракула, причем различного типа (в зависимости от того, принадлежит ли текущая точка {хк,Ук) G G внутренности множества G, или границе G, или не принадлежит G);

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

• вместо одного числа (уровня) Л 6 (0,1) можно использовать набор различных на разных итерациях чисел А;, г ^ 1;

• вместо единичной матрицы в задаче КП может использоваться произвольная симметричная положительно определенная матрица;

• все вспомогательные задачи ЛП и КП можно решать приближенно.

Для методов предлагаемого семейства также получена теоретическая оценка скорости сходимости вида О (А;-1/2).

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

6. Для задач минимизации были разработаны и протестированы три (новых) метода уровней для решения задач ЛП специального (блочного) типа:

• (классический) метод уровней для решения трехиндексной транспортной задачи с аксиальными суммами;

• (классический) метод уровней для решения многопродуктовой задачи снабжения с промежуточными базами (частный случай многопродуктовой транспортной задачи при наличии дуг с ограниченными пропускными способностями);

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

Первые два метода относятся к классу двойственных блочных методов, последний — к классу прямых блочных методов^

Проверялась и на тестовых примерах нашла подтверждение гипотеза о (почти) линейной скорости сходимости метода уровней: где G С Ер, Ер —р-мерное евклидово пространство, к — (достаточно большой) номер итерации метода, Ак — оценка вида mini^k:x,eG f(xi) ~ nxzG f(x) < САк. Здесь под почти линейной скоростью сходимости метода понимается, что дополнительное число итераций метода, которое требуется для увеличения точности на порядок, для каждой из решаемых задач примерно постоянно (но, естественно, зависит от задачи и параметров метода). Методом уровней надежно решались все тестовые задачи с относительной точностью до Ю-7. Во всех приведенных вычислительных экспериментах константа Д < 1.

7. Для задач отыскания седловых точек были разработаны и протестированы два (новых) метода уровней решения- блочных задач ЛП, относящиеся к классу прямо-двойственных блочных методов:

• (классический) метод уровней для решения многопродуктовой'задачи снабжения при наличии производства и промежуточных баз;

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

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

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

9. Метод уровней и его практические реализации допускают дальнейшее усовершенствование. Так, проведенные испытания показали значительный выигрыш по времени при использовании параллельных вычислений. Существенный выигрыш во времени получается и при использовании приема «обновление», при котором часть накопленной'информации о задаче теряется, но этот урон компенсируется уменьшением размеров решаемых задач ЛП и КП. Для» ускорения времени можно воспользоваться также программными реализациями/ методов ЛП и КП, которые учитывали бы структуру этих задач.

Ак < ( max }{хг) mm 1

Заключение

1. Антипин А. С. Метод градиентного типа для отыскания седловой точки модифицированной функции Лагранжа. — Экономика и математические методы, 1977, т. XIII, в. 3, с. 560-565.

2. Антипин А. С. Методы нелинейного программирования, основанные на прямой и двойственной модификации функции Лагранжа. Препринт. М.: ВНИИСИ, 1979, 74 с.

3. Ашманов С. А. Линейное программирование. М.: Наука, 1981, 340 с.

4. Бенсусан А., Лионе Ж.-JI., Темам Р. Методы декомпозиции, деецентрализации, координации и их приложения. — В кн.: Методы вычислительной математики. Новосибирск: Наука, Сибирское отд., 1975, с. 144-274.

5. Бертсекас Д. Условная оптимизация и методы множителей Лагранжа. М.: Радио и связь, 1987, 400 с.

6. Булавский В. А., Звягина Р. А., Яковлева М. А. Численные методы линейного программирования. М.: Наука, 1977.

7. Бэр К., Голъштейн Е. Г., Соколов Н. А. Метод отыскания седловой точки функции, область определения которой содержится в многограннике. — Экономика и математические методы, 2001, т. 37, № 3, с. 97-105.

8. Бэр К., Голъштейн Е. Г., Соколов Н. А. Об использовании метода уровней для минимизации выпуклых функций, не все значения которых конечны. — Экономика и математические методы, 2000, т. 36, № 4, с. 95-107.

9. Васильев Ф.П. Методы решения экстремальных задач. М.: Наука, 1980, 519 с.

10. Габасов Р., Кириллова Ф. М. Методы линейного программирования, ч. I. Общие задачи. Минск: Изд-во Б ГУ, 1977.

11. Гасс С. И. Линейное программирование (методы и приложения). М.: Физматгиз, 1961, 304 с.

12. Гилл Ф., Мюррей У., Райт М. Практическая оптимизация. М.: Мир, 1985, 509 с.

13. Голиков А. И., Жадан В. Г. Итеративные методы решения задач нелинейного программирования с использованием модифицированных функций Лагранжа. — Журнал вычислительной математики и математической физики, 1980, т. 20, JV°4, с. 874-888.

14. Голъштейн Е. Г. Блочный метод выпуклого программирования. — Доклады АН СССР, 1986, т. 288, в. 1, с. 24-27.

15. Голъштейн Е. Г. Метод декомпозиции задач линейного и выпуклого программирования. — Экономика и математические методы, 1985, т. XXI, в. 6, с. 1077-1091.

16. Голъштейн Е. Г. Метод модификации монотонных отображений. — Экономика и математические методы, 1975, т. XI, в. 6, с. 1144-1159.

17. Голъштейн Е. Г. Метод минимизации негладких квазивыпуклых функций, использующий неточные исходные данные. — Экономика и математические методы, 2006, т. 42, № 2, с. 104-110.

18. Голъштейн Е. Г. Об одном двойственном блочном методе линейного программирования. — Автоматика и телемеханика, 1994, № 12, с. 36-43.

19. Голъштейн Е. Г. Обобщенный градиентный метод отыскания седловых точек. — Экономика и математические методы, 1972, т. VIII, в. 4, с. 569-580.20.