Знание — сила. Библиотека научных работ. ~ Портал библиофилов и любителей литературы ~

Меню Главная Биология и химия Иностранные языки и языкознание История и исторические личности Коммуникации связь цифровые приборы и радиоэлектроника Краеведение и этнография Кулинария и продукты питания Маркетинг реклама и торговля Мировая экономика МЭО Не Российское законодательство Немецкий Неопределено Нотариат Общениеэтика семья брак Основы права Охрана окружающей среды экология Философия Финансовое право Финансовый менеджмент финансовая математика Финансы деньги кредит Французский Хозяйственное право Цифровые устройства Этика эстетика Блог Карта сайта Поиск По всему сайту Статьи Комментарии Файлы Форум Гостевая Ссылки Новости

Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при ф...       (3.2.2)               Здесь Ai- столбцы матрицы A длины m, Di столбцы матрицы D длины n, Lk - строки матрицы A длины n, ej - n-мерные столбцы единичной матрицы. Здесь и далее xi - компоненты оптимального вектора задачи x, lk и Dk - множители Лагранжа условий Куна-Таккера. Запишем систему 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 будем считать базис UÁ1,Á2 порожденным одним множеством индексов Á=Á1.

(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*).

Страницы: 1, 2, 3, 4, 5, 6, 7

     Наверх    

© 2009 Все права защищены.