Глава II. Выпуклое программирование. Выпуклое программирование Выпуклое программирование необходимые и достаточные условия

Если в задаче математического программирования требуется найти экстремум функции, например:

на множестве допустимых решений, заданных ограничениями

1) целевая функция является дифференцируемой и вогнутой, т.е. для нее выполняется условие:

При любых ,

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

При любых ,

Тогда задача (4.7)-(4.8) называется задачей выпуклого программирования .

Любая линейная функция одновременно удовлетворяет условиям и выпуклости, и вогнутости; т.е. её можно считать как выпуклой, так и вогнутой. Это позволяет считать линейные задачи частным случаем задач выпуклого программирования.

Если для задач математического программирования в общем случае пока отсутствует стройная теория существования и устойчивости решения, то для задач выпуклого программирования такая теория есть.

Введём три определения:

1). Функцией Лагранжа задачи выпуклого программирования (4.7)-(4.8) называется функция:

,

, (4.9)

2). Говорят, что задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности , если существует хотя бы одна внутренняя точка множества допустимых решений , определяемого строгими неравенствами, полученными из (4.8) (т.е. ).

3). Точка называется седловой точкой функции , если для всех выполнено:

Если целевая функция (убрать)

В теории нелинейного программирования центральное место занимает теорема Куна-Таккера, обобщающая классический метод множителей Лагранжа на случай, когда ограничения нелинейной задачи наряду с ограничениями в виде равенств содержат также и ограничения в виде неравенств.

Теорема Куна-Таккера. Если задача выпуклого программирования (4.7)-(4.8) удовлетворяет условию регулярности, то точка является оптимальным решением этой задачи тогда и только тогда, когда существует такая точка с неотрицательными координатами, что является седловой точкой функции Лагранжа данной задачи.

Условия Каруша- Куна- Таккера в дифференциальной форме:

Если функция Лагранжа является выпуклой по , вогнутой по и непрерывно дифференцируемой по всем и , то для того чтобы пара была седловой точкой функции Лагранжа , необходимо и достаточно, чтобы выполнялись следующие условия:

,

,

,

Пример .Теорема Куна-Таккера обосновывает сведение задачи выпуклого программирования к задаче поиска седловой точки функции Лагранжа. Чтобы такое сведение имело практический смысл, необходимо, чтобы получившаяся задача была в чём-то проще исходной. Это происходит не всегда, поэтому разработан ряд прямых методов поиска решения нелинейной задачи (4.5), (4.6). Рассмотрим некоторые из них.

ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ, раздел математического программирования, в котором исследуется задача максимизации вогнутой целевой функции f(х) векторного аргумента х = (x 1 , ..., х n), удовлетворяющего ограничениям g i (х) ≥ 0, х Є Х, i = 1, ..., m, где g i - вогнутые функции, Х - выпуклое множество. Точка х, удовлетворяющая этим ограничениям, называется допустимой. Основным результатом теории выпуклого программирования является теорема о седловой точке: для того чтобы допустимая точка х* задачи выпуклого программирования была оптимальной, необходимо (при довольно широких условиях) и достаточно существование вектора у* = (у* 1 , ..., y m *) с неотрицательными компонентами у* такого, что точка (х*, у*) является седловой для функции Лагранжа

задачи выпуклого программирования, то есть для любых х Є Х и у с неотрицательными компонентами выполняются неравенства

На теорему о седловой точке опирается ряд методов выпуклого программирования, в которых либо минимизируется функция φ(y 1 , ..., у m) = max x Є X L(x, у) при у i ≥ 0, i = 1, ..., m, либо непосредственно отыскивается седловая точка, причём вместо функции Лагранжа иногда используются некоторые её модификации. Другой подход к решению задачи выпуклого программирования связан с поиском возможных направлений движения допустимой точки х, которые не выводят из множества допустимых точек и при движении вдоль которых целевая функция возрастает. Этот подход реализуется с помощью последовательности итераций. На каждой итерации вычисляется возможное направление, исходящее из очередной точки, после чего производится сдвиг по этому направлению на некоторое расстояние до следующей точки. Существуют методы решения задач выпуклого программирования, специально приспособленные к тому случаю, когда целевая функция нелинейна, а ограничения линейны. Как правило, методы выпуклого программирования требуют для точного определения оптимальной точки бесконечного числа итераций. Исключением являются задачи квадратичного программирования (целевая функция - сумма вогнутой квадратичной и линейной функций, ограничения линейны) и линейного программирования (целевая функция и ограничения линейны), для которых в основном используются конечные методы. Многие вычислительные методы выпуклого программирования реализованы в виде программ для ЭВМ; существуют также пакеты программ, охватывающие задачи линейного программирования и выпуклого программирования. Смотри также Исследование операций.

