|
|
(3.3.3) |
Коэффициенты разложения вектора b по базису UÁ1,Á2 будем называть базисными переменными, остальные коэффициенты - небазисными переменными.
Базис UÁ1,Á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) обладает свойством единственности, и среди Dj, удовлетворяющих условиям Куна-Таккера существует отрицательное Dj0, т.е.
(3.4.5)
Пусть Á ' - множество индексов, полученное из Á вычитанием индекса j0:
(3.4.6)
Тогда, если x*' - оптимальный вектор задачи
(3.4.7)
то справедливо неравенство:
f(x*')<f(x*)
(3.4.8)
Доказательство.
Так как в силу выполнения соотношения (3.4.6) и определения множеств XÁ и XÁ' вытекает, что XÁ' É XÁ то имеет место неравенство f(x*') £ f(x*). Следовательно для доказательства соотношения (3.4.8) достаточно показать, что f(x*') ¹ f(x*).
Предположим, что это не так. Тогда точка x* является оптимальной для задач (3.4.3) и (3.4.7), и удовлетворяет условиям Куна-Таккера в обоих задачах:
(3.4.9)
(3.4.10)
Добавим в правую часть равенства (3.4.10) член 0ej0. Поскольку, по предположению (3.4.5) леммы коэффициент Dj0 отличен от нуля, получаем разложение вектора градиента функции f по системе векторов {L1, .. Lm, ej (jÎ Á(x*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
При использовании материалов активная ссылка на источник обязательна.