Методы оптимизации и исследование операций для бакалавров информатики. Часть 2

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

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

тельность переменных, задача имеет вид

−→

f (X ) = f (x1, . . . , xn) → min, 0 xj < ∞, j = 1, . . . , n.

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

динат xj . В левом варианте безусловный минимум функции по этой переменной находится в области отрицательных значений.

Рис. 9.11. Условная оптимизация по одной переменной с ограничением на ее неотрицательность

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

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

Условия (9.17) являются алгебраическим воплощением дан-

ных геометрических построений. Если xj > 0, то условие «б»

−→

∂f (X ) = 0, условие «а» ему не противоречит,

∂xj

если же xj = 0, то работает условие «a», а условие «б» при этом не работает.

В векторной форме условия (9.17) приобретают вид

−→ −→

a) f (X ) 0,

→− T →− →−

б) X f (X ) = 0,

→−

в) X 0.

Стандартный подход к решению этой задачи [15, с. 35] основан на использовании функции Лагранжа (лагранжиана)

жа (Lagrange multipliers), число которых равно количеству ограничений.

Необходимые (и достаточные в случае выпуклости всех участ-

Несмотря на всю неочевидность этого утверждения, оно объясняется довольно просто. Для начала предположим, что имеется задача минимизации при единственном ограничении. На рис. 9.12, представляющем двумерный случай, жирной линией изображе-

но множество допустимых точек, удовлетворяющих уравнению

−→ −→ g(X ) = 0 на фоне семейства изолиний целевой функции f (X ).

Рис. 9.12. Условная оптимизация с одним ограничением-равенством

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

функции до тех пор, пока не достигнем точки касания с одной из

−→

них. Это и есть искомая точка оптимума X . В ней касательные

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

где λ — произвольный множитель (множитель Лагранжа). На рисунке нормали направлены в разные стороны, поэтому множитель отрицателен.

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

Если ограничивающих уравнений не одно, а много, то данные

→−

gi(X ) = 0, i = 1, . . . , m.

Складывая равенства (9.21) и переобозначая неопределенные

множители через yi = −λmi , получаем необходимые условия экстремума

Вспоминая определение функции Лагранжа (9.18), замечаем, что выражение (9.22) может быть переписано в виде

что эквивалентно (9.19).

Точно так же в силу линейности функции Лагранжа по yi выражение (9.23) может быть представлено как

∂yi

что эквивалентно (9.20).

П р и м е р. На рис. 9.13 представлена задача минимизации функции двух переменных f (x1, x2) = x21 + (x2 + 1)2 → min при

условии 2x1 + x2 = 2.

Рис. 9.13. Пример условной минимизации с ограничением в виде равенства

Функция Лагранжа для этой задачи

L(x1, x2, y) = x21 + (x2 + 1)2 + y(2x1 + x2 − 2).

Необходимые условия экстремума:

1)∂L = 2x1 + 2y = 0, ∂x1

2)∂L = 2x2 + 2 + y = 0, ∂x2

3)∂L∂y = 2x1 + x2 − 2 = 0.

Решая систему уравнений, получаем x1 = 1.2, x2 = −0.4, y = = −1.2.

Поскольку функции f (x1, x2) и g(x1, x2) выпуклые, то приведенные выше необходимые условия являются достаточными для того, чтобы найденная стационарная точка действительно была точкой условного минимума целевой функции.

9.4. Теорема Куна — Таккера

Теорема Куна — Таккера играет ключевую роль в теории выпуклого программирования. Развивая классическую теорию оптимизации с ограничениями в виде равенств, она устанавливает необходимые и достаточные условия оптимальности для общей задачи (9.1):

−→

f (X ) → min,

−→

gi(X ) 0, i = 1, . . . , m,

−→

X 0.

Как и в классической теории, условия оптимальности формулируются с помощью функции Лагранжа (9.18)

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

выпуклого программирования тогда и только тогда, когда су-

→−

Доказательство необходимости. Пусть X — оптимальный

→−

план. Докажем, что существует вектор Y 0, такой, что для

→− →−

(X , Y ) выполняется условие седловой точки.

Построим (m + 1)-мерное (i = 1, . . . , m) евклидово простран-

→−

ство векторов Z = (z0, z1, . . . , zm)T и определим в нем два множества:

как оно является пересечением конечного числа полупространств,