Лит.: Гольштейн Е. Г. Выпуклое программирование. Элементы теории. М., 1970; Зангвилл У. И. Нелинейное программирование. Единый подход. М., 1973.

Пусть дана система неравенств вида

(4.3) и функция

Z = f (x 1 , x 2 , …, x n), (4.4)

причем все функции является выпуклыми на некотором выпуклом множестве M, а функция Z либо выпукла на множестве М, либо вогнута.

Задача выпуклого программирования состоит в отыскании такого решения системы ограничений (4.3), при котором целевая функция Z достигает минимального значения, или вогнутая функция Z достигает максимального значения. (Условия неотрицательности переменных можно считать включенными в систему (4.3)).

Ввиду свойства 3 0 всякая задача линейного программирования является частным случаем задачи выпуклого программирования. В общем случае задачи выпуклого программирования являются задачами нелинейного программирования. Выделение задач выпуклого программирования в специальный класс объясняется экстремальными свойствами выпуклых функций: всякий локальный минимум выпуклой функции (локальный максимум вогнутой функции) является одновременно и глобальным; кроме того, ввиду свойства 2 0 выпуклая (вогнутая) функция, заданная на замкнутом ограниченном множестве, достигает на этом множестве глобального максимума и глобального минимума. Отсюда вытекает, что если целевая функция Z является строго выпуклой (строго вогнутой) и если область решений системы ограничений не пуста и ограничена, то задача выпуклого программирования всегда имеет единственное решение .

Функция F(X) = F(x 1 , x 2 , …, x n) называется сепарабельной , если ее можно представить в виде суммы функций, каждая из которых зависит только от одной переменной, т.е. если

(не исключено, что F i (x i) = 0 при некоторых i).

Пусть в задаче выпуклого программирования заданы система ограничений (4.3) и целевая функция (4.4), при этом и функция цели Z, и все ограничения, являются сепарабельными. Тогда задача имеет вид:

Найти минимум выпуклой (максимум -- вогнутой) функции

при ограничениях

Идея метода кусочно-линейной аппроксимации состоит в том, что все f i , и все заменяются ломаными линиями, состоящими из прямолинейных отрезков. При этом исходная задача выпуклого программирования заменяется новой, приближенной задачей, которая является задачей линейного программирования. Эта задача решается обычно симплексным методом, и ее решение является приближенным решением исходной задачи выпуклого программирования.

Рисунок 12. Решение задачи выпуклого программирование методом кусочно-линейной аппроксимации

Для построения приближенной задачи рассмотрим кусочно-линейную аппроксимацию функции одной переменной h(х), заданной на отрезке . Разобьем этот отрезок на r частей точками x 0

Уравнение участка ломаной между точками (x k ; h k) и (x k+1 ; h k+1) имеет вид (уравнение прямой по двум точкам). Если каждое из отношений в этом равенстве обозначить через, то получим:

Отметим, что для каждого существует единственное значение, удовлетворяющее условиям (4.7). Обозначив можно переписать (4.7) в виде:

[Уравнения (4.8) называются параметрическими уравнениями отрезка.

Если h(x) = 0, то второе из этих уравнений обращается в тождество 0 = 0, а первое принимает вид (4.1) - уравнение отрезка, лежащего на оси абсцисс].

Таким образом, для любого уравнение ломаной можно записать в виде:

причем всегда отличны от нуля только два значения (если х является внутренней точкой k-гo отрезка разбиения) или одно (если х совпадает с концом отрезка).

Возвращаясь к задаче выпуклого программирования с сепарабельными функциями, отметим, что прежде всего (в зависимости от системы ограничений) нужно определить интервал изменения каждой переменной x j . Затем каждый этот интервал разбивается на части точками x jk и с использованием формул (4.9) строится кусочно-линейная аппроксимация для функций f j и. После этого можно для исходной задачи (4.6) записать приближенную задачу:

