3.7. Ограничения типа неравенств

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

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

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

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

Более точное условие получено Джоном [116], который доказал, что будет точкой минимума только тогда, когда существуют неотрицательные числа не равные одновременно нулю, причем такие, что выполняется условие

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

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

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

Достаточные условия локальной оптимальности выведены Мак-Кормиком [142] и Фиакко [71]. Они требуют, чтобы величина была положительной для всех векторов у, направленных внутрь допустимой области или касательных к ней в точке Здесь А — матрица Гессе для функции принято равным единице).

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

минимума гласит, что существуют скаляры и неотрицательные скаляры такие, что

Условия оптимальности являются темой детального рассмотрения в работе

3.8. Задачи

(см. скан)