Экономико-математическое моделирование /
←предыдущая следующая→
1 2
Будем рассматривать следующую форму записи условий Куна-Таккера для задачи выпуклого программирования:
(3.2.1)
В нашем случае получим:
(3.2.2)
Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk - строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, k и k - множители Лагранжа условий Куна-Таккера. Запишем систему 3.2.2 в более обобщенной форме:
(3.2.3)
где составные столбцы P0, ... Pm+2n каждый длиной m+n являются столбцами блочной матрицы P, имеющей следующий вид:
(3.2.4)
В таком виде условия Куна-Таккера (3.2.3) можно записать в еще более простом виде:
(3.2.5)
Поскольку рассматриваемая нами задача является задачей выпуклого программирования, указанные условия существования минимума являются одновременно необходимыми и достаточными. Доказательство указанных условий можно найти в [1,2].
3.3. Базис задачи квадратичного программирования. Оптимальный и невырожденный базисы.
Поскольку ранг матрицы A равен m (см 3.1), система векторов
являются линейно независимой системой векторов. В то же время, легко видно, что линейная оболочка, натянутая на систему векторов P совпадает с пространством Em+n, т.е L(P)=En+m.
Следовательно из системы векторов 3.2.4 можно образовать конечное число базисов N евклидова пространства En+m, содержащих в себе векторы P1, .. Pm. Такие базисы пространства En+m будем называть базисами задачи квадратичного программирования, и обозначать следующим образом:
(3.3.1)
Для упрощения схемы алгоритма, запишем базис (3.3.1) в следующем виде:
(3.3.2)
Здесь 1 и 2 - наборы индексов. В случае, если 1=2 будем считать базис U1,2 порожденным одним множеством индексов =1.
(3.3.3)
Коэффициенты разложения вектора b по базису U1,2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис U1,2 назовем оптимальным, если его базисные переменные удовлетворяют условиям Куна-Таккера (3.2.3).
Базис называется невырожденным, если все его базисные переменные, соответствующие компонентам вектора x отличны от нуля, т.е.
(3.3.4)
Задачу (3.1.2) будем называть невырожденной, если все ее базисы невырождены. В противном случае назовем задачу вырожденной.
3.4. Метод субоптимизации на многообразиях. Выпуклый случай.
Для решения задачи (3.1.2) предлагается использовать метод
субоптимизации на многообразиях. Вначале рассмотрим основные идеи, приводящие к методу субоптимизации в случае задачи выпуклого программирования общего вида.
Рассмотрим задачу выпуклого программирования с линейными ограничениями, состоящую в минимизации выпуклой функции f(x) на множестве L, задаваемом ограничениями типа равенств.
(3.4.1)
Предположим, что задача имеет единственное решение, т.е минимум целевой функции достигается в единственной оптимальной точке x*. В этом случае задаче (3.4.1) эквивалентна задача:
(3.4.2)
Эквивалентность этих двух задач является следствием единственности решения. Переход к задаче (3.4.2) называется выделением активных ограничений, т.е. вместо условия неотрицательности всех переменных, мы переходим к условию равенства нулю всех компонент, решения, индексы которых не принадлежат множеству (x*).
Предположим, что для задачи (3.4.2) нахождение оптимального решения существенно проще, чем для исходной задачи (3.4.1). В этом случае, перебирая каким-либо образом всевозможные множества индексов k, являющиеся подмножествами полного набора индексов {1,..n}, и решая для каждого из них задачу (3.4.2), используя k вместо *, определить искомое множество индексов *.
Предположим также, что задача (3.4.2) обладает свойством
единственности, т.е система векторов {L1, .. Lm, ej (j (x*)}- линейно независима. В случае нарушения свойства единственности задача поиска оптимального вектора задачи (3.4.2) усложняется, и в дальнейшем этот случай рассматриваться не будет.
Алгоритм перебора множеств индексов k основан на следующей лемме.
Основная лемма:
Пусть x* является оптимальной точкой задачи:
(3.4.3)
где X - линейное многообразие, определяемое следующим образом:
(3.4.4)
Предположим, что задача (3.4.3) с условием (3.4.4) обладает свойством единственности, и среди j, удовлетворяющих условиям Куна-Таккера существует отрицательное j0, т.е.
(3.4.5)
Пусть ' - множество индексов, полученное из вычитанием индекса j0:
(3.4.6)
Тогда, если x*' - оптимальный вектор задачи
(3.4.7)
то справедливо неравенство:
f(x*')
←предыдущая следующая→
1 2
|
|