Содержание к диссертации
Введение
Глава 1. Обобщенный метод уровней для минимизации выпуклой недифференцируемой функции 12
1.1. Описание обобщенного метода уровней и его основных модификаций 12
1.2. Общая схема метода уровней 14
1.3. Описание новых вариантов метода уровней 18
1.4. Критерий окончания счета 22
1.5. Метод уровней с приближенным решением вспомогательных задач 25
1.5.1. Приближенное решение задачи линейного программирования Лк 25
1.5.2. Приближенное решение задачи квадратичного программирования Дь 26
Глава 2. Обобщенный седловой вариант метода уровней и его новые модификации 30
2.1. Описание обобщенного седлового варианта метода уровней и его основных модификаций 30
2.2. Описание новых седловых вариантов метода уровней 34
2.3. Обоснование седлового варианта метода уровней 37
2.4. Критерий окончания счета в седловом варианте метода уровней 43
2.5. Седловой вариант обобщенного метода уровней с приближенным решением вспомогательных задач 47
2.5.1. Приближенное решение задач линейного программирования Лк и Лк в седловом варианте обобщенного метода уровней 47
2.5.2. Приближенное решение задачи квадратичного программирования 2 в седловом варианте обобщенного метода уровней 51
Глава 3. Применение обобщенного метода уровней к декомпозиции линейных задач 53
3.1. Двойственный блочный метод уровней с приложением к задачам транспортного типа 53
3.2. Прямой блочный метод решения задач линейного программирования 68
3.3. Прямо-двойственный блочный метод для задач линейного программирования с вертикальным и горизонтальным окаймлением 75
3.4. Распараллеливание в методе уровней; численное сравнение метода уровней с другими вычислительными методами 87
Заключение 95
Список литературы 98
- Общая схема метода уровней
- Приближенное решение задачи линейного программирования Лк
- Описание новых седловых вариантов метода уровней
- Прямой блочный метод решения задач линейного программирования
Введение к работе
Многие практические оптимизационные задачи имеют большие размеры, что затрудняет или делает невозможным получение их решения стандартными оптимизационными методами. В этом случае единственным способом их решения является использование специфической блочной структуры этих задач либо расчленение задач на отдельные подзадачи: исходную задачу можно представить в виде некоторой совокупности подзадач (блоков), связанных между собой общими переменными и ограничениями (их так и называют связующими). При этом отдельные блоки, как правило, имеют небольшие размеры, соответствующие им .оптимизационные задачи решаются достаточно просто. Подобного рода особенности задач позволяют эффективно использовать различные вычислительные декомпозиционные схемы, в которых вместо решения исходной задачи приходится многократно (итеративно) проводить процесс решения отдельных подзадач при фиксированных значениях глобальных (связующих) параметров задачи; локальные решения блоков используются для пересчета этих глобальных параметров, согласующих независимые решения блоков.
Помимо больших размеров исходной задачи, применение декомпозионных методов может быть вызвано другими причинами и целями, такими, как:
• децентрализация процесса управления объединением (разбиение на отдельные подзадачи для каждого предприятия, входящего в объединение);
• распараллеливание вычислительного процесса с использованием многопроцессорных систем;
• отделение хорошо структурированной-части задачи (например, линейной или транспортной) от остальных ограничений, нарушающих эту структуру.
Анализу различных декомпозиционных методов посвящена обширная литература (
Для создания эффективных декомпозиционных алгоритмов необходимо также, чтобы эффективно решались задачи нижнего уровня («простые» задачи), на долю которых обычно выпадает наиболее значительная часть вычислений и времени. В качестве «простых» задач чаще всего выступают задачи ЛП или КП либо задачи, имеющие специальную блочную структуру: транспортные задачи, двухкомпонентные задачи, многоиндексные транспортные и производственно-транспортные задачи, комбинаторные задачи. Выбор оракула зависит от конкретного вида решаемой задачи (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]).
В литературе имеется несколько различных модификаций метода уровней (нормированный, ненормированный, с глубоким отсечением, без глубокого отсечения) для задач минимизации; также имеется несколько различных модификаций седлового варианта метода уровней. Для каждого варианта приходилось заново доказывать, что оценка скорости сходимости имеет вид u(zl) — О (А;-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 = GxxGy. Построенное семейство методов содержит все ранее встречавшиеся (классические и обобщенные) варианты метода уровней (их два типа), а также содержит новые варианты. Обобщение производится в нескольких направлениях: гибрид методов первого и второго типа; произвольное нормирование векторов, определяющих вспомогательную задачу ЛП (с некоторыми ограничениями); вместо одного, постоянного для всех итераций алгоритма числа Л используется набор различных чисел Aj, г — 1,2,...; разрешено добавлять на каждой итерации несколько линейных ограничений; вместо единичной матрицы в задаче КП используется произвольная симметричная положительно определенная матрица; вспомогательные задачи ЛП и КП решаются приближенно. Получена теоретическая оценка скорости сходимости для методов построенного семейства.
Глава 3 посвящена выяснению практической скорости сходимости методов уровней на примере задач, полученных с использованием трех основных декомпозиционных принципов.
В §3.1 построены двойственный блочный метод (ДБМ) 7! для трехиндексной транспортной задачи с аксиальными суммами и ДБМ % для многопродуктовой задачи снабжения с промежуточными базами, имеющими ограниченные пропускные способности. Проведенное тестирование этих методов (классического типа) с помощью специально написанных программ на широких наборах сгенерированных случайным образом тестовых задач выявило линейную скорость сходимости исследованных методов.
В §3.2 построен прямой блочный метод (ПБМ) Л4 для нахождения решения общей задачи линейного программирования, разбитой на два вертикальных блока, один из которых состоит из нескольких диагональных блоков. Проведенное тестирование (обобщенного) ПБМ для набора построенных случайным образом тестовых задач также подтвердило высокую эффективность (линейную скорость сходимости) исследованного ПБМ.
В §3.3 построены прямо-двойственный (классического типа) метод (ПДБМ) 7з для решения производственно-транспортной задачи при наличии производства и баз с ограниченными пропускными способностями и (обобщенный) ПДБМ N решения задачи ЛП блочно-диагональной структуры при наличии горизонтальных и вертикальных связующих блоков. Оба алгоритма протестированы. Получены результаты, которые не столь внушительны по сравнению с ПБМ и ДБМ, но все же значительно превышают теоретическую скорость сходимости тестируемых алгоритмов.
В §3.4 приведены численные результаты по распараллеливанию ПБМ Л4. Показано, что увеличение в два раза количества используемых процессоров примерно в 1,35 раза уменьшает время, требуемое для получения решения исходной задачи (при прочих равных условиях). Проведено сравнение по числу итераций и по времени счета нескольких блочных методов и симплекс-метода общего (MINOS) и специального вида (с использованием разложения Данцига-Вульфа). Полученные результаты демонстрируют преимущество предлагаемых методов, которое возрастает с увеличением количества блоков в тестируемой задаче.
В заключении сформулированы основные результаты и научные выводы проведенного исследования эффективности метода уровней для задач оптимизации и равновесия.
Все основные результаты (леммы и теоремы) глав 1 и 2 получены автором и являются новыми. Предложенные в главе 3 блочные методы получены в соавторстве и также являются новыми, численное апробирование этих методов также произведено автором.
Общая схема метода уровней
Метод уровней можно применять к различным задачам (минимизация, поиск седловых точек, решение вариационных неравенств и т.д.). Ко всем этим задачам применим общую вычислительную схему метода, которую мы опишем, определив вначале оракул. Пусть Q ф 0 —- выпуклый компакт (например, точка), содержащийся в некотором многограннике Q С Е (Е — конечномерное пространство). Нашей целью является нахождение какой-нибудь точки из Q либо приближение к множеству Q с некоторой точностью. Каждой точке z Є Q приписано непустое множество ответов (откликов) оракула B(z) = {(b(z), P(z))}, ответом оракула считается пара (b(z),(3(z)), где b(z) — вектор, /3(z) — число. Множество B(z) содержит набор b(z) = 0, /3{z) — 0 лишь для точек z Є Q . Для остальных наборов 6(-г;) ф 0 и каждое полупространство точек у є Е, для которых выполнено неравенство (b(z),y-z)+P(z) 0, (1.2) содержит множество Q . В описываемом методе уровней при z Є Q \ Q оракул выдает один или несколько наборов векторов b = b(z), \\b(z)\\ ф 0, и чисел /5 = /5( ), (Ь,Р) Є В(г), таких, что для каждого набора выполнено (1.2), если же оракул определяет b(z) = 0 и (3(z) = 0 для некоторой точки z Є Q, то заведомо z Є Q . Опишем вариант обобщенного метода уровней, использующий введенный оракул. Зададим множества SQ = 0, Ао = 0, Qo = Q я число щ = 0. Выберем положительно определенную симметричную матрицу Н и произвольную точку Z\ Q. Пусть уже построено к (к 1) точек Zi Є Q, і = 1,2,..., к, и определено множество 5fc_i, Sfc_i = Пк \. С точкой 2fc свяжем Шк (тк 1) откликов оракула, т.е. зададим т,к наборов векторов bj = bj(zk) и чисел / = /3jyk(zk), j . Jk = {n -i + 1,... ,nfc_i + т }, и будем считать, что для каждого набора выполняется условие (1.2). Положим Sk = Sfc-i U Jk, где I Jjt = mfc, 5fc = Пк = Пк-і+тпк. В отличие от [70], где предполагалось, что все числа Pj,k 0) будем считать, что среди Шк чисел (3jtk, j Є Jfc, хотя бы одно неотрицательно. Обозначим Uk номер одного из этих неотрицательных чисел (их может быть несколько), ик Є Jk, т. е. pVkJl 0. Далее будем предполагать, что 6j- ф 0 для всех j Є Jk (иначе точка zk Є Q ). Будем предполагать также, что многогранник Qk вида Qk = {z Є Q : (bj,z-Zi)+pjtk 0, j Є J{, г = 1,...,k}, где числа Pj,k-i для всех j Є Ji, і = 1,...,к — 1, является непустым множеством и содержит Q . Заметим, что если бы числа (3jtk, j Є J І, і = 1,..., к — 1, не зависели от к, то непустота многогранника Qk была бы очевидна.
Лемма 1.2. Пусть исследуемый вариант обобщенного метода уровней имеет следующие параметры: 0 А Ау А 1 для всех Xj Є Ак и \\Ь3\\ В для всех j Є Sk, к = 1,2,..., где ответы оракула задаются системой неравенств (1.2). Пусть также d — диаметр Q, и — число обусловленности положительно определенной симметричной матрицы Н. Тогда последовательность {А }, которую вырабатывает метод уровней, удовлетворяет условиям леммы 1.1 при с\ = А и с% = (Bdy/Ц/Х)2.
Доказательство этой леммы также проводится по стандартной схеме [25], [100]. Ниже она будет доказана в более общем виде (см. лемму 1.7), в том числе для случая, когда при определении множества Qk{ -k, Afc) и, следовательно, новой точки zk+\ используется приближенное решение Afc Ак задачи Лк вместо ее точного решения Д . Заметим, что что при доказательстве неравенства к = (сз/Д&)2, из которого следует оценка (1.6) леммы 1.1, в импликации ( ) были использованы значения 1 г г + s к. Поэтому числа _ Afc= min Ay, Afc= max Aj, fc = max Ь,- l J n . l J nfc 1 можно использовать в константах с\ и сг леммы 1.2 вместо чисел А, А и В, соответственно. Обозначим Qk = qk(Bk,d1Xk,Xk ) = - , Q = q(B,d,X,X,a)= Вр/Ї_. (L7) Объединяя результаты лемм 1.1-1.2, получаем следующее утверждение. Следствие 1.1. При соблюдении условий леммы 1.2 для последовательности {Дд;}, вырабатываемой методом уровней, имеет место оценка &k Qkk-1/2 Qk-V2, к = 1,2,.... (1.8) Рассмотрим теперь вариант оракула, соответствующий обобщенному методу уровней. Пусть выпуклый компакт Q содержится в многограннике Q; в свою очередь, Q содержит Q (множества Q и Q определены ранее). Множества откликов оракула Jk и Sk разделим на два непересекающихся подмножества: Jk = J kU J k, J k П J k = 0, S k = Ui j jt J-, Sk = Ui fc i i к = 1 2,— Это разделение производится по принципу принадлежности точки zk множеству Q. К первому типу относим точки zk Є int Q, для них любой отклик оракула гарантирует лишь то, что в полупространстве, задаваемом линейным неравенством (Г.2), содержится множество Q . Ко второму типу отнесем точки zk Є Q\Q, для них любой отклик оракула гарантирует, что полупространство, задаваемое неравенством (1.2), отделяет zk от Q. Для граничных точек zk Є 8Q оракул может выдавать отклики как первого, так и второго типов.
Замечание. При выполнении условий леммы 1.2 последовательность чисел {Afc} сходится к нулю. Лемма 1.3 доказана в предположении о наличии у множества Q непустой внутренности (шара радиуса г 0). Без этого условия нельзя гарантировать сходимость последовательности {zk} ни к множеству Q , ни даже к множеству Q. Это подтверждает приводимый ниже пример.
Приближенное решение задачи линейного программирования Лк
В дальнейшем будет рассмотрена общая схема метода уровней, в котором вспомогательные задачи ЛП Лк и КП Бк решаются не точно, а приближенно. Пусть (jzjt, Ак) — точка, удовлетворяющая ограничениям задачи (1.3) и пусть выполнены неравенства 0 Ак-5 Ак Ак, Afc+1 Afc, к = 1,..., (1.31) где Ajk — оптимальное значение задачи (1.3). Первая группа неравенств (при малых значе-ниях 5) означает, что (zk, Ак) можно считать приближенным решением задачи Лк, вторая группа обеспечивает монотонное невозрастание последовательности {Ajt}. В дальнейшем нас будут интересовать ненулевые приближенные значения задачи Лк, т. е. ситуация, когда при А 0 выбираемое приближенное значение Ак также больше нуля, а невозможность отыскания А - ф 0 при некотором к означает, что Ак = 0. Замечание. При переходе от k-ii к (к + 1)-й итерации к ограничениям предыдущей задачи ЛП добавляется тк ограничений. Если (zk,Ak) — точное решение задачи Лк и zk удовлетворяет всем новым (дополнительным) ограничениям, то (zk, Ак) является также решением задачи Лк+і, т.е. Afe+i = А и нет необходимости решать заново задачу Лк+і. Это же относится и к приближенному решению задачи ЛП, поэтому требование монотон-ного невозрастания {Ак} является довольно естественным. Но можно формально ввести в задачах Лк дополнительное ограничение вида t Ajt_x, к 1, До = со. Это ограничение является излишним при поиске точного решения линейной задачи, но гарантированно обеспечит монотонное невозрастание последовательности Ак.
В силу (1.31) и леммы 1.2 (см. ниже доказательство леммы 1.7 при тк = 0) для {Ак} имеет место та же оценка, что и для {Ак} вида (1.8), т.е. А Qk ll2, к 1. Из опреде-ления Ajt получаем следующие аналоги леммы 1.4 и теоремы 1.1. Лемма 1.6. Пусть выполнены все условия леммы 1.4 и 0 5 Аг. Если Ак Акг 5, то А Акг и имеет место оценка f -f CkAk C(Ak + 5), где константы Ск и С определяются, соответственно, формулами (1.13) и (1.17). Лемма 1.6 означает, что решая приближенно задачу Лк с погрешностью 5, нельзя гарантированно получить е-минимум исходной задачи при є С 5. Теорема 1.3. Пусть выполнены все предположения теоремы 1.1, приближенное ре-шение задачи Лк ищется с погрешностью 6 0 и Ак Аг — 5. Тогда fk-Г C(Q к 1/2 + 5) при к К(Аг - 5), (1.32) константы Q и К = К(z) задаются формулами (1-7), (1.16). Для нахождения є-минимума исходной задачи воспользуемся аналогом следствия 1.8 и выберем подходящую точность 5! 0 решения задачи Лк Следствие 1.9. Пусть выполнены условия теоремы 1.1 и пусть є 0, 0 6 тіп{Аг,С 1є}, где константа С задается формулой (1.17). Тогда е-минимум функции f(x) на G можно найти за кє итераций, причем ке 1+ тах{К(є/С - 5),K(Ar -6)}. (1.33) В частности, если AF L и є Ld, то кє 1 + К (є/С — о ); если є Ld, то кє 1 + К(Аг-5).
Оценка (1.32) показывает, что для «оптимального» выбора точности 5 = 5к решения задачи ЛП Лк при к — оо желательно, чтобы выполнялось условие 8к = О {Ак), например, 0 6к ЗАк, где 0 б 1. Тогда (1 - 6) Ак Ак - 5к Ак Ак и при к K(Ar - 6к) 1—0 1—0 Для нахождения е-минимума функции / на G можно приближенно решать задачу ЛП Л к. Обозначим А к — точное, А к — приближенное решение задачи Л к. Пусть при некотором к 1 погрешность 0 А к—А к 5 и множество J k ф 0. Тогда для нахождения е-минимума исходной задачи достаточно приближенно решать задачу Л к с точностью є — 5 0. Это следует из цепочки неравенств Гк - Г АІ А + 8 є - 5 + 5 = є. 1.5.2. Приближенное решение задачи квадратичного программирования Вк Пусть zk+\ Є G — приближенное решение задачи КП Вк, т. е. такая точка из множества Qk(Ak,Ak), для которой (H(zk - Zk+i), zk — zk+i) (H(zk - zk+i), zk - zk+i) (H(zk-zk+i),zk-zk+i)(l + ri), (1.34) где тк (k = 1, 2,...) — относительная погрешность по функционалу решения задачи КП Вк, Zk+i — ее точное решение. Применив разложение Н = (Н)2, где Н — также симметричная положительно определенная матрица, имеем \\H(zk - zfc+1)2 № - zk+l)\f (1 + rl)\\H{zk - zk+l)\t (1.35) Из свойств операции проектирования имеем также неравенство tf( fc - zk+1)f \\H(zk+1 - zk+l)\f + \\H(zk - zk+1)\\2 (угол между векторами H(zk — zk+i) и H(zk+i — zk+i) не может быть острым), откуда следует (с учетом (1.34)) \\H(zk+1-zk+l)\\ Tk\\H(zk-zk+l)\\. (1.36) Поэтому тк молено считать относительной погрешностью (по переменным) решения задачи КП Вк ( в метрике -я). Пусть последовательность {тк} такова, что оо 5 оо. (1.37) Положим оо 5 = ]Г(2т, + т). (1.38) к=1 Лемма 1.7. Пусть выполнены все предположения леммы 1.2, задача Вк решается приближенно с погрешностью тк, к 1, а также выполнены условия (1.34), (1.37) и (1.38). Тогда последовательность {Ак} {точных или ненулевых приближенных) решений задач Лк, вырабатываемая методом уровней, удовлетворяет условию (1.6) при С\ = X и, c2 = {Bd r1)2 {l + S).
Описание новых седловых вариантов метода уровней
Опишем новые варианты метода уровней для нахождения на выпуклом компакте G седловых точек выпукло-вогнутой функции f(z), определенного в предыдущем параграфе. Как и прежде, выберем произвольную точку Z\ Є G. Зададим множество Ло = 0, также выберем числа Ло Є (0,1) и FQ 0 (например, Л0 = 1/2, FQ = 1), введем симметричную положительно определенную матрицу Н (с собственными числами 0 hm\n --- hmax и числом обусловленности ц = /imax/ min)- Назначение этих величин будет указано ниже в процессе описания метода. Пусть уже построено к (к 1) точек z% Є G, і = 1,2,... ,к. Ранее накопленное множество откликов оракула Sk-i, Щ-і — \Sk-\\ (So полагаем равным 0, щ = 0), в точке zk пополним тк (пік 1) откликами оракула Зк — \пк-\ + 1, , Щ-і + пік}, \Jk\ — w&, и положим Sk = Sfc-i U Jk = {1, .., пк}, где пк = Щ-1 + тк.
В отличие от описанных ранее методов уровней первого и второго типа, количество откликов оракула в предлагаемом методе не обязано быть равным единице. Так, для точек zk Є intG субдифференциал dxf(zk) и/или супердифференциал dyf(zk) могут содержать не по одному элементу, а множества различных субградиентов/суперградиентов. Аналогично, для точек zk Є G \G существует бесконечное множество различных гиперплоскостей, отделяющих Zk от G. Для граничных точек множества G можно одновременно применять отклики оракула вида 1 и вида 2. Поэтому мы полагаем далее, что оракул может предложить тк 1 (различных) откликов в точке zk.
Виды откликов_рракула описаны в 2.1. Отклики первого вида (zk Є intG) и частично вида 3 (zk Є dG) обозначим J k, они порождают два подвида неравенств. К первому подвиду J Qk, \J Qk\ = m ok, отнесем неравенства вида иЛ\ [(lxj(zk),x -хк) (lyj{zk), у - ук)] +tvx 0, ко второму подвиду J[k, \J lk\ — m lk, отнесем, соответственно, пару неравенств вида + о [(lxj(zk),x - хк) + f(zk)] - tx 0, -F0 [{lyj(zk),y - Ук) + /Ы] + ty 0.
Здесь Fj(zk) (j Є Jofc), FQ — положительные числа (задаваемые пользователем), f(zk), h(zk) = (lxj(zk), —lyj(zk)) (0,, 0) — информация, выдаваемая оракулом (см. (2.2)). Дадим необходимые пояснения. В откликах первого подвида, в отличие от откликов второго подвида, не используется значение функции f(zk) в точке zk. Отклик оракула первого подвида дает одно неравенство, в котором присутствуют одновременно переменные tx и ty, отклик второго подвида составляют два неравенства, в каждом из которых имеется своя переменная.
Выбор подвида отклика может принадлежать либо оракулу, либо пользователю. В первом случае предполагается, что в отличие от методов уровней первого и второго типа, в которых вид отклика оракула фиксирован (для первого типа J k = J Qk, для второго типа J k = J[k), в предлагаемом варианте метода уровней устройство оракула конструктивно таково, что он может выдавать отклик «смешанного» вида (т. е. либо первого, либо второго подвида).
В случае, когда выбор подвида отклика предоставлен пользователю, мы предполагаем, что оракул выдает полную информацию в точке zk Є G (т.е. число /() и вектор l(zk)), но по каким-то своим соображениям пользователь выбирает тот или иной подвид. В предлагаемом методе уровней возможно масштабирование неравенств первого подвида с помощью уже упомянутых чисел Fj(zk) 0, j Є J Qk. Масштабирование неравенств второго подтипа не обязательно (можно положить FQ = 1), но иногда может быть полезно (например, в случае, когда неравенства первого подвида нормированы так, что Fj(zi) = 1 для всех j Є J Qi, і — 1,2,..., для нормировки неравенств второго подвида можно взять FQ 1/L). Ниже будет показано, что 1] откликов оракула второго подвида (где S[k = U JIJ) «эквивалентно» \S[k\ откликам оракула первого подвида, т.е.-произвольность нормировки неравенств, соответствующих откликам первого подвида, по сути компенсируется большим количеством неравенств для откликов второго подвида (см. ниже (2.12), с. 36).
Предлагаемый вариант обобщенного метода уровней использует информацию, задавав- мую оракулом, но он может ее преобразовывать (например, по-своему нормировать вектор Ij(zi) и/или вектор aj(zi), задающий отсекающую гиперплоскость). Заметим еще раз, что при G = G, m,j = 1, F0 = 1, HQ = I (I — единичная матрица, ц = 1), Xj = const Є (0,1) обобщенный седловой метод уровней совпадает с классическим вариантом метода уровней первого типа (если S[k = 0) или второго типа (при S Qk = 0).
Прямой блочный метод решения задач линейного программирования
В [73], [87] на примере задач ЛП, разбитых на два вертикальных блока, строится прямой блочный метод (ПБМ), в основе которого лежит обобщенный метод уровней, изложенный в главе 1; в [8], [73], [87] приведены результаты тестирования ПМБ.
Итак, для рассматриваемой задачи V в каждой точке х Є G построенный оракул определяет, выполнено ли условие х Є G (в этом случае он вычисляет значение f(x) и субградиент 1(х) Є df(x)) или нет (в этом случае он выдает информацию, позволяющую построить гиперплоскость, разделяющую х a G). Поэтому к задаче V можно применить любой вариант обобщенного метода уровней, описанного в главе 1. Мы ограничимся лишь двумя: ненормированным и нормированным методами с глубоким отсечением, с одним откликом оракула на каждой итерации (пік = 1, F — 1 или Fk = 1(хк) Є df(xk), Рк = 1, Ak = 1, Afc = 1/2). Они генерируют два ПБМ, Л4 и Л4, которые были опробованы на решении задач ЛП блочно-диагональной структуры.
Далее мы будем рассматривать частный случай задачи V, для которого тх = ти = О (матрицы Ах и Ви отсутствуют), пх = N0, пи = к=і к, т = Ylk=i k, К 1. Кроме того, матрица В заполнена К диагональными блоками Вк размера Мк х Nk , матрица А (в дальнейшем будем называть ее связующим блоком), векторы b (правых частей), д (цели), и (переменных) и и (верхних границ на переменные) разбиты на соответствующие части. проценты заполненности матриц А и Вк выбирались независимо и случайно из диапазона (20,40); в матрице А нет пустых столбцов, в матрицах Вк нет пустых строк и столбцов; коэффициенты матриц выбирались случайным образом в диапазоне (0,10); в качестве верхних границ х, й на переменные использовалось значение 10; оптимальные решения задачи V и задачи, двойственной к ней, задавались случайным образом в диапазоне (0,10); векторы bjt, дк, с строились так, чтобы в оптимальной точке выполнялись условия оптимальности, причем там, где выполнялось строгое неравенство, модуль отношения разности левой и правой частей неравенства к его левой части в процентах задавался случайным образом в диапазоне (0,20); множество G, где f(x) +СО, заведомо по построению имело intG ф 0.
Вычислительный эксперимент был проведен с помощью ПК Pentium-166 на множестве тестовых задач при трех значениях К Є {5, 20,128}; Мг — 10, N% = 15, г = 1,..., К (т. е. блоки одного размера 10 х 15); ЛГ0 є {5,10,20,30,..., 200}. Для каждой пары (К, No) решалась серия из 15 тестовых задач, после чего результаты усреднялись. Задача считалась решенной, если удавалось найти ее приближенное решение с заранее заданной относительной точностью є = 10 s. Если максимальное значение (равное —/ ) задачи (3.31) заранее известно (а в генерируемых задачах это так), то был использован критерий прерывания счета вида (Я-Г)/(1 +ІЛХ С (3-32) где fk = mini jjcfc f(xt) — текущее рекордное значение по функционалу, є — (требуемая) относительная точность. Также рассматривался случай, когда информация о / отсутствует. В этом случае для ПБМ М использовался критерий А /(1 +/) є, а для ПБМ М. — критерий mm{A k,d\\lk{xk)\\} 1 + ІЯІ где А к — оптимальное значение задачи Л к, hi k) 9/(хк), d — диаметр множества G.
В вычислительном эксперименте все задачи решались с пятью относительными точностями: є — 10 s, s Є {3,4,5,6,7}. Начальное значение хі далее задавалось как центр G (в [70]) либо Xi — 0 (в [87]). Как и для ДБМ, был использован вычислительный прием «обновление».
Каждому варианту ПБМ в табл. 3.9 соответствует таблица из 15 строк и 10 столбцов. Строки таблицы отвечают различным значениям NQ. Каждая из трех троек столбцов связана с соответствующей относительной точностью полученного приближенного решения, причем в первом столбце тройки помещено среднее число к итераций, затраченных на получение приближенного решения, во втором столбце — число итераций kdom, отвечающих ХІ Є G, в третьем столбце содержится среднее время time (в сек.), затраченное ПБМ для достижения заданной точности є = 10_s, s Є {3,5,7}.
Анализ содержания табл. 3.8, 3.9 позволяет сделать следующие выводы: -алгоритм АЛ работает стабильно; -критерий остановки счета (3.33), связанный с решением задачи А к, достаточно эф фективен; алгоритм Л4 целесообразно использовать в варианте Л4з 3.2.3: В [73] описана программа prog, предназначенная для минимизации недиффе-ренцируемых выпуклых функций (не все значения которых конечны) на многограннике с помощью обобщенного метода уровней. Ее основное использование в [73] — с помощью прямого декомпозиционного подхода решение задачи ЛП, разбитой на два вертикальных блока, один из которых имеет блочно-диагональную структуру, причем блоки, его составляющие, имеют небольшие размеры.
В программе prog в качестве решателя используется вариант программы QL К. Шит-ковского [92], реализующий весьма эффективный и надежный алгоритм Пауэлла решения квадратичных задач при наличии линейных ограничений. Но в prog, кроме квадратичной задачи Вк, нужно на каждой (А;-й) итерации решать задачи ЛП Лк и Л к, а также для определения ответа оракула — линейные задачи V\{x{) и V2(xi)- В этом случае к соответствующим линейным функционалам добавляется квадратичный член вида е(х — хк)2/2, где є 0 — небольшая константа (обычно є — Ю-5). Кроме того, задачи Лк и Рг(ж) переписаны в prog как задачи минимизации.
Для использования программы prog нужно написать процедуру fun. В случае минимизации функции, заданной явно, такую процедуру написать несложно; в случае прямой декомпозиции, который мы рассматриваем, f(x) задана неявно как результат вычислительных действий, и создание такой программы представляет определенные трудности. Поэтому в [73] приведен текст процедуры fun для решения задачи ЛП, в которой исходная матрица задачи имеет блочную-диагональную структуру с К блоками различных размеров. Эту процедуру можно принять за образец при составлении собственной процедуры fun. Она использует в качестве решателя ту же программу QL, которая применяется и в самом методе уровней. Она надежна, но медленна и не имеет возможности работать с уже накопленной ранее информацией о решениях блочных задач.
Итак, реализация прямо-двойственного декомпозиционного метода сводится к отысканию седловой точки некоторой выпукло-вогнутой функции на декартовом произведении многогранников, причем в общем случае эта функция определена конечными значениями не во всех точках декартова произведения, а в качестве оракула можно использовать симплекс-метод.
