Труды семинара Бурбаки за 1988 г (947402), страница 50
Текст из файла (страница 50)
Для любого хан Е пусть )т„— множество всех точек у яЕ, таких, что д,а ) О, которое будет называться множеством соседей х. Говорят, что точка х — локальный минимум Н, если Н(х) ( ( Н(у) для всех у ен т* . Точка х называется глобальным минимумом, если Н(х) < Н(у) для всех у я Е. Мы обозначаем Емш множество глобальных минимумов, а Еьосмтн множество локальных минимумов Н. Введем теперь несколько понятий, использованных Гаеком (На)ек). Говорят, что два состояния х и у из Е сообщаются на высоте й, либо если у =х, и Н(х) ( (т, либо если имеется последовательность хь ..., хь, й = 2, такая, что х, = х, хь = у, и Н(хг)» (й, х(+~ ~ )т, для всех /=1, ..., й. Заметим, что это свойство симметрично относительно х, у. Глубиной й, локального минимума х~Е будем называть наименьшее число Р ) О, для которого существует такое у ен Е, что х и у сообщаются на высоте Н(х)+ Р, и Н (у) ( Н(х).
Заметим, что если х — глобальный минимум, а»=+оо. (5.1) (5.4) л-1 (5.2) Теорема (Гаек). Рассмотрим произвольную функцию энергии Н: Е-+- Р и алгоритм «отпуска» (5.1). Тогда соотношение (5,3) 1пп Р(Х„ыЕмгв)=1 о-»» выполняется тогда и только тогда, когда где константа Р задается формулой (5.5) Р=зпр (й»~х~Еьосмн'Ем14. )7=зпр(Ь»у1х, уев Емш, х че у), Н=гпах()т, Р), (5.7) где Р задается формулой (5.5). Тогда свойство 1пп Р(Х„=х)=О для всех хтыЕмпо 1пп' Р (Х„= х) ) 0 для всех х ы Ем~и о-»+о~ (5.8) вьтолняется тогда и только тогда, когда Е ехр( т )=+ л+~ (5.9) Все методы доказательства, использованные Гаеком, Чаном и Чоу (На)ек, СЫапн и СЬочс), а после этого Катани (Са1ош), который получил технически лучшие оценки, явно или неявно опираются на идеи больших уклонений, введенные Фрейдлиным и Вентцелем при изучении инвариантных мер диффузионных процессов с малой диффузией.
Тот же источник'вдохновения лежит в основе подхода Вона н Шеу (Нчсапа и Язеп) к асимптотике так называемого уравнения Ланжевена. Из-за недостатка места, вместо того чтобы описывать высоко технические результаты этих авторов, мы предпочитаем 16 з»к. 4бВ Из этого элегантного результата легко вытекает, что последовательность Т„, такая, что 1пп Т„!ода=с, будет «мнними«.++ « зирующим» режимом охлаждения тогда и только тогда, когда с ) Р— результат, серьезно улучшающий прежние достаточные условия, данные Д.
и С. Геман (Р. и 8. Оешап), а также Гидасом (Ст!баз). Недавняя теорема Чана и Чоу (СЫапн, СЬоч) приятным образом завершает результат Гаека (На)ек). (56) Теорема (Чан (СЫапн) и Чоу (СЬочс) ). Рассмотрим алгоритм «отпуска» (5.1). Для любых двух различных глобальных минимумов х, у в= Ем,н пусть Йл — наименьшая высота, на которой х и у сообщаются. Определим константы Процедура «от»до»о» Р.
Авен»отт Р~ (Т) = а„„ехр ~ (7.1) 1 „=И„+,Е М~,„, Х я Ал (7.3) предложить значительно более быстрый подход, который будет менее общим, но дает существенные и легко доступные ключевые идеи; выкладки будут намечены неформально, но могут быть с очень небольшими усилиями формализованы и действительно дают полезный инструмент для быстрого понимания новых вариантов алгоритмов «отпуска». 6. АСИМПТОТИЧЕСНИЕ РЕЗУЛЬТАТЫ ФРЕЙДЛИНА — ВЕНТЦЕЛЯ На конфигурационном пространстве Е рассмотрим стохастическую матрицу вероятностей перехода, зависящую от параметра Т ) 0: (6.0) Рт —— [р„„(Т)[» ~ в, е ~ е, где при х~у (6.1) Здесь 6 „, а„„вЂ” произвольные числа из Р+, а параметр Т будет стремиться к нулю.
Предположим, что матрица Рт неприводима, так что есть единственная инвариантная вероятностная мера ит на Е, удовлетворяющая уравнению !»ТРт = ит. Пусть Лт — наибольшее по модулю собственное значение МатрИцЫ Рт СрЕдИ ВСЕХ СОбСтВЕННЫХ ЗНаЧЕНИй, ОТЛИЧНЫХ От 1. Вентцель и Фрейдлнн доказали два интересных результата, ка- сающиесЯ асимптотнческого поведениЯ ит н Ат пРи Т вЂ” ~0. Чтобы сформулировать эти результаты, введем для любого подмножества Р множества Е определенное множество графов 5(Р) с вершинами из Е. По определению граф 6 чей(Р) — это набор стрелок ): х-+.у, где х, у ее Е, х Ф у, таких, что (6.2) 6 не содержит циклов; для каждого х ~ Е~ Р граф 6 содержит единственную стрелку, начинающуюся из х; для всех х ееЕ граф не содержит стрелок, начинающихся из х. Дла любои стРелки ): х- У полагаем тт(1)= ттч, и цена 6(6) любого графа 6 из 5(Р) определяется формулой (6.3) и(6)= Х иа.
!яа Следуя Вентцелю, определим сейчас для й = 1, 2, ..., сагб(Е) числа (6.4) Сь=!Л1(6(6)[6е=5(Р), Рс=.Е, сагб(Р)=й). Вентцель доказал, что если Ф = сагб(Е), то (6.5) С,)С,)... ~«Си=О, т6.6) С~ — Сз ~~ Сз — Сз ~)... ) Сн, — Сн, и что в о в случае общего положения, когда неравенства (6.6)— строгие, при малом Т собственные значения матр ц т р а иыР аз- личны и действительны, и (й+ 1)-е (в порядке убывания) соб- ственное значение 0»(Т) удовлетворяет соотношению (6.7) !пп Т1оп[1 — 8„(Т))= — [С» — С» Д, т-»о В частности, можно слегка уточнить результат Вентцеля и показать, что 2-е собственное значение Ат удовлетворяет соотношению Ах (6.8) 1 — )т сехр ( — — ~, где А=С,— С,>0, а с)0.
т. СтупенчАТОе ОХЛАЖДеНИе Чтобы получить основание для эвристических соображений, мы изучим режимы охлаждения, при которых температура Т„ поддерживается фиксированной в течение ряда К, последовательных шагов, прежде чем понизить ее до,+~. р Т . Такие ежимы охлаждения вполне обычны в приложениях. П Р вЂ” матрица вероятностей перехода за один шаг при усть температуре Т„, определенная схемой «отпуска» ( . ), иой с функцией энергии Н (х). Конечно, в обозначениях (6.0)— (6.1) имеем Р„=Рт„с: 6„о =[Н(у) — Н(х)[+.
Пусть чо — распределение вероятностей начального значения Х„. Распределение вероятностей ч„ значения ~„, д Х г е Е =К1+ +К ° задается рекуррентным соотношением к„ (7.2) т„= У„,Р„». Обозначим Л„множество различных собственных значений мат- рицы Р„, не равных 1. Тогда жорданова нормальная форма Р„ дает Р. Аеепкотт дроцедуро «отпуске» где, поскольку Є— неприводимая стохастическая матрица, все строки матрицы М„до.гжны совпадать с инвариантной мерой матрицы Рл, и 1ги (7А) .
!»„Я»,л=-О для всех 1 ~Л„. В частности, так как строки матрицы М одинаковы, для любой меры !» на Е имеем импликацию: (78) 61»Р л9 ч"а~1 — сехр( — А)~ "!!!»!!, где а — константа (уже другая). Чтобы упростить обозначения, положим ! !и= ехр( — — ], 1п1 Н(х)=Ь, тл л«е !п1 Н (х) = В+ Ь, где В > О. и «в',в»!си (7.9) Вспомним, что инвариантная мера р„матрицы Р,— это гиббсов- ская мера (7.10) (н ги! л т. л где Х„= ~" (нгю у«в (7.5) из ~ ', !» (х) = 0 следУет !»Ми «О. л«в Пусть г!т„— собственное значение из множества Лл с наи- большим модулем; оценки $6 показывают, что по крайней мере в случае общего положения (7.6) !Х!(1 — СЕХР( — —,) ДЛЯ ВСЕХ Д-Лл, А х где А =' С! — Сг ) О, с ) О.
Можно также доказать, что (7.7) !!ф, „!!(а для всех А яЛл и всех Тл, где а — фиксированная константа. Чтобы написать более корот- кое доказательство, предположим, что Р„диагонализуема. Для любой меры !г на Е, такой, что ~, !» (х) = О, имеем и«в рР'л=р~М + Х 1!"~» л1 »«А так что из формул (7.5) — (7.7) выводим Элементарная выкладка, основанная на (7.9), (7.10), показывает, что (7.11) !!р.— р.„!! <а~.', где а — (нОвая) константа. Пусть теперь (7.12) Еи=!!чл — !»„!! .
Используя (7.2) и инвариантность меры !г«получаем ч — !» =т Р" — !»Р"= к к и л л — 1 и л п (ч — 1г )Ркл+(!г !» )Р что ввиду (7.8) и (7.11) дает (7.13) е (а(1 — с1 ) иеи, +а! . Конечно, из (7.13) немедленно следует (7.14) где использованы обозначения (7.15) гьл=аГав при п~>1, ыо — — а„но=1 л ил=оп П(1 — с!»)» для п)1. »-! (7.16) л.++ Вш ' — ~~.К»г»+а1ояа = — оо. А л.++« (7.17) В частности, Х К»1» = + оо. »-! ТепеРь мы можем епоигРать» с Ки и Ги=ехР— —, чтобы ! Ги обеспечить стремление е„к нулю при и — ь+оо. Действительно, если это достигнуто, распределение ти случайной величины Х, должно иметь тот же предел при и — э. +со, что !г„, а этот последний предел очевидным образом есть равномерное распределение рмгп на множестве Ем!я гяобальных минимумов.
Выражение (7.14) показывает, что в выборе таких минимизирующих режимов имеется большая свобода и что граница, полученная для з„может стремиться к нулю при и-~-+оо, только если Нш и„= О, что эквивалентно 2247 Процедура «отпуска» Р. Аееллотт Выберем Кы например, так, чтобы Кь=(с/ь) (!оиа+Ьс), где Ь) О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
