Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

10.4. Метод случайного поиска

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

Итак, рассматривается задача минимизации функции φ(x) на множестве X. Будем предполагать, что найдена точка xk∈X.

Выбор направления спуска. На n-мерной единичной сфере с центром в начале координат выбирается случайная точка rk, подчиняющаяся на этой сфере равномерному распределению, и затем направление спуска - sk выбирают из условий sk = θkrk, где


Схема 1. В качестве начального приближения х0 выбирают любую точку х0∈Х. По вычисленной на k-й итерации точке xk строят (k+1)-ю точку xk+1 по формуле

xk+1=xkksk

качестве βk выбирается любое число из


удовлетворяющее неравенству

(10.47)

где λk любое такое, что 0<λ≤λk≤1, а


Схема 2.


В качестве βk выбирают наибольшее из чисел, удовлетворяющих условиям

(10.64)

где числа qk любые такие, что


Сходимость. Доказательство сходимости будем проводить в следующих предположениях:

1) множество X выпукло и замкнуто;

2) множество X регулярно, то есть в Еn существует сфера радиуса ρ>0, целиком принадлежащая множеству X;

3) для любого элемента х0∈X множество


ограничено;

4) функция φ(х) выпукла и φ(x)∈C1,1(X).

Замечание. Нетрудно убедится, что условие регулярности 2) эквивалентно условию регулярности, введенному в гл. 3, п. 3.1.

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

Свойство А. Если точка х̄∈X не является оптимальной, то найдется такой ȳ∈Х, для которого справедливо неравенство

<φ'(x̄), x̄-ȳ> = ξ > 0

Доказательство. Пусть y является проекцией точки z = x̄ - φ' (x̄) на множество X. В силу свойств проектирования имеет место соотношение


то есть


Отсюда и следует свойство А, поскольку равенство х̄=ȳ является необходимым и достаточным условием оптимальности х̄ (теорема 2.16).

Всюду ниже через х̄ и ȳ обозначены точки, удовлетворяющие свойству А.

Свойство В.Найдется такое число δ>0, что множества


и ' .


не пересекаются, и существуют такие n-мерные сферы R1 и R2 радиусов ρ1 и ρ2, что R1⊂U и R2⊂V.

Доказательство вытекает из свойства А (так как x̄≠ȳ) и предположений 1) и 2)*.

Свойство С. Для ξ=<φ'(x̄), x̄-ȳ> > 0 найдется такое δ>0, что для всех x∈U (х̄, δ) и y∈V(ȳ, δ ) будет выполняться неравенство

<φ'(x̄), x-y&> ≥ 1/2 ξ

Доказательство. Обозначим


Предположение 4) гарантирует, что γ<+∞. Выберем


Пусть u = х-х̄ и v = y-ȳ (x∈U, y∈V), тогда


Далее,


* (Легко показать, что если точка w-центр сферы R (радиуса ρ), принадлежащей регулярному множеству X, то можно взять


причем центром сферы R1 будет точка


Аналогично и для R2.)

Но ввиду предположения 4) и свойства А получаем


Три последних соотношения и выбор величины δ доказывают справедливость свойства С.

Определение. Мы скажем, что осуществилось событие M=M(х, s), если найдется такое β̃>0, что y = х-β̃s∈V (у, б), где x∈U (x̄, δ), а-s-возможное направление, выбранное методом случайного поиска.

Свойство D. Если наступает событие Mk = M(хk, sk), то существует такое ε>0, что


Доказательство. 1) Случай схемы 1. Пусть xk∈U', а yk-любая точка из пересечения луча xk-βsk с множеством V. Так как


то для всех β∈ [0,1] справедливо неравенство


Отсюда, из (10.47) и из леммы 9.3 получаем неравенство


Но


поэтому из свойства С получаем, что для всех β ∈ [0,1] будет


Пусть


Если β = 1, то Lθ2≤1/2ξ и


Если


то


так как λk≥λ>0, то при


свойство D становится справедливым.

2) Случай схемы 2. Из свойства С следует, что

(10.65)

Теперь убедимся, что

(10.66)

где


Так как


из леммы 9.3 следует неравенство


Таким образом, β̄k удовлетворяет соотношениям (10.64). поскольку в качестве βk выбирают наибольшее из чисел, удовлетворяющих условиям (10.64), то справедливо неравенство (10.66).

Выберем величину δ>0 столь малой, что ||х̄-ȳ|| - 2δ > 0. Так как


то из (10.66) и (10.65) следует, что


Отсюда и из (10.64) и (10.65) получаем


Свойство Е. Если последовательность {хk} такова, что xk∈U, то


Доказательство. Из свойств А и В следует, что


При фиксированных x0, x1 ... соответствующие события M0, M1 ... взаимно независимы, так как взаимно независимы случайные величины s0, s1 .... Следовательно,


Здесь M̄k означает событие, дополнительное к событию Mk, то есть M̄k означает, что событие Mk не происходит. Поэтому согласно закону "нуля или единицы"


то есть


Это и означает, что


Теорема 10.9.


Доказательство. В силу предложенной процедуры, последовательность случайных величин {φ(хk)} монотонна:

φ(xk+1)≤φ(xk) (k = 0, 1,..)

ограничена:

φ(xk)≥φ(x*) (k = 0, 1,..)

следовательно, существует


значит, с вероятностью, равной единице, найдется такой номер k0, что для всех k=k0+1, k0+2, ... будет выполняться неравенство

φ(xk)-φ(xk+1)<ε (10.67)

Если для любого, сколь угодно малого δ1>0 найдется такая подпоследовательность {xki}, что


с вероятностью, равной единице,


Предположим, что существует такое число δ1>0, что окрестность U* попадает лишь конечное число точек последовательности {xk}. Не ограничивая общности, можно полагать, что все xk∈U*. Тогда с вероятностью, равной, единице, найдется такой случайный номер k≥k0, что осуществится событие Mk, а следовательно, будет


Это противоречит условию (10.67). Теорема доказана.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"