3.6. Случай дифференцируемости

Весьма важными для практического использования являются неравенства, которые определяют условие существования седловидной точки. Ниже эти неравенства выписаны для основной задачи выпуклого программирования, когда допустимое множество X имеет вид

то есть когда

Теорема 3.3. Если функции φ(х) и f(x) основной задачи выпуклого программирования (3.2) непрерывно дифференцируемы на множестве Г = {x: x≥0}, то для того чтобы пара х^*, y^* была седловой точкой функции Лагранжа в области x≥0, y≥0, необходимо и достаточно выполнение условии

(3.19)

(3.20)

(3.22)

(3.23)

где

Доказательство. Запишем условия (3.19) - (3.24) в эквивалентной форме:

(3.19')

(3.20')

x^*_i≥0 (3.21')

(3.22')

(3.23')

y^*_j≥0 (3.24')

Необходимость. Пусть существуют х^* ≥ 0, y^* ≥ 0 такие, что

Отсюда, в частности, следует

для x_i≥0, то есть точка x_i^* является точкой минимума функции одного переменного L(x_i, y^*) для x_i≥0 (в частности, точкой локального минимума). А условия (3.19') - (3.21') и суть необходимые условия локального минимума при x_i≥0 для функции одного переменного (поскольку либо x_i^* - внутренняя точка полуоси x_i≥0 и тогда , либо x_i^* = 0 и тогда ).

Поскольку L(х^*, y) линейна (по y), то необходимость условий (3.22) - (3.24) очевидна.

Достаточность. Пусть выполняются условия (3.19') -(3.24'). Так как φ(x) и h(x) (см. (3.4)) выпуклы, то L(x, y^*) выпукла по х для x≥0 и, следовательно, для нее имеет место неравенство (см. (2.18))

Отсюда и из (3.19) -(3.21) получаем

Левое неравенство в (3.6) с очевидностью получается из линейности L(x^*, y) по y и из (3.22)-(3.24).

Замечание 1. Если потребовать, чтобы множество X удовлетворяло условиям регулярности, то (3.19)- (3.24) будут необходимыми и достаточными условиями существования оптимальной точки х^*.

Замечание 2. Если в задаче (3.1) Γ = E_n, то аналогичными рассуждениями нетрудно убедиться, что седловая точка будет определяться условием и соотношениями (3.22) - (3.24).

Условия (3.19) - (3.24) можно записать в иной, более геометричной форме.

Как и прежде, будем обозначать

Векторы -φ'(х) и -f_i'(x) в дальнейшем будем называть антиградиентами функций φ(x) и f_i(x).

Заметим, что вектор -e_i является внешней нормалью относительно X к граничной гиперплоскости x_i = 0, а вектор -f'_i(x) - внешней нормалью в точке х к граничной поверхности f_i(x) = b_i.

Рассмотрим точку x∈Х. Если эта точка принадлежит границе множества X, то, естественно, некоторые из неравенств, определяющих X, обращаются в равенства.

Пусть

Теорема 3.4. Пусть множество X основной задачи выпуклого программирования обладает свойством регулярности (3.3), а функции φ(x) и f(х) непрерывно дифференцируемы на множестве Г = {х: x≥0}. Тогда для оптимальности х^*∈Х необходимо и достаточно, чтобы антиградиент целевой функции можно было представить в виде линейной комбинации с неотрицательными коэффициентами внешних нормалей к ограничениям в точке х^*:

(3.27)

Доказательство. Покажем, что условия (3.19)-(3.22) можно записать в форме (3.27). Этим и будет доказана теорема.

Условия (3.21) и (3.22) определяют, что x^*∈Х. Обозначим

тогда (3.19) примет вид

Из условия (3.24) следует y_i≥0 , а условия (3.20') и (3.23') примут вид

υ_ix_i^* = 0

y_i(b_i - f_i(x^*)) = 0

И так как х^*∈Х, то в силу (3.25) и (3.26) получаем окончательно (3.27).

Из сказанного в замечании 1 следует, что условия (3.27) необходимы и достаточны для существования оптимального х^*.

Замечание 3. Если в задаче (3.1) Г = Е_n, то, опираясь на замечание 2, легко убедиться, что соотношение (3.27) примет вид

, y_i ≥ 0, i∈I(x^*).