Субградиентный метод минимизации с коррекцией векторов спуска на основе пар обучающих соотношений

УДК 519.6

СУБГРАДИЕНТНЫЙ МЕТОД МИНИМИЗАЦИИ С КОРРЕКЦИЕЙ ВЕКТОРОВ СПУСКА НА ОСНОВЕ ПАР ОБУЧАЮЩИХ СООТНОШЕНИЙ

В. Н. Крутиков, Я. Н. Вершинин

SUBGRADIENT MINIMIZATION METHOD WITH DESCENT VECTORS CORRECTION BY MEANS OF TRAINING RELATIONS PAIRS V. N. Krutikov, Ya. N. Vershinin

Предложен релаксационный метод сопряженных субградиентов, направление спуска которого корректируется на основе пары текущих обучающих соотношений. Доказана сходимость метода на строго выпуклых функциях. Как показывает численный эксперимент, метод эффективен в задачах минимизации негладких функций высокой размерности. По затратам памяти на хранение информации алгоритм сходен с методом сопряженных градиентов. На гладких функциях большой размерности с высокой степенью вытянутости поверхностей уровня он соизмерим с последним в скорости сходимости.

The paper introduces a conjugate subgradient method whose descent is corrected by a pair of current training relations. The convergence of the method is proved on strictly convex functions. According to the numerical experiment, the method is effective at non-smooth high-dimensional minimization problems. By memory cost, theproposed method is similar to the conjugate gradient method, and at smooth high-dimensional singular functions its convergence rate is not inferior to tha of the conjugate gradient method.

Введение

В связи с ростом приложений методов оптимизации в технике, экономике, управлении потребность в методах решения гладких и негладких задач минимизации большой размерности постоянно растет. Как отмечено в [1], метод сопряженных градиентов (МСГ) (см., например [1; 2]) является единственным универсальным средством решения подобных гладких задач. В работах [3 - 7] развит подход построения релаксационных субградиентных методов минимизации (РСМ) [8; 9] е-субградиентного типа [9] для решения негладких задач, обладающих при определенных условиях свойствами МСГ [3; 6; 7]. В методах этого типа, в отличие от МСГ, заложено улучшение локальных свойств сходимости в виде цели алгоритма обучения для формирования направления спуска [3 -7]. Имеющиеся на настоящий момент РСМ с растяжением пространства [4 - 7; 10], основываются на взвешенной обучающей информации, собранной на всей траектории минимизации. Они соизмеримы по скорости сходимости на гладких функциях с ква-зиньютоновскими методами и эффективны при решении негладких задач овражного типа [4 - 7; 10]. В силу необходимости хранения и преобразования матриц их эффективность по затратам времени счета резко снижается на задачах высокой размерности.

Существующие многошаговые РСМ [3; 6 - 9], не имеющие в своем составе матриц, используют незначительный объем памяти, необходимой для хранения, имеют незначительные вычислительные затраты на обслуживание итерации метода, что позволяет использовать их при решении большеразмерных задач, но при этом они существенно уступают в скорости сходимости субградиентным методам с растяжением пространства и подвержены зацикливанию на овражных задачах негладкой оптимизации, что определяет

актуальность их совершенствования на базе повышения объема используемой обучающей информации. Предлагаемый в работе РСМ, в отличие от метода из

[3], для цели повышения эффективности алгоритма обучения, основан на использовании дополнительных обучающих соотношений на итерации. Отмеченное нововведение, сравнительно с методом из [3], обеспечивает более широкий диапазон решаемых задач негладкой оптимизации и более высокую скорость сходимости при решении гладких и негладких задач минимизации.

Пусть решается задача минимизации выпуклой на Я" функции /(х) . В РСМ последовательные приближения строятся по формулам:

Х+1 = X - У-Э, У, = агБ тт/(х - уэ,),

где направление спуска Э, выбирается как решение системы неравенств [9]:

(э, g) > 0, Vg е О . (1)

Здесь множество О = д е/ (X,) - е-субградиентное множество в точке X,. Обозначим

В работах [3 - 7] предложен и используется следующий подход сведения системы (1) к системе равенств. Пусть G с Я" принадлежит некоторой гиперплоскости, а его ближайший к началу координат вектор т/(0&) является также и ближайшим к началу координат вектором гиперплоскости. Тогда решение системы (я, g) = 1, Vg е G является также решением и для (1). Его можно найти как решение системы [4 - 7]

