Блок 2. В данном блоке определяется решение вспомогательной задачи (3.5.1). Способ определения решения зависит от предыдущего блока алгоритма:

          Блок 2(А). Эта часть блока вступает в действие после блока 3. Оптимальный вектор задачи (3.5.1) находится с помощью операции А. Если полученный оптимальный вектор допустим для исходной задачи (3.1.2), осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.

          Критерием выбора следующего шага является сравнение двух величин:

          Первая величина задает момент обращения в ноль выбранной минимальной величины Dj0 , вторая величина задает момент обращения в ноль первой из базисных компонент вектора x . Если вторая величина оказывается меньше первой, это означает, что новое решение задачи (3.5.1), полученное в результате операции А, не является допустимым для исходной задачи (3.1.2), и необходим переход в блок 4.  

          Блок 2(Б). Эта часть блока вступает в действие после блока 4. В этом блоке минимум в задаче (3.5.1) находится с помощью операции Б. Если получаемое решение оказывается допустимым для исходной задачи (3.1.2), то осуществляется переход в блок 3. В противном случае осуществляется переход в блок 4.

          Критерием выбора следующего шага в этой части блока является сравнение двух величин:

          Блок 4. Этот блок полностью соответствует соответствующему блоку в общем алгоритме субоптимизации на многообразиях для задачи выпуклого программирования.

            3.8. Некоторые особенности вычислительной схемы метода субоптимизации на многообразиях для задачи квадратичного программирования.

          В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.

          Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора 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 на соседних итерациях. Это позволяет избежать непосредственного обращения матрицы на каждом шаге алгоритма, прибегая к нему через определенный промежуток времени с целью коррекции накопившейся ошибки вычисления.    

            4. Задача квадратичного программирования с параметром в правых частях ограничений.

4.1 Постановка задачи

          Задачей параметрического квадратичного программирования с параметром в правых частях ограничений будем называть следующую задачу выпуклого программирования: