Автоматика и телемеханика, № 1, 2019

Н.С. САМОЙЛЕНКО (nostienataly@mail.ru),

В.В. МЕШЕЧКИН, канд. физ.-мат. наук (vvm@kemsu.ru)

(Кемеровский государственный университет)

О СВОЙСТВАХ МЕТОДА МИНИМИЗАЦИИ ВЫПУКЛЫХ ФУНКЦИЙ,

РЕЛАКСАЦИОННОГО ПО РАССТОЯНИЮ ДО ЭКСТРЕМУМА

Представлен субградиентный метод минимизации — аналог метода ми-

нимальных итераций решения систем уравнений, наследующий от послед-

него свойства сходимости на квадратичных функциях. Предложенный

алгоритм при определенном наборе параметров совпадает с известным

ранее методом минимизации кусочно-линейных функций и является эле-

ментом разработанного Б.Т. Поляком семейства релаксационных по рас-

стоянию до экстремума методов минимизации, длина шага которых вы-

числяется на основе заданного значения минимума функции. Параметры

метода увязаны с ограничением на степень однородности функции, полу-

чены оценки его скорости сходимости на выпуклых функциях. Доказано,

что на некоторых классах функций он сходится со скоростью геометри-

ческой прогрессии. Обсуждаются вычислительные возможности метода

при решении задач высокой размерности.

Ключевые слова: субградиент, выпуклая функция, линейная алгебра, ми-

нимум функции, скорость сходимости.

DOI: 10.1134/S0005231019010094

1. Введение

Рассматривается задача минимизации выпуклой, но не обязательно диф-

ференцируемой функции f(x), x ∈ Rⁿ, где Rⁿ — конечномерное евклидово

пространство. Основная цель работы заключается в том, чтобы представить

релаксационный по расстоянию до экстремума субградиентный метод мини-

мизации — аналог метода минимальных итераций, наследующий от последне-

го свойства сходимости на квадратичных функциях, сформулировать и обос-

новать ограничения на выбор параметров метода в зависимости от свойств

функции, получить оценки его скорости сходимости на выпуклых функциях

и привести некоторые обнадеживающие результаты вычислительных экспе-

риментов относительно эффективности метода при решении задач высокой

размерности.

Активные исследования в области субградиентных методов начались по-

сле появления работ [1, 2]. В области построения методов, релаксационных

по функции, метод сопряженных градиентов для решения систем уравнений

был распространен на решение задач гладкой (см., например, [3]) и неглад-

кой оптимизации [4, 5]. Существенного повышения эффективности удалось

достичь в результате создания методов негладкой оптимизации с изменением

метрики пространства [6-9]. Совершенствование нересурсоемких релаксаци-

онных субградиентных методов отражено в [10-12].

126

Одно из активно развиваемых направлений работ по созданию методов

негладкой оптимизации основано на построении и использовании приближе-

ний функции [13-16]. В [14-16] рассматривается подход создания гладких

приближений для негладких функций. На этой основе удалось получить и

теоретически обосновать широкий спектр методов [14-16], предназначенных

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

ческой композитной оптимизации. Методы этого класса применимы для ши-

рокого круга (по величине размерности и условиям гладкости) задач. Алго-

ритмы для решения сверхбольших задач оптимизации предложены в [17].

В работах Б.Т. Поляка [3, 18] предложено и исследовано семейство релак-

сационных по расстоянию до экстремума методов минимизации. В алгорит-

мах этого типа длина шага вычисляется (а не находится подбором) на осно-

вании известного минимального значения функции f^∗ = inf_x∈Rn f(x). Про-

стейший из них следующий [3, 18]:

γ(f(x_k) - f^∗)

(1)

xk+1 = x_k -

