книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей
..pdfГ Л А В А б
МИНИМИЗАЦИЯ ОДНОГО КЛАССА
НЕПРЕРЫВНЫХ ФУНКЦИИ
§ 1. Постановка задачи
Метод сужающихся окрестностей, рассмотренный в предыду щих главах, предназначен для минимизации функционалов, задан ных на множестве перестановок. Однако отдельные идеи, на кото рых основан этот метод, можно использовать и при минимизации одного класса непрерывных функций многих вещественных перемен ных. Материал данной главы можно рассматривать как теоретичес кий пример использования метода сужающихся окрестностей.
Часто возникают задачи об определении глобального экстрему ма (или приближения к нему) таких функций, заданных в Rn, для
которых |
сравнительно просто находить локальные экстремумы, |
но нельзя |
провести полный перебор локальных экстремумов вслед |
ствие их большого количества.
Если нет никакой дополнительной информации о характере поведения функции, экстремум которой ищется, то, по сути дела, единственным способом поиска глобального экстремума является слепой случайный поиск [44]. Схема использования метода МонтеКарло для решения рассматриваемых задач следующая. Случай ным образом «разыгрываются» точки из области определения функ ции. Из полученных точек проводится спуск в «ближайший» локаль ный экстремум. При этом запоминается лучшее из полученных значений экстремумов и соответствующая экстремаль, т. е. точка
пространства Rn, в которой этот экстремум достигается.
Метод случайного поиска имеет достоинства и недостатки, ко торые подробно обсуждаются в работе [44]. Очевидно, что наличие какой-либо дополнительной информации о характере поведения функции, экстремум которой ищется, желательно использовать для того, чтобы каким-то образом модифицировать метод МонтеКарло, использовать в его работе элементы адаптации и тем самым ускорить получение достаточно хороших приближений к глобаль ному экстремуму.
При решении задач автоматизации проектирования часто при ходится определять минимумы (или максимумы) функций, которые обладают некоторыми специфическими свойствами. Эци свойства
171
подробно описаны в монографии [351. Функции, экстремумы кото рых определяются, в соответствии с обычной терминологией будем называть целевыми.
Итак, рассматривается задача о поиске глобального минимума функции f(x), заданной на компакте (замкнутом ограниченном
множестве) D в пространстве Rn.
Предполагается, что известны алгоритмы локальной минимиза ции, однако полный перебор локальных экстремумов не может быть осуществлен вследствие их большого количества. Считается,
что размерность п пространства Rn достаточно велика. Точный смысл такого предположения рассмотрен ниже.
На целевую функцию накладываются следующие ограничения. 1. Функцию f(x) можно представить в виде ^
/(*) = £ М*)« |
(5.1) |
i=i |
|
где каждое слагаемое ft (х) зависит не более, чем от г 4- 1 перемен ных, а именно:
|
(<7<(*(, xt+i.......... |
xi+r), |
если i < л — г, |
it (х) — |
Х[+и |
" . t Хп, хи х2.............. |
x i+r-„ ), если i > п — г. |
|
|
|
(5.2) |
2. Всюду в области D функции ft (х) имеют непрерывные частные производные первого порядка по всем переменным. Это условие обозначается так:
. ft (x)^C1(D), |
t = 1, 2, . . . |
, п. |
Определение 5.1. Функция f(x), обладающая свойствами 1, 2 |
||
называется квазисепарабельной. |
Натуральное |
число г, входящее в |
формулу (5.2), называется показателем сепарабельности.
Класс квазисепарабельных функций подробно рассмотрен в работе 135]. Там же отмечено, что к этому классу принадлежат многие функции, необходимость оптимизации которых возникает в задачах автоматизации проектирования.
Выбор термина «квазисепарабельная функция»’ связан с тем, что свойство 1 является обобщением понятия сепарабельности функ ции.
Как известно, функция f(x), заданная на Rn, называется сепара бельной, если она представима в виде
/(* )= £ /< (* ) . (=1
причем каждая из функций f{ (х) зависит только от одной пере менной:
ft (х) = qt (xj.
172
Легко видеть, что свойство сепарабельности функций есть частный
случай |
свойства 1 |
при г — 0. |
П р |
и м е р ы . |
Функция |
f (х2, х2, х3) = хгх2sin (хх — ха) + х2х3 sin (х2 — х3) + xxx3 sin (х3 — x j
является квазисепарабельной с показателем сепарабельности, равным единице. Функция
/ (х х, Х2, |
Х3, |
Х\Х2Х3 [ |
Х%Х3Х\ | Х3 Х.Х] | Х4Х1Х2 |
имеет показатель |
сепарабельности |
2. |
Сделаем еще несколько замечаний о квазисепарабельных функ циях.
Поскольку сумма конечного числа дифференцируемых функций является дифференцируемой, из представления (5.1) и свойства 2 следует, что функция f (х) имеет непрерывные частные производные первого порядка по всем переменным, т. е.
f(x)£& (D ).
Если учесть, что множество D по предположению является ком пактным, то из непрерывности функции f(x) следует, что она равно мерно непрерывна на множестве D и ограничена на нем [26].
Кроме того, каждая из функций ft (х) ограничена на компакте D.
Поэтому |
существует константа А одна и та |
же |
для всех i такая, |
что для всех x£D справедливо неравенство |
|
|
|
|
|м * ) 1 < 4 - |
|
(5-3) |
Для |
иллюстрации выбора константы А |
в |
неравенстве (5.3) |
рассмотрим еще один пример квазисепарабельной функции. В ка честве компакта D cz Rn выберем «кирпич», т. е. множество точек
х = |
(xlt x2, ..., хп), для которых выполняются |
неравенства |
|||||||
|
|
|
а, < |
xt < bh |
i = 1, 2, . . . . |
п, |
|
||
где |
а{, Ь, (1 = 1, |
2,..., |
л) — заданные |
наборы |
чисел. Функцию |
||||
f (х) определим соотношением |
|
|
|
|
|
||||
f(x) = ~ |
[(хх + |
х2 + х,)2 sin (х^хз) + |
(х2 + х3 + |
х4)а sin (х2х3х^ -f |
|||||
|
|
+ • • • |
+ (Хп- 2 + Хп- 1 |
+ |
ха)2 Sin (Xn—iXn—Iхп) + |
||||
+ (Х п -1+ |
Х„ + х,)2 sin (Xn-iXnXt) + |
(хп + Xj 4 - X2f |
sin (x„xtx2)]. (5.4) |
Это квазисепарабельная функция с показателем сепарабельности равным двум. Из очевидного неравенства
(х<—1 + Х[ 4- x1+i)2 sin (Xi_iXfx,+t) < 3 (х?_1 + Xi + X(+i)
следует, что для любого i верна оценка
1 М * )|< - Т - .
173
где В = max {а?, $}. Следовательно, для этой функции в соотноше нии (5.3) можно положить А = 9В.
Сформулируем задачу, которая будет рассматриваться в данной главе.
Найти минимум квазисепарабельной функции f(x), заданной на компакте D пространства Rn>п{?и следующих условиях.
1. Размерность п пространства Rn достаточно велика.
2.Известны алгоритмы поиска локального минимума, в зоне «притяжения» которого находится произвольная точка компакта D.
3.Число локальных минимумов функции f (х) столь велико, что их получение при случайном выборе начальной точки можно счи тать независимым испытанием. При случайном выборе начальных точек минимумы функции / (х) можно рассматривать как реализации случайной величины, которая имеет нормальное или логнормаль ное распределение вероятностей. Подробнее этот вопрос рассмотрен
в§ 5 третьей главы. Там же указан способ, который автоматически отсеивает такие целевые функции f(x), для которых перечисленные гипотезы не верны.
§ 2. Некоторые свойства квазисепарабельных функций
Рассмотрим, какие слагаемые из разложения (5.1) квазисепара бельной функции f (я) изменяются при переходе от одного локаль ного минимума к другому.
Для решения этого вопроса используется метод построения ло кальных минимумов с помощью градиентного спуска. Однако полученные результаты будут носить общий характер, поскольку точка, в которой достигается минимум, не зависит от того, каким методом она строилась.
Градиент функции / (х), заданной на компакте D из пространства
Rn, определяется следующим |
образом: |
|
|
|
|
||
f ( x ) |
= i £ r |
ei + |
i k - e* + |
••• + - ё г |
е"’ |
(5-5) |
|
где et (t = 1, 2, ..., |
п) — орты в пространстве Rn. |
|
1, 2 ,... |
||||
Из соотношения |
(5.2) следует, что от |
аргумента xt (t = |
|||||
..., п) зависят следующие функции // (*): |
|
|
|
|
|||
| /х» /г» |
• • • » fit |
fn+i—rt • • • > fnt если |
i ^ |
г, |
|
||
1 fi-r, fi-r+u • |
• • , |
ft, |
если |
i > |
г. |
|
Таким образом, при любом t от переменной xt зависят г 4- 1 сла
гаемых разложения |
(5.1). |
соотношениями (5.1) и (5.5), получим |
|
Затем, воспользовавшись |
|||
8rad/М == |
+ |
д/„-г+. |
+ ... |
д х х |
|
174
|
| |
( dfl |
I |
2 |
i |
^fn—r+2 |
|
I |
|
I |
|
Vn_) о -| |
•** |
|
|
||||
|
+ |
Г а ^ ~ + ^ Г |
' |
|
д х г |
|
+ |
*•* |
+ |
|
а*, |
Г 2 + |
|
|
|||||
|
, |
/ |
dft |
|
, |
|
. |
dfr-i . |
dtn- 1 |
■ |
dfn \ |
|
+ |
|
|||||
|
••• + f e r + |
|
+ ^IT + |
|
|
|
+ ^r-i je |
|
|||||||||||
|
|
|
+(-$-+ ••• +-lr+-lrH + |
|
|
|
|||||||||||||
|
|
|
+(-^+-+^K '+- |
|
|
|
|||||||||||||
|
t f d f n- .r- l . |
|
, |
|
dfn -\ |
\ . |
|
, |
/ |
a / « - r |
, |
, |
d f n |
^ |
|||||
*" + ( dx„_, |
+ |
••• + |
~ |
d ^ |
J |
j e n - |
l + |
( |
d x n |
+ •“ |
+ |
d*„ ]*»' |
|||||||
Последнее соотношение можно |
переписать |
в |
виде |
|
|
|
|||||||||||||
где |
|
|
|
|
|
grad/(x) == S |
|
|
|
|
|
|
(5.6) |
||||||
dft |
|
|
|
|
dft |
|
dfn+t-i |
+ |
|
|
+ |
-Щ -, |
если |
i < |
r, |
||||
|
|
+ |
|
|
|
|
|
||||||||||||
Фг = |
dxt |
|
|
dxt |
|
|
dxi |
^ |
|
|
|||||||||
Of,-г |
|
|
+ |
dft |
|
|
|
|
|
|
|
|
|
если |
i > |
r. |
|||
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
dxi |
|
|
dxt |
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
(5.7) |
|
Так, для функции f(x), заданной соотношением (5.4), получаем |
|||||||||||||||||||
grad / (*) = |
-JJ- {(2 (*, + х 2 + х3) sin (х&Хз) + |
2 {хп-\ + хп + хг) х |
|||||||||||||||||
X sin (г»_1а д ) + |
(xt + х2 + х3)2 х2х3 cosfx^Xg) + (x„-i + хп + хг)2х |
||||||||||||||||||
X cos (Xn-tXnXj) + 2(xn + xl + x2) sin (XnX^)2cos (xnxtx2)\ et + |
... |
}. |
|||||||||||||||||
Если функция f(x) определена формулой |
|
|
|
|
|
|
|||||||||||||
|
f(x)= -± r l(x1 + x2 + x3)2 + (x2 + x3 + xi)2+ . . . |
|
|
||||||||||||||||
..• + (Xn- 2 |
+ xn-\ + |
Xn)2 + (Хп- l |
+ x n + |
Xj)2 + (xn + x2+ x2f], (5.8) |
|||||||||||||||
то ее градиент имеет вид |
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
grad f(x) = -j-{ (3*! + 2X2 + X3+ x„-t + 2xn) et -f- |
|
|
||||||||||||||||
|
|
|
+ |
(2xt + |
3x2+ |
2x3 + xA+ xn) e2 + . .. |
|
|
|
||||||||||
|
|
|
... -f- (xn—2 И- 2xn—i + |
3xn + |
2хг -)- x2)en]. |
|
|
|
Рассмотрим вопрос о том, от каких компонент вектора х зависят отдельные компоненты вектора <р. Последовательно используя соотношения (5.7) и (5.2), находим
Ф1 (х) = % (*i, . • •, хг+1, x„^r+i..........хп),
175
ф,(х) = ф ,(xlt . . . , |
Xir, x„), |
||
фл—г(х) — |
—г (Хд—2г* |
• • • » ^в)> |
|
Фл W = |
(^1* • • • |
» |
^л—г» • • • * ^л)' |
При выводе этих соотношений использовалось предположение о том, что справедливо неравенство
2r -f 1 < л. |
(5.10) |
Если это неравенство не выполняется, то каждая из функций за-1 висит от всех компонент вектора х.
Как пример рассмотрим функцию, которая задана соотношением (5.8). Если выбрать п = 7, то получим
- |
Фх (^) |
Фх (XV Х2, Х3, |
Xg, Х7), |
|
ф2 (х) = |
ф2 (Хх, х2, х3, |
х4, х7), |
|
Фз (^) = |
Фз (-*8» *3, ^4» ^5» ^в), |
|
|
ф4 (х) = |
ф4 (х3, х4, х5, хв, х7), |
|
|
Фб (*) = |
Фб (*1. *4- *б. *в> *7). |
|
|
Фв (^0 = |
Фв ( * Х * -^2’ ^5* |
^7)» |
|
ф7 (*) = |
Ф7 (*Х, *3, -«б. -«в» *7)- |
|
Если же п < 5, то функции фх (х) (i = |
1, 2, ..., 5) зависят от всех |
||
координат X/ (/ = |
1, 2, ..., |
5). |
|
Далее рассматриваются только такие квазисепарабельные функ ции, для которых выполняется неравенство (5.10).
Из соотношений (5.9) следует, что |
от |
переменной xt зависят |
||||
следующие |
компоненты вектора ф: |
|
|
|
|
|
Фх, |
• • • » фг-н> фл—r+i, |
Фл, |
если |
i < |
г, |
|
ф/-л, . . . . Фн-г, |
|
если |
г < |
i < п — г, |
||
Фх, |
• • >, ф/-(-/■—л, ф;—г, |
• •. , фл, |
если |
/ > |
г, |
|
т. е. от каждой переменной х( зависит 2г + |
1 |
компонент вектора ф. |
||||
|
А |
|
|
|
|
|
Пусть некоторая точка х, принадлежащая внутренности ком пакта D, является локальной минималью. Иными словами, зна чение функции f(x) в этой точке является локальным минимумом. Поскольку градиент функции в минимали равен нулю, то вследствие равенства (5.6)
Фх (х) = 0, i = 1, 2, . . . , п.
Случайным образом выберем v из п координат точки из пространст ва R", полагая при этом v < п.
Изменим в точке х значения выбранных координат. Это делается
176
случайным образом, но так, чтобы полученная точка (обозначим ее xv) принадлежала внутренности компакта D.
В частном случае, если в точке xv градиент функции f(x) прини
мает нулевое значение (точка хч при этом может быть локальной минималью, локальной максималью или седловой точкой), то при
/ч |
л |
переходе от точки х к точке xv компоненты вектора <р не изменяются, а остаются равными нулю.
Вообще говоря,
grad f (* v) Ф 0, |
(5.11) |
однако из проведенного выше анализа компонент |
градиента <р и |
способа построения точки xv следует, что не более чем |
|
v (2 r+ 4 ) |
(5.12) |
компонент вектора <р в точке х отличны от нуля, а остальные его компоненты совпадают с соответствующими компонентами век
тора ф (х). Действительно, |
изменение одной координаты в точке |
пространства R" может |
вызвать изменение 2г -J- 1 компонент |
вектора ф, а изменения v |
координат могут вызвать изменения в |
v раз больше компонент вектора ф. Заметим, что оценка числа изме |
нившихся компонент (5.12), как правило, резко завышена. Дело в том, что если изменяются значения двух близких координат xt и Xj, то многие компоненты вектора ф зависят от х( и xt, и потому число изменившихся компонент будет меньше чем 2 (2 г + 1). Под бли зостью координат понимается отношение величин |/ — / 1и г.
Поясним сказанное на примере функции, заданной соотношением (5.8). Положим п — 20. От координаты хх зависят следующие ком поненты вектора ф : фх, ф2, фц, ф10 и ф^; от координаты х2: фх, ф2, Ф з, ф19 и ф20; от координаты х7: ф6, ф„, ф7, ф8 и ф9. Показатель сепара
бельности г для данной функции равен двум. Если изменить |
зна |
||
чения координат хх и хь, то свои значения |
поменяют 2 (2г + |
1) = |
|
= |
10 компонент вектора ф, а именно: фх, ф2, |
ф5, фв, ф7, фв, фв, |
фХ8, |
Ф19 |
и ф20. Однако если изменить координаты хх и х2, то свои зна |
чения изменят лишь шесть компонент вектора ф: фх, ф2, ф8, фх8, фХ9 и ф20.
Поскольку выполняется неравенство (5.11), найдется число /х такое, что для точки
(5.13)
лежащей во внутренности компакта!?, будет справедливо неравенст во
12 |
9—961 |
177 |
Из построения (5.13) и сделанного выше замечания о том, какие компоненты градиента отличны от нуля, следует, что по крайней
мере п — v (2г + 1) координат у точек х 1' и xv совпадают. Продолжая процесс градиентного спуска, построим последова
тельность точек xv,/ по следующему правилу: |
|
|
x v,i = x v,1~' -f t, grad / (*v,/_1), / = 2, 3, |
, |
(5.14) |
причем числа t/ выбраны так, чтобы выполнялось неравенство
fCxv‘') < f ( x v-'-1).
Поскольку выполняются условия сходимости метода градиентно го спуска [43], для любого е > 0, найдется такое число шагов q, зависящее от е, что будет справедливо неравенство
\f (xv'9) — f(x )\< е,
где х — локальная минималь, в «зоне притяжения» которой лежит
A V
точка х .
Из формулы (5.14) и проведенных выше рассуждений вытекает, что если при переходе от точки х к точке хч были изменены значения
v координат, то в точках х и xv,<7 разными могут быть лишь s коорди нат, причем
|
s < |
v<7 (2г -f.1). |
(5.15) |
Как следует из (5.2), каждая из функций /, (х) зависит от г + 1 |
|||
координат. Поэтому можно |
утверждать, |
что не более чем |
|
|
/ = v<7 (2г + 1) (г + |
1) |
|
слагаемых |
из функций /, (дс) будут принимать различные значения |
||
/V |
/Ч |
^ |
|
в точках х |
и х '4. |
|
|
Таким образом, доказана следующая теорема, подводящая итог
проведенных в этом параграфе исследований.
л
Теорема 5.1. Если в точке х изменены v координат, то в точ ке х не более чем
l = v q (2 r + l)(r+ l) |
(5.16) |
слагаемых из разложения (5.1) функции f(x) отличаются |
от соот- |
л |
|
ветствующих членов разложения в точке х. |
|
В этой теореме в качестве / (х) используется квазисепарабельная функция с показателем сепарабельности г, a q — число шагов
градиентного спуска, необходимых для построения точки х с за данной точностью е.
178
§ 3. Уменьшение математического ожидания
Опытом, или наблюдением, будем называть выбор произволь ной точки х из компакта D, а результатом опыта, или событием,— значение функции f в точке х.
Пространство элементарных событий [66] состоит из всевозмож ных исходов опыта, т. е. содержит все значения функции f (х) при
условии, |
что точки х |
пробегают |
'Р |
|
|
|
компакт D (ср. гл. 3, |
§ 1). |
|
|
|||
При |
таком |
подходе можно |
|
|
|
|
считать, |
что значение |
функции |
|
|
|
|
f(x) есть случайная величина, и |
|
|
|
|||
говорить |
о ее |
математическом |
' |
|
|
|
ожидании и других вероятност- |
м |
ft*) |
||||
ных характеристиках. |
|
“ |
||||
Рассмотрим квазисепарабель- |
|
|
|
|||
ную функцию |
f (х), математиче- |
Рис. |
45. |
|
||
кое ожидание значений которой |
|
|||||
|
|
|
равно М:
<f(x)> = M.
(Как указывалось во введении, угловые скобки используются для обозначения средней величины.) Будет показано, что при некоторых условиях из неравенства
вытекает |
f(x )< M |
неравенство |
|
|
(/ (*)> < М. |
Здесь в |
соответствии о обозначениями предыдущего параграфа |
л |
|
х — некоторая фиксированная локальная минималь функции / (я),
а х — различные локальные минимали, которые строятся путем из-
А
менения значений v координат в точке х и последующего спуска (рис. 45). Заметим, что номера изменяемых переменных выбирают ся случайным образом, сдвиги по этим переменным также случай
ны и, следовательно, точки xv и соответствующие локальные минимали х являются случайными. Поэтому даже при фиксированной
А~
точке х значение f(x) можно считать случайной величиной и гово рить о ее математическом ожидании.
Выберем две локальных минимали х° и х1. Точки, полученные из дс° и х1путем замены v координат и последующего спуска к «бли
жайшим» локальным минималям, обозначим хоу и х1ксоответственно. Напомним, что функция f (дс) представляется в виде суммы (5.1)
и что при переходе от точки х° к какой-либо из точек х0/ в разложении (5.1) свое значение меняют не более чем / слагаемых, где / определя ется формулой (5.16).
12* |
17$ |
Значение целевой функции f(x) в точке х0/ можно представить в виде
f(x0l) = n£ ‘fiP(x°>)+ |
£ |
'tp{ x \ |
(5.17) |
p=\ |
p = n —/-j-1 |
|
|
Здесь под знаком первой суммы объединены слагаемые из разложе ния (5.1), которые не изменились при переходе от точки х° к точке
х0’. Поэтому соотношение (5.17) можно переписать в виде
/ ( / > ) = 5 'др(*°)+ |
£ |
tip ( Л |
(5.18) |
р=1 |
р = п — /4 -1 |
|
|
Аналогично значение целевой функции в точке xlk можно предста вить так:
f(x lk) = l ! frp (Х')+ |
£ |
frp(xlk). |
(5.19) |
р—1 |
р = п —I—1 |
|
|
Из равенств (5.18) и (5.19) следует, что
f(x ° i) - f(x lk)= f(x O ) - f(x 1) +
+ £ [ Ы Л - Ы ^ + М ^ + Ы * 1*)]. (5-20)
Р= П - 1-\-\
Вравенстве (5.20) перейдем к средним значениям. С учетом того что точки х° и х1 не случайны, а фиксированы, получаем
(/ ( Л ) - (/ (*'")> = / (*°) - / (а:1) +
+ |
2 Kf'P(x0i) ) - f i P(x<>) + frp(x ') - (fr P(x'k))1. |
(5.21) |
|
р—п—/4-1 |
|
Пусть среди всех значений /, (x0/) наибольшим по абсолютной ве личине является ft (х°“‘), а среди значений fr (xik) наибольшим по
модулю — /, (*lpr)- Тогда |
|
|
|
|
I (ft (х01)) | < |
IU (хш ) |, |
i = |
1. 2.......... п, |
(5.22) |
I </, (Л > | < |
| fr(x*r) |, |
г = |
1, 2, . . . , n. |
(5.23) |
Пользуясь тем, что модуль суммы не превосходит суммы моду лей, а также неравенствами (5.22) и (5.23), находим следующую оценку:
|
2 |
|
К / ф ( Л ) - |
ftp ( Х ° ) + frp ( X 1 ) - |
( f r p |
(Л>1 |
|
р=я—Н-1 |
|
|
|
|
|
< |
2 |
( I fw (х Ш ) | + |
| ftP(х°)! + | frp ( X 1) |
| + |
| f r p (хХЬг) IJ. (5.24) |
|
|
р=*л—/4”1 |
|
|
|
|
|
Каждое слагаемое в правой части неравенства (5.24) можно оценить с помощью неравенства (5.3). Учитывая, что таких слагаемых бу-
180