Поиск нормальных решений слау методом внутренних

ПОИСК НОРМАЛЬНЫХ РЕШЕНИЙ СЛАУ
МЕТОДОМ ВНУТРЕННИХ ТОЧЕК1
В.И. ЗОРКАЛЬЦЕВ, С.М. ПЕРЖАБИНСКИЙ, П.И. СТЕЦЮК,
Институт систем энергетики им. Л.А. Мелентьева СО РАН,
Иркутск, Россия,
Институт систем энергетики им. Л.А. Мелентьева СО РАН,
Иркутск, Россия,
Институт кибернетики им. В.М.Глушкова НАН Украины,
Киев, Украина,
[email protected], [email protected],
[email protected]
Рассматривается задача поиска нормальных решений
системы
линейных
алгебраических
уравнений
при
двусторонних ограничениях на переменные. Представлено
описание алгоритмов внутренних точек для решения
указанной задачи. Приведены результаты вычислительных
экспериментов вариантов алгоритма внутренних точек на
тестовых задачах разной размерности.
Ключевые слова: система линейных алгебраических
уравнений, прямые и двойственные алгоритмы внутренних
точек, нормальное решение, двусторонние ограничения на
переменные, octave-программа.
1. ФОРМУЛИРОВКА ЗАДАЧИ
Заданы: векторы b∈ R n , x ∈ R n , x ∈ R n , матрица A размера m × n ,
диагональная матрица W размера n с положительными
коэффициентами w j , j = 1, ... , n на диагонали. Переменные
составляют вектор x ∈ R n . Рассматривается задача:
1 T
x Wx → min ,
2
при ограничениях
Ax = b ,
1
Работа частично поддержана грантом РФФИ 13-06-00152а
202
(1)
(2)
x ≤ x≤ x
Считаем, что x > x , то есть x j > x j для всех j = 1, ... , n .
(3)
Сформулированная задача равносильна проблеме поиска
нормальных, то есть с наименьшей нормой, решения системы
линейных уравнений и неравенств (2), (3). Здесь в качестве нормы
выступает евклидовая норма
x
n
2
W = (∑ w j ( x j ) )
1
2
j =1
с весами w j . Как известно, задачи поиска наименее удаленных от
начала координат решений систем линейных неравенств
(линейные уравнения можно считать частным случаем линейных
неравенств)
часто
используются
при
математическом
моделировании и являются составной частью многих
вычислительных методов. В качестве непосредственного
обобщения данной задачи можно рассматривать проблему поиска
решения системы линейных неравенств, наименее удаленного от
заданного вектора x 0 ∈ R n . В частности в [1] рассматривается
задачи поиска вектора x ∈ R n из условий:
( x − x 0 )T W ( x − x 0 ) → min ,
(4)
при ограничениях (2), (3). Данная задача путем замены
переменных сводится к задаче вида (1) – (3).
Система линейных уравнений и неравенств вида (2), (3)
обладает рядом интересных, очень полезных в вычислительном
отношении свойств, рассматривавшихся в работах [2, 3]. Эти
свойства обусловлены тем, что у системы линейных уравнений (2)
все переменные имеют двусторонние ограничения, что
сформулировано в виде условия (3). Для дальнейшего полезно
представить двусторонние ограничения (3) в виде двух
ограничений-неравенств
− x ≥ −x ,
(5)
x≥x.
(6)
В [2, 3] рассматривалась задача поиска решений системы
линейных неравенств (2), (3) в виде задачи линейного
программирования с фиктивной целевой функцией (тождественно
203
равной нулю). Этой задаче соответствует интересная в
вычислительном отношении двойственная задача линейного
программирования уже с «реальной» (не равной тождественно
константе) целевой функцией при очень удобных в
вычислительном
отношении
однородных
ограниченияхнеравенствах.
Векторы
неопределенных
множителей
Лагранжа
ограничений (2), (5), (6) обозначим u, h , g . Причем u ∈ R m ,
h ∈ R n , g ∈ R n . Далее в качестве расширенного решения задачи (1)
– (3) будем рассматривать наряду с оптимальным значением
вектора x , также конкретные значения векторов множителей
Лагранжа u, h , g и вектор y = Wx .
2. АЛГОРИТМЫ ВНУТРЕННИХ ТОЧЕК
В рассматриваемых далее алгоритмах на итерациях k = 0, 1, 2, . . . ,
вырабатывается последовательность векторов x k из R n , для
которых неравенства (3) выполняются в строгой форме
x < x < x , k = 0, 1, 2, . . . ,
(7)
В качестве стартовой точки можно, например, взять вектор
1
x 0 = ( x + x) .
2
Каждая итерация включает семь этапов вычислений.
1. Задание весовых коэффициентов. Сначала рассмотрим
«классический»
вариант
алгоритма
внутренних
точек,
рассматривавшийся в монографии [4], в котором весовые
коэффициенты определяются по правилу
(8)
d kj = min { ( x j − x kj ) 2 , ( x kj − x j ) 2 } .
Обозначим d k вектор R n , составленный из данных весовых
коэффициентов.
Пусть
Dk = diag d k
диагональная матрица размера n с введенными весовыми
коэффициентами на диагонали.
204
2. Задание вектора невязок балансовых ограничений.
Вычисляем вектор
~
r k = b − Ax k .
Если для него выполняется условие
~
r k ≤ ε1 ,
(9)
(10)
то полагаем
rk = 0 ,
(11)
где r k − вектор из R m , ε 1 − заданная положительная малая
величина. Будем считать, что в этом случае осуществляется
процесс оптимизации в области допустимых решений задачи (1) –
(3).
Если для ~
r k неравенство (10) не выполняется, то полагаем
(12)
rk = ~
rk.
Считаем, что в этом случае осуществляется процесс ввода в
область допустимых решений задачи (1) – (3).
3. Проверка полученного решения на оптимальность (только
для итерации k ≥ 1 ). Если осуществляется процесс оптимизации в
области допустимых решений, r k = 0, то полагаем
~
x = xk , ~
y = Wx k , u~ = u k −1 .
Здесь u k −1 − приближение к значению вектора множителей
Лагранжа, вычисленное на предыдущей итерации (поэтому данный
этап вычислений осуществляется только при k ≥ 1 ).
Исходя из указанных значений ~y , u~ , вычисляем векторы
~
h = ( AT u − ~
y ) , g~ = ( ~
y − AT u~ ) .
(13)
+
+
Здесь ( ) + – операция неотрицательной срезки: для любого
вещественного α
( α ) + = max{0,α } .
Если выполняется неравенство
~
1 ~T ~ 1 ~T ~
T
(14)
x Wx + y Vy − bT u~ + x T h − x g~ ≤ ε 2 ,
2
2
то расчеты прекращаются в связи с получением решения близкого,
с требуемой точностью ε 2 > 0, к оптимальному. Условие (14)
205
означает проверку разности значений целевых функций прямой и
~
двойственных задач, вычисленных в точке ~y , u~ , h , g~ .
4. Вспомогательная задача поиска направления решения.
Обозначим Δx k вектор из R n , являющийся решением следующей
вспомогательной задачи относительно вектора переменных Δx :
1 k
1
(15)
( x + Δx )T W ( x k + Δx ) + Δx T Dk−1Δx → min,
2
2
при условии
AΔx = r k .
(16)
Из условий оптимальности Лагранжа следует, что для
оптимальности вектора Δx во вспомогательной задаче (15), (16)
необходимо выполнение равенства
(17)
(W + Dk−1 )Δx + Wx k = AT u .
Здесь u вектор из R m , состоящий из множителей Лагранжа
ограничения (16). Условие (17) становится достаточным, если Δx
удовлетворяет и условию (16).
Выразим из (16) вектор Δx через u
Δx = (W + Dk−1 ) −1 ( AT u − Wx k ) .
(18)
Подставим данное выражение в (16) Получим систему линейных
уравнений относительно вектора u :
Bk u = r k + c k ,
(19)
где
Bk = A(W + Dk−1 ) −1 AT ,
c k = A(W + Dk−1 ) −1Wx k .
Матрица Bk − симметрическая положительно определенная.
Потом для решения системы (19) может использоваться метод
квадратного корня.
Пусть u k – решение системы (19). Подставляя этот вектор
вместо u в (18), получим значение Δx k .
5. Проверка на совместность ограничений (2), (3). Положим
h k = ( AT u k ) + , g k = (− AT u k ) + .
Если
206
T
x T h k − x g k − bT u k < 0 ,
то согласно теоремам об альтернативных неравенствах [5] условия
(2), (3) противоречивы и дальнейшие расчеты должны быть
прекращены.
6. Вычисление шага корректировки решения. При заданном
параметре алгоритма γ ∈ (0, 1) вычисляем
~
λk = γ ⋅ max{ λ : x ≥ x k + λΔx k ≥ x} .
(20)
Можно рекомендовать использовать γ равным 2 / 3 . Исходя из
(20), величину шага находим по формуле
x j − x kj
x j − x kj ⎪⎫
~
⎪⎧
λk = γ ⋅ min ⎨ min
,
min
⎬.
k
k
j: Δx k >0 Δx k
⎪⎩ j: Δx <0 Δx j
⎪⎭
j
Если осуществляется процесс ввода в область допустимых
решений, то полагаем
~
λk = min{λk ,1}.
(21)
Если осуществляется процесс оптимизации в области допустимых
решений, то вычисляем
(22)
λˆk = arg min ( x k + λΔx k )T W ( x k + λΔx k ) ,
λ ≥0
Отсюда
λˆk = −
И затем полагаем
( x k )T WΔx k
.
(Δx k )T WΔx k
~
λ k = min{ λ k , λˆk } .
(23)
7. Итеративный переход. Он осуществляется по формуле
x k +1 = x k + λk Δx k .
(24)
Правила вычислениия шага (20) – (24) гарантируют, что из
выполнения неравенств (7) для вектора x k следует выполнения
этого неравенства для вектора x k +1 .
Для изложенного алгоритма на всех итерациях
выполняется равенство
~
r k +1 = (1 − λk )~
r k.
Это, в частности, объясняется использованием правила (21) при
вводе в область допустимых решений.
207
Второй вариант алгоритма. Вместо (8) можно использовать
следующее правило задания весовых коэффициентов [6]
⎧⎪ x j − x kj
x kj − x j ⎫⎪
d kj = min ⎨
,
, j = 1, . . . , n, (25)
k −1 ⎬
k −1
⎪⎩ max{ε , h j } max{ε , g j } ⎪⎭
где ε − заданная малая положительная величина,
h k = ( AT u k − Wx k ) + ,
g k = (Wx k − AT u k ) + , k = 1, 2, . . . .
При k = 0 можем считать h 0 = 0 , g 0 = 0 .
3. ЭКСПЕРИМЕНТАЛЬНЫЕ ИССЛЕДОВАНИЯ
Экспериментальные исследования рассматриваемых в
статье вариантов алгоритмов внутренних точек проводились на
задачах вида (1) – (3), отличающихся размерностью и границами
варьирования переменных. Алгоритмы условно обозначим
Primal_1 и Primal_2. В Primal_1 весовые коэффициенты
выбирались по правилу (8), в Primal_2 – по формуле (25). Расчеты
проводились
при
помощи
свободно
распространяемого
вычислительного средства Octave [7].
Целевые функции тестовых задач формировались по
правилу
1 n 2
(26)
ixi ,
2 i =1
ограничения вида (2) – по формулам
n
n−m
xi +
xj =
, i = 1, . . . , m .
(27)
2
j = m+1
∑
∑
Для каждого конкретного значения m и n рассматривались две
задачи, различающиеся правилам задания интервальных
ограничений. В первой задаче использовались следующие
ограничения
n−m
0 ≤ xj ≤
, j = 1, . . . , n .
(28)
2
208
Заметим, что в этом случае отпимальное решение находится
внутри множества векторов, удовлетворяющих ограниченияминеравенствам (28).
Во втором случае вводились ограничения
0.1 ≤ x j ≤ 1, j = 1, . . . , n .
(29)
Оптимальное решение в задаче (26), (27), (29) находится на
границе множества допустимых решений.
При вычислении весовых коэффициентов по правилу (25)
использовалось
ε = 0 .1 ,
для
проверки
оптимальности
вырабатываемых алгоритмом приближений (условия (10), (14)) –
ε1 = 0.001 , ε 2 = 0.01 .
В табл. 1 представлены результаты решения задач
алгоритмами внутренних точек Primal_1, Primal_2. В таблице
указано число итераций, за которое была решена тестовая задача.
В скобках приведено количество итераций, потребовавшихся для
ввода в область допустимых решений.
Таблица 1.
Результаты расчетов тестовых примеров алгоритмами
внутренних точек
Размерность
задачи
m = 100, n = 125
m = 100, n = 150
m = 100, n = 175
m = 100, n = 200
m = 100, n = 300
m = 100, n = 400
m = 200, n = 225
m = 200, n = 250
m = 200, n = 275
m = 200, n = 400
m = 200, n = 600
m = 200, n = 800
Количество итера-ций
для решения задачи (26),
(27), (28)
Primal_1
Primal_2
6 (3)
11 (4)
Количество итера-ций
для решения задачи (26),
(27), (29)
Primal_1
Primal_2
5 (2)
4 (2)
7 (4)
10 (3)
6 (2)
5 (2)
7 (4)
11 (3)
8 (2)
4 (2)
7 (4)
11 (4)
5 (2)
4 (2)
6 (5)
14 (4)
3 (1)
4 (2)
6 (5)
14 (5)
4 (3)
4 (2)
8 (4)
9 (2)
5 (3)
5 (2)
32 (4)
13 (3)
5 (3)
5 (2)
51 (4)
12 (3)
5 (3)
5 (2)
6 (5)
13 (4)
4 (3)
4 (2)
6 (5)
16 (11)
4 (3)
4 (2)
7 (6)
17 (6)
4 (3)
4 (2)
209
Из таблицы видно, что рассматриваемые тестовые задачи для
вариантов алгоритмов точек решаются за небольшое число
итераций. Причем существуют небольшие различия по объемы
вычислений у рассматриваемых алгоритмов. Это означает, что
алгоритм Primal_2 может эффективно использоваться с первых
итераций. Отметим, что первоначально этот алгоритм был введен в
[6] для борьбы с негативными эффектами влияния погрешностей
вычислений исходного алгоритма внутренних точек (Primal_1) в
конце вычислительного процесса.
Из сопоставления результатов решения двух типов задач
следует отметить такой важный факт: задачи с более «жесткими»
ограничениями-неравенствами на переменные (при условии (29))
решаются обоими алгоритмами существенно быстрее, чем задачи с
более «слабыми» огрмничениями-неравенствами (при условии
(28)). Этот факт нуждается в теоретическом осмыслении.
Заключение. Существенного сокращения объема вычислений
можно ожидать от использования двойственных алгоритмов
внутренних точек при решении указанной задачи.
При использовании двойственных алгоритмов внутренних
точек осуществляется монотонное улучшение по итерациям
целевой функции двойственной задачи. При этом на всех
итерациях
двойственные
переменные
удовлетворяют
ограничениям двойственной задачи. Причем ограничения
неравенства выполняются в строгой форме. На каждой итерации
вырабатываются приближения к решению исходной системы (2),
(3). Хотя эти приближения не обладают свойством монотонного
улучшения решения исходной системы они, как показывают
многочисленные эксперименты и некоторые теоретические [8]
результаты, существенно быстрее приводят к решению системы
(2), (3) , чем «прямые» алгоритмы внутренних точек. Как показали
многие эксперименты, «двойственные» алгоритмы также
существенно быстрее (с меньшим объемом вычислений)
идентифицируют случаи несовместности систем (2), (3). В работе
[9] представлены результаты сравнительных исследований,
демонстрирующие эффективность двойственных алгоритмов
внутренних точек для решения систем вида (2), (3) на тестовых
примерах
и
задачах
выбора
допустимых
режимов
210
функционирования электроэнергетических систем. Проведенные
экспериментальные
исследования
на
моделях
потокораспределения в трубопроводных системах также показали
наличие
значительных
вычислительных
преимуществ
у
«двойственных» алгоритмов внутренних точек [10].
Литература.
1. Стецюк П.И., Нурминский Е.А., Соломон Д.И.
Транспортная задача и ортогональное проектирование на
линейные
многообразия
//
Материалы
V-ой
международной научной конференции "Транспортные
системы и логистика", Кишинэу, 11-13 декабря 2013 года.
– Кишинэу, Эврика, 2013. – С. 251–263.
2. Филатов А.Ю. Развитие алгоритмов внутренних точек и
их приложений к системам неравенств: автореферат
диссертации канд.физ-мат. наук. – ИГУ: Иркутск, 2001. –
19с.
3. Зоркальцев В.И. Решения систем линейных неравенств
алгоритмами внутренних точек // Современные методы
оптимизации и их приложения к моделям энергетики –
Новосибирск: Наука, 2003. – С.110–141.
4. Дикин И.И., Зоркальцев В.И. Итеративное решение задач
математического программирования (алгоритмы метода
внутренних точек). – Новосибирск: Наука, 1980. – 144 с.
5. Зоркальцев В.И., Киселева М.А. Системы линейных неравенств. – Иркутск: Изд-во Иркут. гос. ун-та, 2007. – 127 с.
6. Zorkal’tsev V.I. Algorithms of projective optimization which
use the multipliers of previous iterations // Comp.Math.Phys.,
1994. – Vol.34. – №7. – Pp.943–950.
7. Octave [Электронный ресурс]: http://www.octave.org –
Режим доступа: свободный.
8. Zorcal’tsev V.I. Dual interior point algorithms // Russian
Mathematics (Iz VUZ). – Allerton Press, Inc., 2011. – Vol.55.
– № 4. – Pp.26– 43.
9. Войтов О.Н., Зоркальцев В.И., Филатов А.Ю.
Определение
допустимых
режимов
электроэнергетических систем алгоритмами внутренних точек //
211
Сибирский журнал индустриальной математики. – 2000. –
Т. 3. – №1. – С. 57–65.
10. Зоркальцев В. И., Медвежонков Д. С. Численные
эксперименты с вариантами алгоритмов внутренних точек
на нелинейных задачах потокораспределения //
Управление большими системами. – М.: ИПУ РАН, 2013.
– №46.
212