g_k, g_k ∈ ∂f(x_k

k = 0,1,2,

(g_k, g_k)

Здесь и далее g, g(x) — некоторый субградиент из субградиентного множе-

ства ∂f(x) функции f(x), g_k = g(x_k), γ — шаговый множитель, определяемый

свойствами минимизируемой функции f(x), (x, y) — скалярное произведение

векторов. Согласно [3, 18] метод (1) является релаксационным по расстоя-

нию до экстремума. В [19] показано, что процесс (1) при γ = 2 является

аналогом метода минимальных ошибок для решения систем линейных урав-

нений [20, 21], в котором при минимизации квадратичных функций выпол-

няется операция минимизации расстояния до экстремума вдоль направления

антиградиента. В [17] алгоритм (1) используется как один из представителей

простейших субградиентных методов, встроенных в схему решения сверх-

больших задач оптимизации [17].

В [22] для минимизации кусочно-линейных функций предложен метод —

элемент отмеченного выше семейства [18], в котором направление движения

формируется на основе текущего субградиента и предыдущего направления,

а длина шага вычисляется на основе известного значения минимума функ-

ции, аналогично тому, как это делается в (1):

(f(x_k) - f^∗)

(2)

xk+1 = x_k - γ_kp_k, γ_k = γ

k = 0,1,2,...,

(p_k, p_k)

(3)

p₀ = g₀, p_k = g_k + β_kpk-1,

⎧

⎨

(g_k, pk-1)

-α_k

при (g_k, pk-1) < 0,

0 ≤ α_k ≤ 2;

(4)

β_k =

(pk-1, pk-1)

⎩

в противном случае,

где наложено ограничение 0 < γ ≤ 1. Идея вычисления текущего направле-

ния движения на основе предыдущего множества субградиентов [18] здесь

воплощена в виде использования аккумулированного вектора p_k. Ряд резуль-

татов о качестве направления движения в методе (2)-(4), полученных в [22]

для кусочно-линейных функций, обоснован для выпуклых функций в [7].

127

В настоящей работе метод AA^∗-минимальных итераций (см., например,

[20, 21]) распространен на задачу минимизации. Полученный метод эквива-

лентен алгоритму (2)-(4) при α_k = 1 и γ = 2 и наследует свойство конечной

сходимости метода минимальных итераций на квадратичных функциях. На

выпуклых функциях получена оценка скорости сходимости метода, где огра-

ничения на выбор параметра γ в (2) увязаны с ограничением на степень одно-

родности функции аналогично тому, как это сделано в [20] для процесса (1).

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

рость сходимости геометрической прогрессии. Простота реализации, отсут-

ствие необходимости выполнения вспомогательных операций минимизации

и незначительные вычислительные затраты на итерации с учетом представ-

ленных результатов вычислительного эксперимента позволяют надеяться на

эффективность метода при решении задач высокой размерности.

2. Аналог метода минимальных итераций в оптимизации

Покажем, что в случае специального вида квадратичной функции метод

(2)-(4) при α_k = 1 и γ = 2 является аналогом метода AA^∗-минимальных ите-

раций (см., например, [20, 21]). Для этого необходимо перейти от записи ме-

тода минимальных итераций в терминах линейной алгебры к записи в форме

метода минимизации, использующего только характеристики функции (зна-

чения функции и градиента).

Используем способ вывода метода AA^∗-минимальных итераций [20, с. 481;

21, раздел 8.36], описанный в [20, c. 481], для получения метода (2)-(4) при

α_k = 1 и γ = 2. Пусть требуется решить систему уравнений

(5)

Bx = b, x,b ∈ Rⁿ, B ∈ R^n×n,

где B — невырожденная матрица. Образуем вспомогательную систему урав-

нений посредством второй трансформации Гаусса, где после замены B^Ty = x

получим

(6)

BB^T

y = b.

Обозначим:

A = BB^T, r(x) = Bx - b, r_k = Bx_k - b.

Для решения системы (6) используем метод сопряженных градиентов:

(r_k, r_k)

(7)

yk+1 = y_k - γ_ks_k, γ_k =

k = 0,1,2,... ,

(s_k, As_k)

(r_k, Ask-1)

(8)

s_k = r_k + b_ksk-1, b_k = -

> 0.

(p_k, p_k)

Отметим, что в (7)-(8) использованы только те выражения для γ_k и b_k,

которые приводят к схеме (2)-(4). Для того чтобы получить запись метода

128

минимальных итераций в форме (2)-(4), введем квадратичную функцию

(Bx - b, Bx - b)

(r, r)

(9)

f (x) =

+f^∗ =

+f^∗,

где f^∗ — минимальное значение функции (9). Точка минимума x^∗ функции (9)

совпадает с решением системы (5). Градиент функции задается выражением

g(x) = ∇f(x) = B^T(Bx - b) = B^Tr.

Обозначим

B^Ts_k = p_k.

Используя равенства A = BB^T, (r_k, r_k) = 2(f(x_k) - f^∗),

(As_k, s_k) = (BB^Ts_k, s_k) = (B^Ts_k, B^Ts_k) = (p_k, p_k),

(Ask-1, r_k) = (BB^Tsk-1, r_k) = (B^Tsk-1, B^Tr_k) = (pk-1, g_k),

умножая на B^T векторные равенства в (7), (8), с учетом B^Ty = x получим

расчетные формулы, аналогичные (2)-(4) при α_k = 1 и γ = 2:

(10)

xk+1 = x_k - γ_kp_k,

(11)

p_k = g_k + b_kpk-1,

(r_k, r_k)

2(f(x_k) - f^∗)

(12)

γ_k =

(s_k, As_k)

(p_k, p_k)

(r_k, Ask-1)

(g_k, pk-1)

(13)

b_k = -

> 0.

(Ask-1, sk-1)

(pk-1, pk-1)

Поскольку для решения системы (6) используется метод сопряженных

градиентов, минимум специальной функции (9) будет найден процессом

(10)-(13) за конечное число шагов, не превосходящее размерности простран-

ства n. Таким образом, для специального вида квадратичной функции уда-

лось сформулировать метод минимизации, использующий в своей записи

только выражения функции и градиента. Относительно сходимости метода

на квадратичных функциях справедливо следующее.

Теорема 1. Минимум квадратичной функции со строго положитель-

но определенной матрицей Гессе будет найден процессом (2)-(4) при α_k = 1

и γ = 2 за конечное число шагов, не превосходящее размерности простран-

ства n.

Доказательство. Квадратичная функция с невырожденной матрицей

вторых производных A имеет вид

(14)

f (x) = (x, Ax)/2 - (b, x) + c.

Ее точка минимума равна x^∗ = A-1b, а значение минимума — f^∗ = c -

-(A-1b, b)/2. Обозначим: d = B-1b, где B — матрица такая, что B = B^T,

129

BB = A. Тогда несложно установить, что функцию (14) можно представить

в виде, аналогичном (9):

f (x) = (Bx - d, Bx - d)/2 + f^∗.

Точка минимума последней f(x) совпадает с решением системы Bx = d, ко-

торое согласно показанному ранее может быть найдено методом (2)-(4) при

α_k = 1 и γ = 2, использующим только характеристики функции. Теорема до-

казана.

3. Оценки скорости сходимости

Пусть f(x) — выпуклая функция на Rⁿ, а ее множество точек миниму-

ма X^∗ не пусто. В предыдущем разделе метод (2)-(4) при γ = 2 рассмотрен

на квадратичной функции, степень однородности которой γ_f = 2. В [3] вы-

бор γ метода (1) увязывается со степенью однородности функции. При этом

показано, что для анализа сходимости метода (1) вместо условия однородно-

сти можно использовать неравенство [3]

(15)

γ_f(f(x) - f^∗) ≤ (g(x),x - x^∗),

∀x ∈ Rⁿ,

∀x^∗ ∈ X^∗, γ_f

≥ 1.

Как увидим далее, метод (2)-(4) сравнительно с (1) более требователен к вы-

бору шага γ. При условии (15) оценки скорости сходимости метода (2)-(4)

удается получить на интервале 0 < γ ≤ γ_f , что в 2 раза меньше интервала

релаксационности по расстоянию для метода (1). В силу отмеченного огра-

ничения на интервал для γ и необходимости анализа скорости сходимости

метода, например на квадратичных функциях, на класс функций наклады-

валось условие (15).

В леммах 1 и 2 изложены предварительные результаты, где ограничение

0 < γ ≤ γ_f существенно и позволяет получить их доказательство. В [7] по-

добные результаты получены для выпуклых функций, т.е. при γ_f = 1 в (15).

Лемма 1. Пусть f(x) — выпуклая функция на Rⁿ, ее множество точек

минимума X^∗ непусто и выполнено (15). Тогда для последовательности,

генерируемой процессом (2)-(4) при 0 < γ ≤ γ_f, справедлива оценка

(16)

(x_k - x^∗, p_k) ≥ (x_k - x^∗, g_k

k = 0,1,2,

Доказательство. Отметим, что согласно (4) β_k ≥ 0. Докажем (16) ме-

тодом индукции по k. Допустим, что оценка справедлива для k = m. Докажем

ее для k = m + 1.

(xm+1 - x^∗, pm+1) = (xm+1 - x^∗, gm+1) + βm+1(x_m - γ_mp_m - x^∗, p_m) =

= (xm+1 - x^∗, gm+1) + βm+1[(x_m - x^∗, p_m) - γ_m(p_m, p_m)].

Преобразуем выражение в квадратных скобках:

(x_m - x^∗, p_m) - γ_m(p_m, p_m) = (x_m - x^∗, p_m) - γ(f(x_m) - f^∗) ≥

≥ (x_m - x^∗, g_m) - γ(f(x_m) - f^∗) ≥ (γ_f - γ)(f(x_m) - f^∗) ≥ 0.

130

С учетом β_k ≥ 0 и неравенства 0 < γ ≤ γ_f преобразуем предыдущее равен-

ство:

(xm+1 - x^∗, pm+1) ≥ (xm+1 - x^∗, gm+1).

Последнее доказывает лемму.

Отметим, что неравенство (16) играет важную роль в обосновании схо-

димости метода. В силу ограничения леммы 0 < γ ≤ γ_f при использовании

γ_f = 1 не удалось бы получить доказательство сходимости метода на неко-

торых классах функций, где более эффективным является выбор парамет-

ра γ > 1.

Лемма 2. Пусть f(x) — выпуклая функция на Rⁿ, ее множество точек

минимума X^∗ непусто и выполнено (15). Тогда для последовательности, ге-

нерируемой процессом (2)-(4) при 0 < γ ≤ γ_f , направление p_k сравнительно

с g_k образует меньший угол с направлением x_k - x^∗.

Доказательство. Для метода (2)-(4) справедлива оценка

(17)

∥p_k∥ ≤ ∥g_k

∥.

Действительно, при β_k = 0 имеем (p_k, p_k) = (g_k, g_k). В противном случае с

учетом ограничений на α_k в (4) получим:



(g_k, pk-1)

²

(g_k, pk-1)²

∥p_k∥²

= g_k - α_k

pk-1

= ∥g_k∥² - (2 - α_k)

≤ ∥g_k∥².



(pk-1, pk-1)

Из (16) и (17) следует(xk-x∗,pk)_∥p

≥ (xk-x∗,gk)_∥g

. После деления последнего ра-

k∥

венства на ∥x_k - x^∗∥ получим неравенство для косинусов соответствующих

углов, которое доказывает утверждение леммы.

Обозначим достигнутое на множестве итераций процесса (2)-(4) «рекорд-

ное» значение функции ϕ_k = mini=0,...,k f(x_k). В следующей теореме дана

оценка скорости сходимости для последовательности «рекордных» значе-

ний ϕ_k.

Теорема 2. Пусть f(x) — выпуклая функция на Rⁿ, ее множество то-

чек минимума X^∗ непусто и выполнено (15). Тогда для последовательно-

сти x_k, k = 0,1,2,... , генерируемой процессом (2)-(4) при 0 < γ ≤ γ_f , имеет

место x_k → x^∗ ∈ X^∗, а для последовательности «рекордных» значений ϕ_k

справедлива оценка

c∥x₀ - x^∗∥

(18)

ϕk - f^∗ ≤

√

(k + 1)γ(2γ_f - γ)

где c — константа, такая что ∥g(x)∥ ≤ c на множестве {x : ∥x - x^∗∥ ≤

≤ |x₀ - x^∗∥}.

131

Доказательство. Пусть y ∈ X∗ — произвольная точка минимума

функции f(x). Тогда для процесса (2)-(4) получим:



f (x_k) - f^∗)

²



∥xk+1 - y∥² =^x_k - y - γ⁽

(p_k



(p_k, p_k)

(f(x_k) - f^∗)

= ∥x_k - y∥² - γ

(x_k - y, p_k) + γ²

(p_k, p_k)

Отсюда с учетом (16) и (15) следует

(f(x_k) - f^∗)

∥xk+1 - y∥² ≤ ∥x_k - y∥² - γ(2γ_f - γ)

(p_k, p_k)

Преобразуем последнее неравенство с учетом (17):

(f(x_k - f^∗)

(19)

∥xk+1 - y∥² ≤ ∥x_k - y∥² - γ(2γ_f - γ)

∥g(x_k∥²

Отсюда следует (f(x_k) - f^∗)/∥g(x_k )∥ → 0. Так как последовательность x_k

ограничена: ∥x_k - y∥ ≤ ∥x₀ - y∥, то ∥g(x)∥ ≤ c [3, лемма 8, § 1, гл. 5]. Поэто-

му f(x_k) → f^∗. Следовательно, имеется подпоследовательность xki → x^∗, где

x^∗ — некоторая точка минимума. Заменяя в (19) y на x^∗, получим, что

∥x_k - x^∗∥ монотонно убывает, а ∥xki - x^∗∥ → 0. Отсюда следует x_k → x^∗.

С учетом сказанного преобразуем (19):







∑

(2γ_f - γ

^xk+1 - x^∗

² ≤

^x₀ - x^∗2 -γ

(f(x_i) - f^∗)².

c²

i=0

Отсюда получим:

∑



γ(2γ_f - γ

(f(x_i) - f^∗)² ≤

^x₀ - x^∗2.

c²

i=0

Последнее неравенство приведем к следующему виду:



∑

²

c²x0 - x∗

(20)

(f(x_i) - f^∗)² ≤

k+1

(k + 1)γ(2γ_f - γ)

i=0

В левой части неравенства находится среднее арифметическое слагаемых.

Следовательно, хотя бы одно из этих слагаемых с индексом i_k должно быть

не больше среднего, что с учетом определения ϕ_k приводит к неравенству



²

c²x0 -x∗

(ϕ_k - f^∗)² ≤ (f(x_i

)-f^∗)² ≤

(k + 1)γ(2γ_f - γ)

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

132

В случае острого минимума, определяемого соотношением

(21)

f (x) - f^∗ ≥ ρ∥x - x^∗

∥, ρ > 0,

справедлив результат, приводимый ниже.

Теорема 3. Пусть f(x) — выпуклая на Rⁿ функция, имеющая острый

минимум. Тогда для последовательности точек x_k, k = 0,1,2,... , генери-

руемых процессом (2)-(4) при 0 < γ ≤ 1, имеет место оценка скорости схо-

димости геометрической прогрессии

∥xk+1 - x^∗∥² ≤ q∥x_k - x^∗∥², q = 1 - γ(2 - γ)ρ²/c²,

где c — константа, такая что ∥g(x)∥ ≤ c на множестве {x : ∥x - x^∗∥ ≤

≤ |x₀ - x^∗∥}.

Доказательство. Преобразуем (19) с учетом (15) при γ_f = 1:

∥xk+1 - y∥² ≤ ∥x_k - y∥² - γ(2 - γ)ρ²∥x_k - y∥²/c² = q∥x_k - y∥²,

что доказывает утверждение теоремы.

Теорема 4. Пусть f(x) — сильно выпуклая на Rⁿ с константой m,

дифференцируемая функция, ее градиент удовлетворяет условию Липшица

с константой M на множестве S = {x : ∥x - x^∗∥ ≤ |x₀ - x^∗∥} и выполне-

но (15). Тогда для последовательности, генерируемой процессом (2)-(4) при

0 < γ ≤ γ_f, имеет место оценка скорости сходимости геометрической про-

грессии

m²γ(2γ_f - γ)

∥xk+1 - x^∗∥² ≤ q∥x_k - x^∗∥², q = 1 -

M²

Доказательство. Выполнены все условия теоремы 2, поэтому спра-

ведлива оценка (19) при y = x∗. Из сильной выпуклости функции сле-

дует [3] f(x_k) - f^∗ ≥ m∥x_k - x^∗∥², а из условия Липшица имеем ∥g(x_k)∥ ≤

≤ M∥x_k - x^∗∥. Объединяя эти оценки, получим

m²γ(2γ_f - γ)

∥xk+1 - x^∗∥² ≤ ∥x_k - x^∗∥² -

∥x_k - x^∗∥²,

M²

что доказывает утверждение теоремы.

4. Результаты численного исследования

Целью является изучение возможностей метода (2)-(4) (АММИ) на осно-

ве анализа и сравнения его результатов численного исследования с результа-

тами для известных методов оптимизации. В методе АММИ задавались α_k

в (4), γ = μγ_f в (2) (параметр γ_f соответствует минимальной предполагаемой

степени однородности функции) и предельное число итераций KO, проте-

кающих при β_k = 0 в (3), после которого производилось обновление β_k = 0,

т.е. набор (α_k, μγ_f , KO), например (α_k = 1,02, γ = 1,01γ_f , KO = ∞). Во всех

методах функция и субградиент в точке вычислялись одновременно. Будем

133

обозначать через it число итераций метода, а через nfg количество вычисле-

ний функции и градиента, требуемые для достижения заданной точности

(22)

f_k - f^∗

≤ ε.

В табл. 1-3 приведены результаты для методов на функциях:

∑

f₁(x) =

x2ii⁴, x0,i = 10, x^∗i = 0, i = 0,1,2,... ,n,

i=1

∑

f₂(x) =

|x_i|i, x0,i = 1, x^∗i = 0, i = 0, 1, 2, . . . , n,

i=1

∑

f₃(x) =

x2i(1 + (i - 1)(100 - 1)/(n - 1))²,

i=1

x0,i = 1, x^∗i = 0, i = 0,1,2,... ,n,

∑

f₄(x) =

|x_i|(1 + (i - 1)(100 - 1)/(n - 1)),

i=1

x0,i = 1, x^∗i = 0, i = 0,1,2,... ,n.

В качестве методов для сравнения использовались равноценные по затратам

памяти и вычислений на итерации метод сопряженных градиентов (МCГ) и

релаксационный субградиентный метод МСCГ [12].

В табл. 1 приведено число итераций для методов АММИ, МCГ и МСCГ

на первых двух функциях, необходимое для выполнения неравенства (22).

Функции характеризуются увеличением степени вытянутости линий уров-

ня с ростом размерности. Коэффициенты квадратичной функции выбраны

так, чтобы исчез эффект конечного окончания процесса для методов АММИ,

МCГ. Для методов МCГ и МСCГ затраты nfg примерно в 2 раза больше чис-

ла итераций. Для АММИ на f₁(x) заданы параметры (α_k = 1,0, γ = 1,0γ_f ,

KO = ∞), а на f₂(x) — (α_k = 1,02, γ = 1,01γ_f, KO = 10000).

На квадратичных функциях менее сложных, чем f₁(x), методы АММИ

и МСГ достигают необходимой точности за конечное число шагов, что сви-

детельствует о наличии у метода АММИ конечной сходимости. Результаты

на f₁(x) устанавливают, что для метода АММИ эффект потери скорости схо-

димости из-за ошибок округления при увеличении степени вырожденности

функции проявляется в меньшей степени по сравнению с МСГ.

Результаты для f₂(x) позволяют судить о возможностях метода на неглад-

ких функциях при различных масштабах переменных по осям координат и

дают некоторое представление о границах возможностей метода. В данном

случае масштабы переменных функции f₂(x) имеют разброс в n раз мень-

ший по сравнению с масштабами квадратичной функции f₁(x). Для сравне-

ния, методу на основе (1) при n = 10 и n = 100 требуется соответственно 2318

и 2046203 итераций для достижения заданной точности, что свидетельствует

о наличии ускоряющих свойств у метода АММИ.

134

Таблица 1. Количество итераций

100

300

500

1000

f₁(x) (ε = 10-10) МСГ

178

777

8496

25613

129356

f₁(x) (ε = 10-10) АММИ

165

617

5682

17713

76204

f₂(x) (ε = 10-5) АММИ

507

1948

6726

23970

23823

f₂(x) (ε = 10-5) МССГ

1084

2529

4535

15333

32245

42977

Таблица 2. Количество вычислений функции и градиента при ε = 10-8

5000

10000

25000

50000

100000

500000

1000000

f₃(x) АММИ it = nfg

642

658

679

696

713

753

771

656

672

695

711

728

767

783

f₃(x) МССГ

nfg

1036

1064

1109

1134

1196

1328

1388

641

657

679

696

713

753

770

f₃(x) МСГ

nfg

1287

1321

1368

1404

1441

1533

1574

Таблица 3. Количество вычислений градиента и функции при ε = 10-4

5000

10000

25000

50000

100000

500000

1000000

f₄(x) АММИ₁ it = nfg

9166

15885

15033

14739

24563

41528

43054

f₄(x) АММИ₂ it = nfg

11830

10290

13349

19104

15202

26614

28834

52200

53329

54978

56051

57178

59981

61154

f₄(x) МССГ

nfg

104418

106682

109988

112145

114414

120062

122416

Число обусловленности функции f₃(x) равно 10-4 и не зависит от раз-

мерности. Функция f₄(x) имеет равный характер вытянутости линий уров-

ня по осям координат сравнительно с f₃(x). Тесты на этих функциях про-

ведены с целью выявления характера скорости сходимости в зависимости

от размерности при не зависящем от размерности характере вытянутости

линий уровня по осям координат. Для АММИ на f₃(x) заданы параметры

(α_k = 1,02, γ = 1,0γ_f , KO = 1000), см. табл. 2.

Число итераций метода МCСГ несколько выше, чем у метода сопряжен-

ных градиентов, но общие затраты nfg у него в силу грубого одномерного

поиска ниже. Таким образом, на квадратичных функциях при невысокой сте-

пени обусловленности метод АММИ равноценен по числу итераций методам

МСГ и МCСГ, но имеет более низкие затраты по числу обращений к функции

и градиенту.

Результаты для функции f₄(x) приведены в табл. 3. Точность миними-

зации функции выбиралась из расчета исключения возможности окончания

вычислений вдалеке от точки минимума за счет получения нужного значе-

ния в подпространстве малой размерности. Методом АММИ сделано 2 ва-

рианта счета с параметрами (α_k = 1,0, γ = 1,0γ_f , KO = 500) для АММИ₁ и

(α_k = 1,02, γ = 1,01γ_f , KO = 1000) для АММИ₂. Функция f₄(x) имеет острый

минимум. Число итераций, затраченных методами на данной функции, су-

щественно ниже оценок, которые можно получить на основании теоремы 3.

Согласно результатам табл. 3 число итераций методов АММИ и МCСГ толь-

135

ко при росте размерности становится соизмеримым, но общие затраты обра-

щений к алгоритму вычислений функции и градиента разнятся значительно.

Таким образом, на большеразмерных квадратичных тестах выявлено, что

эффект потери скорости сходимости из-за ошибок округления при увеличе-

нии степени вырожденности функции у представленного алгоритма прояв-

ляется в меньшей степени по сравнению с методом сопряженных градиентов.

Результаты решения негладких задач высокой размерности позволяют сде-

лать вывод о стабильной работе метода и малой зависимости свойств его

скорости сходимости от размерности при условии равного характера вытяну-

тости линий уровня функций.

5. Заключение

Предложенный в статье субградиентный метод минимизации, полученный

распространением метода минимальных итераций на решение задач миними-

зации, пополняет семейство релаксационных по расстоянию до экстремума

методов [18], длина шага которых вычисляется на основе известного значе-

ния минимума функции, и наследует свойство конечной сходимости послед-

него на квадратичных функциях. Учет ограничения на степень однородности

функции [3] позволил сформулировать границы его параметров. Предложен-

ный алгоритм при определенном наборе параметров совпадает с известным

ранее методом минимизации кусочно-линейных функций [22].

В статье на классе выпуклых функций получена оценка скорости сходимо-

сти метода, совпадающая с точностью до мультипликативной константы с со-

ответствующей нижней оценкой для этого класса задач [6]. Показано, что на

сильно выпуклых функциях с липшицевым градиентом [3] и функциях с ост-

рым минимумом [3] метод сходится линейно. Проведенный вычислительный

эксперимент свидетельствует, что при умеренной степени вырожденности ме-

тод в меньшей мере подвержен проявлению нестабильности из-за ошибок

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

высокой размерности показывает устойчивые результаты. В силу отсутствия

вспомогательных операций минимизации и незначительных вычислительных

затрат на итерации метод может оказаться предпочтительным при решении

определенных прикладных задач высокой размерности.

СПИСОК ЛИТЕРАТУРЫ

1. Шор Н.З. Применение метода градиентного спуска для решения сетевой транс-

портной задачи // Матер. научн. семинара по теорет. и прикл. вопр. кибернети-

ки и исследования операций. Киев: Науч. совет по кибернетике АН УССР. 1962.

Вып. 1. С. 9-17.

2. Поляк Б.Т. Один общий метод решения экстремальных задач // Докл. АН

СССР. 1967. Т. 174. Вып. 1. С. 33-36.

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

4. Wolfe P. Note on a method of conjugate subgradients for minimizing

nondifferentiable functions // Math. Program. 1974. V. 7. No. 1. P. 380-383.

5. Lemarechal C. An extension of Davidon methods to non-differentiable problems //

Math. Program. Study. 1975. V. 3. P. 95-109.

136

Немировский А.С., Юдин Д.Б. Сложность задач и эффективность методов оп-

тимизации. М.: Наука, 1979.

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

ния. Киев: Наук. думка, 1979.

Крутиков В.Н., Петрова Т.В. Релаксационный метод минимизации с растяже-

нием пространства в направлении субградиента // Экономика и мат. методы.

2003. Т. 39. Вып. 1. С. 106-119.

Крутиков В.Н., Горская Т.А. Семейство релаксационных субградиентных ме-

тодов с двухранговой коррекцией матриц метрики // Экономика и мат. методы.

2009. Т. 45. Вып. 4. С. 37-80.

10.

Нурминский Е.А., Тьен Д. Метод сопряженных субградиентов с ограниченной

памятью // АиТ. 2014. № 4. С. 67-80.

Nurminskii E.A., Tien D. Method of conjugate subgradients with constrained

memory // Autom. Remote Control. 2014. V. 75. No. 4. P. 646-656.

11.

Крутиков В.Н., Вершинин Я.Н. Многошаговый субградиентный метод для ре-

шения негладких задач минимизации высокой размерности // Вестн. Том. гос.

ун-та. Математика и механика. 2014. № 3. С. 5-19.

12.

Крутиков В.Н., Вершинин Я.Н. Субградиентный метод минимизации с коррек-

цией векторов спуска на основе пар обучающих соотношений // Вестн. КемГУ.

2014. № 1-1 (57). С. 46-54.

13.

Гольштейн Е.Г., Немировский А.С., Нестеров Ю.Е. Метод уровней, его обобще-

ния и приложения // Экономика и мат. методы. 1995. Т. 31. Вып. 3. С. 164-180.

14.

Nesterov Yu.E. Smooth minimization of non-smooth functions // Math. Program.

2005. V. 103. No. 1. P. 127-152.

15.

Nesterov Yu. Universal gradient methods for convex optimization problems // Math.

Program. Ser. A. 2015. V. 152. P. 381-404.

16.

Гасников А.В., Нестеров Ю.Е. Универсальный метод для задач стохастической

композитной оптимизации // e-print. 2016.

https://arxiv.org/ftp/arxiv/papers/1604/1604.05275.pdf

17.

Nesterov Yu. Subgradient methods for huge-scale optimization problems // Math.

Program. Ser. A. 2013. V. 146. No. 1-2. P. 275-297.

18.

Поляк Б.Т. Минимизация негладких функционалов // Журн. вычисл. мат. и

матем. физики. 1969. Т. 9. № 3. С. 507-521.

19.

Самойленко Н.С., Крутиков В.Н., Мешечкин В.В. Исследование одного вари-

анта субградиентного метода // Вестн. КемГУ. 2015. № 5 (2). С. 55-58.

20.

Фадеев Д.К., Фадеева Д.К. Вычислительные методы линейной алгебры. М.:

Физматгиз, 1963.

21.

Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. М.: Наука, 1984.

22.

Camerini P., Fratta L., Maffioli F. On improving relaxation methods by modified

gradient techniques // Math. Program. 1975. No. 3. P. 26-34.

Статья представлена к публикации членом редколлегии Б.Т. Поляком.

Поступила в редакцию 15.02.2017

После доработки 15.03.2018

Принята к публикации 08.11.2018

137