книги / Решение некоторых многоэкстремальных задач методом сужающихся окрестностей

Г Л А В А б

МИНИМИЗАЦИЯ ОДНОГО КЛАССА

НЕПРЕРЫВНЫХ ФУНКЦИИ

§ 1. Постановка задачи

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

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

ствие их большого количества.

Если нет никакой дополнительной информации о характере поведения функции, экстремум которой ищется, то, по сути дела, единственным способом поиска глобального экстремума является слепой случайный поиск [44]. Схема использования метода МонтеКарло для решения рассматриваемых задач следующая. Случай­ ным образом «разыгрываются» точки из области определения функ­ ции. Из полученных точек проводится спуск в «ближайший» локаль­ ный экстремум. При этом запоминается лучшее из полученных значений экстремумов и соответствующая экстремаль, т. е. точка

пространства Rn, в которой этот экстремум достигается.

Метод случайного поиска имеет достоинства и недостатки, ко­ торые подробно обсуждаются в работе [44]. Очевидно, что наличие какой-либо дополнительной информации о характере поведения функции, экстремум которой ищется, желательно использовать для того, чтобы каким-то образом модифицировать метод МонтеКарло, использовать в его работе элементы адаптации и тем самым ускорить получение достаточно хороших приближений к глобаль­ ному экстремуму.

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

171

подробно описаны в монографии [351. Функции, экстремумы кото­ рых определяются, в соответствии с обычной терминологией будем называть целевыми.

Итак, рассматривается задача о поиске глобального минимума функции f(x), заданной на компакте (замкнутом ограниченном

множестве) D в пространстве Rn.

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

что размерность п пространства Rn достаточно велика. Точный смысл такого предположения рассмотрен ниже.

На целевую функцию накладываются следующие ограничения. 1. Функцию f(x) можно представить в виде ^

где каждое слагаемое ft (х) зависит не более, чем от г 4- 1 перемен­ ных, а именно:

2. Всюду в области D функции ft (х) имеют непрерывные частные производные первого порядка по всем переменным. Это условие обозначается так:

формулу (5.2), называется показателем сепарабельности.

Класс квазисепарабельных функций подробно рассмотрен в работе 135]. Там же отмечено, что к этому классу принадлежат многие функции, необходимость оптимизации которых возникает в задачах автоматизации проектирования.

Выбор термина «квазисепарабельная функция»’ связан с тем, что свойство 1 является обобщением понятия сепарабельности функ­ ции.

Как известно, функция f(x), заданная на Rn, называется сепара­ бельной, если она представима в виде

