Книги по разным темам Pages:     | 1 | 2 |

Теорема 4. Пусть множество G удовлетворяет предположению 1 и RS = G. Тогда при 2 > 1 алгоритм AW() находит решение неравенств (2) за конечное число итераций.

5. Новый алгоритм минимизации с растяжением пространства Сформулируем метод минимизации на основе алгоритма решения неравенств AW().

Алгоритм минимизации (AWM()).

1. Задать начальное приближение H0 = I, x0 Rn, параметр >1.

Вычислить g0 f (x0 ). Если g0=0, то x0 точка минимума, закончить вычисления.

2. Для i =0,1,2, Е, выполнить действия:

2.1. Найти новое приближение минимума:

xi+1 = xi - isi, i = arg min f (xi - si ), si = Higi, 2.2. Найти субградиент ui+1 f (xi+1) такой, что (ui+1, si ) 0.

2.3. Если i не кратно m, то вычислить yi = ui+1 - gi, (Hi yi, gi ) gi+1 = gi + i yi, i = -, (30) (Hi yi, yi ) T Hi yi yi HiT Hi+1 = Hi - (1-1/ 2), (31) ( yi, Hi yi ) в противном случае произвести обновление H0 = I, gi+1 = ui+1.

Докажем эквивалентность последовательностей {xi}, генерируемых алгоритмом AWM() и методом сопряженных градиентов при минимизации квадратичных функций f (x) = (x, Ax) + (b, x) + c, A > 0, x,b Rn.

Метод сопряженых градиентов (SGM) (см., например, [2]) можно записать в следующем виде.

1. Задать начальное приближение x0 Rn. Вычислить g0 = f (x0), положить s0 = g0.

Если g0=0, то x0 точка минимума, закончить вычисления.

2. Для i =0,1,2, Е, выполнить действия:

2.1. Найти новое приближение минимума:

xi+1 = xi - isi, где i = arg min f (xi - si ).

2. Для i =0,1,2, Е, выполнить действия:

2.2. Вычислить градиент gi+1 = f (xi +1).

2.3. Если i не кратно m, то вычислить yi = ui+1 - gi, Электронный журнал ИССЛЕДОВАНО В РОССИИ 2447 (gi+1, gi+1) si +1 = gi+1 + isi, i =, (gi, gi ) в противном случае произвести обновление si +1 = gi+1.

Теорема 5. На квадратичной функции со строго положительно определенной матрицей Гессе алгоритм AWM() при 1 и метод сопряженных градиентов, при равенстве их начальных точек и циклов обновления m n, генерируют одинаковые последовательности приближения минимума {xi} для im.

Доказательство. В работе [15] (см., также в [1]) доказано, что алгоритмы SGM и AWM при одинаковых начальных точках и длинах циклов до обновления генерируют одинаковые последовательности приближений минимума {xi} на гладких функциях. Поэтому для доказательства теоремы нам достаточно доказать идентичность последовательностей {xi}, генерируемых алгоритмами AWM и AWM() на квадратичных функциях.

Последовательности, генерируемые алгоритмом AWM, будем помечать штрихом.

Докажем равенства xi = xi, (32) gi = gi, (33) si = gi = si = Higi. (34) Доказательство проведем по индукции. При i=0 равенства (32)-(34) справедливы по условию теоремы и построению методов. Предположим, что эти равенства выполнены при 0 i k.

Докажем что они выполняются и при i = k + 1.

В силу выполнимости равенств (32), (34) в пунктах 2.1 алгоритмов AWM и AWM() будут получены одинаковые точки нового приближения. Следовательно (32) будет выполнимо при i = k +1.

В силу единственности градиента в точке, ортогональности последовательности градиентов в методе сопряженных градиентов при imn, а следовательно и в AWM, с учетом преобразования матриц (31), получим ui = ui = Hiui (35) при i = k. Отсюда и (34) следует yi = yi = Hi yi (36) при i = k.Учитывая равенства (36), (33), и преобразования алгоритмов (12) и (30) получим выполнимость (33) при i = k +1.

