Функция риска в задаче поиска глобального экстремума тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

На правах рукописи1

Ковалев Сергей Владимирович ФУНКЦИЯ РИСКА В ЗАДАЧЕ ПОИСКА ГЛОБАЛЬНОГО ЭКСТРЕМУМА

01.01.09 — математическая кибернетика

АВТОРЕФЕРАТ

диссертации на соискание учбной степени кандидата физико-математических наук

Санкт-Петербург 1994

Работа выполнена в лаборатории математического моделирования природных структур и процессов Читинского института природных ресурсов Сибирского отделения Российской Академии наук.

Научный руководитель: доктор физико-математических наук, В.В.Мазалов.

Официальные оппоненты: доктор физико-математических наук, Е.В.Седунов,

кандидат физико-математических наук, . В.М.Буре.

Ведущая организация — Институт прикладной математики ДВО РАН.

Защита состоится (¿uiUci 1994 г. в Ц? часов на засе-

дании специализированного УчЭного совета K-063.57.I6 по присуждению учёной степени кандидата физико-математических наук в Санкт-Петербургском государственном университете.

С диссертацией можно ознакомиться в библиотеке им. A.M. Горького Санкт-Петербургского государственного университета.

Автореферат разослан "'41" М<иц 1994 г.

Ученый секретарь специализированного совета K-063.57.I6, доктор физико-математических наук Ч Горьковой В.Ф.

ъ

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность проблемы. Теория оптимизации — одна из кардинальных проблем современной вычислительной и прикладной математики. Игроков распространение ЭВМ в последние 2-3 десятилетия стимулировало большой интерес к методам оптимизации как средству решения экстремальных задач не поддающихся классическим методам. Математическую теорию экстремальных задач мошо условно разбить на две части: теорию локальной оптимизации и теорию поиска глобального экстремума. Первую из них можно считать в целом сформировавшейся. В то ке время теория глобального поиска находится на начальном этапе развития. Алгоритмы локального поиска обычно основаны на идее спуска, причЭм направление спуска выбирается исходя из линейной (градиентный метод) или кввдра-тической (метод Ньютона) локальной модели целевой функции. Для многоэкстремалышх же задач не известны ни столь очевидная идея алгоритма, ни столь широко приемлемая модель целевой функции. В связи с этим очевидна актуальность разработки новых идей и методов теории глобальной оптимизации.

Цель диссертации. Целью диссертационной работы является

1) разработка математической модели глобального поведения сложных многовкстремальных функций;

2) разработка на основа принятой модели целевых функций алгоритма глобального поиска;

3) создание программы, реализующей предложенный алгоритм на ЭВМ.

Научная новизна. В диссертации предложен новый одномерный

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

Практическая ценность. Результаты работы могут быть использованы при решении экстремальных: задач глобальной оптимизации невысокой размерности (п < 3).

Апробация работы. Результаты диссертационной работа докладывались на 111и IV Школах "Математические проблемы экологии" /Чита, 1990-91 г./, на XIV школе-семинаре "Математическое моделирование в проблемах рационального природопользования" /Ростов-на-Дону, 1991 г./, на научном семинаре кафедры математической отатистики, теории надЭадооти и массового обслуживания факультета прикладной математики — процессов управления Санкт-Петербургского государственного университета /Санкт-Петербург, 1993 г./, .на научном семинаре Института прикладной математики ДВО РАН /Владивосток, 1994 г./.

Публикации. По теме диссертации опубликовано 3 печатных работы.

Структура и объам работы. Диссертационная работа; объёмом 137 страниц, состоит из введения, трбх глав, приложения и списка литературы, содержащего 67 наименований. В работе таккэ содержится II рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении реооматриваютоя основные иавеотшш подходы и методы решения еодвчи глобальной оптимизации.

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