/(* )= £ /< (* ) . (=1

причем каждая из функций f{ (х) зависит только от одной пере­ менной:

ft (х) = qt (xj.

172

Легко видеть, что свойство сепарабельности функций есть частный

f (х2, х2, х3) = хгх2sin (хх — ха) + х2х3 sin (х2 — х3) + xxx3 sin (х3 — x j

является квазисепарабельной с показателем сепарабельности, равным единице. Функция

Сделаем еще несколько замечаний о квазисепарабельных функ­ циях.

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

f(x)£& (D ).

Если учесть, что множество D по предположению является ком­ пактным, то из непрерывности функции f(x) следует, что она равно­ мерно непрерывна на множестве D и ограничена на нем [26].

Кроме того, каждая из функций ft (х) ограничена на компакте D.

рассмотрим еще один пример квазисепарабельной функции. В ка­ честве компакта D cz Rn выберем «кирпич», т. е. множество точек

Это квазисепарабельная функция с показателем сепарабельности равным двум. Из очевидного неравенства

(х<—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 из пространства

Таким образом, при любом t от переменной xt зависят г 4- 1 сла­

174

Рассмотрим вопрос о том, от каких компонент вектора х зависят отдельные компоненты вектора <р. Последовательно используя соотношения (5.7) и (5.2), находим

Ф1 (х) = % (*i, . • •, хг+1, x„^r+i..........хп),

175

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

Если это неравенство не выполняется, то каждая из функций за-1 висит от всех компонент вектора х.

Как пример рассмотрим функцию, которая задана соотношением (5.8). Если выбрать п = 7, то получим

Далее рассматриваются только такие квазисепарабельные функ­ ции, для которых выполняется неравенство (5.10).

Пусть некоторая точка х, принадлежащая внутренности ком­ пакта D, является локальной минималью. Иными словами, зна­ чение функции f(x) в этой точке является локальным минимумом. Поскольку градиент функции в минимали равен нулю, то вследствие равенства (5.6)

Фх (х) = 0, i = 1, 2, . . . , п.

Случайным образом выберем v из п координат точки из пространст­ ва R", полагая при этом v < п.

Изменим в точке х значения выбранных координат. Это делается

176

случайным образом, но так, чтобы полученная точка (обозначим ее xv) принадлежала внутренности компакта D.

В частном случае, если в точке xv градиент функции f(x) прини­

мает нулевое значение (точка хч при этом может быть локальной минималью, локальной максималью или седловой точкой), то при

переходе от точки х к точке xv компоненты вектора <р не изменяются, а остаются равными нулю.

Вообще говоря,

компонент вектора <р в точке х отличны от нуля, а остальные его компоненты совпадают с соответствующими компонентами век­

нившихся компонент (5.12), как правило, резко завышена. Дело в том, что если изменяются значения двух близких координат xt и Xj, то многие компоненты вектора ф зависят от х( и xt, и потому число изменившихся компонент будет меньше чем 2 (2 г + 1). Под бли­ зостью координат понимается отношение величин |/ — / 1и г.

Поясним сказанное на примере функции, заданной соотношением (5.8). Положим п — 20. От координаты хх зависят следующие ком­ поненты вектора ф : фх, ф2, фц, ф10 и ф^; от координаты х2: фх, ф2, Ф з, ф19 и ф20; от координаты х7: ф6, ф„, ф7, ф8 и ф9. Показатель сепара­

чения изменят лишь шесть компонент вектора ф: фх, ф2, ф8, фх8, фХ9 и ф20.

Поскольку выполняется неравенство (5.11), найдется число /х такое, что для точки

(5.13)

лежащей во внутренности компакта!?, будет справедливо неравенст­ во

Из построения (5.13) и сделанного выше замечания о том, какие компоненты градиента отличны от нуля, следует, что по крайней

мере п — v (2г + 1) координат у точек х 1' и xv совпадают. Продолжая процесс градиентного спуска, построим последова­

причем числа t/ выбраны так, чтобы выполнялось неравенство

fCxv‘') < f ( x v-'-1).

Поскольку выполняются условия сходимости метода градиентно­ го спуска [43], для любого е > 0, найдется такое число шагов q, зависящее от е, что будет справедливо неравенство

\f (xv'9) — f(x )\< е,

где х — локальная минималь, в «зоне притяжения» которой лежит

A V

точка х .

Из формулы (5.14) и проведенных выше рассуждений вытекает, что если при переходе от точки х к точке хч были изменены значения

v координат, то в точках х и xv,<7 разными могут быть лишь s коорди­ нат, причем

Таким образом, доказана следующая теорема, подводящая итог

проведенных в этом параграфе исследований.

л

Теорема 5.1. Если в точке х изменены v координат, то в точ­ ке х не более чем

В этой теореме в качестве / (х) используется квазисепарабельная функция с показателем сепарабельности г, a q — число шагов

градиентного спуска, необходимых для построения точки х с за­ данной точностью е.

178

§ 3. Уменьшение математического ожидания

Опытом, или наблюдением, будем называть выбор произволь­ ной точки х из компакта D, а результатом опыта, или событием,— значение функции f в точке х.

Пространство элементарных событий [66] состоит из всевозмож­ ных исходов опыта, т. е. содержит все значения функции f (х) при

равно М:

<f(x)> = M.

(Как указывалось во введении, угловые скобки используются для обозначения средней величины.) Будет показано, что при некоторых условиях из неравенства

х — некоторая фиксированная локальная минималь функции / (я),

а х — различные локальные минимали, которые строятся путем из-

А

менения значений v координат в точке х и последующего спуска (рис. 45). Заметим, что номера изменяемых переменных выбирают­ ся случайным образом, сдвиги по этим переменным также случай­

ны и, следовательно, точки xv и соответствующие локальные минимали х являются случайными. Поэтому даже при фиксированной

А~

точке х значение f(x) можно считать случайной величиной и гово­ рить о ее математическом ожидании.

Выберем две локальных минимали х° и х1. Точки, полученные из дс° и х1путем замены v координат и последующего спуска к «бли­

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

и что при переходе от точки х° к какой-либо из точек х0/ в разложении (5.1) свое значение меняют не более чем / слагаемых, где / определя­ ется формулой (5.16).

Значение целевой функции f(x) в точке х0/ можно представить в виде

Здесь под знаком первой суммы объединены слагаемые из разложе­ ния (5.1), которые не изменились при переходе от точки х° к точке

х0’. Поэтому соотношение (5.17) можно переписать в виде

Аналогично значение целевой функции в точке xlk можно предста­ вить так:

Из равенств (5.18) и (5.19) следует, что

f(x ° i) - f(x lk)= f(x O ) - f(x 1) +

+ £ [ Ы Л - Ы ^ + М ^ + Ы * 1*)]. (5-20)

Р= П - 1-\-\

Вравенстве (5.20) перейдем к средним значениям. С учетом того что точки х° и х1 не случайны, а фиксированы, получаем

(/ ( Л ) - (/ (*'")> = / (*°) - / (а:1) +

Пусть среди всех значений /, (x0/) наибольшим по абсолютной ве­ личине является ft (х°“‘), а среди значений fr (xik) наибольшим по

Пользуясь тем, что модуль суммы не превосходит суммы моду­ лей, а также неравенствами (5.22) и (5.23), находим следующую оценку:

Каждое слагаемое в правой части неравенства (5.24) можно оценить с помощью неравенства (5.3). Учитывая, что таких слагаемых бу-

180