Файл: Васильев Ф.П. Лекции по методам решения экстремальных задач.pdf

54

М И Н И М И З А Ц И Я Ф У Н К Ц И И

МНОГИХ ПЕРЕМЕННЫ Х

[ Л , 2

2.

Для

описания и изучения -методов минимизации нам пон

бятся отдельные формулы и факты

из классического анализа. При­

мем

следующие

обозначения: Е т— евклидово

пространство

размер­

ности т\ и =

а

х

I — вектор-столбец или

точка

пространства Ет с

(

:

\umJ

координатами

u£,

i — 1 ,

2 , . . . , т;

иТ = (и1, ■■■, ит) — вектор-строка;

А =

{

а

— матрица порядка п х

т с элементами

acj(i = 1 ,2 , . . . ,п\

у = 1,

2,

. ••, т)\

матрицу,

полученную транспонированием

А,

будем

т

обозначать через АТ или

А*\

агb =

(а, Ь)еп =

а ‘Ь‘ — скалярное про-

i=i

_______

изведение двух

векторов

а

и b

из Е ,п; |а \Ет =

] / (а, а)Ет~

евклидова

норма вектора

а 6

Ет\ Аи = и — произведение матрицы

А на

вектор-

столбец

и, представляющее

собой

вектор-столбец v 6

Еп с

координа-

т

т

тами

v‘ = £

йци‘ \ (Ah,, t,) =

^

dijVV — квадратичная форма с сим-

Уг=1

£,/=1

метрической матрицей Л

порядка т х /гг,

||А ||„jm =

sup\Аи\Е — норма

матрицы А порядка п х т .

Там,

|и|<1

где не могут возникнуть недоразуме­

J

dj (иу

д Ч ( и )

ди1

д и £дик

’

Qp (U). — множество

всех

функций,

обладающих

на U

непрерывными

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

р включительно;

о (а) — величи­

на, бесконечно малая относительно а при а -» -0 , т. е. limo (а) -а- 1 .=

0 .

а -»0

Как

известно, для любых а, b 6 Ет имеет место неравенство Ко­

ши — Буняковского:

|(а,

Ъ) |< |а \■|Ь\, причем

знак

равенства при

а , Ь Ф 0

возможен

тогда

и только

тогда, когда

a =

ab, а = const.

Далее, \Аи\Еа < IIA ||„,m |и |£|п для любых матриц А порядка п х т

и

любых и 6 Ет.

§ п

Постановка

задачи. Обозначения. Вспомогательные сведения

55

Если J (и) £С р (U),

и +

ah £ U при 0 < а <

1,

то

J (u +

h) — J

(и) =

(/' (и), h) + о ( \h\)

при р =

1 ,

(2 )

J(u + h) — J(u)

=

( J ' ( u ) , h ) + - j ( J "(u)h,h) + o{\h\2)

при р = 2.

(3)

Рассмотрим функцию g (а) — / (и + аК) одной переменной а,

0 <

< С а < ;1 , при фиксированных и, h, предполагая,

что u + a h ^ U

при

всех

а,

0 <

а <

1.

Если J (и) 6

Ср (U),

то g (а) 6

Ср [0,

1],

причем

ё' (а) =

( J ’ (« +

ah),

Щ,

(р >

1),

g" (а) = (/" (и +

ah) h,

h)

(р > 2).

(4)

В самом деле, если,

например,

J

(и) £ С2 ([/), то, заменив в формуле

(3)

и на и + ah, h

на Дah, получим

g (а

+

Да) — g (а) =

Да (/' (и -f- ah), h) +

+

Да2 (/" (и +

ah) h, h) + о ( |Да |2).

Отсюда

следует, что g (а) в С2 [0,

1] и верны формулы (4).

Выпишем следующие формулы классического

анализа для функ­

ции g (а):

а

g(a) — g (0 ) =

g ’ (0 ха) а = | g' (t) dt =

g r (0 ) а +

- y g " (0 2а) а2,

о

g' (а) — g' (0 ) = аg" (0 3а), 0 < в£< 1 .

Полагая в

этих

формулах

а = 1

и

пользуясь равенствами

(4),

получим

J

{и +

h) — J

(и) = g (1) — g (0) =

(J'(u +

Bjh), h) =

= ^ (J'(u + th),h)dt,

(5)

о

J

(u +

h) — J

(u) =

(J' {u),h) +

-1- (/" (и 4 - e2/i) h, h),

(6 )

{J’ (u + h) -

J' (u), h) = g' (1) — g' (0) = (J" (u +

Q3h) h, h).

(7)

56

М И Н И М И З А Ц И Я Ф У Н К Ц И И

М НОГИ Х ПЕРЕМЕННЫХ

[ Г л . 2

iPTu--'

°

’

’ ••• « -

выпуклым,

О п р е д е л е н и е

1 .

Множество

£/ называется

если а и + ( 1— а ) в е (/

при любых

u,

n et/ и любых а, Ог^агсН,

т. е. отрезок £ ^ -а (у — и),

где О ^ а ^ Л ,

соединяющий

любые две

точки и, v множества, также принадлежит множеству.

Таким

образом,

формулы

(2— 7)

справедливы

при

всех

и, u+h^ .U ,

если

U — выпуклое множество, а функция J (и)

доста­

точно гладкая.

Функция J (и ), определенная

О п р е д е л е н и е

2.

на выпук­

лом множестве U, называется выпуклой, если

J (аи + (1 — a) v) •< a J (и) + (1 — a) J (у) f t v

(8 )

при всех и,

v ^ U

и всех

а, O ^ assri.

Если в (8 ) равенство

воз­

можно только при а = 0 и а = 1, то /(и)

называется

строго выпук­

лой функцией.

J (и) выпуклая функция

Т е о р е м а

1. Если

на

выпуклом

множестве

U, то

всякая

точка

локального минимума

J (и)

одно­

жество U* всех точек минимума J (и) на U выпукло

(если

оно не

пусто). Если

J (и) строго выпуклая

функция на U, то она может

достигать своего

минимума

на U не более, чем в одной точке.

Д о к а з а т е л ь с т в о .

Пусть

н* — точка локального

мини­

мума /(«), т. е.

существует

такая

окрестность О точки и*, что

J ( u * ) ^ J ( u )

при всех н е О

и « e U .

Пусть

вопреки утверждению

существует

такая точка

ие1/,

что

/(и*) > / ( у ) .

Так

как

и — и* + a ( v — u*)eO f)£/ при всех достаточно малых а,

0 < а < 1, то

с учетом выпуклости функции J (и)

будем иметь

J (и*) <

/ (и* -Ь а (у — и*)) < a J

(у) + (1 — a) J («*) <

J

(и*).

Противоречие. Следовательно,

ы* — точка

абсолютного

минимума

J {и) на U.

Далее, если выпуклая функция достигает своего минимума в

двух различных точках и*,

v*^ U ,

то она достигает минимума

во

J («*) = J (у*) <

J (<ш* + (1 — а) у*) <

a J (и*) + (1 — a) J

(у’) =

J (и*),

превращающихся в равенства при всех a,

O ^ a^ C l. Однако в слу­

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

при

0 < а < 1 . А

2. Если выпуклая

функция

J ( u ) ^ C l (U)

на

вы­

Т е о р е м а

пуклом множестве U, то

(J'(y ), и — у )< Т (« ) —

(и), и — у)

при всех и, у € U.

(9)

Д о к а з а т е л ь с т в о .

Перепишем

неравенство

(8 )

в

виде

J(v-\-a(u—у) ) —J ( v ) ^ . a [ J ( u ) —/(у)]. К левой

части

этого

нера­

§ П

Постановка задачи. Обозначения. Вспомогательные

сведения

57

венства

применим

формулу

(5):

J(v-{-a(u —v ) ) — J(v) = a(J'(v-\ -

+ 0 a(u — a )), и— v),

O ^ G ^ l, и получим (//(u + ’0 a (« — v)), и— v) ^

^ / ( u ) — 7 (d) при

всех a,

0 < a ^ l . Отсюда

при a -*-+ 0 вытекает

левое неравенство (9). Поменяв в полученном неравенстве

роля­

ми и и v, получим правое неравенство

(9).

А

C 1 (U)

Т е о р е м а

3.

Для того чтобы выпуклая функция J (и) g

достигла

своего

минимума

на выпуклом

множестве

U в

точке

«*е£/ , необходимо и достаточно, чтобы

(/'(«*),

и — ы‘) > 0

при всех

и £ и .

( 1 0 )

Если и* — внутренняя

точка

множества

U,

то условие

(10)

экви­

валентно равенству / '(«*) = 0 .

u *^ U — точка

Д о к а з а т е л ь с т в о .

Необходимость. Пусть

минимума /(и) на U. Тогда при любом u^U , и а,

0 < а < 1 ,

с по­

мощью формулы (2 ) имеем

0 <

J

(и* +

а (и — «*)) — J (и*) = а (J ' (и*),

и — и*) +

о (а),

или

0

< (/ '(« *). « - « * ) +

а

Отсюда при а-Я ) сразу получим условие (10). Заметим, что

условием выпуклости J (и)

мы здесь не воспользовались, так

что

условие

минимума

(10) необходимо

для всех J(u )^ .C l (U),

если

U — выпуклое множество.

Если и* — внутренняя

точка

множества

U и h — произволь­

ный вектор из Ет, то

u — u* + ah^.U

при всех достаточно

малых

a, |a|^ao.

Полагая в (10)

u=u*-\-ah,

получим a (/ '(«*),

h) ^ 0

при всех a,

|a|^ao,

что

возможно

только

при

(Г (и *),

h ) —0.

В силу произвола h отсюда имеем / '(«*) = 0 .

Д о с т а т о ч н о с т ь .

Пусть /(«)

— выпуклая

функция,

пусть

неравенства

(9)

при

v = u*

получим

0 ^

(/ '(«*), и— и *)^ .

(и)— /’(и*)

при всех

и е 1/,

т. е.

и * — точка

минимума.^,

Заметим, что условие минимума

(10) является обобщением

условия ( 1 ) на случай,

когда 11фЕт и точка минимума и*

может

лежать на границе множества.

Так как при и =ы *

(10) превращается в равенство, то условие

( 1 0 ) может

быть

переписано

в эквивалентном

виде

min (J'(u *)t и— и*) = 0 .

uBU

3.

Функция J(u ),

определенная на выпук­

О п р е д е л е н и е

лом множестве U, называется сильно выпуклой, если существует

такая постоянная к > 0 ,

что

J (аи + (1 — a) v) <

a J (и) -j- (1 — a)J(v ) — а (1 — а) и|и — у |2 (11)

при всех u ,v £ U

и всех

а, 0 <С а •< 1 .