Теорема 2 указывает направление перехода от одного многообразия к другому с помощью операции Б, утверждая положительность величины шага d1 .
Ранее (см 3.4) была приведена общая схема алгоритма субоптимизации на многообразиях для случая задачи выпуклого программирования и получена блочная структура алгоритма. Конкретизируем теперь структуру блоков для случая задачи квадратичного программирования.
Блок1.
Определяется начальный набор индексов Á1 , порождающий базис UÁ1 , для которого оптимальная точка задачи (3.5.1) является одновременно допустимой для исходной задачи (3.1.2). Такая точка в [2] называется дополняющей.
В кочестве начального множества индексов можно взять начальный базис, получаемый в ходе решения первой фазы двухфазного симплекс-метода, или же решение задачи линейного программирования, близкой к решаемой квадратичной:
Блок 3. Блок полностью идентичен приведенному ранее в описании алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.
Блок 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. Этот блок полностью соответствует соответствующему блоку в общем алгоритме субоптимизации на многообразиях для задачи выпуклого программирования.
В этой части будет рассмотрен вычислительный аспект процедуры субоптимизации и показаны некоторые ее замечательные свойства.
Выше было показано, что решение каждой вспомогательной задачи метода субоптимизации сводится к поиску разложения некоторого вектора 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, которая также имеет блочную структуру следующего вида:
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