(s, gг ) = У,, г = k, у, = 1. (2)

В [3] (см. также [6; 7]) предложен метод минимизации, в котором для решения системы (2) используется алгоритм Качмажа [11] (см. также [12]):

Як+1 = Як +-я,

(gk, gk)

Метод (3) дает приближение як+1, удовлетворяющее уравнению (я, gk) = 1, т. е. последнему поступившему обучающему соотношению из (2). Алгоритм решения задач негладкой оптимизации на основе (3) при точном одномерном спуске на дифференцируемых функциях обладает свойствами метода сопряженных градиентов [3; 6; 7].

В случае ортогональности векторов gi в (2) метод

(3) на последовательности уравнений из (2) сходится не более чем за п итераций [6 - 7]. Можно построить метод решения системы уравнений (2) на последовательной ортогонализации векторов gj. В методах оптимизации, в силу несовместности систем равенств, возможной линейной зависимости векторов gi, значительных вычислительных затрат на ортогонализацию и необходимости хранения системы векторов, прямые методы полной ор-тогонализации для решения системы (2) неприемлемы. При определенных ограничениях на ошибки в (2) алгоритмы решения системы равенств с последовательной

ортогонализацией векторов gk предложены в [13]. В

настоящей работе для решения системы неравенств (1) используется схема коррекции направления спуска на основе точного решения двух последних равенств из (2) для пары индексов k — 1, k , что реализуется посредством использования на каждой итерации ортогонализа-ции пары векторов gk, gk—1 с последующим применением (3).

(gk, gk—1)

Основной целью построения направления Як в релаксационных субградиентных методах является поиск такого направления, которое обеспечивало бы возможность уменьшения функции из любой точки некоторой окрестности текущего приближения, т. е. решение системы неравенств (1), где множество О составлено из субградиентов окрестности текущего приближения Хк .

Это означает возможность выхода из этой окрестности посредством минимизации функции вдоль этого направления. Чем шире окрестность, тем больше продвижение в направлении к экстремуму, выше устойчивость метода к ошибкам округления, помехам и способность преодоления малых локальных экстремумов. В этой связи особую важность приобретают изучаемые в работе методы минимизации, в которых, в отличие от метода из [8] и его модификации [9], встроенные алгоритмы решения систем неравенств допускают использование субградиентов достаточно широкой окрестности текущего приближения минимума и не требуют точного одномерного спуска.

В излагаемом ниже алгоритме строятся последовательные приближения решения системы неравенств (1) посредством коррекции текущего приближения, обеспечивающей точное решение двух последних равенств типа (2), что реализовано с использованием последовательной ортогонализации пар векторов, предложенной в [13] для решения систем равенств.

Алгоритм А1.

не существует, то Як є S(О), закончить работу алгоритма.

к + 1

если (Як , Як_1) > ° (а)

если (Як , Як_ 1) < °- (Ь)

Алгоритм А1 отличается от алгоритма решения неравенств на основе алгоритма Качмажа (обозначим его А0) [3; 6; 7] реализацией пункта 3. В А0 вместо

(4), (5) используется формула (3).

Согласно (4), (5) равенство , gk ) = 1 выполняется всегда, а равенство (sk+1, gk—1) = 1 сохраняется в случае преобразования (5 Ь), что соответствует точному решению двух последних равенств из (2). В

случае преобразования (5 Ь) производится ортогонализация векторов gk, gk—1, что отражено в равенстве

(6 а). Непосредственно из (5) следует соотношения (6 Ь). Из (5), с учетом (6 а), получим (6 с):

а)(Л,gk—:) = 0 , если ^,gk—:)< 0 ;

Ь)( Рк, gk) ^ (gk, gk); c)(Рk,Рk ) = (Рk, gk). (6)

Обозначим Т]а = 7](С) - ближайший к началу координат вектор множества G ,

Ро =р(0) =\\\\л(0)\\\\, ца =Г/(0)1\\\\Г1(0)\\\\,

я* = Мо / Ро , Яо = Я(о) = тах \\\\ g \\\\.

Сделаем предположение относительно множества Предположение 1. Множество в не пустое, выЯо < да

пуклое, замкнутое, ограниченное

и удовлеРо > 0

творяет условию отделимости, то есть

