Необходимые и достаточные условия

Глава II. Нелинейное программирование: экстремумы функций нескольких переменных

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

f (x ₁, x ₂, …, x_n) ® min (max)

(1)

где f, j_i (i =1, 2, …, m) - некоторые функции из R ^п в R. При этом система ограничений может отсутствовать.

Безусловный экстремум функций нескольких переменных

Напомним, что если в задаче (1) отсутствует система ограничений, то задача называется задачей безусловной оптимизации.

Необходимые и достаточные условия

1.1.1. (Необходимое условие экстремума первого порядка) Пусть X *Î R ^п - точка локального минимума (максимума) функции f (X) на множестве R ^п и f (X) дифференцируема в точке X *. Тогда градиент функции f (X) в точке X * равен нулю:

Ñ f (X *)= 0, (1.1.1)

что равносильно

=0, i =1, 2, …, n. (1.1.2)

1.1.2. (необходимое условие экстремума второго порядка) Пусть X *Î R ^п - точка локального минимума (максимума) функции f (X) на множестве R ^п и f (X) дважды дифференцируема в точке X *. Тогда матрица Гессе, вычисленная в точке X *, является положительно (отрицательно) полуопределённой:

H (X *)³0 (1.1.3)

(H (X *)£0) (1.1.4)

Точки, удовлетворяющие условиям (1.1.1), (1.1.2), (1.1.3) или (1.1.4), называются стационарными.

Условия 1.1.1 и 1.1.2 являются необходимыми условиями экстремума, но не достаточными. Действительно, для функции f (X)= - точка X *=(0, 0) является стационарной точкой, так как

, = 0 Û (3 , 3 )= 0 Û (х ₁, х ₂)=0

(то есть выполняются условия (1.1) и (1.2)), а также

=6 х ₁, =6 х ₂, = =0, H (X *)= .

(то есть выполняются условия (1.1.3) и (1.1.4)). Но эта точка не является точкой экстремума, так как существуют точки X ¹ и X ², в которых имеют место неравенства f (X ¹)< f (X *)< f (X ²): достаточно взять X ¹=(0; e) и X ²=(e; 0), где e >0 - сколь угодно малое число.

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

1.1.3. (Достаточные условия экстремума) Пусть функция f (X) в точке X * дважды дифференцируема, Ñ f (X *)= 0 и H (X *)>0 (H (X *)<0). Тогда точка X * является точкой локального минимума (максимума) функции f (X) на R ^п.

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

1. Найти у функции частные производные первого порядка.

2. Решив систему (1.1.2), найти стационарные точки функции.

3. Найти у функции частные производные второго порядка и составить матрицу Гессе H (X).

4. Определить, какие из стационарных точек являются точками максимума, какие - точками минимума, какие - ни тем, ни другим. Для этого используем информацию о знакоопределённости матрицы Гессе в стационарных точках (критерии 2.2 или 2.3 из Главы I).

Пример. Исследовать функцию f (X)=3 x ₁ x ₂- x ₁ - x ₂ на безусловный экстремум.

Решение. 1. Найдём у функции частные производные первого порядка: =3 x ₂- -2 x ₁ x ₂, =3 x ₁-2 x ₁ x ₂- .

2. Решая систему (1.2), найдём стационарные точки функции:

Вычитая из первого уравнения системы второе, приходим к уравнению 3 x ₂-3 x ₁- + =0. Дальнейшие очевидные преобразования приводят к уравнению (x ₂- x ₁)(3- x ₂- x ₁)=0. Дальше рассмотрим отдельно два случая:

Случай 1. x ₂- x ₁=0, то есть x ₂= x ₁. Подставляя это равенство, например, в первое уравнение системы, получаем уравнение 3 x ₁-3 =0, решениями которого являются x ₁=0 и x ₁=1. Тогда решениями системы являются Х ₁=(0, 0) и Х ₂=(1, 1).

Случай 2. 3- x ₂- x ₁=0, то есть x ₂=3- x ₁. Подставляя это равенство во второе уравнение системы, получаем уравнение -3 x ₁+ =0, решениями которого являются x ₁=0 и x ₁=3. Тогда решениями системы являются Х ₃=(0, 3) и Х ₄=(3, 0).

3. Найдём у функции частные производные второго порядка и составим матрицу Гессе H (X):

=-2 х ₂, =-2 х ₁, = =3-2(x ₁+ x ₂), H (X)=

4. Определим, какие из стационарных точек являются точками максимума, какие - точками минимума, какие - ни тем, ни другим. Для этого используем информацию о знакоопределённости матрицы Гессе в стационарных точках (критерии 2.2 или 2.3 из Главы I).

H (X ₁)= .

Составим характеристическое уравнение и решим его:

=0 Û =0 Û (l ²-9)=0 Û l ₁=3, l ₂=-3.

Так как собственные значения матрицы H (X ₁) имеют разные знаки, то матрица H (X ₁) - знаконеопределённая (см. 2.3 из Главы I и 1.1.2), а точка X ₁ не является точкой экстремума.

Для точки X ₂ имеем

H (X ₂)= , D₁=2<0, D₂= =3>0.

Так как угловые миноры матрицы Гессе знакочередуются, начиная с «-», то она является отрицательно определённой и по 1.1.3 точка X ₂ является точкой локального максимума.

Для точек X ₃ и X ₄ имеем H (X ₃)= и H (X ₄)= , и у них собственные значения l ₁=3+ , l ₂=3- совпадают, имея различные знаки. Поэтому матрицы Гессе для этих точек являются знаконеопределёнными, и точки не являются точками экстремума.

Таким образом, из стационарных точек только точка X ₂ является точкой экстремума - максимума. Значение функции в этой точке - f (X ₂)=3×1×1-1×1²-1²×1=1.

Ответ: (1, 1) - точка максимума, f _max(X)=1.

Дата добавления: 2015-07-20