close

Вход

Забыли?

вход по аккаунту

?

Двойственные алгоритмы внутренних точек.

код для вставкиСкачать
Известия вузов. Математика
2011, № 4, c. 33–53
http://www.ksu.ru/journals/izv_vuz/
Гос. номер статьи по НТЦ "Информрегистр" 0421100123 \0033
В.И. ЗОРКАЛЬЦЕВ
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
Аннотация. Дается описание семейства алгоритмов внутренних точек, осуществляющих монотонное улучшение решения двойственной задачи по отношению к задаче линейного программирования в канонической форме. Приводится теоретическое обоснование процесса оптимизации в области допустимых решений при условии невырожденности двойственной задачи. Выявлены подмножества алгоритмов, приводящих к относительно внутренним точкам
оптимальных решений, имеющих линейную и сверхлинейную скорости сходимости. Выявлено
также подмножество алгоритмов, у которых вырабатываемые на каждой итерации приближения к решению исходной задачи линейного программирования сходятся быстрее к решениям
этой задачи, чем сходятся монотонно улучшаемые по итерациям приближения к решению
двойственной задачи.
Ключевые слова: линейное программирование, двойственные алгоритмы внутренних точек,
относительная внутренность.
УДК: 519.681 : 519.85
Abstract. For a linear programming problem stated in the canonical form we consider the dual
problem and describe a class of interior point algorithms which generate monotonically improving
approximations to its solution. We theoretically substantiate the optimization process in the
admissible domain under the assumption that the dual problem is non-degenerate. In addition,
we describe subsets of algorithms that lead to relative interior points of optimal solutions. These
algorithms have linear and superlinear convergence rates. Moreover, we obtain a special subset of
algorithms which generate iterative sequences of approximations to a solution of the direct problem,
whose convergence rate exceeds that of the sequences of monotonically improving approximations
to a solution of the dual problem.
Keywords: linear programming, dual interior point algorithms, relative interior.
1. Введение
В данной статье рассматриваются алгоритмы решения задач линейного программирования, осуществляющие итеративное улучшение по внутренним (относительно ограничений
неравенств) точкам. Вспомогательная задача поиска направления улучшения решения в
этих алгоритмах представляется в виде проблемы минимизации квадратичной выпуклой
Поступила 05.10.2009
Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований, грант № 09-01-00306a.
33
34
В.И. ЗОРКАЛЬЦЕВ
функции при линейных ограничениях-равенствах. При этом за счет использования изменяемых по итерациям составляющих в минимизируемой функции вспомогательной задачи учитывается потенциальная степень активности отдельных ограничений-неравенств исходной задачи. Штрафные коэффициенты при составляющих минимизируемой функции,
представляющие каждое из ограничений-неравенств, возрастают к бесконечности при приближении численного значения данного неравенства к равенству. Соответственно, обратные
к штрафным коэффициентам величины, которые будем называть весовыми коэффициентами, в этом случае стремятся к нулю.
В частности, весовые коэффициенты могут быть равны квадрату значения линейной
функции, от которой по ограничениям исходной задачи требуется выполнение условия неотрицательности. Такой вариант алгоритмов внутренних точек наиболее широко известен и
получил в зарубежной литературе название affine scaling method.
Уместно отметить, что длительное время с конца 60-х – начала 70-х годов прошлого
столетия алгоритмы внутренних точек разрабатывались и исследовались только в работах
российских математиков, в Институте математики СО АН СССР, в Сибирском энергетическом институте СО АН СССР, в Вычислительном центре АН СССР. В работах И.И. Дикина,
С.М. Анцыза, Ю.Г. Евтушенко, В.Г. Жадана, автора данной статьи [1]–[5] были получены
пионерные результаты в разработке, экспериментальном и теоретическом исследовании алгоритмов, их непрерывных аналогов. Уже с 70-х годов прошлого столетия эти алгоритмы
эффективно используются при реализации ряда моделей энергетики. На основе экспериментальных и теоретических исследований был выявлен ряд интересных свойств алгоритмов. В
частности, было показано, что данные алгоритмы в случае неединственности оптимальных
решений имеют тенденцию вырабатывать относительно внутреннюю точку множества оптимальных решений, имеющую минимальный набор активных ограничений по сравнению с
другими оптимальными решениями. Это свойство алгоритмов эффективно использовалось,
в частности, в моделях анализа надежности электроэнергетических систем [3].
С середины 80-х годов к данным алгоритмам внутренних точек проявился повышенный
интерес в мире, причем многие из работ по этим алгоритмам (например, [6]–[8]) были по
сути переоткрытием сделанного ранее в России. В результате ряда независимых исследований было установлено, что алгоритмы внутренних точек являются не менее эффективным
(и даже по результатам сопоставления ряда авторов — более эффективным) способом решения задач линейного программирования, чем алгоритмы симплекс-метода. При этом на
базе метода внутренних точек относительно просто можно реализовывать алгоритмы решения многих типов задач нелинейного программирования. Все это позволяет ставить вопрос
о целесообразности введения алгоритмов внутренних точек в учебные программы по специальностям прикладная и вычислительная математика, математическая экономика.
Традиционно описание и исследование алгоритмов внутренних точек осуществляется в
основном применительно к задачам линейного программирования в стандартной форме или
к их непосредственным обобщениям, когда линейные функции с несколькими переменными используются в условиях задачи в ограничениях-равенствах. Ограничения-неравенства
вводятся только для значений отдельных переменных задачи. Итеративный процесс улучшения решения такой задачи состоит из двух этапов: 1) ввод в область допустимых решений, при котором монотонно уменьшаются по итерациям абсолютные значения невязок
ограничений-равенств; 2) оптимизация в области допустимых решений, при которой выполняются все ограничения задачи и монотонно улучшается значение целевой функции. При
этом на каждой итерации определяется вектор множителей Лагранжа ограничений вспомогательной задачи, являющийся приближением к решению двойственной задачи линейного
программирования.
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
35
Экспериментально было подмечено [3], что множители Лагранжа ограничений вспомогательной задачи сходятся значительно быстрее к оптимальному решению двойственной
задачи (хотя и без монотонного улучшения целевой функции или невязок ограничений двойственной задачи), чем сходятся монотонно улучшаемые решения исходной задачи. Недавно
в [9] было получено теоретическое обоснование этого факта при условии невырожденности
исходной задачи линейного программирования.
Практический интерес могут представлять двойственные алгоритмы внутренних точек,
осуществляющие монотонное улучшение решения двойственной задачи линейного программирования (сначала ввод в область допустимых решений, затем оптимизацию в области
допустимых решений двойственной задачи). Множители Лагранжа ограничений вспомогательной задачи двойственных алгоритмов внутренних точек предположительно будут сходиться быстрее к оптимальному решению исходной задачи линейного программирования,
чем монотонно улучшаемые приближения к решению двойственной задачи. Для достижения решения исходной задачи линейного программирования с заданной точностью при
использовании двойственных алгоритмов внутренних точек, видимо, потребуется меньший
объем вычислений, чем при использовании исходных алгоритмов внутренних точек.
Двойственные алгоритмы внутренних точек представляют также теоретический интерес.
Они хотя и идейно близки, но существенно отличаются от исходных (называемых иногда
“прямыми”) алгоритмов внутренних точек. Двойственные алгоритмы внутренних точек в
двух вариантах впервые были введены в [10], [11]. Частным случаем алгоритмов из [11]
является dual affine scaling method, предложенный несколько позже в [12], [13].
В данной статье будем пользоваться аксиоматическим, интервальным способом задания
весовых коэффициентов. Изначально при описании и исследовании алгоритмов не будем
формулировать конкретное правило вычисления этих коэффициентов, а будем формулировать условия, которым должны удовлетворять эти правила. В рамках такого определения весовых коэффициентов могут использоваться многие конкретные методы их задания.
Некоторые из них будут обсуждаться в конце статьи.
2. Исходные определения
Рассматривается задача линейного программирования в канонической форме и двойственная к ней задача линейного программирования:
c x → min, x ∈ X,
b u → max, u ∈ U,
(2.1)
(2.2)
где
X = {x ∈ Rn : Ax = b, x ≥ 0},
U = {u ∈ Rm : g(u) ≥ 0}.
Здесь g(u) = c − A u — линейная вектор-функция с компонентами gj (u), j = 1, . . . , n.
Переменные задач (2.1), (2.2) составляют векторы x ∈ Rn , u ∈ Rm при некоторых n ≥ 1,
m ≥ 1. Заданными являются векторы c ∈ Rn , b ∈ Rm , матрица A размера m × n.
Векторы из X, U будем называть допустимыми решениями задач (2.1), (2.2). Множество
оптимальных решений этих задач обозначим
X = Arg min{c x : x ∈ X},
U = Arg max{b u : u ∈ U }.
Задачу (2.1) будем называть исходной задачей линейного программирования, задачу (2.2)
— двойственной задачей линейного программирования.
36
В.И. ЗОРКАЛЬЦЕВ
Введем множества рецессивных направлений задач (2.1), (2.2). Пусть
= {s ∈ Rn : As = 0, s ≥ 0, c s < 0},
X
= {v ∈ Rm : A v ≤ 0, b v > 0}.
U
состоит из направлений неограниченного убывания целевой функции задачи
Множество X
то вектор
(2.1), не выводящих из множества ее допустимых решений: если x ∈ X, s ∈ X,
x(λ) = x + λs будет находиться в X при любом λ ≥ 0 и c x(λ) → −∞ при λ → ∞. Со — множество направлений неограниченного возрастания целевой функции
ответственно U
, то при
задачи (2.2), не выводящих из области ее допустимых решений: если u ∈ U , v ∈ U
любых λ ≥ 0 вектор u(λ) = u + λv будет находиться в U и b u(λ) → ∞ при λ → ∞.
U
полезны для конструктивного выявления случаев несовместности ограМножества X,
ничений задач (2.1), (2.2). Согласно теоремам об альтернативных системах линейных нера пусто. Это утверждение принято
венств ([14]–[17]) одно и только одно из двух множеств X, U
называть теоремой Фаркаша ([16]; [17], с. 62). Из него следует, что если в процессе реше , то тем самым
ния задач (2.1), (2.2) каким-либо алгоритмом будет найден вектор v ∈ U
будет установлена противоречивость ограничений задачи (2.1) и одновременно отсутствие
= ∅, то целевая функция задачи (2.2) будет
оптимальных решений у задачи (2.2): если U
неограниченной сверху на множестве U .
Также согласно теоремам об альтернативных системах линейных неравенств одно и толь пусто. Это утверждение принято называть теоремой Гейла ([16];
ко одно из множеств U , X
то
[17], с. 63). Если в процессе решения задач (2.1), (2.2) будет получен вектор s ∈ X,
будет установлена противоречивость ограничений задачи (2.2) и одновременно отсутствие
= ∅, то целевая функция задачи (2.1) будет
оптимальных решений у задачи (2.1): если X
неограниченной снизу на множестве X.
C учетом этих фактов приходим к следующей основополагающей теореме в линейном
программировании (краткое доказательство которой имеется, например, в [17], с. 88).
Теорема 1. Для задач (2.1), (2.2) возможны только две ситуации.
1. Хотя бы одно из множеств X или U пусто. Тогда обе задачи не имеют оптимальных
решений, X = ∅, U = ∅. Эта ситуация будет в том и только том случае, если не пусто
U
.
хотя бы одно из множеств X,
2. Если X = ∅, U = ∅, то обе задачи имеют оптимальные решения, X = ∅, U = ∅. В
U
пусты.
этой и только этой ситуации оба множества X,
Для любых x ∈ X, u ∈ U
n
xj gj (u) ≥ 0.
j=1
Для любых x ∈ X, u ∈ U
n
xj gj (u) = 0.
(2.3)
j=1
Существуют x ∈ X, u ∈ U такие, что
(xj + gj (u)) > 0, j = 1, . . . , n.
(2.4)
Следуя Р. Рокафеллару ([18], с. 59), для выпуклого множества Y ⊂ Rn подмножество его
внутренних точек относительно минимального линейного многообразия, содержащего Y ,
будем называть относительной внутренностью и обозначать ri Y . Отметим, что если Y —
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
37
множество решений системы линейных неравенств, то подмножество ri Y состоит из решений системы с минимальным набором активных ограничений (ограничений-неравенств,
которые для данных решений выполняются в виде равенств).
Соотношение (2.3) для x ∈ X, u ∈ U принято называть условием дополняющей нежесткости. Выполнение обоих соотношений (2.3) и (2.4) означает, что для векторов x ∈ X, u ∈ U
достигается условие дополняющей нежесткости в строгой форме. В этом и только этом случае x ∈ ri X, u ∈ ri U . Вектор x будет иметь минимальный набор активных ограничений (в
условии x ≥ 0) по сравнению с другими векторами из X. Соответственно вектор u будет
иметь минимальный набор активных ограничений (в условии g(u) ≥ 0) по сравнению с
другими векторами из U.
Множества номеров компонент вектора x ∈ Rn с нулевыми, положительными, отрицательными и ненулевыми значениями обозначим
J0 (x) = {j : xj = 0}, J+ (x) = {j : xj > 0},
J− (x) = {j : xj < 0},
J(x) = J+ (x) ∪ J− (x).
Введем специальные обозначения для множеств номеров компонент вектора g(u). Пусть
при u ∈ Rm
I0 (u) = J0 (g(u)), I(u) = J(g(u)).
Отметим, что при u ∈ U множество I(u) состоит из номеров компонент вектора g(u) с
положительными значениями.
Стационарные решения двойственной задачи. Вектор u ∈ U будем называть стационарным решением задачи (2.2), если при таком x ∈ Rn , что Ax = b, справедливы соотношения
J(x) ⊆ I0 (u), I(u) ⊆ J0 (x).
(2.5)
Эти соотношения равносильные: если выполняется одно из них, то выполняется и другое.
Отметим, что в приведенном условии стационарности не требуется неотрицательность
компонент вектора x. Если же x ≥ 0, то условие стационарности будет равносильным
условию дополняющей нежесткости (2.3). Любое оптимальное решение u ∈ U будет стационарным решением задачи (2.2). Вместе с тем стационарное решение может не быть
оптимальным.
В качестве пояснения отметим, что решение u ∈ U будет стационарным, если, например,
среди столбцов матрицы A с номерами j ∈ I0 (u) будет m линейно независимых. Тогда
обязательно будет иметь решение система линейных уравнений Ax = b при xj = 0 для
j ∈ I(u).
Условие невырожденности двойственной задачи. Решение u ∈ U задачи (2.2) назовем
невырожденным, если оно либо не является стационарным, либо для него условия стационарности (2.5) выполняются только при единственном x ∈ Rn таком, что Ax = b.
Задачу (2.2) назовем невырожденной, если невырождены все ее решения из U .
Замечание 1. Хотя в формулировки доказываемых далее теорем 4, 5 вводится условие
невырожденности задачи (2.2), в этих теоремах достаточно было бы использовать предположение о невырожденности одного из векторов множества U — предельной точки последовательности вырабатываемых алгоритмом векторов. Существование и единственность этой
предельной точки (теорема 2) и то, что она является стационарным решением (теорема 3),
доказывается без использования предположения о невырожденности.
Такое ослабление условий теорем 4, 5 возможно, но оно не носит принципиальный характер. В этом случае трудно априори проверить выполнение условия невырожденности,
поскольку изначально предельная точка вырабатываемой последовательности решений задачи (2.2) неизвестна, к тому же у задач линейного программирования нередко имеют место
38
В.И. ЗОРКАЛЬЦЕВ
вырожденные стационарные решения. В силу искусственности предположения о невырожденности приводимое далее обоснование процесса оптимизации алгоритмами внутренних
точек в области допустимых решений нельзя считать полным. Это только этап, хотя и
очень важный, в теоретическом обосновании алгоритмов, в изучении их свойств.
В качестве пояснения отметим, что если для решения u ∈ U подматрица, составленная
из столбцов матрицы A с номерами из I0 (u), имеет ранг равный m (т. е. эта подматрица
является квадратной матрицей полного ранга), то такое решение будет стационарным и
невырожденным по приведенным здесь определениям. Действительно, система Ax = b при
xj = 0 для j ∈ I(u) в этом случае имеет единственное решение.
3. Вычислительный процесс
Заданы векторы u0 ∈ Rm , g0 ∈ Rn , причем gj0 > 0 для всех j = 1, . . . , n. Например, можно
взять u0 = 0, gj0 = 1, j = 1, . . . , n.
Рассматривается итеративный процесс
uk+1 = uk + λk r k ,
g
k+1
k
k
= g + λk z ,
(3.1)
k = 0, 1, 2 . . .
(3.2)
Здесь r k , z k — векторы из Rm и Rn , задающие направление корректировки решения на
итерации k, λk — положительная величина шага корректировки. Как будет показано далее,
за счет выбора шага на всех итерациях достигается выполнение неравенства
gjk > 0,
j = 1, . . . , n.
(3.3)
Векторы r k и z k определяются как результат решения вспомогательной задачи минимизации квадратичной строго выпуклой функции от переменных, составляющих векторы
r ∈ Rm , z ∈ Rn при линейных ограничениях в форме равенств:
1
1
(3.4)
−b r + r r + z Dk−1 z → min
2
2
при условии
(3.5)
A r + z = δk .
Здесь
(3.6)
δk = g(uk ) − gk
— вектор невязок ограничений задачи (2.2), Dk = diag dk — диагональная матрица размера
n×n, составленная из положительных весовых коэффициентов dkj , j = 1, . . . , n, образующих
вектор dk ∈ Rn .
Для весовых коэффициентов должны выполняться неравенства
σ(gjk ) ≥ dkj ≥ σ(gjk ),
j = 1, . . . , m, k = 0, 1, 2, . . . ,
(3.7)
где σ, σ — некоторые непрерывные функции от положительного аргумента, удовлетворяющие следующим условиям:
σ(α) ≥ σ(α) > 0 ∀α > 0;
(3.8)
при некоторых ε > 0, M > 0 для всех α ∈ (0, ε]
M α ≥ σ(α).
(3.9)
Поскольку существует много разных правил задания весовых коэффициентов, удовлетворяющих условиям (3.7)–(3.9), то излагаемый вычислительный процесс можно рассматривать как некоторое семейство алгоритмов.
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
Величина шага вычисляется по правилу
k , 1}, если δk = 0,
λk = min{λ
k ,
если δk = 0,
λk = λ
39
(3.10)
(3.11)
где
k = −γk gk /z k ,
λ
j(k) j(k)
(3.12)
j(k) = argmin{−gjk /zjk : j ∈ J− (z k )}.
(3.13)
k = ∞.
Если J− (z k ) = ∅, то полагаем λ
Здесь γk — заданный параметр из открытого интервала (0, 1). Далее считаем, что этот
параметр является неубывающим по итерациям
γk ≤ γk+1 ,
(3.14)
k = 0, 1, 2, . . .
Следовательно, существует число γ ∈ (0, 1] такое, что
γk → γ при k → ∞.
(3.15)
Отметим, что правило (3.12), (3.13) равносильно следующему:
k = sup{λ : gk + λz k ≥ (1 − γk )gk }.
λ
(3.16)
Номер j(k) соответствует той компоненте, для которой ограничения неравенства в (3.16)
достигаются в форме равенства. Из (3.2), (3.10), (3.11), (3.16) вытекает
gk+1 ≥ (1 − γk )gk ,
(3.17)
k = 0, 1, 2, . . .
получаемого после
Поэтому из (3.3) и условия γk ∈ (0, 1) следует, что у вектора
итеративного перехода (3.2), также все компоненты будут положительными.
Возможен случай λk = ∞, когда у вектора z k нет отрицательных компонент, J− (z k )=∅.
Это не является препятствием для вычисления шага при δk = 0. В таком случае в соответствии с (3.10) следует положить λk = 1.
Случай λk = ∞ при δk = 0 будет означать необходимость окончания вычислительного
процесса. Это возможно в двух вариантах. Если z k ≥ 0 и z k = 0, то, как будет показано
далее, не будет оптимальных решений из-за неограниченности сверху значений целевой
функции задачи (2.2) на множестве ее допустимых решений. Если z k = 0, то U = U , т. е.
полученное допустимое решение uk будет одновременно и оптимальным решением. Такой
вариант для описанного здесь процесса в силу (3.3), как будет показано ниже, возможен
лишь при b = 0.
Отметим, что на всех итерациях
gk+1 ,
δk+1 = (1 − λk )δk ,
k = 0, 1, 2, . . .
(3.18)
Действительно, используя сначала определение (3.6), затем условие (3.5) и правило (3.1),
(3.2), имеем
δk+1 = g(uk+1 ) − gk+1 = g(uk ) − λk A r k − gk − λk z k = δk − λk (A r k + z k ) = δk − λk δk .
Два этапа вычислительного процесса. Соотношение (3.18) объясняет условие (3.10) на
выбор шага: при λk = 1 вектор δk+1 становится нулевым и, следовательно, вектор uk+1
станет допустимым решением задачи (2.2). Если δk = 0, то из (3.18) и соотношения λk ∈
(0, 1] следует, что после итеративного перехода (3.1), (3.2) все компоненты вектора невязок
δk+1 станут меньше по абсолютной величине, чем соответствующие компоненты вектора δk .
Поэтому будем говорить, что при δk = 0 на итерации k осуществляется процесс ввода в
область допустимых решений задачи (2.2).
40
В.И. ЗОРКАЛЬЦЕВ
Если δk = 0, т. е. gk = g(uk ), то вектор uk является допустимым решением для задачи
(2.2) (т. е. находится в области допустимых решений U данной задачи). Согласно (3.18) после итеративного перехода δk+1 = 0 вектор uk+1 также будет допустимым решением задачи
(2.2). Будем говорить, что в этом случае изложенный вычислительный процесс осуществляет оптимизацию в области допустимых решений задачи (2.2). Далее будет доказано, что
в случае δk = 0, если J− (z k ) = ∅, происходит монотонное улучшение значения целевой
функции задачи (2.2),
(3.19)
b uk+1 > b uk .
Замечание 2. У задачи (2.2) может не существовать решения u ∈ U , при котором I0 = ∅,
даже если U = ∅. Множество U может быть нетелесным.
Для процесса оптимизации в области допустимых решений важно располагать стартовой
точкой u
из области ri U . В частности, к векторам из ri U могут приводить процессы ввода
в область допустимых решений алгоритмами внутренних точек. Если известно, что имеем
решение u
из множества ri U , то в силу свойств ri U для любого допустимого решения
u).
двойственной задачи u ∈ U выполняется равенство gj (u) = 0 при j ∈ I0 (
u) можно выразить одну переменную в виде
Из условия gj (u) = 0 для некоторого j ∈ I0 (
линейной функции от оставшихся переменных (компонент вектора u). Подставляя полученные выражения в остальные ограничения и в целевую функцию задачи (2.2), получим
задачу такого же вида, как и (2.2), только с меньшим количеством переменных и ограничений. Производя последовательно такое сокращение переменных и ограничений с номерами
u), придем к задаче вида (2.2), для которой оставшиеся компоненты вектора u
будут
из I0 (
составлять допустимое решение с неактивными остальными ограничениями (т. е. ограничениями с номерами из I(
u)).
Приведенные соображения позволяют считать, что на этапе оптимизации в области допустимых решений двойственной задачи все ограничения выполняются в строгой форме,
даже если для полученного в процессе ввода в область допустимых решений вектора u
∈ ri U
некоторые из ограничений задачи (2.2) были активными.
Некоторые свойства процесса оптимизации в области допустимых решений. Далее, в
последующих разделах данной статьи будут исследоваться особенности второго этапа вычислений — процесса оптимизации в области допустимых решений. Здесь докажем свойства
этого процесса, в том числе анонсированные выше, в частности, неравенство (3.19). Итак,
считаем, что δk = 0.
Производная целевой функции вспомогательной задачи (3.4), (3.5) по направлению r, z,
не выводящему из области допустимых решений этой задачи, т. е. при
A r + z = 0,
(3.20)
должна быть равна нулю в точке оптимума вспомогательной задачи
−b r + r r k + z Dk−1 z k = 0.
(3.21)
Поскольку gj (uk ) > 0 для всех j = 1, . . . , n, то множество допустимых решений U задачи
(2.2) является телесным, имеющим не пустую внутренность int U , которая в этом случае
совпадает с относительной внутренностью, ri U = int U . При этом uk ∈ int U . Достаточно
малое перемещение по любому направлению в Rm от точки uk будет давать также допустимое решение задачи (2.2).
Если и только если b = 0, то при перемещении по любому направлению от точки uk не
будет меняться значение целевой функции задачи (2.2). В этом и только этом случае U = U ,
и в результате решения вспомогательной задачи получим r k = 0, z k = 0.
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
41
Если b = 0, то векторы r = b, z = −A b будут удовлетворять условию (3.20) и при
этом b r > 0. Из (3.21) получаем, что или r k = 0, или z k = 0. Не исключается, что оба этих
вектора ненулевые. Если z k = 0, то поскольку в условии (3.5) вектор δk нулевой, ненулевым
должен быть вектор r k . Итак, во всех случаях r k = 0.
Поскольку δk = 0, то согласно (3.5) векторы r k и z k удовлетворяют условию (3.20).
Используя эти векторы в (3.21) вместо r, z, получаем равенства
b r k = Gk (r k , z k ),
(3.22)
Gk (r, z) = r r + z Dk−1 z
(3.23)
где
— функции от векторов r ∈ Rm , z ∈ Rn . В силу того, что z k = 0, значение Gk (r k , z k )
положительно и согласно (3.22)
b r k > 0.
(3.24)
рецессивных направлений задачи
Если z k ≥ 0, то вектор z k будет находиться в множестве U
(2.2). По теореме 1 получаем, что задачи (2.1), (2.2) не имеют оптимальных решений.
Далее считаем, что J− (z k ) = ∅ на всех итерациях. По правилам (3.11)–(3.13) будем получать конечные положительные значения шага λk . Из (3.1), (3.24) получаем неравенство
(3.19).
Вспомогательная задача. Основной вычислительной проблемой при реализации изложенного алгоритма является решение вспомогательной задачи (3.4), (3.5). Обозначим через
−xk вектор из Rn множителей Лагранжа ограничений этой задачи. По условиям оптимальности
− xk = Dk−1 z k ,
(3.25)
b − Axk = r k .
(3.26)
Вспомогательная задача (3.4), (3.5) сводится к проблеме решения системы линейных
уравнений с симметричной положительно определенной матрицей. Можно предложить два
варианта вычислений.
Один из них основывается на решении системы линейных уравнений с матрицей размера
m × m. Сначала вычисляем
r k = (I + ADk−1 A )−1 (b + ADk−1 δk ),
(3.27)
z k = −A r k ,
(3.28)
затем определяем
xk .
и по формуле (3.25) вычисляем
Второй вариант вычислений основан на решении системы линейных уравнений с матрицей размера n × n. Вычисляем вектор
xk = (Dk + A A)−1 (A b − δk ),
(3.29)
затем из формул (3.26), (3.28) — векторы r k и z k .
Отметим, что вектор множителей Лагранжа xk служит в качестве приближения к решению исходной задачи (2.1) на итерации k. В качестве критерия останова при получении решения, близкого к оптимальному, можно использовать выполнение следующих трех
условий: вектор uk близок к допустимому решению задачи (2.2), вектор xk близок к допустимому решению задачи (2.1), для векторов uk , xk с заданной точностью выполняется
42
В.И. ЗОРКАЛЬЦЕВ
условие дополняющей нежесткости (2.3). Значит, при некоторых достаточно малых ε1 > 0,
ε2 > 0, ε3 > 0, ε4 > 0 должны выполняться неравенства
δ ≤ ε1 , r ≤ ε2 ,
k
k
n
|min(0, xkj )|
≤ ε3 ,
j=1
n
|xkj gj (uk )| ≤ ε4 .
j=1
4. Сходимость процесса оптимизации в области допустимых решений
Далее считаем, что в изложенном вычислительном процессе исходный вектор uk находится в области допустимых решений задачи (2.2), uk ∈ int U , g(uk ) = gk , δk = 0, k = 0, 1, 2 . . .
При этом b = 0, J− (z k ) = ∅ и на всех итерациях имеем положительные конечные значения λk .
В силу (3.19) значение целевой функции задачи (2.2) сходится к некоторой величине
f = lim b uk .
k→∞
(4.1)
Если f = ∞, то задача (2.2) не имеет оптимальных решений, ее целевая функция не ограничена на множестве допустимых решений. Далее будем считать, что f < ∞. В частности,
это выполняется, если U = ∅.
Сначала установим сходимость последовательности векторов uk к одной точке. Для этого
потребуются приведенные ниже два вспомогательных утверждения. Доказательство первой
из приводимых ниже лемм имеется в [10], [19]. Вторая лемма доказывается стандартно.
Пусть L — некоторое линейное многообразие в Rn . Обозначим через
Q(L) = {q(d) : dj > 0, j = 1, . . . , n}
множество евклидовых проекций начала координат на линейное многообразие L. Здесь
n
dj (qj )2 : q ∈ L
q(d) = argmin
j=1
евклидова проекция начала координат на линейное многообразие L при использовании евклидовой нормы
1/2
n
2
dj (qj )
qd =
j=1
с заданными весовыми коэффициентами dj > 0, j = 1, . . . , n.
Лемма 1. Для любого линейного многообразия L в Rn множество евклидовых проекций
начала координат Q(L) на это многообразие является ограниченным.
∞
αk сходится, последовательность чисел βk ,
Лемма 2. Если положительный ряд
k=0
k = 0, 1, 2, . . . , ограниченная, то ряд
αk βk сходится.
Модификация вычислительного процесса. Итеративный переход (3.1) можно представить
в виде
k rk ,
(4.2)
uk+1 = uk + λ
k = (b r k )λk , rk = 1 k r k .
где λ
b r
Из (3.4), (3.5) следует, что векторы rk и zk =
1 −1
2 z Dk z
→ min при ограничениях A r + z = 0,
1
z k являются
b r k
b r = 1.
решением задачи r r +
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
43
Таким образом, эти векторы можно рассматривать как проекцию начала координат на
линейное многообразие. По лемме 1 при некоторых M1 > 0, M2 > 0
rk ≤ M1 , zk ≤ M2 , k = 0, 1, 2, . . .
∞
k сходится. Из леммы 2, примененной
k = b (uk+1 − uk ), то в силу (4.1) ряд λ
Так как λ
k=0
к процессу (4.2), получается
Теорема 2. Если у процесса оптимизации в области допустимых решений значение целевой функции задачи (2.2) на всех итерациях ограничено сверху, f < ∞, то существует
вектор u ∈ U такой, что
(4.3)
uk → u при k → ∞.
Принадлежность вектора u множеству U следует из того, что на всех итерациях uk ∈ U
и множество U замкнуто.
Пусть g = g(u). Поскольку для процесса оптимизации в области допустимых решений
k
g = g(uk ), то в силу (4.3)
(4.4)
gk → g при k → ∞.
k
k
Отметим, что в полученном обосновании сходимости векторов u , g условия (3.7)–(3.9)
на выбор весовых коэффициентов не использовались в полной мере. Использовалась только
положительность значений весовых коэффициентов dkj .
5. Сходимость к стационарному решению
Докажем теперь, что при выполнении условий (3.7)–(3.9) предельная точка u последовательности векторов uk будет стационарным решением задачи (2.2). Можем считать без
потери общности, что функция σ является неубывающей. Действительно, вместо исходной
функции σ, если она не обладает таким свойством, можно использовать функцию
σ
(α) = sup{σ(β) : β ∈ (0, α]}.
, σ также будут
Если для функций σ, σ выполнялись условия (3.7)–(3.9), то для функций σ
выполняться эти условия. Итак, далее считаем, что
σ(α) ≥ σ(β) > 0 ∀α > 0, β > 0, α ≥ β.
(5.1)
Согласно (4.4) последовательность векторов gk ограничена. Поэтому из (3.7)–(3.9) следует, что при некотором M3 > 0 для всех k = 0, 1, 2, . . . ; j = 1, . . . , n
M3 gjk ≥ dkj ≥ σ(gjk ) > 0.
(5.2)
По условиям оптимальности Лагранжа для того, чтобы векторы r k , z k составляли оптимальное решение вспомогательной задачи (3.4), (3.5) при δk = 0 и вектор xk являлся
вектором множителей Лагранжа ограничений этой задачи, необходимо и достаточно, чтобы эти три вектора были решением следующей системы линейных уравнений:
A r + z = 0,
(5.3)
Ax + r = b,
(5.4)
x+
Dk−1 z
= 0.
(5.5)
Из условия (5.5) выразим вектор z через вектор x, получим следующую равносильную
(5.3)–(5.5) систему линейных уравнений относительно векторов переменных x ∈ Rn , r ∈ Rm :
A r − Dk x = 0,
(5.6)
Ax + r = b.
(5.7)
44
В.И. ЗОРКАЛЬЦЕВ
Рассмотрим задачу
Fk (r, x) → min
(5.8)
Fk (r, x) = r r + x Dk x.
(5.9)
при ограничениях (5.7). Здесь
Из условий оптимальности Лагранжа следует, что векторы x, r будут оптимальными
решениями задачи (5.8) в том и только том случае, если эти векторы являются решением
системы (5.6), (5.7). Оптимальное значение вектора r будет совпадать с вектором множителей Лагранжа ограничений (5.7) задачи (5.8).
Из приведенных рассуждений следует, что векторы xk , r k будут решением задачи (5.8).
В силу формулировки задачи (5.8) эти векторы можно интерпретировать как евклидовы
проекции начала координат на линейное многообразие в Rn+m , определяемое системой линейных уравнений (5.7). Согласно лемме 1 векторы xk , r k будут образовывать ограниченные
последовательности: при некоторых M4 > 0, M5 > 0 для всех k = 0, 1, 2, . . .
xk ≤ M4 , r k ≤ M5 .
Из условия (5.3) и ограниченности последовательности векторов
ность последовательности векторов z k : при некотором M6 > 0
z k ≤ M6 , k = 0, 1, 2, . . .
(5.10)
rk
следует ограничен(5.11)
Выразив в условии (3.5) при δk = 0 вектор z через r, представим вспомогательную задачу (3.4), (3.5) в виде задачи безусловной минимизации квадратичной выпуклой функции
относительно вектора переменных r ∈ Rm :
1
(5.12)
−b r + Φk (r) → min,
2
где
(5.13)
Φk (r) = r r + r ADk−1 A r.
Вектор r k является решением задачи (5.12). В качестве пояснения отметим, что выражение (3.27) вектора r k в случае δk = 0 вытекает из системы линейных уравнений, которая
получается приравниванием нулевому вектору градиента целевой функции задачи (5.12).
Производная целевой функции задачи (5.12) в точке r k по направлению r k должна равняться нулю. Получаем равенство
b r k = Φk (r k ).
(5.14)
Φk (r k ) = Fk (r k , xk ).
(5.15)
Отметим, что
Действительно, согласно (5.6)
xk = Dk−1 A r k .
Используя это выражение в определении (5.9), имеем
(5.16)
Fk (r k , xk ) = (r k ) r k + (r k ) ADk−1 Ar k .
Из определения (5.13) получаем (5.15).
Из (3.11)–(3.14), (3.25), используя неравенства (5.2), (5.10), находим, что величина шага λk ограничена снизу на всех итерациях некоторым положительным числом
λk ≥ γ0 /(M3 M4 ), k = 0, 1, 2, . . .
Действительно,
k /z k
γk gj(k)
j(k)
≥
k /(dk xk )
γ0 gj(k)
j(k) j(k)
≥ γ0 /(M3 M4 ).
(5.17)
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
45
Из (3.24), (4.1) следует b uk+1 − b uk → 0 при k → ∞. В силу (3.1) b uk+1 − b uk =
λk (b r k ). Поэтому λk (b r k ) → 0 при k → ∞. Из (5.17) получаем b r k → 0 при k → ∞.
Согласно (5.14), (5.15)
Φk (r k ) → 0, Fk (r k , xk ) → 0 при k → ∞.
Ввиду определения (5.9) функции Fk при k → ∞
n
r k → 0,
(5.18)
dkj (xkj )2 → 0.
(5.19)
j=1
В силу (5.10) предельные при k → ∞ значения последовательности векторов xk образуют ограниченное множество, которое обозначим Lim xk . Для любого значения x ∈ Lim xk
согласно (5.7), (5.17) выполняется равенство
Ax = b.
(5.20)
Согласно (4.4), (5.2) последовательность векторов dk является ограниченной и, следовательно, имеющей ограниченное множество предельных при k → ∞ значений, которое
обозначим Lim dk . В силу (3.7)–(3.9) для любого d ∈ Lim dk
если g j = 0, то dj = 0; если gj > 0, то dj > 0.
(5.21)
Из (5.19), (5.20) получаем, что для вектора u при любом векторе x ∈ Lim xk выполняется
условие стационарности (2.5). Итак, получили доказательство следующего утверждения.
Теорема 3. Если у процесса оптимизации в области допустимых решений значения целевой функции задачи (2.2) образуют ограниченную последовательность, f < ∞, то последовательность векторов uk сходится при k → ∞ к стационарному решению u задачи
(2.2), векторы xk образуют ограниченную последовательность, любая предельная точка
которой удовлетворяет условию (5.19) и условию стационарности (2.5) для данного вектора u.
Отметим одно важное для дальнейшего изложения следствие из доказанной теоремы,
равенств (3.12), (3.25) и неравенства (5.17): начиная с некоторой итерации k0 для всех
k > k0
j(k) ∈ I0 (u).
(5.22)
Действительно, при любом j ∈ I(u) величины |zjk |/gjk сходятся при k → ∞ к нулю, так
как знаменатель сходится к некоторому положительному значению g j > 0, а числитель
|zjk | = |dkj xkj | сходится к нулю в силу того, что величины dkj ограничены, и по условию
стационарности I(u) ⊂ J0 (x). В то же время согласно (5.17) величины λk ограничены снизу
некоторым положительным значением, что и дает (5.22).
6. Сходимость к оптимальному решению для невырожденных задач
Если задача (2.2) невырожденная, то для стационарных решений u ∈ U не может быть
двух векторов x, удовлетворяющих условию (5.20), при которых выполняются соотношения
(2.5). Поэтому последовательность векторов xk будет сходиться к единственному вектору
x = lim xk .
k→∞
46
В.И. ЗОРКАЛЬЦЕВ
Предположим, что у всякого вектора x имеются отрицательные компоненты. Если xj < 0
для некоторого j, то начиная с некоторой итерации на всех последующих xkj < 0. Поскольку
согласно (3.25)
zjk = −dkj xkj
и dkj > 0, то с некоторой итерации на всех последующих zjk > 0. Из (3.2) и неравенства
λk > 0 получаем, что величина gjk для данного j будет возрастать по итерациям. Поэтому
gj > 0. Неравенства gj > 0, xj > 0 противоречат условию стационарности (2.5), которое
согласно теореме 3 должно выполняться для векторов u, x.
Итак, доказано, что x ≥ 0. В силу (5.20) x ∈ X. Следовательно, условие стационарности
(2.5) для векторов u, x означает выполнение для них условия дополняющей нежесткости
(2.3). На основе теоремы 1 получается
Теорема 4. Если задача (2.2) невырожденная, b = 0, U = ∅, то для процесса оптимизации
в области допустимых решений задачи (2.2) при k → ∞
uk → u, xk → x
при некоторых u ∈ U , x ∈ X.
Здесь условие b = 0 гарантирует, что U = U и процесс оптимизации не останавливается на
первоначальной итерации. Условие U = ∅ обеспечивает сходимость к конечному значению f
последовательности величин b uk .
7. Алгоритмы, вырабатывающие относительно внутренние точки
оптимальных решений
Введем дополнительное условие на правила выбора весовых коэффициентов. Потребуем
от функций σ, σ выполнение следующего свойства: при некоторых ε > 0, N > 0 для всех
β ∈ (0, ε), всех α ∈ (0, εβ) должно выполняться неравенство
N (α/β) ≥ σ(α)/σ(β).
(7.1)
Отметим, что если в (7.1) зафиксировать некоторое значение β ∈ (0, ε), то это условие
перейдет в требование (3.9) при M = N σ(β)/β. Поэтому (7.1) можно рассматривать как
усиление требования (3.9).
Условие (7.1), как будет установлено в данном разделе, позволяет получить два новых
по отношению к теореме 4 факта. Во-первых, будет доказано, что векторы uk , xk сходятся
при k → ∞ к своим предельным значениям не медленней, чем линейно. Значит, величины
uk − u, xk − x сходятся к нулю не медленней, чем со скоростью геометрической прогрессии. Во-вторых, докажем, что векторы uk сходятся к относительно внутренней точке
множества оптимальных решений U , т. е. для векторов u, x будет выполняться условие
дополняющей нежесткости в строгой форме (2.3), (2.4). Для этого потребуется
Лемма 3 ([9]). Пусть последовательность положительных чисел αk , k = 0, 1, 2, . . . , является сходящейся, αk → α при k → ∞ для некоторого α ≥ 0. Выполняются два условия:
1) величины βk = αk+1 −αk сходятся к нулю не медленнее, чем линейно, т. е. βk ≤ P (ρ)k
при некоторых P > 0, ρ ∈ (0, 1);
2) величины βk /αk сходятся к нулю.
Тогда предельное значение величины αk будет положительным, α > 0.
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
47
Особо выделим еще более узкий класс алгоритмов таких, что при некотором ε > 0 для
переменных α > 0, β ∈ (0, ε)
α
σ(α) β
· → 0, если
→ 0,
(7.2)
σ(β) α
β
т. е.
α
σ(α)
=o
.
σ(β)
β
Если выполняется условие (7.2), то будет выполняться условие (7.1). Поэтому все, что справедливо для алгоритмов, удовлетворяющих условию (7.1), будет справедливо и для алгоритмов, удовлетворяющих условию (7.2).
Условие (7.2), как будет доказано здесь, позволяет получить еще два новых свойства алгоритмов. Во-первых, величины xk − x сходятся к нулю быстрее, чем сходятся к нулю
при k → ∞ величины gk − g. Второе свойство — возможность достигать сверхлинейной
скорости сходимости к точке оптимума исходной и двойственной задач линейного программирования за счет задания параметра γk , сходящегося к единице при k → ∞.
Теорема 5. Пусть задача (2.2) невырожденная, b = 0, U = ∅, начальное приближение u0
является допустимым решением задачи (2.2), u0 ∈ int U , g0 = g(u0 ), в изложенном в разделе 3 вычислительном процессе выполняется условие (7.1). Тогда существуют векторы
u ∈ ri U , x ∈ ri X такие, что
xk → x, uk → u при k → ∞.
При этом для некоторых P1 > 0, P2 > 0, P3 > 0, P4 > 0, α ∈ (0, 1) и для всех k = 0, 1, 2, . . .
выполняются неравенства
xk − x ≤ P1 Lk ,
(7.3)
Lk ≤ P2 Tk ,
(7.4)
Tk ≤ g − g ≤ P3 Tk ,
(7.5)
Tk ≤ P4 (α)k ,
(7.6)
k
где
Lk = max{dkj : j ∈ J(x)}, Tk = max{gjk : j ∈ J(x)}.
Если в вычислительном процессе выполняется условие (7.2), то
(7.7)
xk − x/gk − g → 0 при k → ∞
(7.8)
Tk+q+1 ≤ P5 Tk (1 − γk ), k = 0, 1, 2, . . . ,
(7.9)
и при некотором P5 > 0
где q — число номеров в наборе J(x).
Доказательство. Будем нумеровать отдельные фрагменты рассуждений.
1. Пусть
h1k = max{|xkj | : j ∈ I(u)},
h2k = max{|rik | : i = 1, . . . , m},
Hk = max{h1k , h2k }.
(7.10)
Докажем, что при некотором M9 > 0
xk − x ≤ M9 Hk , k = 0, 1, 2, . . .
(7.11)
48
В.И. ЗОРКАЛЬЦЕВ
Предположим, что (7.11) не верно. Тогда должна существовать бесконечная последовательность номеров итераций K такая, что при k ∈ K, k → ∞
|xkj |/xk − x → 0, j ∈ I(u),
(7.12)
|rik |/xk − x → 0, i = 1, . . . , m.
(7.13)
r k = 0, где y k =
Согласно (3.26), (5.20) Ax = b, Axk +r k = b. Поэтому Ay k +
rk =
1
rk .
xk −x
1
(xk −x),
xk −x
Поскольку векторы y k составляют ограниченную последовательность, то
⊂ K такая, что y k → y
существует бесконечная подпоследовательность номеров итераций K
m
при k ∈ K, k → ∞ для некоторого y ∈ R , y = 0.
В силу (7.13) последовательность векторов rk при k ∈ K, k → ∞ сходится к нулевому
вектору. Поэтому
(7.14)
Ay = 0.
Согласно (7.12)
yj = 0 для j ∈ J(u).
(7.15)
Из (7.14), (7.15) и соотношений (2.5) для векторов u, x следует, что соотношения (2.5)
будут выполняться и для векторов u, x + y. Это противоречит условию невырожденности
задачи (2.2). Предположение не верно. Неравенство (7.11) доказано.
2. Докажем, что при некотором N1 > 0
Hk ≤ N1 Lk , k = 0, 1, 2, . . .
(7.16)
Поскольку векторы r = 0, x = x являются допустимыми по условию (5.7) для задачи (5.8),
то
Fk (r k , xk ) ≤ Fk (0, x).
Итак, для всех k = 0, 1, 2, . . .
m
m
(rik )2 +
dkj (xkj )2 ≤
dkj (xj )2 .
i=1
Поэтому
j=1
j∈J(x)
m
(rik )2 +
dkj (xkj )2 ≤
dkj |xj + xkj ||xkj − xj |.
i=1
j∈J0 (x)
(7.17)
j∈J(x)
В силу (5.10), (7.7), (7.11) при N2 ≥ 2M4 M9 имеем
dkj |xj + xkj ||xkj − xj | ≤ N2 Lk Hk .
(7.18)
j∈J(x)
Из (7.10), ограниченности последовательности векторов dk и соотношения I(u) ⊂ J0 (x)
следует, что при некотором N3 > 0
m
2
(rik )2 +
dkj (xkj )2 .
N3 (Hk ) ≤
i=1
j∈J0 (x)
Отсюда, учитывая (7.17), (7.18), получим
N3 (Hk )2 ≤ N2 Lk Hk , k = 0, 1, 2, . . .
Это дает требуемое неравенство (7.16) при N1 = N2 /N3 .
3. Из (7.11), (7.16) получаем (7.3) при P1 = M4 N1 .
Неравенство (7.4) следует из (5.2) и определений (7.7).
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
49
Соотношение x ∈ ri X вытекает из доказанного в теореме 4 соотношения x ∈ X и условия
невырожденности задачи (2.2). Действительно, согласно условию невырожденности задачи
(2.2), если задача (2.1) имеет оптимальное решение, то оно единственное. Относительная
внутренность множества, состоящего из одной точки, совпадает с этой точкой по определению.
Перейдем теперь к доказательству неравенств (7.5), (7.6) и соотношения u ∈ ri U .
4. Поскольку xj > 0 для j ∈ J(x), то, начиная с некоторой итерации k1 , для всех k > k1
ε ≥ xkj ≥ ε, j ∈ J(x),
(7.19)
где ε = 2 max xj , ε = 0.5 min xj .
j∈J(x)
j∈J(x)
5. Пусть l(k) = arg max{dkj : j ∈ J(x)} — номер, на котором реализуется значение Lk в
(7.7). Докажем, что для любого j ∈ J0 (x) при k → ∞
k
xkj dkj gl(k)
·
·
→ 0.
Lk gjk xkl(k)
(7.20)
Действительно, первый сомножитель ограничен по абсолютной величине значением N1 в
силу (7.16) и соотношения J0 (x) ⊂ I(u). Второй сомножитель ограничен по абсолютной
величине значением M3 в силу (5.2). У третьего сомножителя знаменатель, начиная с итерации k1 , для всех k > k1 не меньше положительного числа ε в силу (7.19). Числитель
третьего сомножителя сходится к нулю при k → ∞, поскольку l(k) ∈ J(x), J(x) ⊂ I0 (u).
6. Из (3.25) при j ∈ J0 (x) имеем
k
xkj dkj gl(k)
Lk gjk xkl(k)
=
k
zjk gl(k)
k
gjk zl(k)
.
В силу (7.20) величина в левой части приведенного равенства, начиная с некоторой итерации k2 , для всех k ≥ k2 по абсолютному значению будет меньше единицы. Согласно (3.25),
k
при k ≥ k1 должна быть отрицательной. Поэтому для k3 = max(k1 , k2 )
(7.19) величина zl(k)
при k ≥ k3
k
−gl(k)
gjk
0≤ k
≤ k , j ∈ J0 (x).
(7.21)
zl(k)
|zj |
Поскольку согласно (5.21) для k ≥ k0 , k ≥ k3 номер j(k) находится в I0 (u) и при этом
I(u) ⊂ J0 (x), то из (3.13), (7.21) следует, что для k4 = max{k0 , k3 } при k ≥ k4
j(k) ∈ J(x),
(7.22)
так как на этих итерациях множеству J(x) принадлежит номер l(k).
7. Согласно (3.7), (3.8), (7.1), если gjk < gik , то выполняются неравенства
dkj
dki
≤
σ(gjk )
σ(gik )
≤ N4
gjk
gik
(7.23)
при некотором N4 > 0.
8. Пусть t(k) = arg max{gjk , j ∈ J(u)} — номер компоненты, на которой в (7.7) реализуется
значение Tk .
Из (7.7), (7.22) следует, что при k ≥ k4
k
gj(k)
≤ Tk .
(7.24)
50
В.И. ЗОРКАЛЬЦЕВ
В силу (7.23) для k ≥ k4 получаем
k
dkt(k)
gj(k)
Tk dkj(k)
≥
1
.
N4
(7.25)
Из (3.2), (3.11)–(3.13), (3.25) для всех j = 1, . . . , n и k = 0, 1, 2, . . . имеем
gjk+1
gjk
= 1 − γk
k
xkj dkj gj(k)
xkj(k) dkj(k) gjk
.
Отсюда при j = t(k), учитывая (7.19), (7.24), (7.25), для всех k ≥ k4
k+1
k
gt(k)
≤ (1 − γ
)gt(k)
,
(7.26)
где γ
= γ0 ε/(εN4 ).
9. В силу (3.25), (7.19) величины zjk при k ≥ k4 , j ∈ J(x) отрицательные. Поэтому в
итеративном процессе (3.2) величины gjk монотонно убывают:
gjk+1 < gjk , j ∈ J(x), k ≥ k4 .
(7.27)
Пусть q — число номеров в наборе J(x). При любом k ≥ k4 на итерациях τ = k, . . . , k + q
номер t(τ ) будет дважды принимать одно и то же значение. Пусть t(π) = t(ϕ) при некоторых
π, ϕ, k ≤ π < ϕ ≤ k + q. Из определения (7.7) величины Tk и (7.25), (7.26) имеем
)Tπ < Tπ ≤ Tk .
Tk+q ≤ Tϕ ≤ (1 − γ
Следовательно, для всех k ≥ k4
Tk+q ≤ (1 − γ
)Tk .
Итак, величины Tk и, следовательно, все компоненты gjk при j ∈ J(x) сходятся к нулю
при k → ∞ не медленней, чем линейно. Неравенство (7.6) доказано.
10. Докажем, что при k ≥ k4 , j ∈ J0 (x)
|gjk+1
−
gjk |
xkj dkj k
≤
g .
Lk xkl(k) l(k)
(7.28)
Действительно, используя (3.2), (3.12), (7.20), (7.21) и условие γk ∈ (0, 1), имеем
|gjk+1 − gjk | = |λk zjk | ≤
k
−gj(k)
k
zj(k)
|zjk | ≤
k
−gl(k)
k
zl(k)
|zjk |.
Выражение в правой части этого неравенства имеет то же значение, что и выражение в
правой части (7.28).
Поскольку xj = 0 для j ∈ J0 (x), то в силу (7.16) первый сомножитель в правой части
неравенства (7.28) ограничен. Величина xkl(k) ограничена снизу в силу (7.19) при k4 ≥ 0
значением ε. Величина dkj ограничена сверху в силу ограниченности векторов xk и условий
(3.7), (3.9). Поэтому второй сомножитель в правой части (7.28) также ограничен.
k
≤ Tk . Поэтому из (7.28) следует (7.5).
Поскольку l(k) ∈ J(x), то gl(k)
11. Осталось доказать соотношение u ∈ ri U . Для этого согласно теореме 1 требуется
установить, что g j > 0 для всех j ∈ J0 (x). Воспользуемся леммой 3.
Согласно (7.5), (7.6) величины |gjk+1 − gjk | сходятся к нулю не медленнее, чем линейно.
Первое условие леммы 3 выполняется при всех j ∈ J0 (x).
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
51
Поделим левую и правую части неравенства (7.28) на gjk . Получаем
|gjk+1 − gjk |
gjk
k
xkj dkj gl(k)
.
≤
Lk gjk |xkl(k) |
Выражение в правой части этого неравенства является абсолютной величиной выражения в
(7.20). Из (7.20) получаем, что выполняется второе условие леммы 3, величины |gjk+1 −gjk |/gjk
сходятся к нулю при k → ∞. Следовательно, g j > 0 для всех j ∈ J0 (x) и поэтому u ∈ ri U .
12. Далее считаем, что при задании весовых коэффициентов достигаются условия (7.2).
В силу (7.2) при фиксированном β для α > 0 при α → 0 величина σ(α)/α сходится к
k
k
k )/g k
нулю. Так как gl(k)
∈ I0 (u), и, следовательно, gl(k)
→ 0 при k → ∞, то σ(gl(k)
l(k) → 0
k
k
k .
при k → ∞. Поскольку σ(gl(k) ) ≥ Lk , то Lk /gl(k) → 0 при k → ∞. Согласно (7.7) Tk ≥ gl(k)
Поэтому Lk /Tk → 0 при k → ∞. Из (7.3), (7.5) получаем (7.8).
13. Осталось доказать неравенство (7.9). Сначала докажем, что для алгоритма, удовлетворяющего условию (7.2), при некотором P5 > 0 выполняется неравенство
k
, k ≥ k4 .
Tk ≤ P5 gj(k)
(7.29)
Предположим противное. Тогда должна существовать бесконечная последовательность
номеров итераций K такая, что
k
/Tk → 0 при k ∈ K, k → ∞.
gj(k)
(7.30)
Можем считать, что для k ∈ K номера t(k) и j(k) имеют постоянные значения. Пусть
t(k) = t, j(k) = r при некоторых t и r из J(x) для всех k ∈ K.
В силу (3.7), (3.12), (3.14), (3.25), (7.19) для всех k ∈ K
λk ≥ −γ0 grk /zrk ≥ γ0 grk /(σ(grk )ε).
С другой стороны, из (3.12), (3.13), (3.25), (7.19) и неравенства γk < 1 для k ∈ K имеем
λk < −gtk /ztk ≤ gtk /(σ(gtk )ε).
Следовательно, для всех k ∈ K
ε
σ(grk )gtk
≥ γ0 .
k
k
ε
σ(gt )gr
Вместе с тем по предположению (7.30) и условию (7.2) при k ∈ K, k → ∞
σ(grk )gtk
→ 0.
σ(gtk )grk
Получаем противоречие, доказывающее ошибочность предположения. Неравенство (7.30)
доказано.
Согласно (7.22) на итерациях τ = k, k + 1, . . . , k + q при k ≥ k4 номер j(k) дважды будет
принимать одно и то же значение, которое обозначим p. Здесь q — число номеров в наборе
J(x) согласно обозначениям в формулировке теоремы 5. Пусть первый раз это произойдет
на итерации π, второй раз при τ = ϕ. Из (3.2), (3.17), (7.26), (7.29) имеем
k+q+1
≤ P5 gpϕ ≤ P5 (1 − γπ )gpπ ≤ P5 Tπ ≤ P5 Tk .
Tk+q+1 ≤ P5 gj(k+q+1)
Следовательно, Tk+q+1 ≤ P5 Tk (1 − γπ ). Это дает (7.9) в силу (3.14).
52
В.И. ЗОРКАЛЬЦЕВ
8. Варианты алгоритмов
Весовые коэффициенты можно задавать, в частности, в виде функции от компонент
вектора gk . Можно положить
dkj = (gjk )p , j = 1, . . . , n; k = 0, 1, 2, . . . ,
при заданном p ≥ 1. При p = 1 выполняется условие (7.1). При p > 1 будет выполняться
более сильное условие (7.2). Случай p = 2 соответствует алгоритму, получившему название
dual affine scaling method.
Условия (3.7)–(3.9) позволяют использовать и такие правила вычисления весовых коэффициентов, при которых эти коэффициенты не выражаются в виде функции от значений gjk .
При этом не обязательно иметь конкретные выражения для функций σ и σ. Достаточно
иметь доказательство существования таких функций и указанных их свойств. В частности,
как показывают теоретические и экспериментальные исследования [11], [20]–[22], эффективны следующие правила задания весовых коэффициентов при k ≥ 1:
dkj =
gjk
max{ε, xk−1
}
j
, j = 1, . . . , n,
где ε — положительная малая величина. При k = 0 можно положить dkj = gjk . Такой алгоритм будет удовлетворять условию (7.1) и при этом, как доказано в [22], может иметь
сверхлинейную скорость сходимости при задании параметра γk , который сходится к единице.
Первый этап изложенного в разделе 3 вычислительного процесса (ввод в область допустимых решений задачи (2.2)) можно рассматривать как процесс оптимизации методом внутренних точек в области допустимых решений задачи линейного программирования α → min
при ограничениях
A u + g − αδ0 = 0,
α ≥ 0, gj ≥ 0, j = 1, . . . , n.
Здесь δ0 = g(u0 ) − g0 — вычисляемый по правилу (3.6) вектор на исходной итерации изложенного в разделе 3 вычислительного процесса. Значения uk , gk , αk = δk /δ0 на итерациях (k = 0, 1, 2, . . . ) вычислительного процесса раздела 3 составляют допустимое решение
данной задачи.
Литература
[1] Дикин И.И. Итеративное решение задачи линейного и квадратичного программирования, ДАН СССР
174 (4), 747–748 (1967).
[2] Анцыз С.М., Дикин И.И. Об одном численном методе решения задачи линейного программирования
и некоторых ее обобщений, Управляемые системы (ИМ СО АН СССР, Новосибирск, 1969), вып. 3,
с. 54–56.
[3] Дикин И.И., Зоркальцев В.И. Итеративное решение задач математического программирования: алгоритмы метода внутренних точек (Наука, Новосибирск, 1980).
[4] Евтушенко Ю.Г., Жадан В.Г. Релаксационный метод решения задач нелинейного программирования,
Журн. вычисл. матем. и матем. физ. 17 (4), 890–904 (1977).
[5] Евтушенко Ю.Г. Методы решения экстремальных задач и их применение в системах оптимизации
(Наука, М., 1982).
[6] Vanderbey R.J., Mecheton M.S., Freedman B.A. Modification of Karmarkar’s linear programming algorithm,
Algorithmica 1, 395–407 (1986).
[7] Barnes E.R. A variation on Karmarkar’s algorithm for solving linear programming problems, Math. Program.,
Ser. A 36, 174–182 (1986).
[8] Wei Zi-Luan. An interior point method for linear programming, J. Comput. Math. 5, 342–351 (1987).
ДВОЙСТВЕННЫЕ АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
53
[9] Зоркальцев В.И. Класс алгоритмов внутренних точек, Журн. вычисл. матем. и матем. физики 49
(12), 1–18 (2009).
[10] Зоркальцев В.И. Относительно внутренняя точка оптимальных решений (Коми филиал АН СССР,
Сыктывкар, 1984).
[11] Зоркальцев В.И. Метод относительно внутренних точек (Коми филиал АН СССР, Сыктывкар,
1986).
[12] Adler I., Rende M.G., Veiga G. An implementation of Karmarkar’s algorithm for linear programming, Math.
Program., Ser. A 44 (3), 297–335 (1989).
[13] Monma C.L., Morton A.J. Computational experience with a dual affine variant of Karmarkar’s method for
linear programming (Manuscript, Morristown, NJ, Bell Communication Research, 1987).
[14] Черников С.Н. Линейные неравенства (Физматлит, М., 1968).
[15] Еремин И.И. Теория линейной оптимизации (ИММ УрО РАН, Екатеринбург, 1999).
[16] Broyden C.G. On theorems of the alternative, Optimization methods and software 16, 101–111 (2001).
[17] Зоркальцев В.И., Киселева М.А. Системы линейных неравенств (ИГУ, Иркутск, 2007).
[18] Рокафеллар Р. Выпуклый анализ (Мир, М., 1973).
[19] Зоркальцев В.И. Метод наименьших квадратов: геометрические свойства, альтернативные подходы,
приложения (Наука, Новосибирск, 1995).
[20] Зоркальцев В.И. Методы прогнозирования и анализа эффективности функционирования системы
топливоснабжения (Наука, М., 1988).
[21] Садов С.Л. Исследование эффективности алгоритмов метода внутренних точек, Вопросы теории и
практики создания региональных автоматизированных систем (Коми НЦ УрО АН СССР, Сыктывкар,
1988).
[22] Зоркальцев В.И. Проективные алгоритмы оптимизации, использующие множители предыдущей
итерации, Журн. вычисл. математики и матем. физ. 34 (7), 943–950 (1994).
В.И. Зоркальцев
профессор, кафедра математической экономики,
Иркутский государственный университет,
бульв. Гагарина, д. 20, г. Иркутск, 664003,
Институт систем энергетики им. Л.А. Мелентьева
Сибирского отделения Российской Академии наук,
ул. Лермонтова, д. 130, г. Иркутск, 664033,
e-mail: zork@isem.sei.irk.ru
V.I. Zorkaltsev
Professor, Chair of Mathematical Economics,
Irkutsk State University,
20 Gagarin blvd., Irkutsk, 664003 Russia,
Institute of Energy Systems, Siberian Branch of Russian Academy of Sciences,
130 Lermontov str., Irkutsk, 664033 Russia,
e-mail: zork@isem.sei.irk.ru
Документ
Категория
Без категории
Просмотров
6
Размер файла
265 Кб
Теги
двойственной, алгоритм, внутренние, точек
1/--страниц
Пожаловаться на содержимое документа