При этих условиях векторы МО и я являются решениями (1), а для векторов g е О выполняются ограничения [4 - 7]

Мы изучим сходимость алгоритм А1 к решению ** я . Обозначим Дк = як — я - вектор невязки. Следующие результаты относительно алгоритма А1 получены в условиях справедливости предположения 1.

Лемма 1. Пусть последовательность *■ к* получена в результате работы алгоритмом А1. Тогда, для

k = 0,1,2,... имеют место оценки:

(Д k+l, Рк ) < 0, (8)

(Д k, Рk ) < (Д k, gk ). (9)

Доказательство проведем по индукции. В силу равенства Рк = gk при k = 0 выполнено (9). Учитывая левое из неравенств (7) и условие пункта 2

(А, gk ) < 0 получим:

—(Дк, gk) = (s*, gk) — (як, gk) >1 — (як, gk) >1 (10)

Вычтем из обеих частей (4) я , умножим обе части равенства скалярно на Рк и преобразуем правую часть с учетом (6 с), (9) и (10):

(Д+1. Рк)=(Дк, р„ )+(Рк, Р„) <

(Рк, ёк)

< (д. , р, )—(Рк, и,-) < <>.

(Дк, Рк)=(Дк, ёк)—, ёк—1> < (Дк, gk )■

(gk—ъ gk—1)

Из (9) и (11) следует (8) при к = I. Лемма доказана.

В следующей теореме утверждается, что преобразование (5 Ь) дает направление рк на точку решения

я с более острым углом по сравнению с gk .

Теорема 1. Пусть последовательность *■ к ’ получена в результате работы алгоритма А1. Тогда, для к = 0,1,2,...

имеет место оценка:

(—Д ,, Рк ) > (—Д к, 8, ) >

(Рк, Рк)05 (ёк, 8,Г

Доказательство. Из (9) и (10) следует

(—Д к, Рк ) > (—Д к, gk ) > 1.

Отсюда, с учетом (6 Ь), (6 с), (9), (10) и определе(13)

ния величины

имеем:

(—Д к, Рк ) > (—Д к, Рк ) > (—Д к, 8, ) >,

( ёк , ёк )05

( ёк , ёк )05 Я

Ср, , ёк)

Здесь мы предположили, что последний переход в цепочке неравенств произведен при условии (9) для текущего к . Поскольку неравенство (9) выполняется при к = 0, то справедливо (11), откуда следует (8) при к = 0 .

Предположим, что неравенства (8), (9) выполнены при к = 0,1,...,I — 1, где I > 1. Покажем, что они выполняются при к = I. В случае (5 а) выполнено (9). Для доказательства (9) в случае (5 Ь) умножим скалярно на Д, обе части равенства (5 Ь). Отсюда, в силу справедливости (8) при к = I — 1 и условия (И,, И,—1) < 0 из (5 Ь), получим обоснование (9) при

(Рк, Рк )

Теорема доказана.

Для обоснования сходимости алгоритма А1 нам потребуется следующий результат.

Лемма 2 [4, 6, 7]. Пусть множество о удовле1Т як е 5 (о)

творяет предположению 1. Тогда к , если

\\\\ Д, \\\\< 1/Яо . (14)

В следующей теореме обосновывается конечная сходимость алгоритма А1. Отметим, что полученные оценки полностью эквивалентны оценкам для алгоритма А0.

Теорема 2. Пусть множество о удовлетворяет предположению 1. Тогда для оценки скорости сходи{як} /

мости последовательности к ’ к точке 15 , генерируемой алгоритмом А1 до момента останова, справедливо соотношение:

К — я*\\\\2< (\\\\ ^0 \\\\ +Ро 1)2 — к/до, (15)

для оценки величины Ро имеет место оценка

Ро 1 > (X8,ё!ГУ5 — \\\\ *0 \\>—— \\ \\ *0 \\\\, (16)

а при некотором значении к, удовлетворяющем неравенству

к < к*= ЯоОКУ+Ро-1)2 +1, (17)

будет получен вектор як е 5 (о) .

Доказательство. Найдем невязку Д к+1 вычита*

нием я из обеих частей (4) и получим выражение квадрата ее нормы. Правую часть полученного выражения преобразуем с учетом неравенств (6 Ь), (6 с), (9), (10) и определения величины Яо:

(Ак+1, Ак+l) “ (Ак, Ак ) + 2(Ак, Рк )

+ (Рк, Рк )

(1 - (*к, gk))2 (Рк, gk )2

< (Ак, Ак ) - 2

(1 - (sk, gk ))2 , (1 - (sk, gk ))2

(Рк, gk )

- + (Рк, gk )

< (А к, А к) 1

ik, Ак) t ч < (Ак, Ак) п2 &

(gk, gk ) Rg

Отсюда, используя неравенство

\\К — я*II2<(\\К\\\\ + \\\\/\\\\)2 = (\\\\я0 II +роЛ)2,

которое следует из свойств нормы, получим оценки

(15) и (16).

Согласно оценке (15) величина \\\\ Дк \\\\^ 0. Поэтому на некотором шаге к для вектора як будет выполнено неравенство (14), т. е. будет получен вектор як е 5(о) , являющийся решением системы (1). В качестве верхней оценки необходимого числа шагов можно взять к *, равное значению к, при котором правая часть (15) обращается в нуль, увеличенному на 1. Это дает оценку (17). Теорема доказана.

й(х) = Р(д/(х)) в(2) = {х е Я"\\/(х) < I(2)}.

Примечание 1. Для выпуклой на Яп функции, при

Б( х0)

ограниченности множества 0

х* е В(х0)

справедлива оценка[9, с. 291],

f (х*) - f *< Dd0

для точек

d (х ) < d0

где D - диаметр множества D(х0), f * = inf f (х).

Дадим описание метода минимизации на основе алгоритма А1 для нахождения точек х* е Rn, таких, что d (х*) < Е0, где Е0 > 0&

Алгоритм М1.

gi-1 = ^ = 0&

закончить работу алгоритма.

si+1 = si +

(Рг , gj )

Рj , где

gj, если (gj, gj -1) ^ 0

gj - (j, gj-21 ) )j-1, если (gj, gj-1) < 0

Ilgj -11

Е,+1 =Х, + (ё,, ё,)—1.

Х+1 = X - УДYj = argmin f (х - jjSj+Д

иначе прейти на пункт 4.

Алгоритм М1 отличается от известного метода минимизации [3; 6; 7], основанного на алгоритме решения неравенств А0 с формулой Качмажа (3) (назовем его М0), реализацией пункта 5, где вместо формул (4), (5) используется преобразование (3). В алгоритм М1 в пунктах 2,4,5 встроен алгоритм решения неравенств. Индекс qk, к = 0>1>2> .. введен с целью обозначения номеров итераций г, при которых в пункте 2 при выполнении критериев пунктов 9, 10 происходит обновление для алгоритма решения неравенств (рг-1 = 0). Согласно (15), (17) алгоритм решения неравенств при я0 = 0 имеет наилучшие оценки скорости сходимости. Поэтому при обновлении в пункте 2 алгоритма М1 задаем я, = 0. Потребность в обновлении возникает вследствие того, что в результате смещения в пункте 7 происходит смена субградиентных множеств окрестности текущей точки достигнутого минимума, что приводит к необходимости решения системы неравенств на основе новой информации.

Отметим, что в силу условия точного одномерного спуска вдоль направления (— я,+1) в пункте 7, в новой точке хг+1 вектор £1+1едДхг+1), такой, что (ёг+1,яг+1) < 0, всегда существует согласно необходимому условию минимума одномерной функции (см., например, [9, с. 287]). Следовательно, с учетом роста индекса г в пункте 8, условие (ё,,яг) < 0 пункта 4 всегда удовлетворяется.

Доказательство сходимости метода М1 опирается на следующую лемму.

Лемма 3 [9]. Пусть функция I (х) строго выпукла на Яп, множество П( х0) ограничено, а последовательность

{Хк }Г=0

такова, что

f (Хк+1) = min f (хк + «СХк+1 - хк)) •

ае[0,1]

Тогда lim || Хк+1 - Хк ||= 0 •

Обозначим Ss (G) = {z е Rn | ||z - х||< s, Vx e G} - s -окрестность множества G,

U5(x) = {z e Rn 11| z - х ||< 5} - 5 - окрестность точкИ х, zk = xqt , Qk = 1 qt , k = 1,2,&&&, т. е

точки Xi и значения показателя

Теорема З. Пусть функция D( х0)

