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


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

10.5. Метод проектирования случайного направления

Изложенный в предыдущем разделе метод минимизации может оказаться неэффективным. Дело в следующем. С ростом числа n - размерности пространства En - убывает вероятность того, что направление rk является возможным. Скорость этого убывания характеризует простой пример, когда


a точка хk = 0. В этом случае вероятность того, что случайное направление rk будет возможным, очевидно, равна 2-n". Поэтому для получения возможного направления требуется при больших n на каждой итерации, вообще говоря, большое число испытаний, причем каждое испытание связано с проверкой, будет ли для достаточно малого β точка хk-βrk принадлежать множеству X, то есть будет ли rk = sk и, следовательно, с определенными вычислениями.

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

Обозначим через zk проекцию точки хkkrk на множество X. Здесь Δk = sign <φ' (хk), rk>, а rk строится так же, как и в предыдущем методе.

Схема 1.

xk+1=xkksk
sk=xk-zk

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


где


Схема 2.

xk+1=xkksk
sk=xk-zk

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




Для обоснования сходимости метода проектирования применима та же методика, что и в предыдущем разделе. 1 При этом требование регулярности множества X становится излишним.

В самом деле, рассмотрим множество*


Заметим, что


* (Здесь ȳ, U и V те же, что в п. 10.5.)

Будем говорить, что осуществилось событие N = N(х, r), если найдется такое α>0, что х-αr∈V0, где х∈U, а r -направление, выбранное методом случайного поиска. Определение события M = M(х, s) остается прежним, но при этом


Свойство F.Если осуществилось событие Nk = N(xk, rk), то осуществится и событие Mk = M (хk, sk).

Доказательство. Пусть vk = xk-αrk∈V0, a yk-ее проекция на множество X. Из свойств проекции следует, что


и любом x∈Х и, в частности,


есть yk∈V.

Наконец, очевидно, что для всех x∈U будет


Обосновать сходимость процесса минимизации теперь не представляет труда, если повторить рассуждения, которые использовались при доказательстве теоремы 10.9.

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





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


Диски от INNOBI.RU




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