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

Рефераты. Задача квадратичного программирования с параметром в правых частях ограничений и ее применение при ф...   3.6. Метод субоптимизации на многообразиях в задаче квадратичного программирования. Теоретическое обоснование.             Заметим, что если множество индексов Á порождает базис UÁ , то задача (3.5.1), соответствующая этому множеству индексов имеет единственный оптимальный вектор x* , обладая при этом свойством единственности, введенным ранее для задачи выпуклого программирования.           Выше были описаны вспомогательные задачи метода субоптимизации на многообразиях, однако не были сформулированы правила применения этих операций. Ниже будут доказаны две теоремы, дающие способ определения неизвестных шагов q и d. Для их доказательства потребуется несколько вспомогательных утверждений.           Лемма 1. Пусть вектора x0, x1 удовлетворяют системе уравнений условий Куна-Таккера и пусть f(x) - неотрицательно определенный квадратичный функционал вида xTDx, а D1 вектор ограниценных по знаку множителей Лагранжа, удовлетворяющих условиям Куна-Таккера совместно с вектором x1 . Тогда имеет место следующее неравенство:

(3.6.1)

 

          Доказательство:

 

          Преобразуем левую часть следующим образом:

 

 

          Здесь можно воспользоваться условием выполнения теоремы Куна-Таккера:

 

 

          Требуемое неравенство непосредственно вытекает из последнего соотношения.

 

          Следствие. Пусть x0, x0(q) - оптимальные точки задачи (3.5.1) с некоторым множеством индексов Á и вспомогательной задачи поиска минимума на многообразии (3.5.4). Тогда имеет место неравенство:

 

 

          Доказательство. Так как x0, x0(q) удовлетворяют условиям Куна-Таккера, то выполняется неравенство Леммы 1: 

 

 

          В силу особенностей решений x0, x0(q) правую часть неравенства можно записать в виде

 

 

          что и доказывает справедливость следствия.

 

          Лемма 2. Пусть x0, x1 - оптимальные точки многообразий XÁ0 и XÁ1 соответственно, удовлетворяющие условиям Куна-Таккера совместно с множителями Лагранжа D0  и D1. Тогда справедливо соотношение:

 

 

          Доказательство: Аналогично доказательству Леммы 1, получаем, что:

 

 

          Складывая эти два равенства, получаем:

 

 

          Из выполнения условий Куна-Таккера следует, что:

 

 

          Раскрывая скобки в левой части неравенства получаем искомое неравенство.

 

          Ниже будет доказана теорема, дающая направление движения и условия применения операции А.

          Теорема 1. Пусть оптимальная точка x0 - оптимальная точка многообразия XÁ0 , причем совокупность индексов Á0 порождает базис UÁ0 . Тогда, если среди множителей Лагранжа, соответствующих x0 , существует отрицательный (предположим, что он имеет индекс j0)

 

 

          то новый набор индексов

 

 

          также порождает базис  и  в единственной оптимальной точке  на многообразии  выполнено условие

 

 

          Доказательство.  Если для набора индексов  существует оптимальный вектор , то в силу утверждения леммы 2 и определения нового набора индексов имеем

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