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

• Соколов, Николай Александрович
• кандидат физико-математических наук
• 2008

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

Введение.

Глава 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

Заключение

Список литературы диссертационного исследования кандидат физико-математических наук Соколов, Николай Александрович, 2008 год

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.