Обобщенный метод уровней с приложением к декомпозиции

• Автор: Соколов, Николай Александрович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 102 с. : ил.

Глава 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 E Z,
где функции /: En —> Ei, g: En —» Em, вектор b E Em, множество Z С E„, Es — s-мерное евклидово пространство, и пусть переменные разбиты на две группы 0 = (х, и), Z = X х U С Е„, х € X С ЕП1, и Е U С Е„2, щ + п2 = п.
В прямой декомпозиции отыскание минимального значения f* задачи V производится сначала на нижнем уровне: отыскивается минимум по одной группе переменных, например, по и Е U, при фиксированном значении ж £ А, т. е. решается задача
V{х) : f{x) = min {f(x, и): g(x, и) ^ b, и EU},
а затем — на верхнем уровне, по второй группе переменных, х Е X:
/* = min {/(ж), х Е X}.
Таким образом, для нахождения значения неявно заданного функционала /(ж) в каждой точке х Е X последовательности поисковых точек приходится заново решать (блочную) задачу V(x), т.е. для решения исходной задачи размерности п решается серия задач размерности п2. Обычно эта процедура эффективна при ni п.

Важнейшим представителем прямых декомпозиционных методов является метод распределения ресурсов (Корнай-Липтака) [41]. Он применим к аддитивно-сепарабельным функциям
s s
fiu) = '52Mui)’ д{и) = ^9г{щ), U= Ul х и2 X ••• х Us,
г=1 г
для которых вводится в рассмотрение задача вида V:
( S S )
in <^2fi(ui): 9i{ui) ^ Xi, UiGÜi, i = ^ b L
^ i=i i=l J
Прямая декомпозиция состоит в распределении ресурса 6 таким образом, чтобы обеспечить минимум задачи
s s
f(x) = -► min, YlXi^b’
г=1 г
где значения неявно заданной функции f(x) отыскиваются в результате решения S независимых оптимизационных подзадач
7>(х) : fi(xi) = min {/,(«;), *(«;) < хи щ € {/;}, г = 1 S.
Достоинством прямого декомпозиционного подхода является то, что в нем движение
происходит всегда по допустимым точкам и (некоторые переменные могу быть дискретными), что существенно с практической точки зрения.
Недостатки метода:
• при некоторых х 6 X задача V{x) может оказаться несовместной;
• целевая функция f(x) задана неявно и оказывается негладкой, даже если f{z) и g(z)
обладают высокой гладкостью.
1.2. Двойственная декомпозиция используется тогда, когда неучет некоторых ограничений задачи делает ее легко разрешимой. Вводится (обычная) функция Лагранжа (ОФЛ) вида
£(*,i/) = /(*) + (y,g(z) - ь),
определенная для г е Z, у € Y = Е+ = {у = (уи ут): у{ ^ 0, г = 1 то} (заметим,
что множество Z также может содержать ограничения-неравенства, т. е. в ОФЛ переводится, возможно, только часть ограничений). При помощи ОФЛ определяется двойственная задача
V : гр(у) = min {£(z, у): z G Z} —> max, У & Y.
При выполнении определенных условий оптимальные значения /* задачи V и ф* = max [Ф(у): у £ У} совпадают. Поэтому на нижнем уровне при фиксированном у е Y решается задача нахождения значения функции 'ф(у), а на верхнем уровне — задача V.
Как и при прямой декомпозиции, сохраняется свойство аддитивной сепарабельности, и задача V распадается на S независимых подзадач:

^(у) = ~ My)=min{fiizi) + {y’9i(zi)): ZiEZi}, i = l S.

где Д* — точное решение задачи Ак, о Ск,С определяются формулами (2.20), Гк, Р — формулами (2.18).
Доказательство. Будем следовать схеме доказательства леммы 2.1. Для произвольной точки г = (ж, у) строится точка (х,у) = г = г + д(г° -г)£(3, где д = (Д* + е)/{Аг), 0 < е < Аг — Ак, х°, у0 — центры шаров радиуса г, содержащихся в б* и Оу, соответственно, 2° = (жВ силу (2.54)
Л " Р* • (
Да + 5П > Ф ^ X ^||/Л(А||((^)^-")) + ^ “ Дг*))
;=1 ‘Те
+ XI $*Ь(Д*) - - !/)) + X &Л'(2*)((<ьДг)>^ - г> - <*?)
1е-'"

^ ^ ^ ] ШД^ (2{), 2; ~ г) + ^ ) Щ ({^'(2,), 2^ — ж) — /(2^))
Ьк «=1 &'и
+ X чКД*) - {lyAzi)’Уi - у))
Как и при выводе формулы (2.28), имеем
7(/($*> 3/) ~ }{х,Ук)) < X X з(1з(ъ)>Ъ - г)
+ (1 - 7)Д*.
(2.55)
+ X иЛ(1*М)>х{ -%)- /<Д)) + X ^(/(*)“(Д/ДД № - 2/)) • (2-56)
■г'е-Ф
Из (2.55)-(2.56) следует, что
/@к,у) -1(х,Ук) ^ Д (Да + <Ь/т)>
откуда, заканчивая доказательство как в лемме 2.1, получаем утверждение леммы.
3. Если обе задачи, Ак и Ак, решаются приближенно, то
Д(г*) ^ СДа + Кйд/у ^ С(Д* + 5р) + Рдр/'у ^ СДа + С ^ С2& 1//2 + С,

С = (С£Р + ^<Ь/7), (2-57)
откуда следует, что, решая приближенно задачу Ак с погрешностями 6р ^ 0, 5р ^ 0, 7 > 0, нельзя гарантированно получить е-седловую точку при е С.
Теорема 2.2 и следствие 2.7 резюмируют содержимое пп. 1, 2.
Теорема 2.2. Пусть выполнены все предположения теоремы 2.1, приближенные решения задач Ак и Ак ищутся с погрешностями др ^ 0, др ^ 0, о 7 > 0 и Ак < Аг — др.
Тогда
А(гк) ^ СО.^1/2 + С при к>К(Аг — 6р), (2.58)
константы О, и К = К{Р) задаются формулами (2.17), (1.16).
Для нахождения е-седловой точки функции /(г) на С, приближенно решая задачи Ак и Ак, воспользуемся аналогом следствия 8 из [70].