Найти максимум функции

при ограничениях (4.10)

Поскольку приближенная задача (4.10) является задачей линейного программирования, которая обычно решается симплексным методом, условия неотрицательности переменных записываются отдельно от остальных ограничений.

Отличие полученной задачи (4.10) от обычной задачи линейного программирования состоит в том, что для каждого x j имеется не более двух соседних ненулевых и, значит, нельзя брать в качестве основных переменных два с одинаковым j и несоседними k. Заметим также, что для условий неотрицательности переменных слагаемых f j (x j) и (если таковые окажутся) кусочно-линейную аппроксимацию проводить, конечно, не нужно.

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

Функция называется выпуклой

Функция называется вогнутой на выпуклом множестве , если для любых точек и произвольного числа выполняется неравенство:

Иногда выпуклую функцию называют выпуклой вниз в отличие от вогнутой функции, которую иногда называют выпуклой вверх. Смысл этих названий ясен из геометрического изображения типичной выпуклой (рис. 3.3) и вогнутой (рис. 3.4) функции.

Рис. 3.3. Выпуклая функция

Рис. 3.4. Вогнутая функция

Подчеркнем, что определения выпуклой и вогнутой функций имеют смысл только для выпуклого множества X , так как только в этом случае точка обязательно принадлежит Х .

Задачей выпуклого программирования называется частный случай общей задачи математического программирования (3.7), (3.8), когда целевая функция и функции ограничений являются вогнутыми на выпуклом множестве R .

Так как задача максимизации функции эквивалентна задаче минимизации этой функции со знаком «минус», ограничение эквивалентно неравенству и из вогнутости следует выпуклость и наоборот. Отсюда

задачей выпуклого программирования называется также задача минимизации выпуклой функции при ограничениях:

, ,

где – выпуклые функции; R – выпуклое множество. Это просто другая форма задачи.

Следует обратить внимание, что если задача выпуклого программирования формулируется как задача на максимум, то целевая функция обязательно вогнута, а если формулируется как задача на минимум – то выпукла, Если ограничения записываются в виде , то функции ограничений вогнуты, если ограничения записываются в виде , то функции ограничений выпуклы. Эта связь обусловлена наличием определенных свойств у задачи выпуклого программирования, которые при нарушении такой связи могут отсутствовать. Два основных таких свойства сформулированы в следующей лемме.

Лемма 1

Множество допустимых планов задачивыпуклого программирования

является выпуклым. Любой локальный максимум вогнутой функции на Х является глобальным.

Если бы функции ограничений были выпуклы, то для определяемого множества Х (3.14) выпуклость уже бы не следовала. В этом случае можно доказать выпуклость множества:

Если бы целевая функция была выпукла, то утверждение леммы относительно ее максимумов стало бы неверным, однако аналогичное утверждение можно было бы доказать для минимумов.

Функция называется строго выпуклой на выпуклом множестве , если для любых точек , и произвольного числа выполняется неравенство .

Функция называется строго вогнутой на выпуклом множестве , если для любых точек , и произвольного числа выполняется неравенство:

Лемма 2

Сумма выпуклых (вогнутых) функций выпукла (вогнута). Произведение выпуклой (вогнутой) функции на положительное число выпукло (вогнуто). Сумма выпуклой (вогнутой) и строго выпуклой (строго вогнутой) функций строго выпукла (строго вогнута).

Теорема 1

Если функция строго вогнута (строго выпукла) на выпуклом множестве Х , то у нее может быть только одна точка максимума (минимума).

Доказательство

Предположим противное, т.е. что существует две точки , , являющиеся точками максимума строго вогнутой функции на Х . Обозначив , имеем . Тогда для любого справедливо:

т.е. пришли к противоречию. Аналогично доказывается для минимума строго выпуклой функции.

Линейная функция представляет собой единственный пример одновременно выпуклой и вогнутой функции, значит, она не является строго выпуклой (строго вогнутой). Квадратичная функция может быть не выпуклой (вогнутой), а может быть строго выпуклой (строго вогнутой); все это определяется матрицей D . Элементы матрицы D представляют собой вторые частные производные квадратичной функции, т.е.