На итерациях алгоритмов AWM и AWM(), в силу способа построения (12) и (30) будут выполняться соотношения (gi+1, yi ) = 0, (gi+1, Hi yi ) = 0, (37) что доказывается непосредственной проверкой.

Из (30) и (31), с учетом (37) и (35), (36) получим Электронный журнал ИССЛЕДОВАНО В РОССИИ 2448 (Hi yi, gi ) ( yi, gi ) Hi+1gi +1 = Higi +1 = Higi - Hi yi = gi +1 = gi - yi = gi+1. (38) (Hi yi, yi ) ( yi, yi ) Здесь первый переход получен на основе (31), (37), второй - на основе (30), третий - на основе (34), (36), четвертый - на основе (30), (36) и последний - на основе (12), (33) и (36).

Таким образом, мы доказали выполнимость (32) - (34) при i = k +1, что доказывает теорему.

6. Заключение В работе для получения направления спуска некоторого релаксационного субградиентного метода используется система неравенств (2). В известном методе Ф. Вульфа и r-алгоритме Н.З. Шора выделяются методы решения неравенств (AW и AR()) и обосновывается их сходимость на формализованном множестве неравенств. Результаты обоснования сходимости методов AW и AR() позволяют построить новый комбинированный алгоритм решения неравенств AW(), в котором сочетаются свойства сходимости обоих методов. На основе полученного алгоритма решения неравенств предложен новый метод сопряженных субградиентов с растяжением пространства. Доказана эквивалентность нового метода и метода сопряженных градиентов на квадратичных функциях.

ИТЕРАТУРА 1. Демьянов В. Ф., Васильев Л.В. Недифференцируемая оптимизация. М.: Наука, 1981.

2. Поляк Б. Т. Введение в оптимизацию. М: Наука, 1983.

3. Wolfe P. Note on a method of conjugate subgradients for minimizing nondifferentiable functions // Math. Programming. 1974. v. 7. N 3.

4. Lemarechal C. An algorithm for minimizing convex functions // Proc. IFIP Congress-74.

Amsterdam: North-Holland. 1974.

5. Lemarechal C. On extension of Davidon methods to nondifferentiable problems // Math.

Programming Studi. Amsterdam:North-Hol-land.1975. №3.

6. Крутиков В.Н Методы минимизации на основе частной модели субградиентных множеств//Методы оптимизации и их приложения/Труды 11-й международной Байкальской школы-семинара. Иркутск.1998.Том 1.

7. Цыпкин Я. З. Основы теории обучающихся систем. М.: Наука, 1981.

8. Крутиков В.Н., Петрова Т.В. Релаксационный метод минимизации с растяжением пространства в направлении субградиента// Экономика и мат. методы. 2003. Т. 39, Вып.

1. С 106-119.

9. Крутиков В.Н. Новый релаксационный субградиентный метод с изменением метрики // Вестник КемГУ. Кемерово, 2001. Вып. 4. С. 16-22.

10. Крутиков В.Н., Петрова Т.В. Новый метод решения задач минимизации большой размерности// Вестник КемГУ. Кемерово, 2001. Вып. 4. С.65-71.

11. Крутиков В.Н., Петрова Т.В. Новый релаксационный метод недифференцируемой минимизации // Мат. заметки ЯГУ. 2001. Т.8, вып. 1. С. 50-60.

12. Шор Н. З., Журбенко Ц. Г. Метод оптимизации, использующий операцию растяжения пространства в направлении разности двух последовательных гpaдиентов // Кибернетика.

1971. № 3.

13. Шор Н. З. Методы минимизации недифференцируемых функций и их приложения. Киев:

Наукова думка, 1979.

14. Скоков В.А. Замечание к методам оптимизации, использующим операцию растяжения Электронный журнал ИССЛЕДОВАНО В РОССИИ 2449 пространства // Кибернктика и системный анализ. 1974. №4.

15. Васильев Л. В. О связи релаксационного метода обобщенного градиента с методом сопряженных градиентов // Численные методы нелинейного программирования / Тезисы 3-го Всесоюзного семинара.Харьков. 1979. ч.1.

Pages:     | 1 | 2 |    Книги по разным темам

."/cgi-bin/footer.php"); ?>