В первом параграфе даЭтся постановка задачи. Заданы функция одного переменного у - f(x) и интервал [а, Ь], причЗм вид функции f(х) неизвестен, либо оня задана посредством слокного алгоритма, так что аналитическое исследование е9 свойств невозможно. Требуется найти наибольшее значение f(г) на [а, Ь]. Стратегия поиска максимума во многом определяется принимаемой моделью п'^двния целевой функции. В диссертационной работе в качестве модели поведения сложных функций предлагается принять случайный процесс, описывающий хаотическое движение броуновской частицы ?(х), для которого ?(3ct) = yt, i » 0,п, где yt значения фу1шции f(х) в выбранных для измерения точках х1 и точки х упорядочены по возрастанию. Условная плотность распределения вероятностей етого процесса является, гауссовской

• ь.(и/if. = j(r) ¡^TTX-^^J-I*-"-?:!,

I 1 v cf / </-• (У 'J ' fl P.S.' у

а важнейшие характеристики, то есть математическое опадание mt(x) и bl (х) даются формулами

m (л ) - ———------- j

а . - -7- • i +1 ^

о /; - <

Рассматриваемая модаль этш.ш ьцшодиинш ииродолвна о точностью до параметра о. А.Жшишскво в юшга "Глобальнья оптимизация" Д11ЙТ ОЦШШУ для и по зависшим наблюдениям, иолутошши в ходо оптимизации, обладающую ойой&тьим соогоятельносчи и несмещённости

1.-1

Во морам rmjuiiTiuld носгулнруитоя функционал, названная фушащой риика, который о-хаинч- и ооотгатотвио матрица

/ ¿'.Л

V у. ••■ У-) '

гдо у, - дхt) , i - D'.Ti, a xi - точки шЛрашша дня проводашш измври.ий иошыдуоиой Г (), илкотирои чиоло по формула

J; V j^ 5i«>

гдэ y* ■ max{yu, ..., yn), i* «. f (у") и гдэ согласно выбору подали функции f (х)

P{ -о >:/:}.

' 1

i 1 I </1

т. т < . л \ - с г, - I

i I ' I '

Вид функционала выбирался исходя из следунпнк соображений: у* - тто текущее приближение к глобгт-ному рчшешто задачи у* = гпчг. Г(х).-

х' I <1. t- 1

Последнее мокет оказаться в шкотороП точке х «птэрввла [а, Ы, х / xt, i = oVn. Поэтеv пбеолятноя овгюка могла Он составить величину 3(х) = |х - х*|. У!пюж«о оЗ на условную вероятность того, что в точке х функция примет значение большее чем у* и проинтегрировав по всем х из [а, ъ] получим функцию рпскв. Таким образом риск представляет собой некоторое усроднЗшгаэ значение ö(x). Еороятност!- РШх) > у*} п выражении функции риска выбрана вместо усл"Ч1ь!" плотности распределен™ вероятностей р(у/ у.= r(x. ), i = öTn) по топ 'Ч '.пшш, что позволяет учитывать достигнутое значение максиму::. ;<*. Далее, вводится в рассмотр91ше ещЭ одна функция, казвоштя функцией ожидяомого риска, которая определяется как математическое ожидание риска при прогноз1Гровакии следующего шага оптимизации в некоторой точке х из интервала (х., х )

' Vi' h -jJ1'1 " (2)

Ki, , I - О, г. -1

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

а- г

У 'I

Правило остановки определяется с помощь» некоторого достаточно малого числа е. Алгоритм останавливается в таком состоянии

. -г. ... от,

ч* ••• У"

для которого

• е ■•■ 1 <

Во второй главе упрощается аналитический вид функций риска и ожидаемого риска и исследуются иг свойства. Поскольку конечной целью диосертации является создание программы ЭВМ на основе предложенного в главе I алгоритма, то возникает задача упрощения аналитического вида функций риска и ожидаемого риска. Для втого их необходимо проинтегрировать.

В первом параграфе рассматривается функция риска. По отношению к ней имеет меото следующий результат

^ ? 2 (3) Г -V

"Г*,

3. - е

л/." <4)

