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