Некоторыеособенности вычислительной схемы метода субоптимизации на многообразиях длязадачи квадратичного программирования.
В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.
Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора R
размерности (
m
+
n
)
по базису UÁ1,Á2 ; при этом на соседних итерациях базисы отличаются лишь каким-то одним из векторов.
Как было показано выше, существуют четыре возможных альтернативы при переходе от одного базиса к другому, задающие четыре типа операций:
1. От UÁ1 к UÁ2 (Á
2
=
Á
1
\
j
0
) при помощи замены в базисе вектора Pm
+
n
+
j
0
на Pm
+
j
0
.
2. От UÁ1 к UÁ2,Á1 (Á
2
=
Á
1
\
j
0
U
r
) при помощи замены в базисе вектора Pm
+
r
на Pm
+
j
0
.
3. От UÁ2,Á1 (Á
2
=
Á
1
\
j
0
U
r
) к UÁ2 при помощи замены в базисе вектора Pm
+
n
+
j
0
на Pm
+
n
+
r
.
4. От UÁ2,Á1 (Á
2
=
Á
1
\
j
0
U
r
) к UÁ2',Á2' (Á
'2=
Á
2
U
r
',
Á
'1=
Á
1
U
r
'
) при помощи замены в базисе вектора Pm
+
r
на Pm
+
n
+
r
'
.
Процедура разложения вектора R
по базису эквивалентна решению системы линейных уравнений вида
где B
- базисная часть матрицы P
(то есть матрица, составленная из столбцов матрицы P
, соответствующих векторам данного базиса). Решение уравнения есть процедура, эквивалентная обращению матрицы B.
Из общего вида матрицы P
(3.2.4) можно получить общий вид матрицы B
,
которая также имеет блочную структуру следующего вида:
Можно показать, что
Видно, что зная матрицу S
1
-1
можно легко получить значение матрицы B
-1
. Используя общий вид переходов, а также их общее свойство, сводящееся к замене одного вектора на другой, можно применить для нахождения S
1
-1
известную формулу Фробениуса, и получить рекуррентные формулы, связывающие матрицы S
1
-1
на соседних итерациях. Это позволяет избежать непосредственного обращения матрицы на каждом шаге алгоритма, прибегая к нему через определенный промежуток времени с целью коррекции накопившейся ошибки вычисления.
