18.1Переход к задаче с ограничениями-равенствами

Существует простой метод перехода от (3:1) к задаче с ограничениями только в виде равенств. Для этого следует ввести новые переменные !1; !2; :::; !kсвязанные с исходными переменными соотношениями

(!i)2 + gi(x1; x2; :::; xn) = 0 i = 1:::k (3:2)

Получим следующую задачу: найти минимум ф-и при ограничениях:

(

Равносильность задач (3:1) и (3:3) понимается в следующем смысле: если x точка локального минимума (максимума) ф-и в задаче (3:1), то точка (x ; ! ) будет точкой локального минимума (максимума) ф-и f(x) в задаче (3:3). При этом

!i = ( g (x ))1

i 2

Необходимые условия локального экстремума ф-и f(x) могут быть найдены методом исключения и методом множителей Лагранжа.

Для поиска локальных экстремумов методом множителей Лагранжа в задаче (3:3) следует ввести ф-ю Лагранжа

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

19 Выпуклые множества

Определение 4. Непустое множество X 2 Rn называется выпуклым, если

8

> x1 + (1 )x2 2 X

<

x1; x2 2 X

>

: 2 [0; 1]

То есть, если X вместе со своими точками x1; x2содержит и соединяющий их отрезок. Примерами выпуклых множеств служат:

1.одноточечные множества

2.шар

3.отрезок

4.прямая линия

5.луч

6.гиперплоскость

Теорема 1. Пусть I - любое коне100чное или бесконечное множество индексов, а Xi; i 2 I - выпуклые множества. Тогда их пересечения

X = \i=IXi

Док-во. Пусть x1; x2 2 X - пересечение выпуклых множеств, а 2 [0; 1]. По определению пересечения имеем x1; x2 2 Xi; i 2 I. Значит

x = x1 + (1 )x2 2 Xi

т.к. Xi; i 2 I - выпукло Следовательно

32

x 2 \i2IXi = X

То есть множество X - выпукло.

Важные подклассы выпуклых множеств образуют выпуклые конусы и аффинные множества. Определение 5. Множество X 2 Rn называется конусом, если

(

x 2 X x 2 X

> 0

То есть если множество X вместе с любой своей точкой содержит и проходящий через нее луч с началом в 0.

Множество X 2 Rn называется выпуклым конусом, если

8 1x1 + (1 2)x2 2 X

>

>

>x1; x2 2 X

<

> 1 > 0

>

>

: 2 > 0

то есть одновременно является выпуклым множеством и конусом. Определение 6. Множество X 2 Rn называется аффинным, если

8

> x1 + (1 )x2 2 X

<

x1; x2 2 X

>

: 2 R

то есть множество X вместе с любыми своими двумя точками x1; x2 содержит и всю проходящую через них прямую. Аффинные множества - множества решений систем конечного числа линейных у-ний или пересечения конечного числа гиперплоскостей.

19.1Выпуклые функции

Определение 7. Ф-я f определенная на выпуклом множестве X 2 En называется выпуклой, если

x1 6= x2 2 [0; 1]

неравество (3:5) выполняется как строгое, то ф-я f называется строго выпуклой на X.

В кач-ве определения выпуклой ф-и можно взять следующий критерий: для выпуклости ф-и f(x) на выпуклом множестве X необходимо и достаточно чтобы ее надграфик

Xf = ffx; yg : x 2 X; y > f(x)g

Для гладких функций f(x) 2 C(1)используется такой критерий. f(x) x 2 En выпукла в том и только в том случае, если для всех точек x x 2 En выполняется неравенство

f(x) f(x ) >< f0(x ); x x >(3:5 )

C(1) - множество непрерывных ф-ий имеющих первую производную.

Если ф-я f(x) x 2 En дважды непрерывно-диффернцируемая, т.е. f(x) 2 C(2) то она выпукла тогда и только тогда, когда ее матрица Гессе

@2f > 0 x 2 En @x2

неотрицательна. Для неотрицательности квадратной матрицы Anxnнеобходимо и достаточно чтобы все ее главные миноры были неотрицательны.

33

19.2Необходимое и достаточное условие минимума ф-и на выпуклом множестве

Теорема 2. Пусть X - выпуклое множество и ф-ия f(x) 2 C(1). Пусть X - множество точек минимума f(x) на X. Тогда в любой точке x 2 X выполняется неравенство

<f0(x ); x x > > 0 (3:5 )

а если x 2 Int X, то неравенство (3:5 ) превращается в равенство

f0(x ) = 0

Если кроме того f(x) выпукла на X, то условие (3:5 ) является достаточным для того, чтобы x 2 X

Док-во.

Необходимость. Пусть x 2 X тогда при любых x 2 X 2 [0; 1].

f(x) =< f0(x); h > +O(h; x) (3:6 )

где h - приращение аргумента x, O(h; x) - бесконечно малая величина, получим

0 6 f(x + (x x )) f(x ) = < f0(x ); x x > +O( )

или

x = x + "0e 2 X

Получим, что

"0 < f0(x ); e >> 0

при всех ", что выполняется условие

j"j 6 "0

что возможно лишь при

<f0(x ); e >= 0

Всилу произвола вектора e отсюда получаем, что

f0(x ) = 0

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

X 6= En

т.е. на части пространства En.

Достаточность. Пусть ф-я f(x) 2 C(1) является выпуклой на X. Пусть для некоторой точки v 2 X выполнено условие (3:5 ), тогда из неравенства (3:5 )

f(x) f(v) >< f0(v); x v >> 0

справедливого для любой выпуклой ф-и, заданной на выпуклом множестве. При v = x получим f(x) f(x ) >< f0(x ); x x >> 0

f(x) f(x ) > 0 f(x) > f(x )

для всех точек x 2 X, то есть точка x принадлежит множеству точек минимума.

34