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

> I и

"б ИАН к.

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

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

ТИХОМИРОВ АЛЕКСЕЙ СЕРГЕЕВИЧ

НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ ЗАДАЧИ ТЕОРИИ СЛУЧАЙНОГО ПОИСКА ЭКСТРЕМУМА

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

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

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

ТИХОМИРОВ АЛЕКСЕЙ СЕРГЕЕВИЧ

НЕКОТОРЫЕ МАТЕМАТИЧЕСКИЕ ЗАДАЧИ ТЕОРИИ СЛУЧАЙНОГО ПОИСКА ЭКСТРЕМУМА

Специальность 01.01.09 - математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

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

Работа выполнена в Санкт-Петербургском государственном университете

Научный руководитель -Официальные оппоненты -

Ведущая организация -

кандидат физико-математических наук доцент & Е Некруткин

доктор физико-математических наук профессор В. Н. Фомин, кандидат физико-математических наук доцент М. К Кондратович

Санкт-Петербургский технический университет

Защита диссертации состоится " Ъ " «^уи^-л. 1993г. в /5". ЪО часов на заседании специализированного совета К 063. 57. 49 по присуждению ученой степени кандидата физико-математических наук в Санкт-Петербургском государственном университете по адресу: 198904, Санкт-Петербург, Петродворец, Библиотечная пл., д. 2.

С диссертацией можно ознакомиться в библиотеке имени А. М. Горького Санкт-Петербургского государственного университета по адресу: 199164, Санкт-Петербург, Университетская наб. Д. 7/9.

Автореферат разослан "23" с^л&уиидл 1993г.

Ученый секретарь специализированного совета кандидат физико-математических наук

А. И. Шепелявый

- 3 -

Общая характеристика работы.

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

Темой диссертации является изучение скорости сходимости некоторых марковских алгоритмов глобального случайного поиска, причем основное внимание уделяется изучению Порядков оценок этой скорости сходимости сверху и снизу при стремлению требуемой точности В- к нулю. Если целью поиска является определение Хс. = ал^^лх (предположим, что такая точка единствен-

на, а функция вычисляется без случайной ошибки) с точностью до £- в некоторой подходящей метрике, то хорошей характеристикой случайного поиска, использующего только значения целевой функции | , будет являться величина Еть , где - число вычислений функции £ , необходимое для первого "попадания поиска в е. - окрестность хф . Зту величину естественно называть трудоемкостью рассматриваемого случайного поиска. Другой естественной характеристикой скорости сходимости является такое число АЧ £ > у) вычислений целевой функции, при котором достижение £ - окрестности зсс гарантировано с вероятностью £ . функция Л/(£ будет называться гарантиррванным числом шагов случайного поиска.

Оценки этих характеристик и рассматривается в диссертации, причем и /V (£, у) будут в точности совпадать с

"числом шагов" соответствующего случайного поиска.

Цель работы - исследование трудоемкости и гарантированного числа шагов некоторых классов марковских случайных поисков, причем параметры ("форма") поиска подбираются таким образом,

чтобы сделать эти характеристики минимальными хотя бы по порядку при £ ->.0.

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

Научная новизна. В работе содержится ряд новых результатов, а именно:

- построен такой однородный марковский случайный поиск, трудоемкость и гарантированное число шагов которого (аппроксимация "по аргументу") имеют вид 0 (с(х,|.^б^О . В случае регулярного поведения целевой функции в окрестности экстремума коэффициент с (,зс, £, I") ограничен по Ь . При этом для построения поиска не нужна информация о целевой функции.

- показано, что для широкого класса неоднородных мар-

I

ковских случайных поисков, обладающих естественным свойством симметрии, трудоемкость не может быть меньше, чем с!&и,£.\.

- построенный однородный поиск применен для оценки максимального значения целевой функции. Выведенные оценки трудоем-ксти и гарантированного числа шагов (аппроксимация "по функции") в целом аналогичны оценкам при аппроксимации "по аргументу".

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

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

- при наличии априорной оценки коэффициента ассиметрии построен такой неоднородный поиск, гарантированное число шагов которого (при фиксированной надежности) для регулярных в окрестности экстремума целевых функций имеет порядок I ^ I \'

« <и | е-1. .

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

£ -окрестность точки экстремума с вероятностью 1 за конечное число шагов £, i). При этом, для регулярных в • окрестности экстремума функций А/ С £ > О = 0(1i \~).

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

Апробация. Результаты работы докладывались 'на третьей мел. дународной конференции "Model-Oriented Data Analysis", СПб, 1992 и на семинарах кафедры статистического моделирования математике- механического факультета СПбГУ.

Публикации. Основные результаты диссертации опубликованы в работах C1-3J.

Объем и структура работы. Диссертация состоит из введения, двух глав и заключения и занимает 160 страниц. Список литературы содержит 47 наименований.

Содер;кание .работы.

Во введении приведены известные оценки трудоемкости и гарантированного числа шагов различных методов оптимизации целевых функций не слишком специального вида. Заметим, что введенные , величины имеют смысл и для детерминированных методов, при этом величина Tt уже не является случайной, осмысленно только y—L и -rE — A/(t, 1) . Таким образом, для детерминированных методов понятия трудоемкости и гарантированного числа шагов совпадают. Тем самым устанавливается некоторая шкала скоростей сходимости алгоритмов оптимизации и видно, ' какое место в этой шкале занимают полученные результаты......""

По этой шкале к "быстрыми" относятся такие методы оптимизации, чьи трудоемкость или гарантированное число шагов имеют логарифмический порядок (то есть не превосходят с при некоторых оОО и С>0 ).

"Медленными" считаются такие методы оптимизации, чьи трудоемкость или гарантированное число шагов имеют степенной порядок (то есть не превосходят с./£> при некоторых <¿>0 и о о 3.

По этой шкале локалышэ методы оптимизации "хороших" функций в оснсеном являются "быстрыми" методами. Приведенные во Iведении результаты для методов стохастической глобальной опти-¡■шзации позволяют считать их "медленными'' методами. Таким образом, по известным ранее результатам, существовал большой разрыв ыеэду логарифмическими порядкам "быстрых" локальных методов и степенными порядками "медленных" ыотодов стохастической глобальной оптимизации. Результаты диссертации показывают, что методы глобального поиска могут на самом деле быть "быстрыми", если их хорошо организовать.

В диссертации исследуются некоторые классы марковских (однородных и неоднородных) случайных псискоз. Первая глава посвя-цена изучению трудоемкости тагах поисков.

Е § 1.1 даны сснчвные определения и условия, относящиеся к шодеству оптимизации, целевой функции.

В качестве множгства оптимизации используется (X , р ^) -метрическое пространство с мерой у4*- достаточно специального вида. Приведем главные из условий, наложенных на (Xу>; ^ Если через обозначить замкнутый шар радиуса х с цент-

ром в точке х , то для любых 1>о и /^(ЗчЛзО") =

~ /а . Таким образом, можно ввести функцию ра-

венством ^ (Л (¿'г(хУ). кроме того предположим, что для всех достаточно маленьких "г ЧЧЧУ>АХ^ (где не-

которые постоянные). Основным примером таких пространств может служить ^ - евклидово пространство с какой-либо обычной метрикой и мерой Лебега.

Относительно целевой функции { будет 'предполагаться, что она ограничена сверху, : измерима, принимает максимальное значение в одной единственной точке Хо^-цл^«. |ЧХ) - и непрерывна в точке эс0. Кроме того, предполагается, что для всех

X> О цлр ( [ ) ? х с- <

Важной задачей при изучении случайного поноса является учет и использование априорной информации о целевой Функции. В полученных оценках ■вся информация о целевой функции содержится в виде тш? называемого коэффициента ассккэтрии Р (.'г ) , сравнивающего поведение о "капоничеегай" одноэкетремаяьпо;; функцией. В частности, £ коэйщпонте озешяяраи закодирована информация о локальных экетрзмутг Сушэдш V . Введем шоязсу-ва ) : {-(иу> {(г; дт лабого ? -

' И ПОЛОЖИМ Р(У) ~ /и ( Мх)//* .

Основной материал 5 1.1 поовяс\?н кзучешга свойств коэффициента ассимэтрии Р . Отиэтим „тень, что г(г)>с при всех "г > о , а при регулярном поведении целевой функции в окрзст-ности экстремума Ьли. ^ ^ I*"-4) — Ро > О при т. —» о. В частности (лемма 1.1.8). если в ошелидозом случае ( йЛ ) £бСг (З^хсЛ4) при некотором о и матрица ^ (-(^о) вторых производных функции невыроядена в точке х0 , то

при "ь о , где V,. - собствепныз числа матрицы f и ^ = пчл-х\j-cO.

Иногда вместо коэффициента асеимэтрии будет удобно попользовать функцию »-«.(х^ (Мг^ ~ Р С^) ^ (.*<. ^ "называемую з дальнейшем функцией ассимэтрш.

В §1.2 описывается структура наследуемого случайного поиска и приводится о6е»я схет его моделирования. Положим = {^бХ ^^^^Сх4)}. Пусть , К > о , х е X . А ь 2? у. обладает следующими свойствами: а) для любых К и х Р( к ^ х, • } является вероятностной мерой б) для любых К и А является Ззу. - измеримой функцией. В качестве случайного поиска ш будем рассматривать бесконечное марковское семейство (. £ § к ^ , £ } <= Xс переходной фуикщкгй к(.к>:х 3 О— - (•)Р(к,х,ве(ж+ Р С к, х, • А Очевидно, такой поиск будет монотонны:', то есть гагаш, что Кьс-1) • рез Ек х будет обозначаться ьатагкгичес?»® оуадапто. соответствующее Рк,х. (в случае однородного 'марковского семейства обозначения будут соотвехствзпно В,. » Р V") и-Ех ). Ео всех случаях будет предполагаться, что Р ( кх обладает плотностью относительно мэры К-

Выбранный класс случайных поисков достаточно прост. Он заключается в том, что при сохранении "формы" поиска (для однородного случая) на каждом шагу с "большой" вёроятностью "прощупывается" окрестность точки ^««.х ££(^51. при атом с "малой" вероятностью ищутся далекие от Чг- точки, в которых значение ^ больше, чем (4^) . После этого "центр" поиска переходит в новую точку 4n.fi. и все повторяется сначала. Такой поиск легко моделируется и свободен от громоздкости более изощренных методов.

В основном (исключение составляют § 1.6 и частично § 2.3) целью поиска считается отыскание точки хс~ ач^тлх 4-(х) с наперед заданной точностью & . Тем самым нас будет интересовать попадание случайной величины ^1 в множество ■^(эсо). Здесь, однако, может случится так, что поиск, оказавшись в на шаге I, выйдет из ¿е (,х0) на следующем шаге. Чтобы избежать анализа таких неприятных эффектов, мы будем интересоваться попаданием Щ в множество И е. . Ввиду того, что поиск предполагается монотонным, он, попав в Не. , из него больше не выйдет. Таким образом, нас будет интересовать величина = г«*/«. {. ^ 5 0 ; ^ №' ^.

При аппроксимации "по функции" мы будем исследовать величину- 1>ь«1п*Дли {,190: -К'^-*-'}.

Параграф 1.3 содержит некоторые вспомогательные неравенства, неоднократно используемые в дальнейшем.

О методе получения оценок трудоемкости можно судить по § 1.4, занимающем в некотором смысле центральное место в первой главе. Основной результат этого параграфа - теорема 1.4.1 - утверждает (при условии ограниченности. X полагается /^(У*) = = ), что для определенного в § 1.2 однородного

; ы

поиска определенного с Р(х, • Г с >,ч) ^

где = . /УЧрК^е.!],

1 и при Ы а^-^^ + Ч',.-! , а

таковы, что ге^Сг^ ^С364? ( - некоторая харак-

теризующая функцию ^ постоянная) верна следующая оценка трудоемкости.

Теорема 1.4.1. При выполнении приведенных выше условий

ЕхТе. ^аг. р |иЕ| 1'*-У)(!-»-с/ы).

Здесь Ре = Ц- {РСО,^^ и при зс 4 Н£ Л^(х,£54)< ^ д/ -1: (х ) ^1 , причем > аг,

Таким образом доказано, что при заданных ограничениях на X , р , рл и 4 всегда можно выбрать такой монотонный однородный марковский поиск, что Е х - 0 (/ . Если же, кроме того, целевая функция регулярна в окрестности экстремума, то Е х = 0 [ № Е ).

Приведенные выше параметры поиска зависят от £. В § 1.4 обсуздается вариант теоремы 1.4.1 с не зависящим от Ь случайным поиском. В этом случае можно получить оценку ■= 0 е^е^ и £ бп* ¿/Е) при <=<->1 (лем-

ма 1.4.3). Кроме того в § 1. 4 обсуддается вариант теоремы 1.4.1 в случае неограниченного X (скажем, Х- Я'*" ). В этом случае параметры однородного марковского случайного поиска можно выбрать таким образом (теорема 1.4.2), что порядок оценок Ехтг при Е будет такой же, как и оценок теоремы 1.4.1 и леммы

1.4.3 в случае ограниченного X .

В § 1.5 доказано (теорема 1.5.1 и лемма 1.5.6), что при некоторых дополнительных ограничениях на метрическое пространство (этим ограничениям удовлетворяет, например, пространство Я0*- с евклидовым расстоянием и мерой Лебега) для широкого класса неоднородных монотонных случайных поисков, обладающих естественным свойством симметрии (полагаем, что вероятностная . мера обладает плотностью р* = = ( f^-У I х-)) и -^к является невозрастающей функцией) и для произвольной целевой•функции, имеющей единственную точку максимума, выполняется неравенство Е^х > С(х) | £ \.

В § 1.6 построенный в § 1.4 поиск применяется для оценки максимального значения | (х целевой функции 4 • Функции здесь дополнительно требуется выполнение неравенства ^— — {-(.х) == \1, рс (х5'Хо) с некоторыми положительными постоянными Ь и с . Выведенные оценки трудоемкости ("аппроксимация по функции") в целом аналогичны результатам § 1. 4. В частности, если &/т Р(т.)> о при о , то порядки оценок Е^а. ( ^ == { : ? о : > {(хс^-Е} ) в точности' совпадают

(лемма 1.6.2) с порядками оценок теоремы 1.4.1 или леммы 1.4.3.

В § 1.7 результаты § 1.4 обобщены на случай топологических

пространств. Показано, что при введении подходящей системы окрестностей точки максимума целевой функции и построении переходной функции определенного в § 1.2 случайного поиска можно отказаться от использования метрики, при этом общий характер рассуждений и оценок теоремы 1.4.1 сохранится. Эти рассуждения полезны в некоторых случаях. Во-первых, при отказе от некоторых, введенных в § 1.1 ограничений на X , и ^ . Во-вторых, при использовании .дополнительной информации об ориентации множеств {у еХ|^("г-")} . хеХ . В-третьих, отказ от использования связанной с задачей метрики может также быть полезен при выборе "формы" поиска из соображений удобства моделирования.

В § 1.8 рассмотрен поиск, являющийся вероятностной смесью случайного и детерминированного методов. Пусть выбран некоторый метод локальной оптимизации и какой-либо из методов случайного поиска, описанных в § 1,2 и § 1.4. Общая идея состоит в том, что на каждом шаге нового поиска о вероятностью р применяется локальный метод и с дополнительной вероятностью (Д-р} глобальный случайный поиск. На пространство X и целевую функцию 4 при этом налагаются дополнительные ограничения, обеспечивающие реализуемость выбранного локального метода. Оказывается, что, если в заранее неизвестной окрестности экстремума целевая функция "достаточно хороша", то порядок трудоемкости смеси наследует свойства более быстрого локального метода. Это иллюстрируется на примере градиентного метода, хотя утверждение носит более общий характер. Точные формулировки утверждений не приводятся ввиду их громоздкости.

Вторая глава посвящана оцениванию гарантированного числа шагов поиска и учету априорной информации о целевой функции. В 8 2.1-§ 2.7 рассматривается однородный монотонный марковский случайный поиск. Как и в § 1,2 будем рассматривать вероятностные «эры Р(ос/) , обладающие плотностью относительно меры ^. Кроме того будем предполагать, что рС3-^)-— , где 7Г невозрастающая, строго положительная функция, ■

Параграф 2.1 носит вспомогательный характер.. В нем получены оценки функции распределения моментов первого,достижения ' £-окрестности точки эс0 . эти оценки используются в § 2.2 и 5 2.3. г'

- 11 -

В § 2.2 вводятся величины

з (*><} > е > 5 )-1/(+ 5 1/д (Ч)

(Е>«П

и

Здесь т. - функция ассиметрии, ^(г) - Х"(2Л Л с1сллпХ- о^ при о< XУ2. (функцйя ЭТТ определяет "форму"

поиска) а £ — 5"(а-} = 6 ^ о : хе М^ }.

В теореме 2.2.1 доказано, что трудоемкость описанного вьше однородного случайного поиска ("форма" которого определяется функцией С'1' ) удовлетворяет неравенству

Параграф 2.3 занимает одно из центральных мест з исследовании однородного поиска. В нем в предположении о регулярности функции 4 з окрестности точки найдены величины

^о (х) ^ 1 ) > асимптотически эквивалентные гарантированному числу шагов А/(х, е , Приведем формулировку соответствующего утверждения.

Теорема 2.3.2. Пусть для коэффициента ассиметрии выполняется соотношение в-т. при X О и Ио. -функция 'ассиметрии. Цусть вероятностная мера Р(зс>>) введенного в § 1.2 однородного марковского поиска обладает плотностью

где Ж невозрастакхцая и такая, что

и для любого о <• «_< (М.л-гуу X выполнйется неравенства • 0<Ц 1с(1),о<г<а} и -^-р Тогда для любого г е

й/т. ^ 1\ > I(> 3 ■>£ > о-уэдтф £,£(*))'^

где Т - функция распределения стандартного нормального закона . При ЭТОМ

£ > = ^(^»g^tjS'cx^iew^u^,

где Cx и cs. отделены от нуля и ограничены по £. Напомним, что для всех достаточно малых £ <fСО>(для евклидовой метрики и меры Лебега в R^ ^ftO =c«l £.«*- ).

Для найденной в теореме 2.3.2 величины /У0 (_х> у у= ^ШО^Ц^О-УН ir V2) С ha е с у^У^О выпол-

няется соотношение е c?((r') -С^ / Y'\CvT.>f (О

Я^о-) при £.-»0 . Тем самым /4 (зс., t, у4) может служить гарантированным числом шагов А'(х > fc > ¡f') . где ^

при £ О.

В теореме 2.3.1 найдены величины, ассимптотически эквивалентные гарантированному числу шагов для определенных в теоремах 1.4.1, 1.4.2 и лемме 1.4.3 однородных поисков. В этой же теореме при решении задачи оценки максмального значения целевой функции, для определенных в лемме 1.6.2 поисков получены величины, ассимптотически эквивалентные гарантированному числу шагов при аппроксимации "по функции". Полученные оценки в целом аналогичны результатам теоремы 2.3.2 и не приводятся ввиду громоздкости. Во всех случаях при фиксированной надежности $ и £ -> о.

В условиях теоремы 2.3.2 До 0(£nf*- L) при

фиксированной надежности. Величины А/о и I зависят от функции ассиметрии, содержащей в себе информацию о целевой функции -f и от "формы" поиска. Поэтому можно ставить вопрос об оптимальном виде поиска, который минимизирует A4 при фиксированной функции ассиметрии. В § 2.4-§ 2.7 эта задача решается в упрощенной постановке, когда вместо У о минимизируется величина I , эквивалентная . Кроме того, так как в силу теоремы 2.2.1 величина I является оценкой трудоемкости поиска, то такая постановка задачи осмыслена и с точки зрения минимизации трудоемкости. Плотность .("форму" поиска), минимизирующую при фиксированной функции ассиметрии, естественно назвать оптималь-' ной плотностью.

В § 2.4 доказана существование оптимальной плотности (тео-, рема 2.4.1). Кроме того, там показана (теорема 2.4.2) устойчивость оптимизационной задачи по отношению.к-малым изменениям функции ассиметрии. Тем самым обоснован'учет априорной информа-

ции о целевой функции в виде функции, приближающей функцию ассиметрии.

В § 2.5 (теорема 2.5.1) при дополнительном предположении о непрерывности функции ассиметрии (соответствующие условия на £ обсуждаются в § 1.1 в лемме 1.1.3) показана непрерывность оптимальной плотности.

В § 2.6 найдена структура оптимальной плотности и кратко обрисован один из возможных методов организации алгоритма для ее нахождения. Точные формулировки утверждений не приводятся ввиду отсутствия места.

В § 2.7 обсуждаются свойства стандартной плотности (то есть оптимальной плотности для постоянного коэффициента ассиметрии). Такая плотность не зависит от значения коэффициента ассиметрии к >«о»ет быть использована в случае, когда конкретная информация о целевой функции отсутствует. Кроме того (лемма 2.7.1), для фиксированной регулярной в окрестности экстремума целевой функции и малых £ стандартная и оптимальная плотности дают примерно одинаковый эффект в смысле оценки трудоемкости. В тоже время при фиксированном (малом) £ можно подобрать такую функцию £ , что эти эффекты будут сильно различаться.

Кроме того, в § 2.7 получены более точные оценки трудоемкости стандартного поиска снизу. Оказывается (лемма 2.7.3), что для "идеальной" функции ( Р = 1 ) ЕХ"СЬ> А * | Е. |. Таким образом, полученные оценки трудоемкости поиска сверху ( ЕХ"С£.—0(</л.гЕ.) ) дают порядок, недалекий от истинного.

В двух заключительных параграфах рассмотрены простейшие виды неоднородного марковского монотонного поиска. В § 2.8 найдены оценки гарантированного числа шагов для очень простого, но тем не менее успешно использующегося на практике случайного поиска. Частным примером подобного поиска может служить описанный в § 1.2 поиск, если положить = (• /

/ да У) . где Л«. - некоторые положительные веществен-

ные числа Параметры этого поиска могут быть выбраны таким образом (теорема 2.3.1), что для гарантированного числа шагов будет выполняться неравенство

Такой поиск может не сходиться к Х0 , тем не менее оказыва-

ется, что (при наличии априорной оценки коэффициента ассимет-рии) для регулярных в окрестности точки ос0 функций для рассматриваемого случайного поиска *

»при фиксированном ^ , в то время как для однородного поиска

В §2.9 рассмотрена детерминированная модификация введенного в § 2.8 случайного поиска, в которой вместо равномерно распределенных точек берутся точки некоторой специальным образом сконструированной сетки. В этом случае (теорема 2.9.1) (при дополнительной информации о целевой функции) L-окрестность точки сх-о может быть найдена за конечное число шагов M^i). Кроме того, для регулярных в окрестности экстремума функций

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

Публикации автора по теме диссертации.

1. Некруткин Е R , Тихомиров А. С. Некоторые свойства глобального марковского случайного поиска // Вестн. Ленингр. ун-та. Сер. 1, 1989., Вып. 3(15), с. 23-26.

2. Nökrutkin V. V., Tikhomirov A. S. Several results on random search methods in metric spaces. // Stochastic Optimisation and Design. VI,1, 1992., p. 49-71.

3. Тихомиров A.C. О трудремкости поиска экстремума функции. //Вестник С1ЮГУ. Сер. 1. 1992.. Вып. 3(15), с. 106-107.