- 1р.-1 - Г '¡^ | 1----,

■11

и? - (г Р. - в,.^,.! - { Т (|Л) { - Зй£ - 6,. (г ^ ^ I 1 > '

-У , * 50 ' 'Л

ё. =

Хотя прокнтегрированноэ виракашга (3) несколько длиннее походного (I), вс8 жа вычисление (3) является намного более простой задачей, чем вычисление двойного интеграла (I), распространенного к тому же на неограниченную область.

Во втором параграфе рассматривается функция ожидаемого риска. Посла интегрирования она принимает слэдупций вид

' в.. в.. ,

м -¡<1

где

ЛГ.)'

CT

í ••

с H

определяются формудьш (4);

Л ---е

J J г^к

_ ó)

ter" it\ -

.¡STKlÇê \

'Ж

.i о)

dl- - L■

]

<. 1 e

J- J

i U г

м;

л г J >

■тс

г ê Л?í. -с J 7

ú) , , , л , k, ■ s V 1

J + —г----)

i , + ( с - ¿.) t ■

»

"Г = í

J

? .i* f'P . íiiill

i <,

(ГГ j - J

PC-Íi, .1 (J

t? - rt<f>

гт ~ít~ е.

e c.tp

я., fcJiïi^jl. ' ■ ' 1 tiffti)

В, --

c>o

e4

- Л J .7.. Л (/-Л)

J

Г II fV- Л J

e -

:e, É,

•5 <\,

¿ f.(t- M i' " lí'iír .''X7V-7.ii • V r

c- c< V 'I 1 Cí ' ' ' . t '

t ' jff'fLCt-Ü

fr'V-^ ('i S - /

,г " ¿ ni <

■tí i л •(

M

■

^'M-i 4'W/M ¡ i ЛЙ. -

- ir«l -i Г H ДГ/-/У f fy};

J

PJT^ (Pj-if

л- a^'CeíjZU^X

с,

S..:^!^ i Л X

ja sJ7x |V & J . \{ГйПГ) J

» i -ГГХ u" P " (I) *

-к-У - и.

1)

(Л е ^Ч^^Ч' ■'

■ и / + 1=Л- -?!—

Л ' Л 5,

Г. - ] е

гя/с«'V

г [_

'Л

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

В третьем параграфа рассмотрены некоторые овсйатва Фун.-лй

риска и ожидаемого риска. Пуоть у* » ук, о < и п. Имоет место , Теорема 3. Ноли > ук и уь > иазСу,,.,, 1 » то

Условия сформулированные в теореме на силом далэ являатся лишь достаточными. Ваключение теораш остается вераым докэ вола нэ

вое у. > шах{ук1, Численные експерименты с функцией

риска показали, что неравенство (6) при у^ » ук нарушается лишь в том случае, когда у или ук^ много больше остальных уе. Теорема 4. Для любого п > О функция риска ограничена

Теорема 6. Функция ожидаемого риска ограничена

, , ( • 'tf - -

О < I—;];— > J £' " ' -«

Теорема 7. Функция ожидаемого риска непрерывна на вс8м интервале [а, ъ].

В третьей главе проводится исследование эффективности построенного алгоритма путбм решения ряда тестовых задач.

В приложении указан текст работающей программы, использованной в диссертации.

Работы, опубликованные по теме диссертации:

1. Ковалбв C.B. Функция ожидаемого риска в задаче глобальной оптимизации. Сб. тезисов конф. "Теоретические и прикладные проблемы экологии." Чита, 1992, ?. ¿3.

2. Kovalev S.V., Mazalov V.V. A risk funotion in global optimization problem. Third, oonf. "Probab. Method in DiBorete Math." — ГУР Boi. t p . 2 É6 - 2 -ГС-

3. Ковалбв C.B., Мазалов B.B. Функция риска в задаче планирования вкспвримента. Моделирование природных систем и задачи оптимального управления. Новосибирск: Наука, 1993, £ • <? S -/„