ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2007, том 47, < 7, с. 1151-1157
УДК 519.658.4
УЛУЧШЕНИЕ ЛАГРАНЖЕВЫХ ОЦЕНОК В ЗАДАЧАХ ОПТИМИЗАЦИИ1)
© 2007 г. И. С. Литвинчев
(119991 Москва, ул. Вавилова, 40, ВЦ РАН) e-mail: litvin@ccas.ru
Поступила в редакцию 01.09.2006 г.
Переработанный вариант 09.01.2007 г.
Рассматривается лагранжева релаксация ограничений и соответствующие оценки оптимального значения исходной задачи оптимизации. Для случая невыполнения условий дополняющей нежесткости из-за невыпуклости исходной постановки или неоптимальности множителей Лагранжа рассмотрены способы улучшения классических лагранжевых оценок. Приводятся примеры целочисленных и выпуклых задач, для которых модифицированные оценки лучше классических лагранжевых. Библ. 17.
Ключевые слова: лагранжевы оценки в задачах оптимизации, улучшение лагранжевых оценок, задачи оптимизации.
ВВЕДЕНИЕ
Многие задачи оптимизации большой размерности, как непрерывные, так и целочисленные, имеют специальную структуру ограничений, которая может быть использована при построении эффективных методов решения (см. [1]). Одним из наиболее общих примеров такой структуры является случай, когда все условия задачи можно разделить на так называемые "хорошие" и "плохие". Иными словами, исходная задача решалась бы существенно проще, если бы в ней были оставлены только "хорошие" ограничения. Примером таких постановок может служить задача оптимизации с блочными и связывающими ограничениями и целевой функцией, сепара-бельной по блочным переменным. Удаление (релаксация) связывающих ограничений приводит к декомпозиции оставшейся задачи на ряд независимых подзадач меньших размерностей.
Одним из хорошо известных способов использования указанной специальной структуры является лагранжева релаксация "плохих" ограничений. В этом случае "плохие" ограничения игнорируются, но в целевую функцию добавляется "штрафное" слагаемое, характеризующее нарушение этих ограничений. В классическом случае такой мерой отклонения от допустимости служит линейная комбинация невязок ограничений, взятых с коэффициентами, называемыми множителями Лагранжа. Полученная лагранжева задача, рассматриваемая при фиксированных множителях, содержит только "хорошие" ограничения и во многих случаях существенно проще исходной. Важным свойством лагранжевой задачи является то, что ее оптимальное значение дает верхнюю (для задач максимизации) оценку оптимального значения исходной задачи. Задачу выбора наилучших, т.е. минимизирующих верхнюю оценку множителей Лагранжа принято называть лагранжевой двойственной задачей. Известно, что для невыпуклых (например, целочисленных) задач значение двойственной задачи может и не совпадать с оптимальным значением исходной. Тем не менее получение и уточнение оценок исходного оптимального значения играет существенную роль как при построении численных методов решения (например, в различных вариантах метода ветвей и границ), так и при оценке их сходимости, позволяя оценить близость по функционалу текущего и оптимального решений.
Список литературы по лагранжевой релаксации, ее обобщениям и приложениям огромен. Отметим лишь несколько публикаций, оказавших существенное влияние на развитие исследований по дискретной оптимизации: работы [2]-[6], а также обзоры [7]-[13].
В данной работе рассматривается возможность улучшения классических лагранжевых оценок оптимального значения, основанная на оценке штрафного слагаемого, вводимого в функцию Лагранжа. При определенных условиях выпуклости и регулярности это слагаемое обраща-
1) Работа выполнена при финансовой поддержке РФФИ (код проекта 06-01-81020-Бел_а).
ется в нуль при подстановке в него оптимальных множителей Лагранжа и исходного оптимального решения (теорема о дополняющей нежесткости, см. [1]). Однако для невыпуклых (например, целочисленных) задач оно может отличаться от нуля даже для оптимальной прямо-двойственной пары, а также для выпуклых задач, если множители Лагранжа не оптимальны. Вводится вспомогательная задача оптимизации, служащая для оценки указанного штрафного слагаемого и используемая для построения модифицированных лагранжевой оценки и двойственной задачи. Рассматриваются случаи, когда решение вспомогательной задачи существенно проще решения исходной. Изложение основных построений проводится для задач максимизации линейной целевой функции при линейных ограничениях, включаемых в функцию Лагранжа, и дополнительных прямых ограничениях, которые могут быть невыпуклыми, содержать условия целочисленности и т.д.
1. ОСНОВНЫЕ ПОСТРОЕНИЯ Исходная задача рассматривается в виде
z* = max^x | Dx < d, x e X}, (P)
где D e R™ x ", X с [Rn, а вектор-столбцы c, d, x и матрица D имеют согласованные размерности. Ограничения Dx < d считаются "плохими", т.е. без них исходная постановка существенно упрощается. Обозначим через x* оптимальное решение задачи (P).
Выпуклую релаксацию задачи (P) определим так:
zR = max{cTx | Dx < d, x e conv(X)}, (PR)
где conv(X) обозначает выпуклую оболочку множества X. Поскольку X с conv(X), то z* < zR. В дальнейшем будем предполагать, что для задачи (PR) выполнены условия дополняющей нежесткости uR (DxR - d) = 0. Здесь xR, uR - оптимальные решение и множители Лагранжа в релак-сированной задаче.
Пусть u = {u} > 0 есть ™-мерный вектор множителей Лагранжа. Лагранжева задача определяется следующим образом:
z(u) = max{cTx + uT(d- Dx)}.
x e X
Предположим для простоты изложения, что эта задача имеет оптимальное решение для всех u > 0. Поскольку x* допустим для лагранжевой задачи, то
cTx *+ uT( d - Dx * )< z (u) Vu > 0.
Кроме того, поскольку x* допустим в (P) и u > 0, то uT(d - Dx*) > 0 и мы получаем следующую хорошо известную (см. [3], [10]) лагранжеву оценку:
z* < z(u) Vu > 0. (1)
Наилучшая (наименьшая) лагранжева оценка и соответствующие множители Лагранжа u* определяются из решения двойственной задачи
z (u *) = min z (u ) = wD. (D)
u > 0
Если множество X выпукло, то при определенных условиях регулярности (см. [1]) выполняется условие дополняющей нежесткости (u*)T(d - Dx*) = 0. Тем не менее для u Ф u* величина uT(d - Dx*) может быть строго положительна. Если же множество X невыпукло, то величина uT(d - Dx*) может быть строго положительна и при u = u*. Таким образом, можно ожидать, что за счет более точного оценивания слагаемого u^d - Dx*) в неравенстве c^x* + u^d - Dx*) < z(u) можно улучшить лагранжеву оценку (1) и соответственным образом модифицировать двойственную задачу (D).
Предположим, что имеется некоторая априорная информация об оптимальном решении x*
задачи (P). Именно, пусть задано множество Wс I" такое, что x* e W. Будем называть множество Wлокализацией оптимального решения x*, или просто локализацией. Множество Wможет быть получено путем комбинации исходных ограничений, в результате опроса экспертов и т.п.
Обозначим через 0(u) оптимальное решение следующей вспомогательной задачи при u > 0:
0( u) = min uT (d - Dy). (AP)
y e W
Утверждение 1. Пусть Wесть локализация. Тогда для любого u > 0 выполнено соотношение
z* < zM(u)= z(u) - 0(u), (2)
которое будем называть модифицированной лагранжевой оценкой. Наилучшая оценка этого вида определяется из модифицированной двойственной задачи
Wmd = minzM (u). (MD)
u > 0
Доказательство. Из определения z(u) и условия x* e X следует, что z* < z(u) - uT(d - Dx*) для всех u > 0. Тогда имеем
z* < min{z(u) - uT(d - Dx *)} < maxmin {z(u) - uT(d - Dy)} < minmax{z(u) - uT(d - Dy)} =
u>0 ye Wu>0 u>0ye W
= min{z(u) - minuT(d - Dy)} = wMD < z(u) - minuT(d - Dy) = zM(u) Vu > 0.
u > 0 y e W y e W
Второе неравенство здесь получено из условия x* e W. Утверждение 2. Для любого u > 0 неравенство
uTDx < uTd - 0(u) (3)
выполнено при x = x*. Если uR - вектор оптимальных множителей Лагранжа в релаксированной задаче (PR) и 0(uR) > 0, то при u = uR неравенство (3) не выполнено для оптимального решения xR релаксированной задачи.
Доказательство. Поскольку x* e W, то из определения 0(u) имеем
0( u) = min uT (d - Dy )< uT (d - Dx *),
y e W
откуда получаем справедливость неравенства (3) для x = x* при всех u > 0. По условию дополняющей нежесткости имеем uR DxR = uR d, откуда следует, что при 0(uR) > 0 неравенство uR Dx < uR d - 0(uR) не выполнено для x = xR.
Следствие. Пусть (3)R - неравенство (3) при u = uR, (PR n C( )) - задача, полученная добавлением ограничения (3)R к релаксированной постановке (PR), а zRn C( ) - соответствующее оптимальное значение. Тогда если 0(uR) > 0, то z* < zR n C( ) < zR.
Для доказательства заметим, что условие z* < zR n C( ) следует из выполнимости неравенства (3)R для x = x*. Задача (PR) есть релаксация (PR nC( )) и поэтому zRn C( ) < zR. Последнее неравенство выполнено как строгое, поскольку оптимальное решение xR задачи (PR) не удовлетворяет ограничению (3)R.
Из доказательства утверждения 1 следует, что величина
maxmin{z(u) - uT(d - Dy)}
ye Wu>0
также является оценкой сверху для z*, причем по крайней мере не хуже, чем wMD. Однако в рамках данной статьи мы ограничимся рассмотрением лишь модифицированных оценок zM(u) и wMD.
Отметим также, что в общем случае wMD Ф z(u*) - 0(u*), а двойственные задачи (D) и (MD) имеют различные оптимальные множители Лагранжа.
Получим теперь выражение для оптимального значения wMD модифицированной двойственной задачи (MD) в терминах прямых переменных, предполагая, что либо оба множества X и W содержат конечное число точек, {xb ..., xS} и {yb ...,y£} соответственно, либо оба этих множества есть ограниченные многогранники с соответствующими вершинами. Утверждение 3. Справедливо соотношение
wMD = max{ стx \ Dx < Dy, x e conv(X), y e conv(W)}.
(MP)
Доказательство. Используя определение wMD, zM(u) и z(u), имеем
wMD = min {max { cTx + uT( d - Dx)}-min { uT( d - Dy)}} =
u > 0 x e X y e W
= min{ max {cTxs + uT(d- Dxs)} - min {uT(d- Dy^)}} =
u > 0 s = 1, 2,..., 5 г =1, 2,..., L
minn - ^
П > cxs + uT(d- Dxs), s = 1, 2, ..., 5 uT (d - Dy,), I = 1, 2, ..., L u > 0, n, ^ e R1
Здесь переменные n, ^ используются для представления максимума и минимума по x e X и y e W соответствен
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.