.

Обозначим матрицу вторых частных производных через .

Лемма 3

Для того чтобы квадратичная функция была выпуклой (вогнутой) на всем пространстве , необходимо и достаточно, чтобы матрица D была положительно (отрицательно) определена. Если D положительно (отрицательно) определена, т.е.

то строго выпукла (строго вогнута).

Задача максимизации (минимизации) квадратичной функции при линейных ограничениях, где D – отрицательно (положительно) определенная матрица, причем D T = D , называется задачей квадратичного программирования .

Из леммы вытекает, что рассмотренная в разделе 2 задача линейного программирования, как и задача квадратичного программирования, представляет собой частный случай задачи выпуклого программирования.

Бывают функции, которые выпуклы по одной группе переменных и вогнуты по другой. Такие функции представляют собой один из основных классов функций, у которых заведомо существует седловая точка.

Теорема 2

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

Рассмотрим функцию Лагранжа для задачи выпуклого программирования:

(3.15)

определенную на прямом произведении , где . Эта функция в силу вогнутости , является вогнутой по и линейной, а следовательно, выпуклой по .

Однако нельзя утверждать на основании теоремы 1, что она имеет седловую точку, так как множество R не обязательно является замкнутым и ограниченным, а Y заведомо неограниченно. Тем не менее, можно ожидать, что при некоторых условиях седловая точка все же будет существовать.

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

Теорема Куна-Таккера

Если задача выпуклого программирования удовлетворяет условию Слейтера, то необходимым и достаточным условием оптимальности плана является существование такого , что пара является седловой точкой функции Лагранжа (3.15) на .

То, что условие Слейтера является существенным, показывает следующий пример.

Пример 1

Дана задача выпуклого программирования:

Здесь, очевидно, что x = 0 есть решение задачи, но у функции Лагранжа седловой точки нет, так как внешняя грань в минимаксной задаче не достигается:

Разбиение ограничений в задаче выпуклого программирования на и , как уже говорилось, является условным. Поэтому обычно под R понимается множество простого вида, это либо все пространство E n , либо неотрицательный ортант, либо параллелепипед. Сложность же задачи выпуклого программирования определяется системой ограничений:

.

Так как седловая точка функции Лагранжа ищется на произведении множеств , где Y также является множеством простого вида (неотрицательным ортантом), то смысл теоремы Куна-Таккера состоит в сведении задачи поиска экстремума функции со сложными ограничениями на переменные к задаче поиска экстремума новой функции с простыми ограничениями.

Если множество R совпадает с E n , то условия экстремума, как известно, имеют вид:

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

Теорема 3

Для того чтобы непрерывно дифференцируемая вогнутая функция имела в точке максимум на E n , необходимо и достаточно, чтобы градиент функции в точке был равен нулю, т.е. .

Вспомним, что градиент функции равен:

.

Таким образом, для нахождения седловой точки функции Лагранжа на произведении , а следовательно, и для нахождения решения задачи выпуклого программирования при R = E n надо решить систему уравнений (3.16). Но в этой системе n уравнений, а неизвестных n + m , так как помимо n -мерного вектора нам неизвестен и m -мерный вектор множителей Лагранжа . Однако для седловой точки функции Лагранжа выполняется очень важное свойство:

. (3.17)

Из уравнения (3.17) вытекает, что либо , либо , либо то и другое одновременно. Это свойство аналогично второй теореме двойственности (подразд. 2.5) линейного программирования. Ограничения, которые выполняются в некоторой точке как равенства, называются активными .

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

Лекция 11. Выпуклое программирование

Определение 1. З адачей выпуклого программирования называется задача нелинейного программирования, где все функции являются выпуклыми.

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

(1)

, (2)

. (3)

Нам понадобятся некоторые вспомогательные построения в пространстве
векторов
. Вектор из первых
компонент точки будем обозначать через . Итак,
.

Для задачи (1) – (3) определим множество

где
.

Лемма . Для задачи выпуклого программирования (1) – (3) множество выпукло .

Доказательство. Выберем произвольные векторы
из множества и число
. Тогда существуют точки и из такие, что и . Умножим эти неравенства на и
, соответственно, и сложим их. В силу выпуклости всех функций получаем

