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

4.1. Постановка задачи и определения

Постановка задачи поиска минимума функций.

Найти такой

вектор

x = (x , ..., x

n

)T

, принадлежащий области допустимых

1

значений U En

( En − евклидово пространство), целевая функция от которого

f (x ) = min f (x) .

(4.1)

x U

Необходимо обратить внимание на следующее.

1. Поиск максимума функции

f (x) сводится к задаче определения минимума

путем замены знака перед функцией на противоположный

f (x ) = max f (x) = −min(− f (x)) .

x U

x U

2. Задача определения минимума и максимума целевой

функции f (x)

называется задачей поиска экстремума

f (x ) = extr f (x) .

x U

3. Если множество

допустимых

решений U

задается

ограничениями

(условиями), накладываемыми на вектор

x , то решается задача поиска условного

экстремума. Если U = En ,

то ограничения (условия)

на вектор x

отсутствуют, и

решается задача поиска безусловного экстремума.

включает точку x

и значение целевой функции в ней.

Напомним, что точка

x U

называется точкой глобального минимума, или

просто минимума функции

f (x)

на множестве U , если функция достигает в этой

точке своего наименьшего значения, т.е. f (x ) ≤ f (x)

для всех x U ;

точка

x U

называется точкой

локального

минимума функции

f (x)

на

множестве

U , если

существует

такое

ε > 0 , что

если x U и

x − x

< ε ,

то

f (x ) ≤ f (x) . Здесь

x

= x2

+... + x2 − евклидова норма вектора x .

1

n

Определение.

Поверхностью уровня

функции

f (x) называется множество

точек, в которых функция принимает постоянное значение, т.е.

f (x) = const . Если

n = 2 , то поверхность уровня изображается линией уровня на плоскости E2 .

Пример 4.1. Построить линии уровня функций:

а)

f (x) = x2

+ x2

;

б) f (x) =

x2

2 ;

в)

f (x) = x2 − x2 ;

г) f (x) = x2 .

1

+ x

1

2

4

2

2

1

2

□ а) f (x) = x2 + x 2

= const = r 2 − уравнение окружности с центром в точке (0 , 0)T

1

2

и радиусом, равным r ;

x2

б)

f (x) =

1

+ x22 = const − уравнение эллипса. Если const =1, то a = 2, b =1 −

4

большая и малая полуоси эллипса;

в)

f (x) = x

2

− x2

= const − уравнение гиперболы;

2

1

г)

f (x) = x2

= const

− уравнение двух параллельных оси Ox

прямых. ■

2

1

Определение.

Градиентом f (x) непрерывно

дифференцируемой функции

∂f (x)

∂x1

∂f (x)

f (x) =

∂x

2

.

...

∂f (x)

∂xn

f (x) = f (x + x) − f (x) = f (x)T x +

1

xT H (x) x + o(

x

2 ) ,

(4.2)

где

2 )

2

o(

x

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

xT H (x)

x − квадратичная форма.

Пример

4.2.

Для

функции

f (x) = x2

+ x2

вычислить градиент

в точках

1

2

x(0)

= (0, 1)T , x(1) = (

1 ,

1 )T , x(2)

= (1, 0)T , x(3)

= (0,

−1)T и найти матрицу Гессе.

2

2

□ По определению градиента и матрицы Гессе имеем f (x) = (2x , 2x

2

)T ,

1

f (x(0) ) = (0,

2)T , f (x(1) ) = ( 2,

2)T , f (x(2) ) = (2,

0)T , f (x(3) ) = (0, − 2)T ,

H (x) =

2

0

.

2

0

Заметим, что матрица Гессе квадратичной функции не зависит от x . ■

Пример 4.3. Для функции f (x) = x2

+ x4

вычислить градиент и найти матрицу

1

2

Гессе в точках x(0) = (0, 0)T , x(1) = (1, 1)T .

□ Согласно определениям имеем f (x) =

3

T

2

0

;

(2x1 , 4x2 )

,

2

H (x) =

0

12x2

f (x(0) ) = (0,

0)T ,

H (x(0) ) =

2

0

f (x(1) ) = (2,

4)T ,

H (x(1) ) =

2

0

;

. ■

0

0

0

12

Определение. Квадратичная форма

xT H (x) x (и соответствующая ей матрица

Гессе H (x) ) называется:

положительно

определенной

( H (x) > 0 ),

если

для

любого

ненулевого

x

выполняется неравенство

xT H (x)

x > 0 ;

отрицательно

определенной ( H (x) < 0 ),

если

для

любого

ненулевого

x

выполняется неравенство

xT H (x)

x < 0 ;

положительно полуопределенной ( H (x) ≥ 0 ), если для любого

x

выполняется

неравенство

xT H (x) x ≥ 0

и имеется отличный от нуля вектор

x ,

для которого

xT H (x)

x = 0 ;

отрицательно полуопределенной ( H (x) ≤ 0 ), если для любого

x

выполняется

неравенство

xT H (x) x ≤ 0

и имеется отличный от нуля вектор

x ,

для которого

xT H (x)

x = 0 ;

неопределенной,

если существуют такие векторы

x ,

x ,

что выполняются

~

неравенства

x

T

H (x)

x > 0 ,

~T

~

< 0 ;

x

H (x) x

тождественно

равной нулю,

( H (x) ≡ 0 ),

если

для

любого

x

выполняется

xT H (x)

x = 0 .

Пример

4.4.

Классифицировать

квадратичную

форму

и

матрицу

Гессе

H (x) =

2

0

.

2

0

□

Выпишем

квадратичную

форму

xT H (x)

x = (

x ,

x

)

2

0

x

2

1

=

1

0

x2

2

2 x2 + 2

x2 .

1

2

Очевидно,

xT H (x) x > 0

для любого ненулевого

x . Согласно определению,

квадратичная форма (матрица Гессе) положительно определенная. ■

Пример

4.5.

Классифицировать

квадратичную

форму

и

матрицу

Гессе

H (x) =

2

0

.

0

0