є = (d * — d0)I2.

Согласно предположению (21), условиям выбора 8 (22), 5 (23) и к (24) при к > K будет выпол(2З)

, соответствующие

индексам г на момент обновления в пункте 2 алгоритма М1.

строго выпукла

на Rn, множество & 0/ ограничено и параметры 8k, mk, задаваемые в пункте 2 алгоритма М1, фиксированы:

Тогда, если х предельная точка последовательности {xqk }кк=1, генерируемой алгоритмом М1, то

d (х*) < max{E°, R(x°)/^M°} = d0, (20)

R(x0) = max max || v || где xeD( X°) veCf (х) . В частности, если

M0 > R2(x0)E(-2 , то d(x*) < E0.

Доказательство. Существование предельных точек последовательности {zk } следует из ограниченности множества D(х°) и zk е D(х°). Допустим, что утверждение теоремы неверно: предположим, что

подпоследовательность zk ^ X , но

d (х*) = d *> d° > 0. (21)

Положим:

Обозначим 5*£ = 58(д/(х*)). Выберем 5 > 0, такое, что

д/ (х) с 5* Vx е 5,( х*). (23)

Такой выбор возможен в силу полунепрерывности сверху точечно-множественного отображения д/(х) (см. [9, с. 289]).

Выберем номер К, такой, что при кя > К будет справедливо:

\\ е 552(х*),

хе 5Ж). qks <г < qк +М0, (24)

т. е. такой номер К , что точки хг остаются в окрестности 55 (х*) в течение, по крайней мере, М 0 шагов алгоритма. Такой выбор возможен в силу сходимости 2, ^ х и результата леммы 3, условия

которой выполняются при условиях теоремы 3 и наличии точного одномерного спуска в пункте 7 алгоритма М1.

няться неравенство:

Р( 58) >Р(д/ (х*)) —

—8 = й * — (й *— й0)/2 > й0.

При кя > К, в силу справедливости соотношений (24), из (23) следует:

е 58, qк <г < qк + М0.

Алгоритм М1 содержит в своем составе алгоритм А1. Поэтому, с учетом оценок из (16), в зависимости от того, в каком из пунктов алгоритма М1 (9 или 10) произойдет обновление при некотором г =}, будет выполнено одно из неравенств:

Р(58) <1—0 5 <8, < Е0 < й0, (26)

Р(58) < Я(х0)/у1тк < Я(х0)/л/М0 < й0, (27)

где последний переход в неравенствах вытекает из определения величины й0 в (20). Но (25) противоречит как (26), так и (27). Полученное противоречие доказывает теорему.

Согласно оценке (20), для любой предельной точки последовательности {гк} , генерируемой алгоритмом М1, будет выполнено й(х*) < й0, а следовательно, будет справедлива оценка (18).

В следующей теореме определяются условия, при которых алгоритм М1 генерирует последовательность

{хг} , сходящуюся к точке минимума. г , сходящуюся к точке минимума.

Теорема 4. Пусть функция •& у & строго выпукла, Б( х0)

множество 0 ограничено и

е, ^0 тк . (28) Тогда любая предельная точка последовательноК}

генерируемая алгоритмом М1, является

точкой минимума функции / ( х) на Яп.

Доказательство. Допустим, что утверждение теоремы неверно: предположим, что подпоследова*

тельность 2, ^ х , но при этом найдется такое

й0 > 0 , что будет выполняться неравенство (21). Как

и ранее зададим е согласно (22). Выберем 5 > 0 такое, что будет выполнено (23).

В силу условий (28), найдется такое К0 , что при

к>К0 будет выполняться соотношение:

max{8k. ЯЫ/л[щ } < й0 . (29)

Обозначим Е0 = й0 и М0 - наименьшее значение тк при к > К0. Дальнейшие рассуждения аналогичны доказательствам теоремы 3.

Выберем номер К > К0, такой, что при кя > К

будет справедливо (24), т. е. такой номер К , что точки х г остаются в окрестности 55 (х*) в течение, по крайней мере, М0 шагов алгоритма. Согласно предположению (21), условиям выбора е (22), 8 (23) и к (24) при кя > К будет выполняться неравенство (25).

При кя > К , в силу справедливости соотношений

(24), из (23) следует: е 5е\\ qK < . < qK + М0.

Алгоритм М1 содержит в своем составе алгоритм А1. Поэтому, с учетом оценок из (16), в зависимости от того, в каком из пунктов алгоритма М1 (9 или 10) произойдет обновление при некотором г =}, будет выполнено одно из неравенств (26), (27), где последний переход в неравенствах следует из определения величин Е0 и М 0 . Но (25) противоречит как (26),

так и (27). Полученное противоречие доказывает теорему.

Алгоритм М1 реализован согласно технике реализации РСМ [3; 6; 7]. Рассмотрим версию алгоритма М1, включающую в себя процедуру одномерной минимизации вдоль направления 8, функции которой заключаются в построении: а) текущего приближения минимума хт; б) точки у из окрестности хт, такой, что

для ед/ (у) выполняется неравенство

(я, ё1) < 0. Субградиент ё1 используется для решения системы неравенств.

Обращение к процедуре обозначим:

Блок входных параметров состоит из точки текущего приближения минимума х , направления спуска

я , ё х е д / (х) , /х = /(х) , начального шага к0. Предполагается, что выполняется необходимое условие возможности спуска (ёх, я) > 0 в направлении я .

Блок выходных параметров включает в себя ут -шаг в точку полученного приближения минимума х+= х — У тя , /т = /(х+ ), т е д/(х + ), Ух шаг вдоль я , такой, что в точке у + = х — у1я для ё1 е д/(у + ) выполняется неравенство (ё1, я) < 0, и

И1 - начальный шаг спуска для следующей итерации. В излагаемом ниже алгоритме векторы ё1 е д/ (у + ) используются для решения множества неравенств, а точки х+ = х — утя как точки приближений минимума.

Алгоритм одномерного спуска (ОМ). Пусть требуется найти приближение минимума одномерной функции ф(в) = /(х — в я), где х - некоторая точка, я - направление спуска. Возьмем возрастающую последовательность в0 = 0 и вг = 1 при г > 1.

Обозначим = х — в, гг е д/(), г = 0,1,2,..., I -номер г , при котором впервые выполнится соотношение (г, я) < 0. Зададим параметры отрезка локализации [у0, у1 ] одномерного минимума: у0 = в/—1, /0 = / (2-1), 0 = ГУ1 = в I , /1 = / (2 ),

чу * КУ

ё1 = Г и наидем точку минимума у одномерной

кубической аппроксимации функции на отрезке локализации. Вычислим:

дг/1, если I = 1 и у* < д^,

/1, если у — у* < qу (у1 — у0), (30)

У0, если I > 1 и у* — /0 < qу(Уl — у,),

у , в остальных случаях.

Вычислим начальный шаг спуска для следующей итерации:

Й1 = qm (\\Ут) . (31)

Алгоритм минимизации. В предлагаемом ниже варианте реализации алгоритма М1 обновление для метода решения неравенств не производится, а точный одномерный спуск заменен на приближенный. Алгоритм

г ^ 0 = ~0 ед/(x0), г—1 = ^ /0 = /(x0),

я0 = я0 = 0 . Задать параметры останова: N - максимально допустимое число итераций, е х - точность минимизации по аргументу, е - точность минимизации по градиенту.

я +1 = $ +где Рг =

г, gг-1) II2

если (~,, > 0

^ если (~,£._1)< 0.

Здесь осуществляются шаг метода решения неравенств.

если (+^ и. >1

я+1 + И,(1 — (я,+1, И,)) /(, И,X если (я,+1, ) <1

/ 4—1/2

Щ+1 = я+1(я-+^ я+1) :

/,^ ,+1,у^ к+1}).

Вычислить приближение точки минимума

х+1 = х — У,+1Щ,+1.

II .11 <

е , то закончить вычисления, иначе положить г = г +1 и перейти на пункт 2.

Поясним действия алгоритма. Из 0М поступают два субградиента г+1 и ,+1 . Первый из них используется для решения неравенств в пункте 2, а второй -в пункте 3, для коррекции направления спуска с помощью формулы (3) с целью обеспечения необходимого условия (я,+1, ё г) > 0 возможности спуска в направлении (— я,+1). Как показано в [3; 4; 6;7] итерация (3) в (32) при (я,+1, ё,) < 1 не ухудшает текущее приближения я решения системы неравенств, поэтому это преобразование проводится. В пункте 3, когда (~+1, ё, ) > 1, условие (~+1, ё ,) > 0 выполнено и, согласно результатам работ [3; 4; 6; 7], нет теоретических рекомендаций по улучшению решения системы неравенств. Поэтому преобразование коррекции не производится.

Хотя обоснование сходимости идеализированных версий РСМ [3 - 10] производится при условии точного одномерного спуска, реализации этих алгоритмов осуществляется с процедурами одномерной минимизации, в которых начальный шаг, в зависимости от прогресса, может увеличиваться или уменьшаться, что определяется заданными коэффициентами

qм > 1 и Чт < 1.

При этом минимальный шаг на итерации не может быть меньше некоторой доли начального шага, величина которой задана в (30) параметрами ду1 = 0.1

и ду = 0.2, приведенные значения которых использовались нами при расчетах.

Алгоритм М1 реализован согласно технике реализации алгоритма М0 [3; 6; 7], в которой ключевое значение играют коэффициенты уменьшения чт < 1 и

увеличения чм > 1 начального шага одномерного спуска на итерации. Значения дт близкие к 1 обеспечивают малую скорость убывания шага и, соответственно, малую скорость сходимости метода. При этом малая скорость убывания шага устраняет зацикливание метода в силу того, что субградиенты функции, участвующие в решении неравенств берутся из более широкой окрестности. Выбор параметра дт должен соизмерятся с возможной скоростью сходимости метода минимизации. Чем выше скоростные возможности алгоритма, тем меньшим может быть выбран этот

параметр. Например, в РСМ с растяжением пространства [4 - 7, 10] выбирается дт = 0.8. Для гладких функций выбор этого параметра некритичен и его можно брать из интервала [0.8 - 0.98]. От параметра возрастания шага скорость сходимости практически не зависит, поэтому его можно взять постоянным

дМ = 15 .

Проведенное тестирование алгоритма М1 на известных негладких и невыпуклых малоразмерных функциях свидетельствует о его работоспособности и достижении задаваемой точности. Например, тестирование на негладких функциях малой размерности из [14], показало что алгоритмы М0 и М1 при п = 50 практически не уступают в скорости сходимости известному методу с растяжением пространства в направлении разности субградиентов [10]. Основная задача приводимого здесь эксперимента состоит в изучении закономерности поведения метода на большеразмерных функциях и его сравнении с МСГ на квадратичных функциях, где последний является конечным.

В таблицах приведены результаты для квазинью-тоновского метода с формулой БРв8 (КНМ) [1], метода сопряженных градиентов (МСГ) [1, 2], алгоритма с растяжением пространства в направлении разности субградиентов (МШ) [10] и алгоритма с растяжением-сжатием пространства (М2) [5; 7]. В методах КНМ и МСГ реализован одномерный поиск с квадратичной интерполяцией. В методах М0, М1, МШ и М2 используется одна и та же процедура одномерной минимизации.

Исследование проводилось на следующих функциях:

/1=Ё\\х, \\ ^k, /1 =00,

х* = (0,0,...,0),

/2 =Хх. • к/: = 0.0,

х* = (0,0,...,0), х0 =(10,-0,—),...,—);