Из полученных неравенств и вытекает выпуклость множества .

Теорема 1. (Теорема Куна-Таккера в форме о седловой точке функции Лагранжа задачи выпуклого программирования ) Пусть в задаче выпуклого программирования (1) – (3) система (2) удовлетворяет условию Слейтера относительно был решением задачи (1) – (3), необходимо и достаточно, чтобы существовал неотрицательный вектор такой, что
– седловая точка функции Лагранжа.

Доказательство. Поскольку достаточность этого условия уже доказана для произвольной задачи нелинейного программирования (см. теорему 2.6 введения), осталось доказать только необходимость.

Необходимость. Пусть – решение задачи (1) – (3). Положим
. Очевидно, что
, так как
,
и
.

Убедимся, что
. Предположим противное. Это означает, что найдется точка
такая, что
. Следовательно, – такая допустимая точка, значение целевой функции в которой меньше минимального. Получаем противоречие с тем, что – решение задачи выпуклого программирования.

Итак,
. Согласно лемме множество выпукло. Следовательно, выполняются все требования теоремы 8.2. Поэтому существует ненулевой

вектор
опорный в точке ко множеству :

Убедимся далее, что все координаты вектора неположительны. Предположим противное. Пусть существует координата
. Зафиксируем у вектора все компоненты, кроме -ой. Тогда, учитывая, что произведение
может принимать сколь угодно большие значения (в силу неограниченности сверху координаты ), получаем противоречие с неравенством (4).

Легко увидеть, что при любом
векторы
включаются во множество . Тогда из (4) имеем:

Покажем, что
. Пусть это не так. Тогда
. Следовательно,
. По условию Слейтера существует вектор
такой, что
. Поэтому
. Полученное противоречие и означает, что
.

Обозначим
. Покажем, что построенный вектор представляет собой искомый вектор множителей Лагранжа. Очевидно, что
и из (5) получаем

Отсюда при
следует

. (7)

С другой стороны, так как
(поскольку
) и
, получаем неравенство

. Отсюда и из (7) следует, что в точке
выполняется условие дополняющей нежесткости:

. (8)

Из (6) и (8) имеем

или, что то же самое,

Далее, пусть
. Тогда
. Отсюда и из (8) получаем неравенство

Неравенства (9), (10) и означают, что
– седловая точка функции Лагранжа задачи выпук-

лого программирования. Что и требовалось.

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

Теорема 2. Пусть – выпуклая и дифференцируемая на
функция, множество
выпукло. Тогда для того, чтобы точка
была условным минимумом функции на множестве
, необходимо и достаточно, чтобы выполнялось включение

. (11)

Доказательство следует непосредственно из теоремы 6.5 и определения конуса
опорных векторов в точке ко множеству
.

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

, (12)

.

Доказательство. Покажем, что условия (12) и (13) эквивалентны включению (11). Пусть точка
такова, что
. Тогда
и
.

Пусть теперь
. Тогда из теорем 2 и 10.5 следует, что необходимым и достаточным условием экстремума является существование таких множителей
,
, для которых
. Положим
для всех
и получим из последнего равенства условия (12) и (13). Что и требовалось.

В заключение параграфа приведем формулировки двух теорем Куна-Таккера для задачи вы-

пуклого программирования с линейными ограничениями.

Теорема 4. Пусть в задаче выпуклого программирования (1) – (3) система ограничений (2) имеет вид

, b – вектор размерности
. Тогда для того, чтобы неотрицательный вектор был решением задачи, необходимо и достаточно, чтобы

существовал неотрицательный вектор такой, что
– седловая точка функции Лагранжа данной задачи.

Отметим, что в этом случае функция Лагранжа имеет вид .

Теорема 5. Пусть в задаче выпуклого программирования (1), (2) целевая функция непрерывно дифференцируема, система ограничений (2) имеет вид
, где A – матрица размерности
, b – вектор размерности
. Тогда для того, чтобы вектор
был решением задачи, необходимо и достаточно, чтобы существовал неотрицательный вектор такой, что выполняются условия
,
.

Заметим, что в теоремах 4 и 5 не требуется выполнения условия Слейтера, поэтому они не являются частными случаями теорем 1 и 3 и требуют самостоятельного доказательства.