ЭКОНОМИКА И МАТЕМАТИЧЕСКИЕ МЕТОДЫ, 2009, том 45, № 4, с. 105-120
МЕТОДЫ ОПТИМИЗАЦИИ
СЕМЕЙСТВО РЕЛАКСАЦИОННЫХ СУБГРАДИЕНТНЫХ МЕТОДОВ С ДВУХРАНГОВОЙ КОРРЕКЦИЕЙ МАТРИЦ МЕТРИКИ
© 2009 г. В.Н. Крутиков, Т.А. Горская
(Кемерово)
Предложено семейство релаксационных субградиентных методов (РСМ) с двухранговой коррекцией матриц метрики для решения задач негладкой безусловной оптимизации. Доказана сходимость его алгоритмов на строго выпуклых функциях. Приводятся результаты численного исследования одного алгоритма семейства.
1. ВВЕДЕНИЕ
Излагаемое в работе семейство методов минимизации с двухранговой коррекцией матриц метрики (обозначим его Raß) принадлежит классу релаксационных методов s-субградиентного типа (РСМ) (Демьянов, Васильев, 1981) с растяжением пространства (RPCM) (Крутиков, Петрова, 2003; Крутиков, 2003), к числу которых, как доказано в (Крутиков, 2003), относится и r-алгоритм (Шор, 1979). Актуальность исследования и совершенствования подобного рода алгоритмов обусловлена тем, что при относительно невысоких вычислительных затратах на итерации они имеют высокую скорость сходимости и работоспособны в условиях отсутствия выпуклости и гладкости, в силу чего дополняют по области применимости и вычислительной эффективности известные методы минимизации, основанные на квадратичной либо кусочно-линейной моделях функции, в частности квазиньютоновские (Денис, Шнабель, 1988), и алгоритмы, определяемые идеологией метода уровней (Lemarechal, Nemirovskii, Nesterov, 1995; Гольштейн, Немировский, Нестеров, 1995; Бэр, Гольштейн, Соколов, 2000; Гольштейн 2006).
Пусть решается задача минимизации выпуклой на Rn функции fx). В РСМ последовательные приближения строятся по формулам
Xi+1 = Xi - CiSi, Ci = arg min f(xt - cst),
c
где направление спуска Si выбирается как решение неравенств (Демьянов, Васильев, 1981):
(s, g) > 0 6g ! G. (1)
Здесь множество G = дffx) - s-субградиентное множество в точке хг-. Обозначим через S(G) множество решений неравенства (1), df(x) / df0(x) - субградиентное множество в точке х. В РСМ для решения систем неравенств (1) применяют итерационные методы (алгоритмы обучения), где в качестве элементов s-субградиентных множеств, поскольку их явное задание отсутствует, используют субградиенты, вычисляемые на траектории спуска алгоритма минимизации.
Идея построения быстросходящихся алгоритмов обучения для методов класса RrcM состоит в распространении итерационного метода наименьших квадратов (ИМНК) на решение систем неравенств типа (1) на отделимых множествах, близких к плоским множествам (содержащихся в некоторой гиперплоскости) (Крутиков, Петрова, 2003). Подобным образом получены алгоритм с растяжением пространства в направлении субградиента (МРП) (Крутиков, Петрова, 2003) и одноранговое семейство методов с растяжением пространства Ra (Крутиков, 2003). В (Крутиков, Арышев, 2005) предложен алгоритм решения неравенств с растяжением/сжатием пространства на плоских отделимых множествах, не выводимый посредством техники ИМНК.
В настоящей работе дано обоснование сходимости этого алгоритма, сформулировано семейство алгоритмов решения неравенств с двухранговой коррекцией матриц метрики, включающее в себя алгоритмы обучения семейства Ra, обоснованы ограничения на характеристики отделимых мно-
жеств и параметры алгоритмов обучения, обеспечивающие их сходимость. На базе предложенного семейства алгоритмов обучения разработано двухранговое семейство методов минимизации Raз и на строго выпуклых функциях (при соответствующих ограничениях на субградиентные множества) обоснована сходимость его алгоритмов. Приводятся результаты численного тестирования одного варианта алгоритма, сходного по форме с квазиньютоновскими методами.
2. СЕМЕЙСТВО МЕТОДОВ РЕШЕНИЯ НЕРАВЕНСТВ
Обозначим через •% = Ж G) ближайший к началу координат вектор множества G:
PG = р(е)=|| -п(е)||, Пе = Же)/|| е)||, 5* = Пе/ре, Яе = Я(е) = тах|| я||,
я ! е
Rs = Rs(е) = тах(Пе, я), ге = г(е) = Реь(в) = р^Яв.
я ! е
Будем полагать, что относительно множества е выполняется следующее предположение.
Предположение 1. Множество е выпуклое, замкнутое, ограниченное < з) и удовлетворяет условию отделимости, т.е. ре > 0.
Векторы и 5* являются решениями (1). Параметры ре и Rs характеризуют толщину множества е в направлении выражаемую в виде двухстороннего неравенства
Ре < (Не, Я) < Rs 6я ! е. (2)
Из (2) с учетом вида вектора 5* получим
1<(5*, я)< Rs/Ре ! е. (3)
Граничное значение RS/рG в (3) существенно влияет на скорость сходимости рассматриваемых в работе методов решения неравенств. Величина Rs согласно ее определению и (2) удовлетворяет ограничениям
ре < Rs <|| М тах|| я II < RG. (4)
я! е 11 11
Для произвольной симметричной строго положительно определенной матрицы Н размера п х п будем использовать обозначение Н > 0. В предлагаемом алгоритме строятся последовательные приближения решения системы (1) в виде 51 = Нгде - произвольный вектор из е, а матрицы Н1 > О, г = 0, 1, ..., корректируются так, что при определенных ограничениях на характеристики множества е через конечное число итераций будет получено решение системы (1).
Алгоритм решения неравенств А(а, 3).
1. Пусть г = 0. Зададим параметры а, 3, удовлетворяющие условиям
а > 1, 0 < 3 < 1, а3 > 1, (5)
начальную матрицу Н0 = I и выберем ! е.
2. Найдем вектор иг ! е, такой, что
(Ни, я) < 0. (6)
Если такого вектора не существует, то ! S(G) и алгоритм заканчивает свою работу.
3. Вычисляем вектор у г = - иi и ортогональный ему вектор V 1 = Нрг, где
Рг = иг + *= (1 - tг)иг + ^ь = -(Нгуь и;)/(н;уь уд. (7)
Затем получаем новое приближение матрицы метрики:
Н,+1 = Нг -(1- 1/а2)Н;У;уТН\/(у. Ну) -(1- 1/32)НргрГН\/(р, Нр) (8)
4. Выбираем произвольный вектор яг+1 ! е.
Увеличиваем г на 1 и переходим на п. 2 алгоритма.
В работе (Крутиков, 2003) было доказано присутствие в г-алгоритме метода решения неравенств, дано его описание и предложен более общий алгоритм, отличающийся от алгоритма А(а, 3) лишь формулой преобразования матриц (8). Этот метод положен в качестве основы однорангового семейства методов с растяжением пространства Ra. Для уменьшения числа извлечений векторов из
множества (в алгоритме минимизации извлечение означает вычисление субградиента) рассмотрим предложенные в (Крутиков, 2003) способы вычисления вектора gi+1 (п. 4 алгоритма А(а, 3)) с учетом того, чтобы новое приближение si+1 = Hi+1gi+1 удовлетворяло неравенству (Hi+1gi+1, u) > 0 из (1) для последнего извлеченного вектора ui ! G.
1. Выбираем вектор gi+1, как в методе решения неравенств r-алгоритма, полученном в (Крутиков, 2003):
gi+1 = u.. (9)
2. Из оболочки векторов u, gi в текущей метрике выбираем вектор минимальной длины:
gi+1 = Р. (10)
3. Получаем семейство алгоритмов решения неравенств, комбинируя (9) и (10):
gi+1 = Ap+ (1- А) u, 0 < А <1, (11)
где А - задаваемый параметр.
Обозначим через А(а, 3, А) алгоритм A(a, 3) с реализацией его п. 4 по формуле (11). Частные случаи алгоритма с использованием (9) или (10) вместо п. 4 будем обозначать A(a, 3, 0) и A(a, 3, 1), соответственно. Алгоритм А(а, 3, 1) при фиксированных Hi = I, i = 0, 1, ..., реализует алгоритм решения неравенств методом сопряженных субградиентов (Wolfe, 1974). Алгоритм A(a, 3, 0) при 3 = 1 является методом решения неравенств r-алгоритма. Алгоритм А(а, 3, A) при 3 = 1 является алгоритмом обучения однорангового семейства Ra.
Пусть Ai = H-1. Обозначим через Sp A и det A - след и определитель матрицы A, соответственно. Для произвольной матрицы А > 0 будем обозначать через А1/2 матрицу, для которой А1/2 > 0 и А1/2А1/2 = А.
Лемма 1. Пусть Hi > 0, матрица Hi+1 получена в результате (8), где параметры a, 3 удовлетворяют условию (5), а для произвольных векторов у i Ф 0, р i Ф 0 выполняется равенство
gi+1 = Pi. (12)
Тогда H+, > 0 и
Ai+1 = At + (a2 -1) yiyTi +(32-1) PiPi , (13)
Ofr Hiyd (Рь HiPi)
БрА1+1 = БрА1 + (а2 -1) У,) +(32-1) р) , (14)
(Уь И(Уд (Рь ИгРд
аег И1+1 = аег И1 /а2 32, аегА1+1 = а2 32ёег А1. (15)
Доказательство. Равенство (12) позволяет представить (8) в виде двух последовательных преобразований:
И ¡у уТ ИТ
—L, (16) (Уь И1Уд
И1+Р1Р1И1+ (17)
(Рь И1+рд
Действительно, в силу (12) из (16) следует, что И+р 1 = Ир. Используя полученное равенство и подставляя формулу (16) в (17), получим (8).
Дважды применяя к (16) и (17) формулу Шермана-Мориссона, с последующим учетом равенства И1+р1 = Ир1 получим (13). Из (13) следует (14). Для преобразования (16) известна формула преобразования определителя (Шор, 1979): det И+ = det И/а2. Применяя ее дважды для преобразований (16) и (17), получим (15). Из (15) с учетом И 1 > 0 и (5) следует, что И++1 > 0.
В следующей лемме изучаются свойства последовательностей, генерируемых введенными алгоритмами.
Лемма 2. Пусть множество е удовлетворяет предположению 1. Тогда для генерируемых последовательностей при г = 0, 1,... одним из алгоритмов А(а, 3) или А(а, 3, А) выполняются соотношения:
1) значение в (7) доставляет минимум величинам (р,, Нрг) и (р,, Н,+р);
2) 11 Уг | > 0, ! (0,1), р, ! е, я,+1 ! ^ Н1+1 > 0, (Нг+1 рг, и) > 0;
а для последовательностей алгоритма А(а, 3, А) дополнительно выполняется неравенство (Н;+1я;+1, и,) > 0.
Доказательство. Проведем доказательство леммы методом индукции. Пусть на некоторой итерации Н1 > 0, я, ! С. При , = 0 это допущение выполнено для обоих алгоритмов. Покажем выполнимость соотношений леммы для заданного г.
Так как (НiУi, у,) = и) + (Н;Я;, я,) - Н, > ° Щ Я, ! ^ и выполняется неравенство (6),
то (Ну, у,) > 0, что определяет корректность формул (7) и вместе с Н1 > 0 доказывает неравенство
II У, II >0.
Если Нг > 0, то выполняется первое утверждение леммы. Действительно, решая задачу минимизации (р;, Н,+р) по параметру *,, где р1 определен в (7), найдем
„ _ (Н;+1 У» щ;) _ (H;У;, и,) _ (Н1иь иЬ- (Н1иь Я,) п ох --------. (18)
(Н;+1 Уь Уд (H;У;, У;~) (H¡U¡, иг) + (НгЯь - 2(Hl'ui,
В силу справедливости (12), которое устанавливается непосредственной проверкой, из (8) следует равенство Н;+1у; = Ну/а2, которое обосновывает замену Н,+1 ^ Н1 в (18) и доказывает высказан
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.