3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования.
К оглавлению1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 1617 18
В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.
Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора R размерности (m+n) по базису UÁ1,Á2 ; при этом на соседних итерациях базисы отличаются лишь каким-то одним из векторов.
Как было показано выше, существуют четыре возможных альтернативы при переходе от одного базиса к другому, задающие четыре типа операций:
1. От UÁ1 к UÁ2 (Á2=Á1 \ j0 ) при помощи замены в базисе вектора Pm+n+j0 на Pm+j0 .
2. От UÁ1 к UÁ2,Á1 (Á2=Á1 \ j0 U r) при помощи замены в базисе вектора Pm+r на Pm+j0 .
3. От UÁ2,Á1 (Á2=Á1 \ j0 U r) к UÁ2 при помощи замены в базисе вектора Pm+n+j0 на Pm+n+r .
4. От UÁ2,Á1 (Á2=Á1 \ j0 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, которая также имеет блочную структуру следующего вида:
Можно показать, что
Видно, что зная матрицу S1-1 можно легко получить значение матрицы B-1 . Используя общий вид переходов, а также их общее свойство, сводящееся к замене одного вектора на другой, можно применить для нахождения S1-1 известную формулу Фробениуса, и получить рекуррентные формулы, связывающие матрицы S1-1 на соседних итерациях. Это позволяет избежать непосредственного обращения матрицы на каждом шаге алгоритма, прибегая к нему через определенный промежуток времени с целью коррекции накопившейся ошибки вычисления.
В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.
Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора R размерности (m+n) по базису UÁ1,Á2 ; при этом на соседних итерациях базисы отличаются лишь каким-то одним из векторов.
Как было показано выше, существуют четыре возможных альтернативы при переходе от одного базиса к другому, задающие четыре типа операций:
1. От UÁ1 к UÁ2 (Á2=Á1 \ j0 ) при помощи замены в базисе вектора Pm+n+j0 на Pm+j0 .
2. От UÁ1 к UÁ2,Á1 (Á2=Á1 \ j0 U r) при помощи замены в базисе вектора Pm+r на Pm+j0 .
3. От UÁ2,Á1 (Á2=Á1 \ j0 U r) к UÁ2 при помощи замены в базисе вектора Pm+n+j0 на Pm+n+r .
4. От UÁ2,Á1 (Á2=Á1 \ j0 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, которая также имеет блочную структуру следующего вида:
Можно показать, что
Видно, что зная матрицу S1-1 можно легко получить значение матрицы B-1 . Используя общий вид переходов, а также их общее свойство, сводящееся к замене одного вектора на другой, можно применить для нахождения S1-1 известную формулу Фробениуса, и получить рекуррентные формулы, связывающие матрицы S1-1 на соседних итерациях. Это позволяет избежать непосредственного обращения матрицы на каждом шаге алгоритма, прибегая к нему через определенный промежуток времени с целью коррекции накопившейся ошибки вычисления.