общего алгоритма субоптимизации на многообразиях для задачи выпуклого программирования.
Операция А. Пусть для некоторого набора индексов Б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)
Суть операции Б состоит в переходе от многообразия XБ0(q1) к другому многообразию XБ1 , соответствующему набору индексов Б1 , определяемому следующим образом:
(3.5.9)
т.е. индекс j0 из (3.5.4) заменяется на индекс r из (3.5.8).
Учитывая (3.5.8), разложение (3.5.5) на многообразии XБ0 можно представить следующим образом:
(3.5.10)
Аналогично случаю, рассмотренному в операции А, что, если имеет место разложение:
(3.5.11)
причем выполнено соотношение
(3.5.12)
то условиям Куна-Таккера для задачи (3.5.1) соответствующей набору индексов Б1 , удовлетворяют переменные, получаемые с помощью следующих формул:
(3.5.13)
где
(3.5.14)
Учитывая вышеописанные условия, операция Б оказывается осуществимой в том случае, когда наборам индексов Б0 и Б1 соответствует базис UБ1,Б0 . Операция Б является аналогом блока 4 общей схемы метода субоптимизации на многообразиях для задачи выпуклого программирования.
Для большей наглядности можно определить множество LБ1,Б0 представляющее собой прямую, порождаемую базисом UБ1,Б0 следующего вида:
(3.5.15)
Здесь
- коэффициенты разложения вектора P0,
а xir - вектора Pm+n+r
по базису UБ1,Б0. Заметим, что LБ1,Б0(0) есть оптимальный вектор многообразия (3.5.4) при q=
. Переход от этой точки к новому многообразию с помощью
операции Б представляет собой движение по указанной прямой от дельта равного
нулю в положительную (как будет показано позже) сторону.
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, получаем, что:
Складывая эти два равенства, получаем:
Из выполнения условий Куна-Таккера следует, что: