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

Напомним, что общая задача условной оптимизации выглядит так

f(x)  min, x  ,

где  — собственное подмножество R^m. Подкласс задач с ограничениями типа равенств выделяется тем, что множество  задается ограничениями вида

f_i(x) = 0,

где f_i: R^m R (i = 1, ..., k).

Таким образом, = {x  R^m: f_i(x) = 0, i = 1, ..., k}.

Нам будет удобно писать у функции f индекс "0". Таким образом, задача оптимизации с ограничениями типа равенств записывается в виде:

f₀(x)  min, (3.1)

f_i(x) = 0, i = 1, ..., k. (3.2)

Если обозначить теперь через f функцию на R^m со значениями в R^k, координатная запись которой имеет вид f(x) = (f₁(x), ..., f_k(x)), то (3.1)–(3.2) можно также записать в виде f₀(x)  min, f(x) = .

Геометрически задача с ограничениями типа равенств — это задача о поиске наинизшей точки графика функции f₀ над многообразием  (см. рис. 3.1).

Рис. 3.1

Точки, удовлетворяющие всем ограничениям (т. е. точки множества ), обычно называют допустимыми. Допустимая точка x* называется условным минимумом функции f₀ при ограничениях f_i(x) = 0, i = 1, ..., k (или решением задачи (1)–(2)), если при всех допустимых точках x f₀(x*)  f₀(x). (3.3)

Если (3.3) выполняется только для допустимых x, лежащих в некоторой окрестности V_x* точки x*, то говорят о локальном условном минимуме. Естественным образом определяются понятия условных строгих локального и глобального минимумов.

Правило множителей Лагранжа.

Описываемый ниже необходимый признак локального условного минимума был сформулирован Лагранжем. Определим F: R^m  R^k+1, положив F(x) = (f₀(x), f₁(x), ..., f_k(x)). Заданная на R^m×R^k+1 скалярная функция Лагранжа M по определению принимает значения в R и задается равенством

M(x, ) = (, F(x)) =  _i f_i(x) (x  R^m,   R^k+1).

Координаты вектора , т. е. числа ₀, ₁, ..., _k называются множителями Лагранжа или двойственными переменными. Оказывается, имеет место следующая теорема, часто именуемая правилом множителей Лагранжа:

Теорема. Пусть F  C¹ и x* — локальный условный минимум функции f₀ при ограничениях f_i(x) = 0 (i = 1, ..., k). Тогда найдется ненулевой вектор * такой, что x* является стационарной точкой функции x M(x, *):

M_x(x, *)|_x=x*= *_i f _i(x*)= Q

Правило множителей Лагранжа доставляет необходимое условие локального условного минимума и поэтому позволяет искать точки, "подозрительные" на экстремум. В самом деле, для нахождения точки (x*, *)  R^m+k+1, т. е. для нахождения m + k + 1 неизвестных, мы имеем m + k уравнений

f(x) = , M_x(x, )= .

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

Регулярные точки.

Допустимая точка x задачи (3.1)–(3.2) называется регулярной, если векторы {f _i(x)}^k_i=1линейно независимы. Оказывается, что если x* — регулярная точка минимума, то в векторе * можно считать *₀ ненулевым, а поскольку множители Лагранжа определяются с точностью до множителя, можно считать, что *₀ = 1. Чтобы сформулировать это утверждение более точно, введем следующие обозначения. Пусть   R^k, а функция Лагранжа в регулярном случае определяется равенством

L(x, ) = f₀(x) + (, f(x)) = f₀(x) + _i f_i(x) (x  R^m,   R^k).

Очевидно, L(x, ) = M(x, ), где  = (1, ).