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

например, функция I{и )

задана лишь таблично или лишь извест­

но, что в любой точке

значение /(«) может быть вычислено

функций

одной переменной

уточним

постановку задачи.

Пусть функция

J (и)

определена

на отрезке [а,

Ь]— { и :а ^ .

^ и ^ .Ь }

и достигает

на

[а,

Ь] своей

нижней грани,

и пусть тре­

интересуемся еще и значением

/ («*),

следует

различать две

по­

становки задачи минимизации [56]:

Задача А:

Найти точку w *e[a,

b] и значение

J

(и') =

inf

J

(и) =

J".

Задача Б\

Найти

точку

и *^ [а , Ь],

в которой / (ц *)= / *

(не

интересуясь самим значением J(u * )).

Для приближенного решения

этих

задач

обычно поступают

следующим образом:

1) вычисляют значения функции в каких-либо

резка

[а, Ь]\ 2) перебором значений J (Ui)

среди точек {«i} ( i=

=

1,

..., п) выделяют точку йп, в которой J

(ип) =

min/ (иг);

точек а, Ь, ии ..., ип

1< £ <п

3)

из

определяют точку

а„,

ближайшую

к

йп слева, и точку Ьп, ближайшую

к

ип справа;

4)

в качестве

и*

принимают какую-либо точку

ип

из отрезка [ап, Ьп]. При реше-

нии задачи А часто полагают

♦

—

(с вычисленным значением

ип =

ип

§ 2]

Задачи А и Б.

Строго квазивыпуклые

функции

9

/ (« „ ));

в задаче Б

можно, например, взять

и\

~ ( ап+Ьп)

(зна­

чение

J(u*n)

здесь нас не интересует).

Понятно, что такой порядок действий имеет смысл лишь в тех

случаях, когда у нас есть основание считать, что

и * е [ а п,

6„].

Од­

нако нетрудно подобрать функцию (даже непрерывную),

для

ко­

торой и *ф [ап, Ьп].

Укажем один важный класс функций,

для

ко­

торых всегда «*<=[«„, Ьп].

О п р е д е л е н и е

1.

Функция / («), определенная на множестве

U = { и : а ^ .и ^ .Ь },

называется строго

квазивыпуклой

на

U,

если

существуют

числа

а,

Р,

а ^ а ^ р ^ б ,

такие, что: 1)

J (и)

строго

монотонно убывает

при

a^ .u<Z а

(если а < а ^ р ^ & ) ;

2) J (и)

строго

монотонно

возрастает при

р < и ^ 6

*(если а ^ а ^ р с б ) ;

3) J (и) = / * = jnf/(u)

при а < « < р

(если й ^ а < р ^ й ) ; 4) в точ-

и€(/

ках и = а

и и = р выполняются у с л о в и я : / ( а ) п р и а = а ^ р ^ 6

;

J (а — 0) — lim J (и) > J

(а) > J*

при

а С а С Р ^ б ;

J (b )^ tJ * при

и-за—О

lim J (и) > J

ф) > J* при

й ^ а ^ Р = 6 ; / ( Р

+ 0) =

а ^ а < р < 6 ;

и

наконец,

в случае

а < а = р < 6

: / * ^ / ( а ) < ;т а х {/ ( а — 0), 7 ( а + 0

}

нении 3)

[135].

Множество всех строго

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

а ^ .и ^ .Ь

обозначим через

Q[a, Ь]. Вот примеры таких функций:

при любых a, b\

J 3( u ) = j ^

’

принадлежит Q[a, 6] при

l

1» й ^

0 1

любых a, b. Функция

/ 4(й) =

{|“ 1, “ J o } e Q [ o .

i], но m i - i , 1].

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

функция на U локальных ми­

то на

отрезке

[а„, Ъп] существует хотя бы одна точка минимума

J (и)

на [а, Ь].

Поэтому намеченная выше схема поиска минимума

оправдана.

10

МИНИМИЗАЦИЯ ФУНКЦИИ ОДНОЙ ПЕРЕМЕННОЙ

ГГл. 1

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

Пусть

/(w )eQ *[a,

b] и

пусть

вычислены

значения /(«О в некоторых точках { а ,}е [о ,

b],

( £ =1,

п). Ска­

жем, что тройка точек а„, Ьп, ип, локализует точку минимума J (и)

на [а,

6] по точкам

{и,}

( £ =1,

п)_, если: 1) а„, Ьп, ип содержат­

