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

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

Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при ф...           Предположим, что это не так. Тогда точка 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*)}. Получаем противоречие с условием единственности, а стало быть, и с условием основной леммы.

          Доказанная лемма указывает направление перебора множеств индексов Ák (а стало быть и многообразий), уменьшающее значение целевой функции f(x).

          Из доказанной леммы вытекает

          Алгоритм поиска оптимального вектора

          Общий вид алгоритма метода субоптимизации для задачи выпуклого программирования приведен на рис. 1. Ниже приводятся описания блоков алгоритма, изображенных на этом рисунке.

          Блок 1. Определяется допустимая начальная точка x1 для исходной задачи. Это может быть точка, получаемая с помощью алгоритма построения начального базиса линейного симплекс-метода, или же решение в некотором смысле близкой линейной задачи. Предполагается Á1=Á(x1), k=1.

                Блок 2. Находится оптимальный вектор x*k для задачи

                Если x*k оказывается допустимой для исходной задачи (3.4.1), совершается переход к блоку 3, в противном случае осуществляется переход к блоку 4.

          Блок 3. Вычисляется значение

          Если

          то в силу выполнения условий Куна-Таккера для исходной задачи (3.4.1) точка x*k является оптимальной точкой задачи (3.4.1) и работа алгоритма заканчивается.

          Если

          то предполагаем

          и происходит переход к блоку 2.

Блок 4. Поскольку оптимальная точка вспомогательной задачи оказалась недопустимой для исходной, выбираем в качестве новой начальной точки ближайшую к ней точку, допустимую для исходной задачи (3.4.1), и лежащую на прямой, соединяющей оптимальные точки вспомогательной задачи, т.е.

                Далее полагаем Ák+1=Á(xk+1), заменяем k на k+1, и переходим к блоку 2.

          Таким образом построен итерационный процесс, позволяющий осуществить направленный перебор множеств индексов Á k, позволяющий найти оптимальный вектор исходной задачи. Сходимость процедуры будет рассмотрена позже.

3.5 Метод субоптимизации на многообразиях. Задача квадратичного программирования.

          Рассмотрим применение метода субоптимизации, рассмотренного в (3.4) к задаче квадратичного программирования (3.1.2). Как было ранее отмечено, условием успешного применения метода субоптимизации на многообразиях в задаче выпуклого программирования является существенная простота решения задачи (3.4.2) по сравнению с исходной задачей (3.4.1).

          Рассмотрим эквивалентную (3.1.2) задачу:

(3.5.1)

          Запишем условия Куна-Таккера для задачи (3.5.1) с произвольным набором индексов Á :

(3.5.2)

          Используя ранее введенные обозначения (3.2.3-3.2.4), систему условий Куна-Таккера (3.5.2) можно записать следующим образом:

(3.5.3)

          Если множество UÁ порождает базис, вследствие (3.5.3) поиск минимума на многообразии XÁ представляет собой разложение вектора P0 по этому базису, т.е. эквивалентен решению системы линейных уравнений. Таким образом, метод субоптимизации на многообразиях в случае задачи квадратичного программирования оказывается эффективным в том случае, если в цепочке итерационного процесса встречаются только множества индексов, порождающие базисы.

          Процедура метода строится на двух основных операциях, аналогичных блокам общего алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.

          Операция А. Пусть для некоторого набора индексов Á0 определена оптимальная точка x* и множители Лагранжа l*k и D*j удовлетворяющие условиям Куна-Таккера совместно с оптимальным вектором x. Рассмотрим вспомогательное многообразие

(3.5.4)

Операция А состоит в нахождении оптимального вектора x*(q), а также множителей Лагранжа, удовлетворяющих условиям Куна-Таккера задачи минимизации квадратичного функционала на многообразии (3.5.4).

          Запишем условия Куна-Таккера для этой вспомогательной задачи:

          Если набор индексов Á0 порождает базис, то существует разложение вектора Pm+j0 по этому базису, имеющее следующий вид:

(3.5.6)

          Подставляя это разложение в (3.5.5), и учитывая оптимальность набора x*,l*,D*, получаем следующие выражения для компонент оптимальной точки на многообразии (3.5.4):

(3.5.7)

          Таким образом, в случае, если набор индексов Á0 порождает базис, операция А осуществляется тривиально, и определяется выражениями (3.5.7).

          Суть операции А состоит в нахождении оптимальной точки на новом многообразии (3.5.4) по известной оптимальной точке на многообразии (3.4.4).

          Операция Б. Пусть некоторое вспомогательное многообразие XÁ0(q1) таково, что одна из базисных компонент вектора x обратилась в ноль:

(3.5.8)

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

     Наверх    

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