ПРОГРАММИРОВАНИЕ ВЫПУКЛОЕ

— раздел программирования математического, изучающий задачи минимизации, в которых минимизируемая функция выпукла, а ограничения задаются также выпуклыми функциями. В общей форме задача П. в. может быть записана так: минимизировать ф-цию при ограничениях

где - -мерный вектор, от — выпуклые ф-ции. Задачи П. в. встречаются в математической экономике, электрических цепей теории; задачи аппроксимации ф-ций также представляют собой задачи П. в. В частности, в задачах аппроксимации ф-ций появляются такие выпуклые ф-ции, которые не являются дифференцируемыми, они требуют спец. изучения.

Пусть выпуклая ф-ция, определенная при всех х. Обозначим через мн-во таких векторов с, для которых при всех у выполняется неравенство: где скалярное произведение. Мн-во непусто, выпукло, замкнуто и ограничено. В случае, если дифференцируемая ф-ция в точке х, мн-во состоит из единственного вектора с, совпадающего с градиентом ф-ции

Характеристика точки минимума в задаче П. в. дается теоремой Куна — Таккера: если решение задачи П. в., то найдутся такие неотрицательные, не все равные нулю числа что

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

Тогда для того, чтобы точка была решением задачи П. в., необходимо и достаточно существование таких чисел , что

причем неравенство выполняется для всех х и для всех Если выполняются неравенства (2), то говорят, что точка есть седловая точка ф-ции .

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

Следующие ф-лы для вычисления множеств позволяют эффективно записывать необходимое условие экстремума в дифф. форме: если то . И если , то для любого найдутся такие числа и векторы что . Здесь мн-во тех индексов , для которых Эти ф-лы позволяют строить мн-ва для выпуклых ф-ций, образованных в результате суперпозиции других выпуклых ф-ций.

В некоторых случаях задача П. в. может ставиться в другой форме, в которой ограничения на переменные заданы не в виде системы неравенств. Пусть требуется минимизировать выпуклую ф-цию при условии, что х принадлежит выпуклому множеству X. Пусть точка решение задачи. Определим выпуклый конус как множество всех элементов у, представимых в виде где Сопряженный или двойственный относительно конус (обозначается ) определяется, как мн-во всех векторов с, удовлетворяющих неравенству для всех Тогда для того,

чтобы точка была решением поставленной задачи, необходимо и достаточно, чтобы существовал такой вектор что Для эффективного построения конуса можно воспользоваться следующим результатом: если выпуклая ф-дия и существует такая точка что то конус для области X, состоящей из точек х таких, что , состоит из единственной точки 0, если и из векторов с, представимых в виде если

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

Лит.: Пшеничный Б.Н. Необходимые условия экстремума. М., 1969 [библиогр. с. 148—151]; Зуховицкий С. И., Авдеева Л. И. Линейное и выпуклое программирование. М., 1967; Зойтендейк Г. Методы возможных направлений. Пер. с англ. М., 1963 [библиогр. с. 171—1741.

В. Н. Пшеничный.