The subgradient multistep minimization method for nonsmooth high-dimensional problems.pdf 1. Введение Излагаемый в работе многошаговый релаксационный субградиентный метод минимизации (РСМ), основанный на принципах организации методов «сопряженных субградиентов» [1, 2], принадлежит классу релаксационных методов е-субградиентного типа (РСМ) [1, 2] и предназначен для решения задач высокой размерности. Имеющиеся на настоящий момент РСМ с растяжением пространства [4-8] соизмеримы по скорости сходимости на гладких функциях с квазиньютоновскими методами [6, 8] и эффективны при решении негладких задач овражного типа [6, 8]. В силу необходимости хранения и преобразования матрицы их эффективность по затратам времени резко снижается на задачах высокой размерности. Существующие многошаговые РСМ [1, 3] существенно уступают в скорости сходимости субградиентным методам с растяжением пространства, подвержены зацикливанию на овражных задачах негладкой оптимизации, что определяет актуальность их совершенствования. Пусть решается задача минимизации выпуклой на R" функции f (x). В РСМ последовательные приближения строятся по формулам xk+1 = xk - Yksk > Yk = argminf (xk -ysk), yeR где направление спуска sk выбирается как решение неравенств [2]: (s,g) > 0, Vg e G . (1) Здесь множество G = де f (xk) - е-субградиентное множество в точке xk. Обозначим S(G) - множество решений (1), df(x) = df0(x) - субградиентное множество в точке х. В РСМ для решения систем неравенств (1) применяют итерационные методы (алгоритмы обучения), где в качестве элементов е-субградиентных множеств, поскольку их явное задание отсутствует, используют субградиенты, вычисляемые на траектории спуска алгоритма минимизации. В работах [3, 5-8] предложен и используется следующий подход сведения системы (1) к системе равенств. Пусть G с Rn принадлежит некоторой гиперплоскости, а его ближайший к началу координат вектор n(G) является также и ближайшим к началу координат вектором гиперплоскости. Тогда решение системы (s, g) = 1, Vg е G , является также решением и для (1). Его можно найти как решение системы [5-8] (s,gt) = y, i = 0,1,...,к, y = 1. (2) В [3] (см. также [7, 8]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [9] (см. также [10]) Sk+1 = Sk + gk. (3) (gk, gk) Такой алгоритм минимизации при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов и эффективен при решении задач негладкой оптимизации [3, 7, 8]. В случае ортогональности векторов gk метод (3) конечен [7, 8]. Алгоритм решения системы равенств с последовательной ортогонализацией векторов gk предложен в [11]. В настоящей работе этот алгоритм распространен на решение неравенств и используется для поиска направления спуска в методе минимизации. Основной целью построения направления sk в субградиентных методах является поиск такого направления, которое обеспечивало бы возможность уменьшения функции из любой точки некоторой окрестности текущего приближения, т.е. решение системы неравенств (1), где множество G составлено из субградиентов окрестности текущего приближения xk. Это означает возможность выхода из этой окрестности посредством минимизации функции вдоль этого направления. Чем шире окрестность, тем выше устойчивость метода к ошибкам округления, помехам, наличию малых локальных экстремумов и большее продвижение в направлении к экстремуму. В этой связи особую важность приобретают изучаемые в работе методы минимизации, в которых, в отличие от метода из [1] и его модификации из [2], встроенные алгоритмы решения систем неравенств используют субградиенты достаточно широкой окрестности текущего приближения минимума и не требуют точного одномерного спуска. 2. Многошаговый метод решения неравенств В предлагаемом алгоритме строятся последовательные приближения решения системы (1). Алгоритм А1. 1. Положить k = 0, pk_ = 0 (pk _ е Rn). Задать начальное приближение S0 е Rn. 2. Выбрать произвольно gk е G , удовлетворяющий условию (sk,gk) < 0 , если такого вектора не существует, то sk е S(G), закончить работу алгоритма. 3. Получить новое приближение Sk+\. sk+1 = Sk + ^Щ) Pk, (4) {Pk,gk) gk, если (gk, Pk_1) ^ 0, (a) gk ,P]Pk_1, если (gk,Pk_1) 1. Обозначим z5 = x - P5s , ri ед/ ( z5 ), i = 0,1,2,..., l - номер i, при котором впервые выполнится соотношение (г5 , s) < 0 . Зададим параметры отрезка локализации [у0, у1 ] одномерного минимума: у0 = pl-1, f0 = f (zl-1), g0 = rl-1, у1 = Pl, f = f (zl), g1 = rl и найдем точку минимума у* одномерной кубической аппроксимации функции на отрезке локализации. Вычислим qyYl, если l = 1 и у* < qylYl, , У1 , если У1 -у*^у(У1 -0Х у m =1 * (32) у0, если 1 >1 и у -у0 < qy(у1 -уo), * у , в остальных случаях. Вычислим начальный шаг спуска для следующей итерации: h = qm hуm )1/2. (33) Алгоритм минимизации. В предлагаемом ниже варианте реализации алгоритма М1 обновление для метода решения неравенств не производится, а точный одномерный спуск заменен на приближенный. Алгоритм. 1. Задать начальное приближение x0 е R", начальный шаг одномерного спуска h0 . Положить: i = 0, g0 = g0 е df (x0), g^ = 0, p.- = 0, f = f (x0), s0 = s0 = 0 . Задать параметры останова: N - максимально допустимое число итераций, еx - точность минимизации по аргументу, е - точность минимизации по градиенту. 2. Получить приближение si+1 = s5 +--( 5') p5. (Pi, g-) gr, если (, Pi-1) > 0, & , -) Pi-1, если (g., p.-1) < 0. pi-1 2 где pi = Здесь осуществляется шаг метода решения неравенств. 3. Получить направление спуска ^ если (si+1,gi) >1 +1 + gi(1 - (si+1, gi)) l(gi, gix если (si+1, gi) < !. 4. Произвести одномерный спуск вдоль wi+1 = si+1(si+1, si+1)-112 : OM({xi, w+1, gt, fi, hi}; {Yi+1, f+1, gi+1, Yi+1, gi+1, hi+1}). Вычислить приближение точки минимума xt+1 = xt - yv+1wi+1. 5. Если i > N или ||xi+1 - xj 1, условие (s+1, gi) > 0 выполнено и, согласно результатам работ [5, 7, 8], нет теоретических рекомендаций по улучшению решения системы неравенств. Поэтому преобразование коррекции не производится. Хотя обоснование сходимости идеализированных версий РСМ [2-8] производится при условии точного одномерного спуска, реализации этих алгоритмов осуществляется c процедурами одномерной минимизации, в которых начальный шаг, в зависимости от прогресса, может увеличиваться или уменьшаться, что определяется заданными коэффициентами qM > 1 и qm < 1. При этом минимальный шаг на итерации не может быть меньше некоторой доли начального шага, величина которой задана в (32) параметрами qY1 = 0,1 и qY = 0,2, приведенные значения которых использовались нами при расчетах. 5. Численный эксперимент Алгоритм М1 реализован согласно технике реализации алгоритма М0 [5-8], в которой ключевое значение играют коэффициенты уменьшения qm < 1 и увеличения qM > 1 начального шага одномерного спуска на итерации. Значения qm близкие к 1 обеспечивают малую скорость убывания шага и соответственно малую скорость сходимости метода. При этом малая скорость убывания шага устраняет зацикливание метода в силу того, что субградиенты функции, участвующие в решении неравенств берутся из более широкой окрестности. Выбор параметра qm должен соизмерятся с возможной скоростью сходимости метода минимизации. Чем выше скоростные возможности алгоритма, тем меньшим может быть выбран этот параметр. Например, в РСМ с растяжением пространства [4-8] выбирается qm = 0,8. Для гладких функций выбор этого параметра некритичен и его можно брать из интервала [0,8-0,98]. От параметра возрастания шага скорость сходимости практически не зависит, поэтому его можно взять постоянным qM = 1,5 . (34) Исследование проводилось на следующих функциях. 1. /1(х) = xk | -k,x* = (0,0,...,0),Х0 = (10,10,10,...,-); k=1 23 n 2. f2(x) = £xk2 • k2,x* = (0,0,...,0),X0 = (10,10,10,...,10); k=1 23 n 3. /з(x) = 11 [1000(xk - xk+1)2 + (1 - x^)2], x* = (1,..,1),x0 = (0,..,0). k=1 Функция fs(x) взята из [12]. В таблице приведено количество затраченных методом вычислений функции и субградиента, которое соответствует моменту выполнения условия fk - f *

Скачать электронную версию публикации