§ 3. Некоторые свойства обобщенного портрета

Нахождение обобщенного портрета, очевидно, сводится к задаче квадратичного программирования: найти минимум функции  при линейных ограничениях (14.3).

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

Для дальнейшего нам понадобится следующая теорема.

Теорема 14.4 (Куна – Таккера). Пусть заданы дифференцируемая выпуклая функция  и линейные функции ; . Пусть  доставляет минимум  при ограничениях

                   .             (14.8)

Тогда существуют такие числа , удовлетворяющие условиям

                ,             (14.9)

что справедливо равенство

                    (14.10)

( знак оператора градиента).

И обратно, если для некоторой точки  выполняются условия (14.8) и можно найти числа , удовлетворяющие условиям (14.9) и (14.10), то в точке  достигается условный минимум  при ограничениях (14.8).

Доказательство этой теоремы приведено в приложении.

Введем еще одно определение.

Определение. Будем говорить, что вектор  является крайним вектором множества  для вектора , удовлетворяющего (14.3) при константе , если выполняется равенство

.

Справедлива следующая важная для дальнейшего теорема.

Теорема 14.5. Обобщенный портрет может быть представлен в виде линейной комбинации крайних векторов. Причем крайние векторы множества  входят в это разложение вектора с неотрицательными коэффициентами, а крайние векторы множества  – с неположительными коэффициентами.

Иначе говоря, минимальный по модулю вектор , удовлетворяющий (14.3) может быть представлен как

,

,

            ,                       (14.11)

причем

      ,

   .            (14.12)

Доказательство. Для доказательства теоремы 14.5 воспользуемся теоремой 14.4, где положим

,

        ,

   .

Согласно утверждению теоремы 14.4 существуют такие неотрицательные  и , что

      ,

и

.

Вычисляя градиент, имеем

.

Полагая

,          ,

получаем

,

,

;

,

.

Теорема доказана.

Справедлива обратная теорема.

Теорема 14.6. Всякий вектор , удовлетворяющий (14.3) и допускающий разложение вида (14.11) по своим крайним векторам, совпадает с обобщенным портретом.

Доказательство немедленно следует из обратного утверждения теоремы 14.4 (Куна – Таккера) и единственности обобщенного портрета, если функции  и  интерпретировать так же, как при доказательстве предыдущей теоремы.

Замечание. В теореме 14.2 была доказана единственность обобщенного портрета. Однако обобщенный портрет, вообще говоря, не единственным образом разлагается по своим крайним векторам в виде (14.11).