§ 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).