Первая величина задает момент обращения в ноль выбранной минимальной величины 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 Постановка задачи
Задачей параметрического квадратичного программирования с параметром в правых частях ограничений будем называть следующую задачу выпуклого программирования:
(4.1.1)
Требуется найти вектор-функцию x*(m) , минимизирующую целевую функцию при каждом m . Интервал изменения параметра может быть и неограниченным.
4.2 Некоторые свойства решения параметрической задачи квадратичного программирования.
Пусть получено решение задачи (4.1.1) при некотором значении параметра, равном m0 . Это означает, что получен вектор x*(m0) , а также набор индексов Б(m0) , и порожденный им оптимальный базис. Рассмотрим множество таких m , для которых это решение остается оптимальным и допустимым. Для этого запишем условия Куна-Таккера:
(4.1.2)
Как следует из постановки задачи, правую часть выражения (4.1.2) можно представить в следующем виде:
(4.1.3)
Разложив вектор R по указанному базису, и подставив это разложение в (4.1.3), получим следующие выражения для коэффициентов разложения (4.1.2):
(4.1.4)
Здесь
-
коэффициенты разложения вектора R по базису. Условием нарушения оптимальности решения
является факт обращения в ноль одного из неотрицательных коэффициентов (4.1.4).
Отсюда следует, что интервал, на котором исходное решение является оптимальным,
является отрезком следующего вида:
(4.1.5)
где
(4.1.6)
а
(4.1.7)
Из выражений (4.1.4) вытекает также тот факт, что на интервалах (4.1.5) вектор-функция x*(m) представляет собой отрезок прямой в пространстве En , и является линейной. Стало быть, значения целевой функции на интервале представляют собой параболу.
4.3 Применение метода субоптимизации на многообразиях к решению параметрической задачи квадратичного программирования.
Непосредственно из вышеизложенного следует алгоритм решения задачи квадратичного программирования с параметром в правых частях ограничений:
1. В начальной точке интервала допустимых значений параметра строится решение задачи квадратичного программирования с помощью метода субоптимизации, описанного выше.
2. С помощью формул (4.1.6-4.1.7) определяется интервал на котором полученное решение остается оптимальным.
3. В правой точке полученного интервала строится решение задачи квадратичного программирования методом субоптимизации на многообразиях. Поскольку в этой точке существуют два оптимальных базиса, с целью предотвращения зацикливания в качестве начального базиса для решения задачи предлагается использовать предыдущий оптимальный базис (если решение потеряло оптимальность) или предыдущий оптимальный