Автоматика и телемеханика, № 4, 2014
© 2014 г. Е.А. НУРМИНСКИЙ, д-р физ.-мат. наук (Институт автоматики и процессов управления ДВО РАН, Владивосток, Дальневосточный федеральный университет, Владивосток), Д. ТЬЕН, д-р философии (Университет Чарльза Стюрта, Батхерст, Австралия)
МЕТОД СОПРЯЖЕННЫХ СУБГРАДИЕНТОВ С ОГРАНИЧЕННОЙ ПАМЯТЬЮ1
Представлен метод решения выпуклых задач недифференцируемой оптимизации, использующий основную идею классического метода сопряженных градиентов и совпадающий с ним в случае квадратичных функций. Основное отличие от ранее рассмотренных аналогов состоит в фиксированном заранее ограничении на объем используемой памяти, не зависящим от требуемой точности получаемого решения. Численные эксперименты показывают практически линейную скорость сходимости этого алгоритма.
1. Введение
В этой работе рассматривается выпуклая задача недифференцируемой оптимизации
(1) min / (ж) = Д,
xeE
где E является конечномерным евклидовым пространством с обычным скалярным произведением ху и соответствующей нормой ||ж|| = л/хх. Предполагается, что задача (1) вполне определена в том смысле, что ее решение существует. Основная цель работы заключается в том, чтобы предложить для таких задач метод типа сопряженных градиентов с фиксированной априори границей на используемую память, доказать его сходимость и представить некоторые обнадеживающие результаты вычислительных экспериментов.
Наиболее общие методы решения задачи (1) используют так называемые субградиентные оракулы, обеспечивающие возможность вычисления в произвольной точке значения целевой функции / (ж) и некоторого субградиента g из субдифференциального множества д/(ж). Простейший из таких методов -субградиентный алгоритм
(2) xk+l = xk - \kgk, gk € д/(xk), k = 0,1,...
который активно исследовался начиная с пионерских работ Шора [1], Поляка [2]. В наиболее общем случае было показано, что (2) сходится к решению (1) при весьма слабых условиях, если шаговые множители Лk удовлетворяют условиям "расходимости ряда": k Лk = о, Лk ^ +0. Однако
1 Работа выполнена при финансовой поддержке Российского фонда фундаментальных исследований (проект №13-07-12010).
3* 67
численные эксперименты и теоретический анализ показали, что это правило выбора шаговых множителей приводит обычно к медленной сходимости. Поэтому практически сразу начался поиск более эффективных алгоритмов, в частности, многочисленные варианты квадратично-линейных алгоритмов, использующих кусочно-линейные модели негладких целевых функций и квадратичные поправки, повышающие, по замыслу, точность этих аппроксимаций [3-5]. Весьма эффективными на практике оказались идеи переменной метрики [6], из последних идей в этой области можно упомянуть сглаживание в комбинации с оптимальными градиентными схемами гладкой оптимизации [7], расщепление на подпространства гладкости-негладкости (так называемые UV-алгоритмы [8]).
Вместе с тем начиная с работ [9, 10] исследовались и аналоги метода сопряженных градиентов [11-13]. Эти исследования развивались в основном в следующих двух направлениях. В первом из них, восходящих к начальным работам Ph.Wolfe [9, 10], алгоритмы использовали накапливаемый пакет субградиентов, полученных на некоторой предыстории текущей итерации. Этот пакет субградиентов использовался для попытки построения направления убывания целевой функции как решения задачи
(3) ||pk||2 = min ||p||2 ,
peco{g°,g1,...,gk}, gi€df (xi), i=0,1,...,k
где x0,x1,...,xk представляет собой историю предыдущих итераций (пробных и рабочих шагов). Здесь для простоты обозначений рассматривается предыстория, начинающаяся с нулевой (начальной) итерации.
Далее в зависимости от различных условий происходит либо рестарт алгоритма, что можно рассматривать как смену начальной точки, либо дальнейшее накопление информации с помощью пробных шагов, либо делается рабочий шаг вида
(4) xk+1 = xk - ЛkPk,
где Лk определяется с помощью точной или приближенной одномерной оптимизации. Проблема с этим подходом заключается в том, что объем накапливаемого пакета субградиентов определяется оценками точности решения, полученного в данном цикле, и при повышении точности неограниченно возрастает. Помимо увеличения затрат памяти и роста объема обрабатываемых данных, с соответствующим достаточно быстрым ростом объем вычислений это приводит и к нежелательным алгоритмическим последствиям: некоторый неудачный пробный шаг может усложнить поиск хорошего направления убывания на протяжении многих последующих итераций.
Второе направление можно рассматривать как приближенное решение задачи (3) с использованием аналогов формулы Полака - Рибьера для построения сопряженных направлений см., например, [11, 12], где использовались постоянные шаговые множители и постоянные весовые коэффициенты. Вычислительные эксперименты, проведенные с этими алгоритмами, показали, однако, прогрессивный рост количества пробных шагов в ситуации, например, отсутствия острого "минимума". Соответственно сходимость алгоритма
при этом сильно замедлялась в терминах временных вычислительных затрат. Для гладких экстремальных задач эти методы тем не менее показали неплохие вычислительные результаты и под названием SR-методов (shortest residuals) активно исследуются и в настоящее время [14-16].
В настоящей работе для решения задач выпуклой недифференцируемой оптимизации производится в некотором смысле объединение этих двух подходов: в предлагаемом варианте метода сопряженных субградиентов сохраняются преимущества метода Ph.Wolfe, заключающиеся в синтетическом использовании субградиентного пакета, а с другой стороны, ограничивается объем вычислительных затрат на обработку этого пакета. Последнее достигается заданным априори ограничением на размер пакета, по достижении которого происходит рестарт алгоритма.
2. Метод сопряженных субградиентов с ограниченной памятью
Рассмотрим метод сопряженных субградиентов с ограниченной памятью как правило построения последовательности хк, k = 0,1,..., сходящейся при определенных условиях к решению задачи (1). Это правило использует пакет субградиентов, накапливаемый и модифицируемый в ходе работы алгоритма. В общем виде этот пакет обозначается через G(z,s,t) и состоит из инициализирующего вектора z и субградиентов дг € df (хг), i = s, s + 1,..., t, вычисленных на итерациях s,s + 1,..., t:
G(z,s,t) = {z,gi € df(xi),i = s,s + 1,...,t}.
Инициализирующий вектор z используется для передачи информации при рестартах алгоритма. Для упрощения обозначений обозначим через Gco(z, s, t) выпуклую оболочку конечного множества G(z,s,t).
Пакет G(z,s,t) состоит не более чем из N + 1 векторов, где N — фиксированный параметр метода. В алгоритме задается также управляющая последовательность величин 5 к — +0, k = 0,1,... , являющихся некоторым эквивалентом точности выполнения условий оптимальности.
Алгоритм строит последовательность итераций, прерываемых моментами рестарта, во время которых происходит очистка пакета G(-, ■, ■) от накопленных субградиентов и изменение инициализирующего вектора. Рестарт алгоритма выполняется при выполнении, по крайней мере, одного условия: либо количество субградиентов в пакете достигает максимального размера N, либо норма кратчайшего вектора в выпуклой оболочке пакета Gco(-, ■, ■) падает ниже текущей оценки выполнения условий оптимальности.
В введенных обозначениях метод имеет следующий вид. Инициализация. Установить начальные значения счетчика рестартов r = 0, счетчика итераций t = 0, определить начальный момент рестарта tr = 0. Задать максимальный размер N пакета субградиентов, последовательность оценок точности {5к} и начальную точку х0. Вычислить g0 € df (х0), координирующий вектор z0 установить равным д0 и положить начальный пакет Go = G(z0,0,0) равным {g0,g0}.
При условии, что проделано t итераций, за которые произведено r рестартов и последний из них произошел в момент tr < t, очередная t+1-я итерация выполняется следующим образом: t + 1-я итерация
Шаг 1. Решить задачу поиска элемента минимальной евклидовой нормы (5) min >Ц2 = 1И2
и если ||pty > ör, то перейти к шагу 2.
Если ||pt| ^ ör то осуществить рестарт алгоритма с увеличением требований к точности выполнения условий оптимальности:
• Увеличить счетчик рестартов r = r + 1 и полностью реинициализиро-вать пакет субградиентов:
(6) tr = t, zr = gt € д/(xt), G(zr,t,t) = {gt};
Повторить шаг 1.
Шаг 2. Решить одномерную задачу
(7) min /(xt - Л^) = /(xt - Л^) = /(xt+1) < /(xt)
Л
и выбрать gt+1 € д/(xt+1) такой, что gt+1 pt = 0. Условие оптимальности для этой задачи гарантирует существование такого gt+1 даже для Лt = 0. При нахождении точки xt+1 методом дихотомии, как предел вложенных интервалов [xt — Л-^, xt — Л+р^, k = 0,1,..., c g^pt = a-k < 0, а g+pt = = a+k > 0, где gk € д/(xt — Л-^), а g+ € д/(xt — Л+р) такой вектор
может быть найден как предел последовательности gk = Ykg- + (1 — Yk)g+,
a+
к = 0,1,... , где Yfc = -г—-- G [0,1] и обращает gk'pt в нуль. По по-
a+k — a k
лунепрерывности сверху субдифференциального отображения д/ вектор gt+1 = limk^^ gk € д/(xt+1), где предел возможно будет необходимо брать по произвольной сходящейся подпоследовательности. Шаг 3. Пополнить множество G(zr ,tr, t) вектором gt+1:
G(zr ,tr ,t + 1) = {G(zr ,tr, t),gt+1},
увеличить значение счетчика итераций t ^ t + 1 и перейти к шагу 4.
Шаг 4. Этот шаг осуществляет рестарт алгоритма при достижении ограничений на объем используемой памяти, без изменений счетчика рестартов и текущей оценки точности решения. Если t — tr ^ N, изменить координирующий вектор zr = pt, переопределить момент последнего рестарта tr = t, инициализировать пакет субградиентов G(zr,tr,t) = {zr,gt}, gt € д/(xt) и перейти к шагу 1.
3. Сходимость алгоритма
Для исследования сходимости алгоритма используем условия сходимости, подробно рассмотренные в [17]. С точки зрения этих условий алгоритм решения оптимизационной задачи представляет собой некое правило для построения последовательности приближенных решений {хк}, которая должна сходиться к некоторому желаемому множеству X*. Само это множество обычно определ
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.