и х) = Х[1000( х, — х, „)! + (1 — х, 1

/3* = 0.0, х* = (1,1,...,1), х0 = (0,0,...,0). Функция /3( х) взята из [14].

В таблицах 1 и 2 приведено количество затраченных методом вычислений функции и субградиента, которое соответствует моменту выполнения условия

/к — / < 8. Знаком N помечены задачи, которые не

удалось решить за количество итераций не превышающее заданное максимальное, т. е. найти точку приближения хк , в которой бы выполнялось условие останова алгоритма по значению функции, т. е. /к — / < 8. При тестировании другие критерии останова не использовались.

Результаты численного эксперимента для функции /2

МАТЕМАТИКА |

Таблица 1

п /2 - є = 10-10 /2 - є = 10 , Чыт = 0 98, Чылх =15

КНМ М2 МШ МСГ М0 М1

Функция 2 квадратичная с отношением собственных значений 1/п2. На функции 2 МСГ требуется существенно большее количество итераций для достижения заданной точности, чем п. В методе КНМ количество итераций равно п. В методе М2 при п > 200 за счет использования грубого одномерного поиска общие затраты ОТв меньше, чем в методе КНМ. Тем не менее при существенно больших затратах №0 в методах М0, М1 и МСГ сравнительно с методами КНМ, М2 и МШ, они затрачивают существенно меньше времени счета, чем алгоритмы, использующие матрицы преобразования пространства. Подобные преимущества по времени счета могут иметь место при решении задач, где затраты на вычисление функции и

Результаты численного

градиента пропорциональны размерности. На функции 2 алгоритм М1 эффективнее метода М0 и сравним с МСГ при размерностях выше 300 на функции 2.

На квадратичной функции 3 с небольшим разбросом собственных значений методы М0 и М1 практически эквивалентны, причем при росте размерности затраты М1 соизмеримы с затратами МСГ. В силу малой сложности функции количество итераций МСГ меньше размерности решаемой задачи.

На основании этих результатов можно сделать вывод, что при решении гладких задач минимизации высокой размерности с высокой степенью вытянуто-сти поверхностей уровня наряду с МСГ возможно и применение многошаговых РСМ.

Таблица 2

дмента для функций /1 и /3

п /1 є = 10 5 /1 є = 10 5 /1 - є= 10 5-Чиїм = °-999°5 -Чылх = I-5 0 = є /3 - є = 10-10 -Чиїм = 0-85 -Чылх = 1-5

М2 МШ М0 М1 МСГ М0 М1

Кусочно-линейная функции 1 имеет одинаковую вытянутость линий уровня с функцией 2, но неизмеримо сложнее для метода минимизации. Здесь в методе М0 происходит зацикливание, а увеличение числа итераций не приводит к решению задачи. На этом примере заметно существенное повышение эффективности алгоритма М1 сравнительно с М0 за счет использования дополнительного обучающего соотношения при решении неравенств.

Анализируя результаты для МШ и М1 приходим к выводу об уменьшении разрыва между ними по затратам ОТв при росте размерности. При решении этой задачи для п = 1000 уже не наблюдается десятикратного превосходства метода М2, как это было на функции 2. При этом затраты времени решения задачи 1 у метода М1 существенно меньше, чем у методов М2 и МШ. На основе полученных результатов можно сделать вывод, что при решении задач, где затраты на

вычисление функции и градиента пропорциональны размерности, метод М1 может оказаться предпочтительнее методов с изменением метрики пространства. Тем не менее, следует отметить, что при росте степени вырожденности задачи, граница этой степени, при которой метод в состоянии решить задачу, выше у субградиентных методов минимизации с растяжением пространства по сравнению с границей для М1. На негладких функциях оказывается существенным выбор коэффициента дт, который определяет широту

окрестности, из которой берутся субградиенты для встроенного в метод минимизации алгоритма решения неравенств. В силу того, что практически важную задачу минимизации, как правило, приходится решать многократно, то параметр дт можно предварительно подобрать экспериментально.

Заключение

В работе итерационный метод решения системы равенств, использующий на итерации коррекцию решения, обеспечивающую точное решение двух последних из них [13], распространен на задачу решения множества неравенств. Разработанный метод обоснован теоретически, получены оценки его скорости сходимости. На основе предложенного метода сформулирован и обоснован новый релаксационный суб-градиентный алгоритм минимизации, который пригоден для решения, в том числе и невыпуклых задач.

По свойствам сходимости на квадратичных функциях высокой размерности, при больших разбросах собственных значений, разработанный алгоритм эквивалентен методу сопряженных градиентов. Новый метод позволяет решать негладкие большеразмерные задачи минимизации с высокой степенью вытянуто-сти поверхностей уровня, где он при затратах на вычисление функции и субградиента пропорциональных размерности, может превосходить по времени счета известные методы минимизации с растяжением пространства.

Литература

Информация об авторах:

Крутиков Владимир Николаевич - доктор технических наук, профессор кафедры математической кибернетики КемГУ, 8-905-077-53-48, krutikovvn@gmail.com.

Vladimir N. Krutikov - Doctor of Techniocal Science, Professor at the Department of Mathematical Cybernetics, Kemerovo State University.

Вершинин Ярослав Николаевич - аспирант кафедры математической кибернетики КемГУ, 8-960-919-74-13, Azimus88@gmail.com.

Yaroslav N. Vershinin - post-gradiuate student at the Department of Mathematical Cybernetics, Kemerovo State University.

Статья поступила в реколлегию 21.10.2013 г.