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

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 11.04.2024

Просмотров: 197

Скачиваний: 1

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

44

 

МИНИМИЗАЦИЯ

ФУНКЦИИ

ОДНОЙ ПЕРЕМЕННОЙ

[Гл. 1

< у < 6 ,

чтобы J(u)^J(v)-\-l(v) (и—о)

при верх и, а<.и<.Ь.

До­

казать.

Покажите,

что l(v )= J'(v )

почти всюду.

 

 

 

11.

Если

J {и) выпукла

и

монотонно

возрастает на

отрез

[а, 6],

а

функция

u = z(x ) выпукла

на

отрезке

c ^ . x ^ d ,

и z{x ) е

е [ а , Ь]

при х е [ с ,d], то J(z(x))

выпукла на {с,б\. Доказать.

 

 

 

 

§

11. МЕТОД ПАРАБОЛ

 

 

 

В

двух предыдущих

параграфах

минимизируемая

функция

J (и)

аппроксимировалась кусочно-линейными функциями Р п(и), и

исходная задача заменялась последовательностью задач миними­

зации функций 'Рп (и). Однако вместо кусочно-линейных функций

в качестве аппроксимирующих функций Р п (и) могут быть выбра­

ны и другие классы функций. Если Р п-(ц), л = 0 , '1,

..., достаточно

хорошо аппроксимируют исходную функцию J (и)

равномерно на

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

Итак, пусть / (u )eQ *[a ,

b] и пусть требуется определить точ­

ку и* минимума /(и)

на [а,

Ь]

с заданной точностью е > 0 .

 

О п р е д е л е н и е

1. Тройку точек

{о—т,

v, v-\-h) (h, т > 0 )

на­

зовем удачной, если каждая

из

этих

точек

принадлежит отрезку

.[а, Ь] и, кроме того, Д~ = J ( v ) —J ( v —т ) ^ 0 ,

A + = J { v ) —J(v - j- h )^ .О,

Д -+ Д + < 0 .

 

 

 

 

точек {v—т,

v, о+/г}

 

 

Т е о р е м а

1.

Если тройка

удачная,

то

через точки (и—т,

J ( v —т )),

(о,

/(и)),

(o-f/i, J(v-{-h))

на плоско­

сти (и,

J) можно провести параболу L(u) ==pu2-{-qu-\~c с коэффи­

циентом

р > 0,

причем

точка

w = ------— •—

минимума L(u)

при

 

 

 

 

 

 

 

2

р

 

 

 

— о о < ;«< ; + оо удовлетворяет неравенству

 

 

 

 

 

 

 

\v— w\ <

 

т а х {т , h).

 

 

 

Д о к а з а т е л ь с т в о . Искомая парабола является обычным интерполяционным многочленом и имеет вид [19]

t м

g ) . < - » > < ■ - ; - * >

+

( 1)

§ И]

 

 

 

Метод парабол

 

 

 

45

Так как

тройка точек

{и- -т, v,

v + h}

удачная,

то

 

 

 

 

 

Д-

д+ \

1

 

> 0

 

 

 

 

Р = ( -

h J х-j- h

 

 

 

 

 

 

 

 

 

 

и минимум L (и)

на

числовой оси •— ос <

 

и <

+ ° °

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

точке

 

 

 

 

 

 

 

 

 

 

 

 

Ш =

V + ■

/I2д- — т2А+

 

 

 

 

 

тД+ -f ЛД"

 

 

 

 

 

 

 

 

 

 

 

 

 

Отсюда

следует,

что

 

 

 

 

 

 

 

 

 

 

 

1

[Я2 1Д-| —

т2 )Д+Ц <

— max {Л,

т}.

 

 

 

2 т | Д + | + Л | Д - |

 

 

 

 

 

Последнее неравенство доказывается элементарно, простым рассмот­

рением случаев h2J А— J — т2 |Д +|>0

и Л2|Д~|—-т 2|Д + | < 0 . ^

Опишем метод парабол в сочетании с методом золотого се­

чения. Пусть сделано k

шагов ( k ^ 3 )

метода золотого сечения и

найден отрезок [с^, bk],

содержащий точку минимума и* функции

J (и) на [я, 6 ]. Примем

гипотезу о том,, что функция J (и) на от­

резке [ад, bh] хорошо аппроксимируется параболой. Если строго квазивыпуклая функция J (и) достаточно гладкая на отрезке [ah, bk] и сам отрезок [a*, bk] имеет достаточно малую длину, а < а к^ и * ^ ~ b h < b , то такая гипотеза вполне правдоподобна, поскольку в окре­ стности внутренней точки минимума гладкая функция, вообще го­ воря, близка к параболе. Далее возьмем одну из точек ип, произ­ водящих золотое сечение отрезка [a*, bh], и вычислим значение J (Uk) (если только оно еще не было вычислено на последнем шаге

метода золотого сечения).

Если bk— Я д ^ is, то точку uk принимаем

за точку минимума и*, и

процесс на этом заканчивается. Пусть

bk—«А>'е. Тогда проверяем, является ли тройка {ал, Uk, Ьк} удач­ ной или нет. Если эта тройка неудачная, то делаем следующий шаг

метода золотого сечения, находим отрезок {Яй+ь bk+i] и с ним по­ ступаем так же, как с отрезком [a,k, bk].

Пусть тройка

(aft, uk,

bk} удачная,

и пусть

wk — точка мини­

мума

параболы

( 1 )

с v=Uk,

т = т h— Uh— a-k,

h = h k = b k —

— ик.

Согласно теореме 1

 

 

 

 

 

 

 

IЧ — wk I < у

max ihk> **}.

 

 

Положим ak=m ax { |uk — wk |; e/4}.

 

 

 

 

Нетрудно проверить,

что uk — ak,

uk + ak 6

[ak, bk\. Вычислим

 

Ak = J (uk) — J {u k — a k) , b t =

J (uk) — J (u k +

ац).

46

 

МИНИМИЗАЦИЯ

ФУНКЦИИ ОДНОЙ

ПЕРЕМЕННОЙ

 

 

\Гя. 1

В зависимости

от

знаков

Ак ,

возможны 4 случая.

1.

Дй < 0 ,

A t < 0 , А/Г +

Дй~< 0 . Это значит, что тройка {ик — ак, ик,

ик 4 - ак} —

удачная.

Полагаем

ak+ i = u k — ak,

Ьк±\ = ик -f- ак

и

с

 

отрезком

[ай+ь

6 ^+1] поступаем так

же,

как с

предыдущим

отрезком

[ай, Ьк].

2. AJ-< 0 ,

Afe".>0. Тогда полагаем ak+\ =

ик, Ьк+[ = Ьк и с отрезком

[afe+i, 6 й+1] поступаем так же,

как

с

[а*, Ьк]. 3.

Д Г > 0 ,

Д ^ < 0 .

Тогда принимаем ай+1 = ай, Ьк+\ = ик и с

отрезком

[ай+ь 6 fc+i] пос­

тупаем так же, как

с \ак, Ьк]\ 4. А ^ > 0 ,

A t > 0 . Тогда

на [аЛ, Ьк[ де­

лаем

следующий шаг метода

золотого

сечения,

находим

отрезок

[ай+1, 6 fe+i]

и с ним поступаем

так же,

как с предыдущим

отрезком

[ай, Ьк]. Впрочем, если заранее известно, что функция J (и) строго

квазивыпукла на [ай, Ьк\,

то последний

случай возможен

лишь при

АГ = Дк" = 0 , т. е.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

J (и) =

J* —

inf

J

(и)

 

 

 

 

 

при ик— аА-< и <^ик + ак. Здесь остается

принять

в

качестве точки

минимума любую точку из отрезка

[ик — ак, uk -f a A],

и процесс

поиска на этом заканчивается.

 

 

 

 

 

 

 

 

 

Повторяя описанный процесс многократно, получим последо­

вательность вложенных стягивающихся отрезков [ак, Ьк]\

 

 

 

[ай+ь 6 *+ i] с : [ай, bk], Ьк+\— ай+] <

1

(Ьк— ак).

 

Отсюда видно, что на классе функций Q*[a, b] метод парабол по скорости сходимости не уступает методу золотого сечения и йенам-' ного уступает ему по числу вычислений значений функции J(u ). Если же функция / (« )e Q *[a , b], хорошо аппроксимируется пара­ болой хотя бы в некоторой окрестности точки минимума, то метод парабол может оказаться гораздо лучше плана Фибоначчи и по скорости сходимости, и по числу вычислений значений функции. Разумеется, это не противоречит оптимальности плана Фибоначчи, ибо этот план был выработан из расчета нд «наихудшую» функцию из класса Q*[a, b], что не исключает возможности построения бо­ лее эффективных методов поиска минимума на «хороших» под­ классах из Q*[a, Ь]. Для функций, не являющихся строго квазивыпуклыми, описанный метод парабол приводит, вообще говоря, лишь к точке локального минимума.

Нетрудно модифицировать метод парабол так, чтобы можно былс пользоваться параболами ( 1 ) при выполнении лишь условия

не требуя неположительности величин Д+, А- . Од­

X + ' Т < ° -

нако при этом следует иметь в виду, что точка минимума такой

s щ

О некоторых других методах минимизации

47

параболы "на отрезке [v—т, v-\-h] может не совпадать с точкой ми­ нимума параболы на всей числовой оси.

Другой вариант метода парабол описан в {2 0 1 ].

§12. О НЕКОТОРЫХ ДРУГИХ МЕТОДАХ МИНИМИЗАЦИИ

1.Описанные выше методы позволяют с заданной точностью решить задачу минимизации строго квазивыпуклых функций, а на других классах функций эти методы (кроме метода ломаных) мо­ гут привести к точке локального минимума. Задача определения глобального минимума функций, не являющихся строго квазивыпуклыми, в общем случае весьма трудна, и методы решения таких задач в настоящее время разработаны еще недостаточно.

Здесь мы остановимся на одном методе поиска глобального минимума функций, основанном на информационно-статистическом подходе [212], [213]. Для некоторых достаточно широких классовфункций (подробное статистическое описание этих классов см. в работе [2 1 2 ]) удается построить оценки апостериорной вероятности расположения глобального минимума на основе уже проведенных испытаний, заключающихся в вычислении значений минимизируе­ мой функции в определенных точках ио, щ , ..., ц* из отрезка [а, Ь]. На основе этих оценок затем можно получить оценку максимума

информации о расположении точки минимума и указать простое правило выбора следующей точки ии+\. Отсылая читателя за под­ робностями к работам [212], [213], здесь ограничимся лишь опи­ санием самого метода.

Пусть требуется минимизировать функцию J (и)

на

отрезке

[а, Ь]. Процесс поиска минимума начинается с двух

точек

и0= а ,

Ui = b, и вычисления величины

 

 

\J Ы — J (цр)1

“1 — “q

После чего полагается

f гДх при А1 > 0 ,

1 1 при Ах = 0,

где г — const> .'1 представляет собой параметр алгоритма, выбирае­ мый вычислителем. В качестве следующей точки m берется точка

U2 = Y (u i + “ о)

J j u J — J (ц„)

2т1

Предположим, что точки «о, Щ,

“fe (6 ^ 2 ) уже известны.

Произведя при необходимости перенумерацию этих точек, можно считать, что а = и й< .и i < ... <.Uk-\<.Uh— b. Далее определяются величины

48

МИНИМИЗАЦИЯ

ФУНКЦИИ

о д н о й ПЕРЕМЕННОЙ

 

\Гл 1

 

 

Ак =

шах

\ J ( u S) - J ( l l s - l ) \

 

 

 

и

 

 

 

l<s<fc

 

Us — U S- 1

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

m

=

 

ПРИ ДА>

°>

 

 

 

 

 

 

k

 

[

1 . при ЛА=

0 .

 

 

 

Затем составляется функция

 

 

 

 

 

 

 

 

 

Rk is) =* Щ (и, -

Из-,) + —

s l- - - (Us-l)|2-- 2 [J (и5) + J

(и^

)]

 

 

 

 

 

 

Uj

.Uj . j

 

 

 

 

 

целочисленного аргумента s,

1

 

и

простым

перебором

значе­

ний Rk (s) определяется

тот

номер

s =

sA,

для

которого

Rk (sk) =

=

шах Я* (s). Если

us

— us _ i < 6 ,

где

е >

0 — заданная

точность,

.

l<s<fe

в

 

 

я

 

 

 

 

 

 

 

то процесс поиска прекращается и точка uSft принимается в качестве искомой точки минимума. Если же и5д,— «Sfc- i > е , то полагаем

ый+1 = — (Us*

Us*->) —

J (USft)

7

(a sk - i )

 

2mk

 

 

 

 

 

 

Из определения mfe, очевидно, следует

nSfe_ i < u ft+I < u Sfc.

Теперь ос­

тается перенумеровать точки

и0, uv . . .

, uk, Uk+i

в

порядке

возраста­

ния и перейти к определению следующей точки ин-\-2 аналогичным образом. Метод поиска минимума описан.

В качестве иллюстрации приведем результаты применения опи­ санного метода для отыскания минимума функции

/ (и) = sin и -}- sin

10

 

 

 

 

 

-----'и -f- 1п и— 0,84«]+ 3

 

 

на отрезке 2 ,7 ^ и < 7 ,5

[213].

График

функции J (и)

приведен на

 

 

рис. 6 , там же вертикальными

 

 

штрихами на оси Ои отмечено рас­

 

 

положение

точек

щ

при

г = 2 ,

 

 

е = 0,01;

группа из

14

точек, распо­

 

 

ложенных вблизи точки глобально­

 

 

го минимума, изображена черным

 

 

прямоугольником.

Как видим, из

 

 

28 точек, в

которых

вычислялись

 

 

значения

функции

в

ходе поиска

 

 

минимума, большая часть (21

точ­

 

 

ка) расположена вблизи точки гло­

 

 

бального

минимума.

 

 

С целью проверки

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

были

проведены

чис­

ленные эксперименты на большом количестве задач минимизации при различных г > 1 , е > 0 [212]. В частности, была проведена ми­

Смотрите также файлы