ся среди точек а, Ь,

ии

ип\2)

/(».„) =тш п/(мг-); 3) ап< и п< .Ь п\

_

1<£<л

чек ии_..., ип (т. е. на интервале а п< и < Ь п имеется

лишь одна

точка и„, в которой вычислено значение функции).

На практике часто бывает, что мы заранее ограничены числом

точек {« 1, .... ы „}е[а , Ь], в которых можно вычислить

значение

дачи А и Б. Поясним это на примере п — 2.

Пусть / (ii)eQ *[0 , 1],

пусть минимум / (и)

на [0, 1]

достигается

в точке к * е [ 0, 1].

Возь­

мем точки их — -£-(1 — б), «2 = — (1 + 6 ), 0 < 6

< 0 , 1 и вычислим зна­

чения

/(ui), /(иг).

Может

оказаться,

что

J (щ) ^ '/ (« 2).

Тогда

и *е {0 ,

щ]. В задаче А в этом случае в качестве приближения к и*

естественно принять точку и* = и1 с уже вычисленным значением

J {иi) « / ( и * ) . При этом гарантированная точность есть

|и* —•«*1 <

-< -■ — , поскольку в худшем случае для некоторых

функций из

Q*[0, 1] может быть и * = 0.

В задаче Б в качестве приближения к

и* можем принять

и* = —

(1 + 6) — середину отрезка [0, и2], ибо

значение Т(ыг) здесь нам не требуется, и получим

лучшую гаран­

тированную точность

\и*•— и* j < ^ -(1 + 6), чем в

задаче А. Слу­

S 3]

Оптимальный пассивный

поиск в

задачах А

и Б

11

чай

J ( u 1) > J ( u 2) рассматривается

аналогично

и приводит

к

тем

же

оценкам |«* — и2* 1 для задач А и Б.

Заметим,

что для

зада­

чи А возможен более лучший выбор точек

иг =

и и2 =

~ ,

дающий гарантированную на классе Q*[0,

1] точность, равную

— ,

3

Упражнения.

1. Как нужно

доопределить

функцию

J(u ) =

=

1/а!

в

точке

и = 0,

чтобы

J (и) <=Q[0, 1]? Q[— 1,

1]? Q[— 1,

0]?

6

“Г *

2.

Как

нужно

доопределить

функцию

J (и) = I

’

^

I

точке и =

чтобы J {и) 6 Q [0,1]?

1—ч ~т А, « < 0 )

в

0,

Q[— 1,0]?

Q [—-1,1]?

Q[a, b]

при любых a, 6?

Рассмотреть случаи А = 0;

+ 1;

— 1.

3. Доказать, что функция J (и) строго' квазивыпукла на проме­

жутке £/= {и : а ^ и ^ .Ь }

тогда

и только

тогда,

когда

/ (а « +

+

(1— a)v ) ^ .m a x {J(u ); J (v)} при всех и, в е й

и всех а, 0 < а < 1 ,

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

может достигаться

лишь при J ( u ) = J ( v ) .

4.

Если Ji(u ),

/2(w )eQ [a, b], то будут ли принадлежать Q[a,

Ь]

следующие

функции:

J\ {u )+ h (u ),

Ji(u ) —J 2(u),

J i( u ) - J 2(u),

Ji{u )/J2(u)?

§ 3. ОПТИМАЛЬНЫЙ ПАССИВНЫЙ ПОИСК в ЗАДАЧАХ А И Б

О п р е д е л е н и е 1. Пусть /(w )eQ *[a, Ь].

Скажем, что на

от­

резке [а, b] задана пассивная стратегия Р п, если:

1) на [а,

Ь]

за ­

ранее задаются все п точек {и,}

( г = 1,

.... п),

и0= а ^ : и 1< :и 2<. ...

... < и п^ и п+1= Ь и вычисляются

значения

J (щ)

( i = l ,

...,

п);

2) путем сравнения величин /(«г)

( £ =1, ..., п) определяются точ­

ка uk,

в которой J (uk) = min J («г), и

отрезок

uh+i],

содер-

жащий

точку и* минимума J (и)

на [a,

Ь] (таким

образом,

точки