Методом условного градиента как найти вспомогательное приближение

33. Алгоритм метода условного градиента

если то строим отрезок (5) и соединяем точки и . На отрезке (5)рассматриваем функцию и решаем задачу одномерной минимизации . Обозначим через –решение последней зад. минимизации т.е , тогда следующее приближение .

Замечание:

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

Задают некоторое значение и проверяют условие (6)
В случае выполнения (6), ; иначе дробят

В качестве критериев окончания счета используют выполнение неравенств или , где и согласованные числа, характеризующие точность вычисления.

Теорема3

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

34. Алгоритм метода покоординатного спуска.

Рассмотрим задачу . Пусть выбрано некоторое начальное приближение. И мтодом покоординатного спуска было получено приближение . Ч/з , , обозначим координатные вектора (1 на j-ом месте). Положим и для , где определяется из условия . И следующее приближение , если для некоторого k , то процесс вычисления заканчивают, А т считают приближением к точке минимума.

Данный метод хорошо подходит для задач с параллепипедными ограничениями,

, . В этом случае при решении вспомагательной задачи минимизации , .

Метод условного градиента

Рассматривается ЗНП
f(x) → min , (1)
g_i≤0, i=1. m , (2)
x_i≥0, j=1. n , (3)
где f(x) — выпуклая функция.
Пусть x ∈ S — очередное приближение исходной задачи НП и ▽f(x k )≠0. Тогда в окрестности точки x k ЦФ f(x) представима в виде

и линейная функция
f_k(x)=▽f T (x-x k )
является приближением разности с точностью до величины O(ǁx-x k ǁ) в некоторой окрестности точки x k .
Поставим вспомогательную задачу минимизации на множестве S линейной функции f_k(x), т. е.
f_k(x)=▽f T (x-x k ) → min (4)
при тех же ограничениях (2), (3).
Пусть x k — решение этой задачи. Следующее приближение x k+1 к точке минимума x * исходной ЦФ f(x) на множестве S найдем по формуле:
x k+1 =x k +α_k( x k -x k ), α_k∈(0,1), (5)
В силу выпуклости S следует, что x k+1 ∈ S .
Величина α_k из (5) может вычисляться различными способами. Например,
α_k=min(1,α * _k),
где α * _k найдено из условия наискорейшего спуска по направлению
( x k -x k )=d_k;
.
Другой способ вычисления значения α k . В начале выполнения итерации (5) полагают α k =1, после чего проверяют условие:
f(x k+1 ) < f(x k ). (6)
Если это условие нарушается, то α_k уменьшают в 2 раза (до тех пор, пока неравенство (6) не будет выполнено) и переходят к следующей итерации (5).
Критерий останова:
ǁ▽f(x k )ǁ≤ε или &#449x k -x k-1 ǁ≤ε.
Отметим, что в общем случае задача (4) является задачей нелинейного программирования (g_i(x) — нелинейные функции). Укажем случаи, когда поиск решения x k не представляет затруднений.
Допустимое множество S задано линейными ограничениями и условием неотрицательности переменных. Тогда (4) — ЗЛП и ее решение можно найти с помощью симплекс-метода.
Допустимое множество S=j≤x_j≤b_j, j=1. n> является n-мерным параллелепипедом. Тогда
(7)
Пусть ▽f(x k )=g; ▽f T (x k )x k =d.
В этом случае имеем:
.
Имеем ЗЛП. Пусть n=2. Найдем начальную угловую точку. Имеем
x₁-x₃=b₁; x₂-x₄=b₂; x₁+x₅=a₁; x₂+x₆=a₂.
Составим таблицу.
Таблица 1

x₁	x₂	x₃	x₄	x₅	x₆
1	0	-1	0	0	0	a₁
0	1	0	-1	0	0	a₂
1	0	0	0	1	0	b₁
0	1	0	0	0	1	b₂

x₁	x₂	x₃	x₄	x₅	x₆
1	0	-1	0	0	0	a₁
0	1	0	-1	0	0	a₂
0	0	1	0	1	0	b₁ – a₁
0	0	0	1	0	1	b₂ – a₂

x₃	x₄
x₁	-1	0	a₁
x₂	0	-1	a₂
x₅	1	0	b₁ – a₁
x₆	0	1	b₂ – a₂
g₁	g₂	— p₀

Пример . Решить ЗНП с помощью метода условного градиента, завершая вычисления при ǁx k -x k-1 ǁ≤0.1.
f(x)=x₁ 2 -4x₁+x₂ 2 -2x₂ → min ,
0≤x₁≤1, 0≤x₂≤2.
Решение. Возьмем x 0 =(0;0)∈S.

Шаг 1. Найдем ▽f=(2x₁-4;2x₂-2) в точке x 0 : ▽f(x 0 )=(-4;-2).
Запишем вспомогательную задачу (4):

Это ЗЛП, ее можно решить симплекс-методом. Однако проще воспользоваться соотношениями (7), откуда следует: x 0 =(1;2).
Найдем α₀ первым способом. В данном случае
F₀(α) = f[x 0 +α·( x 0 -x 0 )] = f <(0;0)+α·[(1;2)-(0;0)]>= f(α, 2α) = 5α 2 -8α.
Из условия ▽F₀(α)=0 ⇒ α=α * =0.8. Поэтому α₀=min(1; 0.8)=0.8.
Вычислим очередное приближение x₁ по формуле (5):
x₁=(0;0)+0.8(1;2)=(0.8;1.6).
Т.к. ǁx 0 -x 1 ǁ=1.79>0.1=ε, то требуемая точность не достигнута.
Результаты вычислений на следующих итерациях приведены в таблице.

k	x k	ǁx k -x k-1 ǁ	x k	α_k
1	(0,8; 1,6)	1,789	(1; 0)	0,8
2	(0,892; 0,861)	0,745	(1; 2)	0,212
8	(0,957; 0,953)	0,1	Точность не достигнута

ОПТИМИЗАЦИЯ ПАРАМЕТРОВ АЭРОДИНАМИЧЕСКОГО УСТРОЙСТВА ФОРМИРОВАНИЯ НЕТКАННОГО ПОЛОТНА МЕТОДОМ УСЛОВНОГО ГРАДИЕНТА Текст научной статьи по специальности «Электротехника, электронная техника, информационные технологии»

Аннотация научной статьи по электротехнике, электронной технике, информационным технологиям, автор научной работы — Земсков Владимир Михайлович, Виштак Ольга Васильевна, Штырова Ирина Анатольевна, Виштак Наталья Михайловна

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

OPTIMIZATION OF PARAMETERS OF AERODYNAMIC DEVICE FOR FORMING A NONWOVEN FABRIC BY THE CONDITIONAL GRADIENT METHOD

The article deals with the task of automating the production of non-woven fabric, its scope and stages of its production. At the stage of forming the structure of the material, as a rule, an aerodynamic method is used, the use of which makes it possible to obtain a web of a given density. Therefore, the calculation of the settings of the parameters of an aerodynamic device for the production of a web of a given density is an urgent task, the solution of which ensures high product quality. Accordingly, it becomes necessary to solve the production prob- lem of setting up an aerodynamic device: determining the optimal values of the pressure supplied to the aerodynamic device, the distance between the web and the diffuser for the production of a web of a given density. A brief analysis of nonlinear optimization methods is given, on the basis of which the conditional gradient method is chosen as the most suitable for the type of objective function and constraints. The calculation of the pressure supplied to the aerodynamic device and the distance between the base web and the diffuser for the production of a web of surface density was made, which will ensure the formation of a web structure of a given density and, accordingly, high product quality.

Текст научной работы на тему «ОПТИМИЗАЦИЯ ПАРАМЕТРОВ АЭРОДИНАМИЧЕСКОГО УСТРОЙСТВА ФОРМИРОВАНИЯ НЕТКАННОГО ПОЛОТНА МЕТОДОМ УСЛОВНОГО ГРАДИЕНТА»

ОПТИМИЗАЦИЯ ПАРАМЕТРОВ АЭРОДИНАМИЧЕСКОГО УСТРОЙСТВА ФОРМИРОВАНИЯ НЕТКАННОГО ПОЛОТНА МЕТОДОМ УСЛОВНОГО

В.М. Земсков, О.В.Виштак, И.А.Штырова, Н.М.Виштак

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

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

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

Неткаными, как следует из названия, называют полотна, произведенные без процедуры ткачества. Вместо этого, сырью — натуральным и синтетическим волокнам, нитям, волокнистым отходам, придают форму, укладывая его в выбранном порядке, и скрепляют механическим, аэродинамическим, гидравлическим, электростатическим или волокнообразующим способами [2]. Сферами применения нетканого полотна являются:

промышленность: фильтровальные, обтирочные, изоляционные, обивочные изделия, униформа для персонала;

медицина: одноразовые салфетки, полотенца, пеленки и простыни, перевязочный материал;

бытовая: пошив одежды, искусственный мех, основа кожзаменителей, ватин, фетр, войлок, махровые полотна.

Технологический процесс производства нетканого полотна состоит из следующих этапов:

подготовка сырья: разрыхление, очитка от примесей, смешивание волокон;

формирование основы полотна — укладка волокон, пропитка, склеивание;

формирование единого монолитного полотна, разрезание.

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

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

Математическая модель зависимости поверхностной плотности нетканого материала от давления, подаваемого в аэродинамическое устройство, и от расстояния между полотном основы и диффузором имеет вид:

Р = 145,00 + 6,67*! — 15,00ж2 — 35,00ж| — 10,00ж| , (1)

где х1 — давление, подаваемое в аэродинамическое устройство, МПа; х2 — расстояние между полотном основы и диффузором, м.

При этом ограничения значений давления, подаваемого в аэродинамическое устройство, и расстояния между полотном и диффузором имеют вид:

/ = -рр + 145,00 + 6,67хх — 5,00х2 — 35,00х^ — 10,00х| ^ min (3)

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

Метод множителей Лагранжа. Рассмотрим задачу, когда ограничения представлены равенствами, переменные могут принимать отрицательные значения, а целевая функция, функции ограничений и их частные производные непрерывные

Для решения такой задачи необходимо ввести переменные Ал, А2, . А™ — множителями Лагранжа, и составить функцию Лагранжа:

= F (х-^хг. ,xj + _^j(x1,x2,^,xn))

Найти и приравнять к нулю частные производные

В результате получим систему п + т уравнений:

lal» = bi ~hi(Xl, Х2, Хп) = 0(7 = 1, . Ш) Наличие экстремума целевой функции F(x) в точке Х = (х°,х2. х°) говорит о существовании такого вектора Л = (А5,А2. А^), что точка (X°,X2. X°,A°,A2. A^) является решением системы. Значит, решение системы -множество точек возможного экстремума. В нем необходимо найти такие, где экстремум достигается, и вычислить значения функции F(x) в этих точках.

Недостаток данного метода — ограниченное множество разрешимых им

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

F(x,rfc) = f(x) + P(x,rfc)^min (10)

где Р(х, rk) — функция штрафа; rk — параметр штрафа, задаваемый на каждой k -ой итерации.

Штрафные функции строится согласно условиям:

0, при выполнении ограничений

^ ‘ > 1>0, при невыполнении ограничений,

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

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

Недостаток метода внешних штрафов — сходимость только при достаточно слабых ограничениях.

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

1. обратную штрафную функцию

2. логарифмическую штрафную функцию

Проекция градиента. Сущность метода проекции градиента состоит в поиске проекции точки а на множество X — Пх(а), то есть ближайшей к а точки из множества X:

Точка может быть получена по методу градиентного спуска, тогда ее проекция примет вид:

хк+1 = пх(х* = 0,1. где (17)

— вычисленный в точке х^еХ градиент целевой функции; ак — шаг в направлении точки X .

Каждая итерация метода представляет собой задачу условной минимизации. Потому множество X должно быть достаточно простым, иначе задача на очередном шаге приближения к решению оказывается той же сложности, что исходная задача. Это является недостатком данного метода. Примеры достаточно простых множеств X — шар или параллелепипед. Проекция для шара с радиусом R:

Проекция для координатного параллелепипеда, задаваемого неравенствами

Метод условного градиента. Решение задачи представляет собой процесс последовательных переходов между точками от исходной хк вплоть до нахождения приемлемого решения задачи [5,6].

Пусть на к-ой итерации известна точка хк~х £Х. Для нахождения направления спуска используется минимизация функции, являющейся линейным приближением данной целевой функции/(х) в точке то есть функции

Так как /(х^_1) является константой, то данная задача может быть представлена в виде:

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

кк = ага тт(У/(х^_1),х — х^-1) -х^-1, (22)

определяющий на этой итерации допустимое направление в точке хк~х £Х. Обычно

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

Новая точка хк строится следующим образом:

хк =хк~1 +кк И.к, где (23)

жк — шаговый множитель.

На практике жк ищут обычно следующим способом:

min(1, агд тт(/(х^) + (24)

Поиск осуществляется до тех пор, пока критерий остановки не будет выполнен. В качестве критерия остановки возьмем

£> 0- точность решения.

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

Недостаток данного метода — низкая скорость сходимости.

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

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

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

Так как в задаче вычисления давления, подаваемого в устройство производства полотна, и расстояния между полотном и формирующим его устройством для удовлетворения требований по поверхностной плотности полотна целевая функция — выпуклая дифференцируемая на множестве допустимых значений вектора варьируемых переменных Д Б сйп, а ограничения — линейные, для ее решения используем метод условного градиента. Решим задачу:

45,00 + 6,67хх — 5,00х2 — 35,00х2 — 10,00х| ^ш/п 0,1

Зададим начальную точку х0 = (0 и точность 8 = 0,01.

ч _ /6,67 — 70хх \ ^ -5 — 20х2 )

Составим вспомогательную задачу:

Найдем новую точку приближения:

Х1 = хо +«1 (хо _хо) = (о)^сх»1 (0 3) (31)

«1=а^тт(145 + 6,67(0 + 0,1 — 5(0 + 0,3 «^-35(0 + 0,1 кх)2 (

-10(0 + 0,3 «х)2) = + сю (32)

Вычислим новую точку приближения:

хх =х0 +«! (х0 -х0) = (°°)+«1 (°°,3)= (05,3) (34) (

Проверим критерий остановки:

Н^/(х1)11 = 7(-0,33)2 + (-11)2 =11>е (36)

Критерий не выполняется, значит, продолжим приближения.

Продолжая решение, получим оптимальное решение

В этой точке значение целевой функции — 42,5. Таким образом, при заданных ограничениях минимально возможное значение поверхностной плотности полотна — Р = 142,5 г/м2. Для достижения этого значения давление, подаваемое в устройство, должно составлять 0,2 МПа, расстояние между полотном и формирующим его устройством — 0,3 м.

Таким образом, зависимость поверхностной плотности нетканого полотна от давления, подаваемого в аэродинамическое устройство, и от расстояния между полот-

ном основы и диффузором представляет собой квадратичную функцию. Решение задачи минимизации квадратичной функции произведено с помощью метода условного градиента, как наиболее подходящего для вида целевой функции и ограничений. Произведен расчет давления, подаваемого в аэродинамическое устройство, и расстояния между полотном основы и диффузором для производства полотна поверхностной плотности. В заданных ограничениях целевое значение поверхностной плотности Р = 100 г/м2 не достижимо. Минимальное значение Р = 142,5 г/м2

1. Дягилев А.С., Инновации в текстильной промышленности. Монография. Витебск, 2016. 221 с.

2. Коган А.Г., Моделирование процесса производства нетканых материалов методом горячего прессования // Моделирование в технике и экономике. Витебск, 2016. С. 180-182.

3. Штырова И.А., Виштак Н.М., Токарев А.Н., Карпова А.В. Функциональные возможности программного модуля для формирования технологических карт. // Современные наукоемкие технологии. 2021. № 5. С. 102-107.

4. Аббасов М.Э. Методы оптимизации: учеб. пособие. СПб.: Издательство «ВВМ», 2014. 64 с.

5. Гасников А.В. Современные численные методы оптимизации. Метод универсального градиентного спуска: учеб. пособие. М.: МФТИ, 2018. 291 с.

6. Козлов В.Н. Системный анализ, оптимизация и принятие решений: учеб. пособие. СПб.: Изд-во Политехн. ун-та, 2011. 244 с.

Земсков Владимир Михайлович, д-р техн. наук, профессор, VMZemskov@mephi.ru, Россия, Балаково, Балаковский инженерно-технологический институт (филиал) НИЯУМИФИ,

Виштак Ольга Васильевна, д-р пед. наук, профессор, OVVishtak@mephi.ru, Россия, Балаково, Балаковский инженерно-технологический институт (филиал) НИЯУ МИФИ,

Штырова Ирина Анатольевна, канд. техн. наук, доцент, IAShtyrova@mephi.ru, Россия, Балаково, Балаковский инженерно-технологический институт (филиал) НИЯУ МИФИ,

Виштак Наталья Михайловна, канд. пед. наук, доцент, NMVishtak@mephi.ru, Россия, Балаково, Балаковский инженерно-технологический институт (филиал) НИЯУ МИФИ

OPTIMIZATION OF PARAMETERS OF AERODYNAMIC DEVICE FOR FORMING A NONWOVENFABRIC BY THE CONDITIONAL GRADIENT METHOD

V.M. Zemskov, O.V. Vishtak, I.A. Shtyrova, N.M. Vishtak

lem of setting up an aerodynamic device: determining the optimal values of the pressure supplied to the aerodynamic device, the distance between the web and the diffuser for the production of a web of a given density. A brief analysis of nonlinear optimization methods is given, on the basis of which the conditional gradient method is chosen as the most suitable for the type of objective function and constraints. The calculation of the pressure supplied to the aerodynamic device and the distance between the base web and the diffuser for the production of a web of surface density was made, which will ensure the formation of a web structure of a given density and, accordingly, high product quality.

Key words: nonwoven fabric formation, given probability structure, aerodynamic device, non-linear programming methods, conditional gradient method

Zemskov Vladimir Mikhailovich, doctor of technical sciences, professor, VMZemskov@mephi.ru, Russia, Balakovo, Balakovo Engineering and Technology Institute (branch) of National Research Nuclear University MEPhI,

Vishtak Olga Vasilevna, doctor of pedagogical sciences, professor, OV-Vishtak@mephi. ru, Russia, Balakovo, Balakovo Engineering and Technology Institute (branch) of National Research Nuclear University MEPhI,

Shtyrova Irina Anatolievna, candidate of technical sciences, docent, IAShtyrova@mephi.ru, Russia, Balakovo, Balakovo Engineering and Technology Institute (branch) of National Research Nuclear University MEPhI,

Vishtak Natalya Mikhailovna, candidate of technical sciences, docent, NMVishtak@mephi.ru, Russia, Balakovo, Balakovo Engineering and Technology Institute (branch) of National Research Nuclear University MEPhI

АВТОМАТИЗАЦИЯ И УПРАВЛЕНИЕ ПРОИЗВОДСТВОМ В МАШИНОСТРОЕНИИ

О.И. Борискин, С.Н. Ларин, Г.А. Нуждин, М.Г. Нуждин

Обсуждены вопросы электронной технологической документации и информации об изделии в машиностроении в соответствии с требованиями новых ГОСТ Р 58675, ГОСТР 54089 и ГОСТР 59192. Показана возможность их интеграции с системами менеджмента и комплексными информационными системами внутри организации в машиностроении. Указаны определенные преимущества формализованного описания технологии проектирования и компьютерного моделирования технологических процессов и операций в машиностроении.

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

Требования к обеспечению качества продукции машиностроения в большинстве случаев прямо включены в договорные условия. Обычно это целый ряд позиций в регламентированных требованиях к системе менеджмента качества (СМК) поставщика. По установленным требованиям к СМК организация-поставщик должна планировать и

Стохастические градиентные методы с неточным оракулом Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е.

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

i Надоели баннеры? Вы всегда можете отключить рекламу.

Текст научной работы на тему «Стохастические градиентные методы с неточным оракулом»

А. В. Гасников1’2, П. Е. Двуреченский2’4, Ю. Е. Нестеров3’5

1 Московский физико-технический институт (государственный университет)

2Институт проблем передачи информации РАН 3Национальный исследовательский университет Высшая школа экономики 4Weierstrass Institute for Applied Analysis and Stochastics 5Universite catholique de Louvain, Center for operations research and econometrics

Стохастические градиентные методы с неточным

В работе предпринята попытка описать современное состояние методов проекции градиента (в том числе прямых методов и методов покомпонентного спуска) решения задач выпуклой стохастической оптимизации с неточным оракулом (неточность неслучайной природы), выдающим стохастический субградиент. Заметная часть приведенных в статье результатов была получена относительно недавно. Цель данной работы — собрать все вместе и посмотреть на разнообразные факты из этой области с единой позиции.

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

A. V.Gasnikov1’2, P. E.Dvurechensky2’4, Yu. E.Nesterov3’5

1Moscow Institute of Physics and Technology (State University) 2 Institute for Information Transmission Problems RAS 3National Research University Higher School of Economics 4Weierstrass Institute for Applied Analysis and Stochastics 5Universite catholique de Louvain, Center for operations research and econometrics

Stochastic gradient methods with inexact oracle

In this paper, we try to describe state of the art in projected gradient methods, including gradient-free and coordinate descent methods, for convex stochastic optimization problems with inexact oracle. This oracle is meant to give access to the stochastic subgradient of an objective function with some inexactness of deterministic nature. Most of the results described in the paper are obtained relatively recently. The goal of this work is to collect these results all together and consider them from a unified viewpoint.

Key words: stochastic optimization, randomozation, inexact oracle, gradient-free methods, coordinate descent method

Статья приурочена к 80-летию Бориса Теодоровича Поляка 1. Введение

В 1960-е годы численные методы выпуклой оптимизации переживали свою первую большую революцию. В работах того времени четко и последовательно развивалась линия градиентных методов. Основополагающим здесь можно признать вклад Бориса Теодоровича Поляка [1, 2], с работ которого во многом и началось активное и повсеместное использование градиентных методов в Советском Союзе. Следующая революция началась в конце 1970-х годов после фундаментальных работ А. С. Немировского, Д. Б. Юдина, Л. Г. Хачияна, N. Karmarkar’а и др. [3, 4]. В монографии [4] была предложена классификация задач выпуклой (и не только) оптимизации по степени гладкости и выпуклости. Были получены нижние оценки для соответствующих классов задач оптимизации с оракулом, выдающим по запросу градиент или стохастический градиент, его компоненту или

просто значение функции в точке. Стало понятно, чего в принципе можно достичь. Стали строиться оптимальные методы, см., например, [5-7]. При этом на задачи начали смотреть более пристально с точки зрения теории сложности. Появилась битовая сложность. Была показана полиномиальная разрешимость задач линейного программирования в битовой сложности [3]. Началась разработка полиномиальных методов внутренней точки для задач выпуклой оптимизации на базе метода Ньютона, которая впоследствии привела к созданию общей теории [8-11] и соответствующего пакета CVX [12], способного решать широкий спектр задач выпуклой оптимизации в пространствах размерности до n ~ 104 —105. Однако вызовы нового тысячелетия заставляют снова вернуться к градиентным методам. Задачи, которые стали возникать в последние десять лет, отличаются огромными размерностями n ~ 106 — 109. Такие задачи (классифицируемые как задачи large-scale и huge-scale оптимизации) приходят из анализа данных, поиска равновесий в различных сетевых моделях (связанных с компьютерными и транспортными сетями), биоинформатики и многих других областей. Для таких размерностей шаг (итерация) метода Ньютона, становится слишком дорогим, поэтому приходится снова возвращаться к более медленным (в смысле скорости сходимости), но более дешевым (в смысле стоимости одной итерации) градиентным методам (см. [13]). Но для указанных размерностей даже градиентные методы могут испытывать проблемы. В этой связи оказалась очень полезной концепция «заглядывания в черный ящик», т.е. использование структуры задачи с целью ускорения вычислений [14], и использование вместо градиента его легко вычислимой (стохастической) аппроксимации [11]. Как следствие, принято стало считать, что правильный способ эффективно решать ту или иную задачу — это отказаться от общих методов, оптимальных на больших классах, и погружаться в специфику конкретной задачи в надежде ускориться и получить оценки лучше, чем нижние границы [4]. Можно сказать, что началась новая революция. Поток работ на эту тему в основных профилирующих журналах (например, Math. Program.) резко возрос (см., например, обзор [11]). Тем не менее, параллельно стали появляться работы (в том числе работы авторов статьи), показывающие, что многие эффективные методы решения современных задач выпуклой оптимизации в пространствах огромных размеров получаются сочетанием небольшого количества приемов и идей. Цель настоящей работы состоит в том, чтобы собрать воедино набор основных таких идей и показать их связь с некоторыми концепциями 1960-х годов, многие из которых восходят к Б. Т. Поляку. Мы сосредоточимся на оценках числа итераций, требующихся различным методам для решения задачи выпуклой оптимизации с заданной точностью по функции. Эта информация не в полной мере характеризует эффективность метода, но она необходима для последующего его полного исследования. Мы также ограничимся рассмотрением методов проекции градиента [15, 16], в которые, например, не входят очень популярные в последнее время методы условного градиента [11, 17, 18]. В качестве основного инструментария для получения эффективных методов используется метод оценивающих последовательностей, восходящий к работам одного из авторов статьи [7, 10, 14]. Здесь имеются и альтернативные подходы, например, [19-21]. Из-за ограничений на объем статьи и большого количества технических деталей мы ограничимся здесь лишь изложением общей картины. В частности, в статье не приводится псевдокод соответствующих алгоритмов, но, как правило, указываются источники, в которых его можно найти. Мы также не претендуем здесь на полный обзор современного состояния исследований, посвященных градиентным методам. Более того, при ссылках на литературу мы далеко не всегда ссылались на первоисточники, иногда предпочитая ссылаться на удачно написанный более доступный и более современный обзор или монографию.

2. Стохастическая оптимизация

Рассматривается задача выпуклой стохастической оптимизации [2, 22, 23]:

(V (ХМ) — шщш / (X) > см^ 1 + =

= ^ [/ (ХМ, С)] — ЩШ! щ [/ (х, 0] > СМ^ 1 + < а,

где С — константа (здесь и далее константы в основном будут в диапазоне ~ 100 — 102), а случайный вектор хм — то, что выдает алгоритм (например, метод зеркального спуска [30] или метод двойственных усреднений [27] — сравнительный анализ и описание «физики» этих методов в детерминированном случае проводится в работе [21]) после N итераций. Мы будем называть хм — (£, ст)-решением задачи (1), если

PxN ( f (хм) — min f (х) > е ) < а. \ x£.Q у

Таким образом, для достижения точности по функции е и доверительного уровня а методу потребуется (здесь и далее мы будем использовать О (■), однако все эти формулы могут быть переписаны с точными константами, что важно, поскольку во многих ситуациях такие оценки используются для формирования критерия останова метода)

2Для задач онлайн оптимизации условие перестановочности необходимо записывать в более общем (мар-тингальном) виде [26].

3Впрочем, в случае неограниченного множества Q, даже когда выпуклая функция f (х) имеет ограниченную вариацию на мы не можем никак априорно оценить это расстояние Я в общем случае — оно может быть сколь угодно большим [4]. Интересный нюанс для выпуклой (но не обязательно сильно выпуклой и гладкой) функции / (х) имеет место, если / (х) задана на ограниченном множестве . В этом случае размер Я множества может не входить в оценку необходимого числа итераций. Например, это имеет место для метода центра тяжести [2, 4, 11].

4Б. Т. Поляком было показано [28], что такое сочетание позволяет получать эффективные методы для данного класса задач.

5 Эта оценка неулучшаема с точностью до мультипликативной константы С (при N < п оценка неулуч-шаема и в детерминированном случае / (х, £) = f (х)), см. [4].

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

Отметим, что если использовать метод Монте-Карло, заключающийся в замене исходной задачи (1) следующей задачей

где с.в. — i.i.d., и распределены так же, как и £, то для того, чтобы гарантировать, что абсолютно точное решение этой новой задачи является (е, ст)-решением исходной задачи потребуется взять N порядка [24]

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

Здесь важно подчеркнуть фундаментальную идею7, которую можно усмотреть, например, в [2] и в цикле работ Б.Т. Поляка с Я.З. Цыпкиным [33], о том, что для получения (агрегирования) хороших оценок неизвестных параметров (особенно когда размерность пространства параметров велика) имеет смысл рассматривать задачу поиска оптимальных значений параметра как задачу стохастической оптимизации и рассматривать выборку как источник стохастических градиентов. Например, истинное значение неизвестного вектора параметров в предположении верности исходной параметрической гипотезы может быть записано как решение задачи стохастической оптимизации [34, 35] (метод наибольшего правдоподобия Фишера):

9* = arg max Е£ \L (д,£)1, eeQ ?

где L (в,£) — логарифм функции правдоподобия. Однако решать эту задачу обычными методами мы не можем, потому что математическое ожидание берется по с.в. £, распределение которой задается неизвестным параметром в*. Обойти эту сложность можно, если решать ту же самую задачу

методами стохастической оптимизации, получая на каждом шаге новую реализацию (элемент выборки) и рассчитывая значения стохастического градиента dL (в, ^) /дв. То, что выдает алгоритм, и будет оценкой вектора неизвестных параметров в*. Как правило, дополнительно известно, что L (в, £) — гладкая и ^-сильно вогнутая (равномерно по £) функция от в. Последнее обстоятельство позволяет получить лучшую оценку скорости сходимости по функции [36-39] (в [36, 37] используется специальная модификация метода проекции

6Особенно ярко это проявляется в случае, бесконечномерных пространств, возникающих в статистической теории обучения (СТО = SLT, Statistical Learning Theory) [32]. Попытка обучиться за счет минимизации эмпирического риска (а именно так можно расшифровать формулу (3) в СТО) может не дать состоятельной оценки/решающего правила, в то время как соответствующий стохастический зеркальный спуск дает состоятельную оценку. Отметим, что в работе [32] приводится достаточно интересный общий результат: в задачах обучения (в частности, в задачах СТО, математической статистики и онлайн обучения) способ получения оптимальных (с точностью до логарифмических факторов) оценок/решающих правил (или, другими словами, способ наискорейшего обучения) базируется на применении соответствующего метода зеркального спуска. Правда, найти «соответствующий метод», в свою очередь, представляет собой непростую задачу.

Распространяемую и на непараметрическую статистику. Отметим, что начиная с 1980-х годов XX века в этом направлении был цикл работ А.С. Немировского, Б. Т. Поляка и А. Б. Цыбакова, оказавших заметное влияние и на текущие исследования в этой области.

градиента с усреднением и выбором шагов Нк = 2 (ц ■ (к + 1)) 1 и Нк = (цк) 1, где к -номер итерации, о подходе [38] и близком к нему подходе [39] будет немного написано в п. 3)

т.е. (x = в, f = —L, С — некоторая константа)

f(xN) — min f (х) > СМ

Из неравенства Рао-Крамера [35] (Q = Rra) будет следовать, что оценка (4) — не улучшаемая (с точностью до слагаемого ln(ln ( N))). Правда, тут возникают некоторые тонкости, когда мы говорим о неулучшаемости оценок с учетом вероятностей больших отклонений. Строго говоря, классические результаты типа Рао-Крамера, Ван-Трисса и т.п. (см., например, [35]) позволяют лишь говорить о неулучшаемости в смысле сходимости полных математических ожиданий (без вероятностей больших отклонений), и именно в таком смысле можно получить (с помощью методов [11, 37-39]) неулучшаемую (с точностью до мультипликативной константы) оценку:

EtXN [f(xN, О] — min [f (x, 0]

где С — некоторая константа.

PXN f(xN) — min f (x) >CaMR

PxN f(xN) — min f (x) >СаМ

8Приводимые ниже неравенства стоит понимать так, что хм выдается методом [27,30], а в сильно выпуклом случае, методом [37-39]. При этом для оценок вероятностей больших уклонений в случае тяжелых хвостов требуются некоторые оговорки и уточнения. К сожалению, мы не смогли найти соответствующий выписанным оценкам (в случае тяжелых хвостов) источник литературы. Приведенные здесь нами формулы нуждаются в дополнительной проверке.

второе неравенство подразумевает ^-сильную выпуклость f (х).

Можно задать вопрос: насколько вообще уместно рассматривать постановки, в которых возникают тяжелые хвосты. Ведь, если мы можем эффективно вычислять значения функции f (х) = Е^ [f (х, £)] в задаче (1), то ни о каких тяжелых хвостах можно не заботиться. Поскольку, выбрав число шагов так, чтобы метод находил е-решение с вероятностью > 1/2, запустив log2 (а-1) реализаций такого метода и выбрав реализацию с минимальным значением функции в конечной точке алгоритма, мы за дополнительную log2 (а-1) плату (мультипликативную) получим с вероятностью 1 — а среди выданных ответов хотя бы одно е-решение [31, 39]. Однако предположение о возможности эффективно вычислять значения функции (при условии трудной вычислимости ее градиента), как правило, не встречается на практике. В некотором смысле типичным тут является пример 1 (см. ниже) вычисления вектора PageRank (при n ~ 109). Собственно, искусственность ситуации, в которой значение функции легко вычислимо, а градиент нет, неплохо соответствует философии быстрого автоматического дифференцирования (БАД) [41, 42]. Согласно теории БАД, если мы можем посчитать значение функции, то мы можем не более чем в 4 раза дороже посчитать и ее градиент.9 Как следствие, если мы можем эффективно вычислить значение f (х), то, как правило, мы и V f (х) можем эффективно вычислить. Тогда и на исходную задачу (1) можно смотреть уже не как на задачу стохастической оптимизации, а как на обычную задачу выпуклой оптимизации, что может существенно ускорить ее решение (см. п. 3 ниже). Впрочем, во многих интересных приложениях отмеченный прием (амплификация), как правило, весьма успешно работает [43, 44], поскольку время работы метода, как правило, оказывается заметно большим, чем расчет значения функции.

Отметим также (следуя А. С. Немировскому), что с помощью концепции неточного оракула (см. п. 3 ниже) мы можем редуцировать задачу с тяжелыми хвостами ||Vf (х, £)||2 и компактным множеством Q к ситуации, когда п.н. ||Vf (х, £)||2 < М (е). Для этого нужно «обрезать» стохастический градиент

Константа М (е) подбирается оптимальным образом, исходя из желаемой точности е. Чем больше М (е), тем меньше смещение (bias) обрезанного стохастического градиента, как следствие, тем точнее можно восстановить решение исходной задачи, но при этом возрастает необходимое число итераций (см. (2), (4), в которые входит константа М = М (е)). Оптимальный выбор этой константы (с точностью до логарифмического фактора) дает приведенные выше оценки.

Все сказанное выше10 обобщается и на другие прокс-структуры [4] (не обязательно евклидовы, когда выбирается прокс-функция d (х) = ||х||2/2), согласно которым осуществляется (как правило, по явным формулам11) «проектирование» на Q. Например, для множества Q = Sn (1) (Sn (R) = 0, г = 1. n, Y^i=1 х% = R> — единичный сим-

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

10В сильно выпуклом случае (если в прямом пространстве выбрана д-норма (¿») и прокс-функция

й (х) > 0) в оценку (4) дополнительно входит фактор ш = вир 2У (х,у) (а Цу — ж||2) > 1, где V (х,у)

11Впрочем, в подавляющем большинстве случаев даже если нет возможности явно решить задачу проектирования, ее можно эффективно решить приближенно [9] (посредством перехода к двойственной задаче малой размерности). Как правило, при таком способе рассуждений необходимо использовать концепцию неточного оракула (см. п. 3), поскольку рассчитать градиент двойственного функционала можно лишь приближенно. Однако все эти выкладки обычно не изменяют по порядку сложность одной итерации метода, основной составляющей которой является расчет (пересчет) градиента или его стохастического аналога. Некоторые тонкости и оговорки тут возникают в случае разреженных постановок задач [43, 44].

чтобы число R2 = maxd (х) /а было минимально возможным. Если Q = ВП (1) — единич-x€Q

ный евклидов шар, то значение R < 1, т.е. не зависит от размерности пространства n, но если Q = ВГ (1) - единичный шар в 1Г норме, то R = Q (n) (т.е. существует такое число X, что при достаточно больших значениях n имеет место неравенство R >%n, причем можно добиться того, что R = О (n)). Как будет видно из замечания 2 (на примере когда Q = В’Г (1)), выбор 1Г нормы не всегда приводит к оптимальным во всех смыслах оценкам (аналогичные примеры нам встретятся и в следующих двух пунктах).

Замечание 1. Стоит обратить внимание на то, что если выбрана евклидова прокс-

структура, то R — квадрат евклидова диаметра Q. При переходе к другой прокс-

структуре в оценках числа итераций в качестве R фигурирует прокс-диаметр Q

(diam ( Q) = maxd (х)), поделенный на константу сильной выпуклости a = a (Q) прокс-x£Q

функции, заданной на Q, относительно выбранной нормы в прямом пространстве. Скажем, в случае выбора KL-прокс-структуры, 1-нормы в прямом пространстве и Q = Sr (г), имеем

R2 = diam(Sr (г))/a (Sn (г)) = г ■ diam(Sr (1)) / (a (Sr (1)) /г) = г2 ■ (lnn)/1 = г2 lnn.

Для евклидовой прокс-структуры размер Q = Sr ( ) равнялся бы 2 2. Отсюда можно сделать вывод (верный и в общем случае), что выбор прокс-структуры имеет целью оптимально учесть структуру множества с точки зрения того, как в итоговую оценку числа итераций будет входить размерность пространства, в котором происходит оптимизация. При гомотетичном увеличении/уменьшении множества оценки числа итераций будут меняться одинаково, независимо от выбранной прокс-структуры. Отметим также, что в формуле (2) для прокс-структуры, отличной от евклидовой, точнее писать не R2 ln , где R2 = г2 lnn (приводим для KL-прокс-структуры), а г2 (lnn + ln (ст-1)) = г2 ln (n/a). В действительности, в оценки скоростей сходимости (в среднем, но не в оценки вероятностей больших уклонений, см. замечание 4) всех упомянутых в данной статье методов (кроме обычного (прямого) градиентного метода и метода Франк-Вульфа) входит не прокс-диаметр множества Q, на котором происходит оптимизация (если Q = Rn прокс-диаметр будет бесконечным), а брэгмановское «расстояние» V (х* ,х0) от решения х* до точки старта хо (часто выбирают хо = arg mind (х), d (х0) = 0, Vd (х0) = 0 [27]), где V (х, у) = d (х) — d (у) — (Vd (у) ,х — у).

Замечание 2. Пусть Q = Вn (1) — единичный шар в д-норме или, в более общем случае, Q содержится в В^п (1). Относительно оптимального выбора нормы и прокс-структуры можно заметить следующее (см., например, [4, 9, 47]): если q > 2, то в качестве нормы оптимально выбирать ||||2 (2-норму) и евклидову прокс-структуру. Определим q’ из 1/ q + 1/ q’ = 1.

Пусть 1 < q < 2, тогда q' >2. Если при этом q’ = o(logn), то оптимально выбирать || У = ||||д, а прокс-структуру задавать прокс-функцией d (х) = 2(д-1) \\х\\2 Во всех этих случаях R2 = О (1). Для q’ > Q (logn), выберем a = 2 logn/ (2 logn — 1), |||| = ||||a, а прокс-структуру будем задавать прокс-функцией d (х) = 2(а-1) ||х|^. В этом случае R2 = О (logn). Не сложно проверить, что для единичного симплекса, вложимого в единичный шар в 1-норме, выбор соответствующих прокс-структур из замечаний 1, 2 приводит к одинаковым оценкам числа итераций в категориях О (). В частности, для случая когда Q = В^ (1), выбор 2-нормы и евклидовой прокс-структуры приводит к оценке (далее в замечании речь идет только об оценке (2)) 1) О (M2;n ln (а-1) /е2) вместо 2) О (M^n ln (а-1) /е2)

Следует, однако, различать задачи стохастической оптимизации и задачи, в которые мы сами искусственно привносим случайность (используя рандомизацию), с целью уменьшения числа арифметических операций на одну итерацию метода [31, 43, 44, 48]. К последнему можно отнести случай, когда (негладкий) выпуклый функционал в задаче является детерминированным, но представляет собой трудно вычислимый интеграл (сумму), зависящую от (оптимизируемых) параметров, который может быть компактно представлен в виде математического ожидания по некоторой простой вероятностной мере. Тогда выгоднее вычислять на каждой итерации метода стохастический градиент, существенно экономя на вычислениях на каждом шаге и лишь немного теряя на логарифмическом увеличении числа шагов ln (ст-1)). Подробнее об этом подходе будет сказано ниже в примере 3. Ярким примером на эту тему является Google problem (PageRank). По-видимому, одними из первых на эту задачу посмотрели в указанном выше контексте А. В. Назин и Б. Т. Поляк в работе [49], см. также [44, 50-52].

Пример 1 (PageRank). Задача поиска вектора PageRank р из уравнения Ртр = р (Р — стохастическая матрица по строкам матрица), сводится [51, 52] к негладкой задаче выпуклой оптимизации (седловой задаче)

max (и, Ртр — р) ^ min . uesn(1y pesn(1)

Перепишем эту задачу в общем виде

min max (у, Ах) , xesn(1) yesn(1)

где матрица А большого размера п х п (вообще говоря, неразреженная) с элементами, ограниченными по модулю числом М = 1. Ключевое наблюдение для решения этой задачи состоит в том [30, 49], что:

где А(г) — г-й столбец матрицы А, вектор х € Sn (1), а с.в. i [х] имеет категориальное распределение с вектором параметров х. Важным следствием является тот факт, что левая часть равенства, А х, вычисляется за О n2 арифметических операций, а выражение, стоящее в правой части под математическим ожиданием, А^ И) — всего лишь за О ( n) арифметических операций. Используя это наблюдение (и аналогичное для умножения матрицы А на вектор-строку слева), можно показать, что (рандомизированный) метод зеркального спуска [30] (с KL-прокс-структурой) и стохастическим градиентом по х, равным А^[x]) (аналогично по у), после

0 ^ nM2 ln (n/a) ^ _ 0 ^ n ln (n/a) ^

элементарных арифметических операций выдает такие х € Sn (1) и у € Sm (1), что

с вероятностью > 1 — a.

Отметим, что в определенных ситуациях (например, при условии n ^ е-2 — типичном для задач huge-scale оптимизации) такому рандомизированному методу потребуется использовать относительно небольшое количество элементов матрицы А за все время работы, в то время как для класса детерминированных алгоритмов потребуется считать как минимум половину элементов матрицы А [3] для = 0.1.

Хочется также отметить, что на задаче из примера 1 можно продемонстрировать большую часть современного инструментария, необходимого для решения задач huge-scale оптимизации. Так, в случае разреженной матрицы А для решения поставленной негладкой задачи выпуклой оптимизации (и многих других) хорошо подходит метод Б. Т. Поляка [2, 51], работающий по нижним оценкам (2) (функционал негладкий) и при этом учитывающий разреженность А при пересчете градиента [51]. Другой подход [50] (задача поиска вектора PageRank сводится к минимизации другого функционала), также нашедший широкое применение [43, 53-55], связан с заменой градиентного спуска на покомпонентный спуск. Такая замена увеличивает в среднем число итераций всегда не больше (а, как правило, намного меньше), чем в n раз, но зато (благодаря разреженности) происходит экономия при пересчете одной компоненты градиента, как правило (но не всегда — особенности возникают в разреженных задачах), в n раз по сравнению с расчетом полного градиента. В результате получается выгода, которая при определенных условиях может сократить объем вычислений в ~ л/n раз (см., например, [43]). Поясним это следующим примером [48], который можно понимать как вариацию неускоренного варианта покомпонентного метода с выбором максимальной компоненты [50].

Пример 2 (разреженный PageRank). Задача поиска вектора PageRank также может быть сведена к следующей задаче выпуклой оптимизации (далее для определенности будем полагать 7 = 1, в действительности, по этому параметру требуется прогонка)

где, как и в примере 1, А = Рт — I, I — единичная матрица, е = (1. 1)т,

При этом мы считаем, что в каждом столбце и каждой строке матрицы Р не более в ^ л/п элементов отлично от нуля (Р — разрежена). Эту задачу предлагается решать обычным градиентным методом12, но не в евклидовой норме, а в 1-норме (см., например, [21]):

Хк+1 =Хк + arg min /(а*) + (V f (Хк) ,h) + L \\h\\1

где L = max ||А||9 + 7 < 3 (А- г-й столбец матрицы А). Для достижения точности

е2 по функции потребуется сделать О (LR2/е2) = О (l/e2) итераций [14]. Не сложно проверить, что пересчет градиента на каждой итерации заключается в умножении АтAh, что может быть сделано за О (s2). Связано это с тем, что вектор h всегда имеет только две компоненты, отличные от нуля (такая разреженность получилась благодаря выбору 1-нормы), причем эти компоненты соответствуют arg min df (хк) /дхг и arg max df (хк) /дхг, что пере-

считывается (при использовании специального двоичного дерева (кучи) для поддержания максимальной и минимальной компоненты градиента [51]) за О (s2 inn) (логарифмический фактор можно ослабить, если использовать, например, фибоначчиевы или бродалевы кучи [48]). Таким образом, общая трудоемкость предложенного метода будет О (n + s2inn/e2), что заметно лучше многих известных методов [52]. Стоит также отметить, что функционал, выбранный в этом примере, обеспечивает намного лучшую оценку \\Ах||2 < £ по сравнению с функционалом из примера 1, который (в варианте [31]) обеспечивает УАхЦ^ < е. Наилучшая (в разреженном случае без, условий на спектральную щель матрицы Р [52]) из известных нам на данный момент оценок О (sinn ln(n/a) / e2) [26, 52] для \\Ах^ может быть улучшена приведенной в этом примере оценкой, поскольку, как уже отмечалось ранее, \\Ах|| 2 может быть (и так часто бывает) в ~ y/ñ раз больше \\Ах^, а s ^ y/ñ.

Заметим, что в решении могут быть маленькие отрицательные компоненты. Также численные эксперименты показали [48], что для достижения выписанных оценок требуется препроцессинг (в нашем случае он заключается в представлении матрицы по строкам в виде списка смежности: в каждой строке отличный от нуля элемент хранит ссылку на следующий отличный от нуля элемент, аналогичное представление матрицы делается и по столбцам). Заметим, что препроцессинг помогает ускорять решение задач не только в связи с более полным учетом разреженности постановки, но и, например, в связи с более эффективной организацией рандомизации [31, 43, 50].

Пример 2 также характерным образом демонстрирует, как используется разреженность (см. также [44, 51, 56]). Обратим внимание на то, что число элементов в матрице Р, отличных от нуля, даже при наложенном условии разреженности (по строкам и столбцам), все

12Выписанная далее оценка скорости сходимости (на число итераций) — неулучшаема с точностью до мультипликативного фактора. Речь идет не об оптимальности метода на классе гладких задач на симплексе, а о том, что конкретно для этого метода такая оценка если и может быть улучшена, то лишь на мультипликативный фактор. Это замечание касается практически всех известных сейчас градиентных методов. Показывается это приблизительно так же (даже еще проще), как и в случае оптимальности оценок на классах [4]: строятся конкретные примеры (семейства) функций.

равно может быть достаточно большим вп. Удивляет то, что в оценке общей трудоемкости это число не присутствует. Это в перспективе (при правильной организации работы с памятью) позволяет решать задачи огромных размеров. Более того, даже в случае небольшого числа не разреженных ограничений вида (аг ,х) = Ьг, г = 1. т = О (1), можно «раздуть» пространство (не более чем в два раза), в котором происходит оптимизация (во многих методах, которые учитывают разреженность такое раздутие не приведет к серьезным затратам), и переписать эту систему в виде А х = , где матрица будет иметь размеры О (п) х О (п), но число отличных от нуля элементов в каждой строке и столбце будет О (1). Таким образом, допускается небольшое число «плотных» ограничений.

Заметим, что если применить метод условного градиента [17] (Франк-Вульфа) к задаче из примера 2, то общая трудоемкость (для точности е2, как и в примере 2) будет [48, 56]

В связи со сказанным выше, заметим, что задача может быть не разрежена, но свойство разреженности появляется в решении при использовании метода Франк-Вульфа, что также может заметно сокращать объем вычислений в постановках аналогичных примеру 2, но с матрицами А, у которой число столбцов на много порядков больше числа строк (см., например, п. 3.3 [11], [57]).

Приведем еще один пример, подсказывающий, как следует решать задачу (3), полученную из (1) с применением идеи метода Монте-Карло.

Пример 3 (рандомизация суммы). Пусть необходимо решить задачу выпуклой оптимизации (или ее композитный вариант, см., например, замечание 6):

где ¡к (х) — негладкие выпуклые функции с ограниченной числом М нормой субградиента, Q — выпуклое замкнутое множество простой структуры (можем эффективно на него проектироваться, согласно заданной прокс-функции) прокс-диаметра К. Введем новую функцию

где £ принимает значения от 1 до N с вероятностью 1/N. Стохастический субградиент функции /(х, £) легко вычислить. Для этого разыгрывается за О (lnN) с.в. £, принимающая значения 1. N с равными вероятностями (см., например, [52]). Затем считается субградиент Д (х) (и выполняется прокс-проектирование на Q). Как уже отмечалось ранее, можно найти (е, ст)-решение так понимаемой задачи (5) за

итераций, со стоимостью одной итерации, равной О (1nN), + затраты на вычисления субградиента Д (х) + затраты на вычисление проекции. Если решать задачу без рандомизации, то число итераций будет О (М2К2/е2Л), строго говоря, здесь М должно быть немного

меньше за счет того, что

но мы считаем, что обе части неравенства одного порядка. Зато шаг итерации будет теперь почти в N раз дороже. И если N ^ 1, это может оказаться существенным.

Приведенную постановку можно распространить на случай, когда взвешивание функций не равномерное (тогда первое разыгрывание с.в. £, имеющей категориальное распределение, или приготовление процедуры рандомизации займет О (Ж), а все последующие О (1пЖ)) и /к (х) := [/к (х, £к)] с равномерно ограниченными (по к, х и £) нормами стохастических субградиентов. При этом все приведенные оценки числа итераций сохранятся. Причем требование равномерной ограниченности норм стохастических субградиентов можно существенно ослабить за небольшую плату (см. выше).

Если на решение задачи (3) теперь посмотреть в контексте описанной рандомизации с !к (х) = f (х, £к) (здесь ^к — не случайная величина, а полученная в методе Монте-Карло к-я по порядку реализация с.в. £), то «все встанет на свои места» в смысле одинаковости (с точностью до логарифмического фактора) двух подходов к решению задачи (1), описанных в начале пункта.

Описанная рандомизация при вычислении субградиента суммы функций, по-видимому, была одной из первых, которые предлагались в стохастической оптимизации [22]. Однако она популярна и по сей день, например, в связи с приложениями к поиску равновесий в транспортных сетях [58-62] и анализу данных [63-65]. В частности, в [11, 43, 59, 6671] в предположении, что все функции в (5) гладкие с константой Липшица градиента Ь, предложен специальный рандомизированный метод (на базе описанного выше способа рандомизации суммы), в котором число вычислений градиентов слагаемых13

О^Ж + шт |ьВ2/е, ^ЖЬВ2/^ (1п(Д//е) + 1п (а-1))^ ,

где Д / разность значения функции в стартовой точке и в минимуме. Эта оценка с точностью до выражения под логарифмом соответствует нижней оценке в классе детерминированных алгоритмов [70, 72]. Если дополнительно имеется еще и ц-сильная выпуклость ( х), то оценку можно переписать следующим образом

О ((V + шт |ь/ц, ^ЖЬ/ц>) (1п (Д//е) + 1п (а-1))

Отметим, что вторая оценка переходит в первую при следующей квадратичной регуляризации. К выпуклому функционалу прибавляется регуляризирующее слагаемое ц \\х||2. В результате функционал становится сильно выпуклым и справедлива вторая оценка на число вычислений градиента. Такая регуляризация изменяет исходную целевую функцию на число, не больше цВ2 /2, и чтобы итоговая погрешность по исходной функции была порядка е, нужно выбирать ц ~ е/В2 и решать регуляризованную задачу с точностью е/2. При подстановке этого значения во вторую оценку числа вычислений градиента последняя переходит в первую оценку.

Отметим также, что сначала (см., например, [55, 68]) получается результат о сходимости

N = N (е) = О ((я + шт |ь/ц, л/ЖЬ/ц^ 1п (Д//е)) , Потом из неравенства Маркова получают оценку вероятности больших уклонений:

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

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

ТРУДЫ МФТИ. 2016. Том 8, № 1 А.В. Гасников, П.Е. Двуреченский, Ю.Е. Нестеров 53 которую переписывают в виде

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

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

При наличии дополнительной структуры у задачи (5) приведенные оценки можно было получить (и даже немного улучшить, например, учитывая разреженность) исходя из рандомизированных покомпонентных методов (например, ЛЬРИЛ или ЛРРИОХ [63] или ЛСИСБ* из замечания 8 [43]) для «двойственной» к (5) задаче [43, 55, 59, 73, 74].15 Заметим также, что в работе [43] показывается, как можно просто получить часть выписанных оценок с помощью метода, работающего по оценкам (8) (см. ниже).

В книге [2] Б. Т. Поляк отмечает, что если рандомизация осуществляется каким-то специальным образом, например, таким, что16

где А > 0 — некоторая малая погрешность, и в точке минимума V / (х) = 0, то приведенные выше оценки (2), (4) можно существенно улучшить. Примеры будут приведены ниже в п. 4 (см. (22)). В частности, в сильно выпуклом случае можно получить геометрическую скорость сходимости. Важно отметить, что при рандомизации, возникающей в покомпонентных спусках, спусках по направлению и безградиентных методах в гладком случае условие (6) выполняется [2, 50, 76]. Мы вернемся к этому кругу вопросов в п. 4. Описанная же выше конструкция (с довольно грубым неравенством Маркова) используется в данном контексте [50, 76] для (точной!) оценки больших уклонений. Причем за счет регуляризации функционала, о которой было сказано выше, все это переносится и просто на гладкий случай без предположения сильной выпуклости.

3. Стохастические градиентные методы с неточным оракулом

В этом пункте мы опишем, что можно получить, если дополнительно известно, что / (х) — гладкая по х функция, с константой Липшица градиента Ь и(или) сильно выпуклая с константой ^ > 0, но вычисление стохастического градиента на каждом шаге происходит с неконтролируемой неточностью 5, вообще говоря, не случайной природы.17

Замечание 3. И гладкости, и сильной выпуклости можно добиться искусственно. Как уже отмечалось в п. 2, сильная выпуклость всегда легко получается регуляризацией функционала в исходной задаче. Как правило, это не дает ничего нового с точки зрения выписанных оценок (и даже может ухудшать эти оценки на логарифмический фактор), но в ряде специальных случаев (см. ниже) это может давать определенные преимущества. Кроме того, такая регуляризация иногда просто необходима для корректности постановки. Это связано с тем, что в общем случае даже для гладких детерминированных выпуклых задач мы можем гарантировать сходимость итерационного метода лишь по функции, но не по аргументу. Для сходимости по аргументу нужна сильная выпуклость функционала,

15Строго говоря, построение двойственной задачи предполагает возможность явного выделения в функционале в виде отдельного слагаемого сильно выпуклого композита — желательно сепарабельного.

16Если рассматривать приложения методов стохастической оптимизации к СТО [32], а в правой части неравенства вместо ||У/(ж)У^ писать ||У/(ж)||У2, то выписанное неравенство будет соответствовать условиям малого шума Цыбакова-Массара, Бернштейна [75].

17Особое внимание таким постановкам стали уделять после выхода книг [2, 33]. В них обстоятельно изучается «влияние помех», в том числе не случайной природы, на методы выпуклой оптимизации.

N (ea) = О ((V + min^L/ß, ^NL/ß>) (in (Af/e) + In (a-1)))

которую и обеспечивают должной регуляризацией (см., например, конец п. 2), при этом сходимость по аргументу имеет место к решению регуляризованной задачи. Идея регуляризации используется в популярном методе двойственного сглаживания [77] (регуляризация двойственной задачи с целью улучшения гладких свойств прямой). В отличие от прямой регуляризации эта техника хорошо работает только для вполне конкретных задач, имеющих определенную (седловую — Лежандрову) структуру (модель), когда исходная задача имеет явное двойственное представление (см. пример 4), введя в которое регуляризацию, можно явно (эффективно) пересчитать, во что превратится исходная прямая задача. Другой пример сглаживания будет приведен в п. 4.

Сформулируем более точно предположения об оракуле, выдающем стохастический градиент, следуя [78, 79].18

Предположение 1. (5, Ь, ц)-оракул выдает (на запрос, в котором указывается только одна точка х) такую пару (Р (х, £), С (х, £)) (с.в. £ независимо разыгрывается из одного и того же распределения, фигурирующего в постановке (1)), что для всех х € ( ограничена дисперсия

\\С (х, О — Е? [С (х, Ш\2

Из недавних результатов [78-87] можно получить общий метод (мы приводим огрубленный вариант оценки времени работы этого метода для большей наглядности) с такими

оценками скорости сходимости :

шп + Ш + N.) , О (ЬВ2ехР (—ХЖ ■ (Ь) *) + И + (*) * >) >.

ш'» (N+1 + + , О (ЬВ2ехР ■ (Ь) *) + И + > .

Этот общий метод есть в некотором смысле «выпуклая комбинация» двойственного градиентного метода (БСМ) и быстрого градиентного метода21 (РОМ) [83, 87], оценки скорости сходимости для которых имеют соответственно вид

18В работе [78] собрано много различных мотиваций такому предположению (определению), обобщающему классическую концепцию ¿-субградиента [2]. В определенном смысле это предположение 1 наиболее общее и одновременно наиболее точно отражающее спектр всевозможных приложений [43, 55, 60-62].

19 Оценки характеризуют достигнутую в среднем точность (по оптимизируемому функционалу) после N итераций. При этом, в случае когда минимум достигается на втором аргументе (выгодно использовать факт наличия ^-сильной выпуклости), под N правильнее понимать не число итераций, а число обращений к 0 (см. [79]). Также заметим, что в метод (например, в размер шагов) не входит требуемое число итераций (или желаемая точность — одно через другое выражается). Таким образом, можно говорить об адаптивности метода. Отметим, что за это не приходится дополнительно платить логарифмическую плату [27]. Отметим также, что при р = 1 метод наихудшим (а при р = 0 наилучшим) способом (среди всех разумных вариаций градиентного метода) накапливает неточность в вычислении градиента. Это переносится и на негладкие задачи (см. далее).

20Насколько нам известно, для всех методов, которые используют только градиент и значение функции (или их стохастические аналоги) накопление шума методом со скоростью Ир6 с р € [0,1] — является общим местом.

21 Отметим, что при В = 0 не улучшаемые оценки, которые дает метод РОМ [11], были установлены Б. Т. Поляком [2] для ряда других многошаговых методов (метод тяжелого шарика, сопряженных гради-

Комбинируя эти два метода, можно непрерывно настраиваться (оптимально подбирая метод, регулируя р £ [0,1]) на шум (известного масштаба). В этой связи также полезно отметить (аналогичный факт имеет место и для покомпонентного варианта FGM [43]), что FGM есть специальная выпуклая комбинация прямого градиентного метода (PGM), оценки скорости сходимости которого совпадают с оценками DGM, и метода зеркального спуска/двойственных усреднений [21, 92] (по-видимому, здесь вместо зеркального спуска можно использовать и метод из работы [93]). Нельзя в этой связи не обратить внимание на то, что комбинация двух методов привела к новому методу, работающему лучше, чем каждый из методов по отдельности. Отметим здесь также недавнюю работу [94], в которой предлагается общий способ получения ускоренных (быстрых) методов.

Вся последующая часть п. 3 будет посвящена обсуждению этих результатов и их окрестностей.

Прежде всего, заметим, что дисперсию у первого аргумента минимума в (7) можно уменьшать в m раз, запрашивая на одном шаге реализацию стохастического градиента не один раз, а m раз, и заменяя стохастический градиент средним арифметическим [11, 31, 79] (в случае тяжелых хвостов у стохастических градиентов лучше пользоваться более робастными оценками, например, медианного типа [4]).22 Это имеет смысл делать, если слагаемое, отвечающее стохастичности, доминирует. Важно, что мы при этом не увеличиваем число итераций, и слагаемое Np5 остается прежним. Отметим, что число вызовов оракула при этом увеличивается, но тем не менее в некоторых ситуациях такой подход может оказаться оправданным. Такая игра используется23 в способе получения второго аргумента оценки (7). В этой связи оценку (7) правильнее переписать следующим образом (здесь N (е) — число обращений к (5, L, р)-оракулу, необходимых для достижения в среднем по функции точности , индекс 1 соответствует просто выпуклому, а индекс 2 сильно выпуклому случаю):

при (условия на допустимый уровень шума, при котором оценки (8) имеют такой же вид, с точностью до О (1), как если бы шума не было)

ентов). Отличие в том, что тогда оценки были установлены локально. Все приведенные в данной статье оценки — глобальные, т.е. не требуют оговорок о близости точки старта к решению, для гарантии нужной скорости сходимости. Заметим также, что техника установления локальной сходимости основана, как правило, на первом методе Ляпунова [2, 88], в то время как глобальной — на втором [2, 89]. При этом функцию Ляпунова можно искать по непрерывному аналогу итерационного процесса — системе дифференциальных уравнений [89]. Скажем, для обычного градиентного метода это будет система [1] (Коши, 1847): dx/dt = — Vf (х). Скорости сходимости у итерационного процесса и его непрерывного аналога могут отличаться. Скажем, непрерывный аналог метода Ньютона сходится за конечное время. Другой пример -метод зеркального спуска [4]. Недавно появилась работа, посвященная и непрерывному аналогу FGM [90], см. также [91].

22Этот прием в западной литературе часто называют «mini-batch» [11].

23Вместе с идеей рестартов [38, 43, 56, 84-87], распространяющей (ускоряющей) практически любой итерационный метод (желательно с явной оценкой необходимого числа итераций N (е) для достижения заданной точности е) на случай сильно выпуклого функционала. Нетривиально здесь то, что при довольно общих условиях при таком распространении сохраняется (и работает уже в условиях сильной выпуклости) свойство оптимальности исходного метода.

Как уже отмечалось, выписанные оценки (7) ((8), (9)) характеризуют скорость сходимости в среднем. Они, с одной стороны, не улучшаемы24 с точностью до мультипликативной константы (см. п. 2 и [4, 47]), а, с другой стороны, достигаются. Все это (неулучшаемость оценок) справедливо и при 5 = 0 и(или) И = 0. При этом в случае И = 0, ц = 0 необходимо считать, что требуемое число итераций для достижения точности удовлетворяет неравенству N (е) < п [4], в противном случае оценки улучшаемы - метод центров тяжести [4, 11], с оценкой числа итераций типа О (п 1п(В/е)), где |/(х)| < В. В терминах больших отклонений возникают оценки, аналогичные тем, которые были приведены в п. 2, см. [87].

Отмеченные результаты переносятся и на прокс-структуры отличные от евклидовой [87]. При этом рассмотрение какой-либо другой д-нормы ( Iя-нормы) в прямом пространстве ( ц > 1), отличной от евклидовой, в сильно выпуклом случае (когда минимум достигается на втором выражении в (7)), как правило, не имеет смысла. Связано это с тем, что квадрат евклидовой асферичности -нормы, который может возникать в оценках числа обусловленности прокс-функции в -норме (это число, в свою очередь, оценивает увеличение числа итераций метода при переходе от евклидовой норме к -норме), больше либо равен 1. Равенство достигается на евклидовой норме. Скажем, для 1-нормы эта асферичность оценивается снизу размерностью пространства [14, 38]. Другими словами, действительно, можно выбирать в сильно выпуклом случае -норму (отличную от евклидовой) и получать оценки на число итераций вида (см. (7), (8) и п. 2)

ц ) Vе )) х,уеяа \\у — х\\1

где Ь и ц считаются относительно д-нормы, а Л2 — брэгмановское «расстояние» от точки старта до решения (см. замечание 1). Однако смысла, как правило, в этом нет, поскольку » > 1, а число обусловленности % = Ь/ц не меньше, чем в случае выбора 2-нормы. Например [38], для функции \\ х\ 22 = х1 + . + х2 в евклидовой норме число обусловленности % = 1, а в 1-норме % = п. Тем не менее выгода от использования не евклидовой прокс-структуры в сильно выпуклом случае может быть, если рассматривать задачи композитной оптимизации, в которых сильная выпуклость приходит от композитного слагаемого (см. замечание 6). Так, в приложениях, описанных в работах [55, 59], в качестве композитного слагаемого возникает сильно выпуклая в 1-норме энтропийная функция. Отметим, что энтропию при этом нельзя использовать в качестве прокс-функции. Другими словами, в данной ситуации нельзя использовать КЬ-прокс-структуру (см. замечание 1), поскольку для нее » = те. Нужно брать (и это можно сделать, см. замечание 2) другую прокс-функцию, соответствующую 1-норме, которая обеспечивает (по-видимому, оптимально возможную) оценку » = О (1пп).

Заметим также, что обычный метод РОМ в не стохастическом сильно выпуклом случае для задач безусловной оптимизации, в действительности, дает оценку (следует сравнить с (8)) [10]: ^

24В нижнюю оценку во втором выражении под знаком минимума при экспоненте вместо ЬН2 входит цВ2, а константа Т = 1 в (7). Впрочем, получить вместо фактора ЬН2 фактор ^Н2 можно аккуратно проанализировав оценки, даваемые с помощью техники рестартов (см., например, [21, 87]).

Замечание 4. Отметим, что пока нам не известно (для произвольной прокс-структуры, отличной от евклидовой) строгое обоснование оценок (7) ((8), (9)) с вероятностями больших отклонений для случая не ограниченного множества Q. В известном нам способе получения оценок вероятностей больших уклонений (см., например, [79, 87]), к сожалению, явно используется предположение об ограниченности множества Q. С другой стороны, для используемых в статье неускоренных методов (кроме Франк-Вульфа и кроме PGM в варианте [21], для PGM в варианте [79] все хорошо) оценки на скорость сходимости обычно получаются в следующем виде [14, 27, 60, 61, 79, 87, 92]:

+ Е Хк (G (Хк, Ск) — V/ (Жк) , х* — Хк) +

или, в случае ускоренных методов (к которым относится РОМ и его производные), в похожем, но немного более громоздком (с большим числом параметров и оценивающих последовательностей). Опуская в правой части V(х*,хN+1), далее оптимально подбирают параметры метода , получают оценку скорости сходимости метода по функции в среднем. Если считать, что ||х* — Хк|| = О (Я), то отсюда также получают оценки скорости сходимости и с вероятностями больших уклонений (используется обобщение неравенства Азума-Хефдинга для последовательности мартингал-разностей [24, 79]). В детерминированном случае соотношение ||х* — Хк|| = 0 (Я) имеет место (всегда в евклидовом случае, и в зависимости от метода в общем случае) ввиду сходимости метода и того, что параметры оптимально подбираются так, что слагаемые V (х*,х0) и ДN одного порядка (отличаются обычно не более чем в 10 раз):

к = 0, . N, если [21] (прокс-диаметр здесь не нужен):

R = max (Уж — х* || : х е Q, f (х) .

Заметим в этой связи, что если в предположении 1 считать

Щ [f (У, 01 — Щ [F (х, 01 — (Es [G (х, 01 ,У — х) < L \\у-х\\2 + М \\у - ж|| + S,

то вместо D в (7) стоит писать М2 + D [95, 96].

Таким образом, например, можно получить оценки (2), (4) из оценки (7). В частности, метод двойственных усреднений и зеркальный спуск (см. п. 2) можно получить из PGM в варианте [79] с неточным оракулом и L = М2/ (25). Но наряду с введенной нами искусственной неточностью оракула, можно допустить, что имеется также реальная неточность оракула. Несложно привести оценки (на базе формулы (7) и ((8), (9))), сочетающие наличие в задаче искусственной и реальной неточности [61].

собственное значение матрицы АТА, Rx = \\х*\\2 = ||(АТА) АТЬII ). Аналогичное можно

сказать и про седловые задачи: для отыскания такой пары ( х, ), что (левая часть этого неравенства всегда неотрицательная)

потребуется не меньше, чем ЩЛ/е ) (Л — максимальный по модулю элемент матрицы А) операций типа умножения Ах и утА. Заметим, что обе выписанные нижние оценки справедливы при условии, что число итераций (операций типа умножения Ах) к < n. Как

следствие, в общем случае даже для гладкой детерминированной сильно выпуклой постановки при наличии всего лишь аффинных ограничений Ах = b нельзя надеяться на быстрое решение. Тем не менее некоторые дополнительные предположения в ряде случаев позволяют ускорить решение таких задач (см., например, [55, 97]).

Замечание 5 (см. также [92]). Задача поиска такого х*, что Ах* = b сводится к задаче выпуклой гладкой оптимизации

f (х) = У Ах — 6||2 ^ min.

Нижняя оценка для скорости решения такой задачи [4] (см. также формулу (7) с 5 = D = 0, р = 1) имеет вид: f (хк) > ^ (LXR^/k2). Откуда следует, что только при k > Q (y/LXRX/e) можно гарантировать выполнение неравенства f (хк) — е2, т.е. ||Ах& — &12 — Заметим, что эта нижняя оценка для специальных матриц может быть улучшена. Причем речь идет не о недавних результатах D. Spielman^ [98] (премия Неванлины 2010 года), а о более простой ситуации. Вернемся к задаче поиска вектора PageRank (примеры 1, 2), которую мы перепишем как

где I— единичная матрица. По теореме Фробениуса-Перрона [99] решение такой системы с неразложимой матрицей Р единственно и положительно х > 0. Сведем решение этой системы уравнений к вырожденной задаче выпуклой оптимизации:

Построим двойственную к ней задачу [9]:

1 2 f 1 2 min ö 1|ж|12 = min max < - ||х||2 + (b - Ах, A) f =

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

Поскольку система Ах = b совместна, то по теореме Фредгольма не существует такого Л, что АтЛ = 0 и (Ь, Л) > 0, следовательно, двойственная задача имеет конечное решение (т.е. существует ограниченное решение двойственно задачи Л*). Зная решение Л* двойственной задачи

(Ь, Л) — — ||АТЛ||2 ^ max, 2 Л

можно восстановить решение прямой задачи (из условия оптимальности по х): х (Л) = АТЛ. Однако важно здесь то, что FGM [10] для этой двойственной задачи дает возможность попутно получать следующую оценку на норму этого градиента [92]:

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

кг=1 , Ly = ffmax (АТ) = ffmax (А) , Ry = 11Л* 12 ,

где можно считать, что Л* — решение двойственной задачи с наименьшей евклидовой нормой. Кажется, что это противоречит нижней оценке ||Ахк — Ш2 > П (y/LXRx/k). Однако важно напомнить [4], что эта нижняя оценка установлена для всех k < п (п - размерность вектора х), и она будет улучшена в результате описанной процедуры, только если дополнительно предположить, что матрица А удовлетворяет следующему условию: Ly Ry < пл/LXR x, что сужает класс, на котором была получена нижняя оценка

Пример 4. Если имеется дополнительная информация о структуре седловой задачи, то можно её использовать для ускорения [14, 100]. Более того, многие современные постановки задач (негладкой) выпуклой оптимизации (в частности, связанные с compressed sensing и 1\-оптимизацией) в пространствах огромных размеров специально стараются представить сед-ловым образом с целью получения эффективного решения (см. работы А. С. Немировского, А. Б. Юдицкого [31, 101, 102]). Далее будет разобран один простой пример (немного обобщающий результаты [78, 79], см. также [92]), демонстрирующий возможности градиентных методов с неточным оракулом в седловом контексте. Рассматривается седловая задача (х е Rn,y е Мт):

где функция G (у) — сильно вогнутая с константой к относительно 2-нормы и константой Липшица градиента Lg (также в 2-норме). Тогда функция f (х) будет гладкой, с константой Липшица градиента в 2-норме Lf = umax (В) /к. Казалось бы, что мы можем решить

задачу минимизации функции f (х) за О ^Y^mäxCB^RXZ^KfiÖj итераций, где е — желаемая точность по функции. Но это возможно, только если мы можем абсолютно точно находить Vf (х) = Ву* (х), где у* (х) — решение вспомогательной задачи максимизации по у при заданном х. В действительности, мы можем решать эту задачу (при различных х) лишь приближенно. Если мы решаем вспомогательную задачу быстрым градиентным методом [14] с точностью 8/2 (на это потребуется О

^ ( Lg(t max (В)RX LfLaRXA

итераций (на итерациях производится умножение матрицы В на вектор/строчку и вычисление градиента G (у)) е-решение задачи минимизации /(х). Отметим, что если не использовать сильную вогнутость функции G (у), то для получения пары (хм,Vn), удовлетворяющей неравенству

потребуется Q (max /е) итераций (см., например, [4, 9, 11]).

При этом вместо энтропии в качестве функции G (у) можно брать любую сильно вогнутую в 1-норме функцию, для которой решение задачи максимизации (вычисление f (х) с точностью е) может быть осуществлено за О (ln (£-1)). В примере с энтропией, для f (х) есть просто явная формула. Точнее, важно то, что есть явная формула25 для оптимального

25Сложность формулы оценивается числом ненулевых элементов в матрице В. При этом считаем, что градиент С (у) рассчитывается быстрее, чем занимает умножение матрицы В на столбец/строку.

решения у* (ж).26 К сожалению, имеется проблема вхождения в оценку необходимого числа итераций неизвестного размера решения ж* задачи минимизации / (ж). Эта проблема решаема [97]. В частности, в случае, когда С (у) имеет ограниченную вариацию на множестве 8т (Щ) (для энтропии эта вариация равна Ку 1пт), можно предложить метод, с оценкой числа итераций О(е-11п (£-1)). В эту оценку уже никак не входит неизвестный размер решения ж*, который может оказаться большим [97]. Далее мы еще вернемся к вопросу о том, как действовать, в случае, когда тот или иной параметр задачи (в данном случае размер решения) априорно не известен.

Отметим, что сильной вогнутости можно добиться и искусственно [77], глава 3 [79], [92, 97]. Подход отмеченных работ приводит к оптимальным для такого класса задач оценкам (с точностью до логарифмического фактора27 1п (£-1)) и позволяет, на самом деле, контролировать точность решения одновременно по ж и по без использования прямо-двойственности в классическом варианте (см. ниже), что может быть полезным в определенных ситуациях [55]. Здесь под оптимальными методами мы имеем в виду методы с проксимальным оракулом. Однако в ряде задач оптимизации огромных размеров оказывается эффективнее использовать линейный минимизационный оракул [103], пришедший из метода Франк-Вульфа (см., например, п. 3.3 [11]). Грубо говоря, суть подхода в том, что сначала вычисляется не / (ж) согласно модели, описанной в примере 4, а в седловом представлении задачи меняется порядок взятия максимума и минимума и вычисляется с помощью линейного минимизационного оракула сначала минимум по ж. Причем это не обязательно делать точно (см. п. 5 § 1 главы 5 [2]). Получающаяся задача максимизации по у уже не будет гладкой, поэтому с учетом сильной вогнутости С (у) здесь молено рассчитывать только на зависимость числа итераций от желаемой точности О (£-1). Получается вроде как хуже, чем раньше. Но тут надо учитывать, как входят размерности п и т, которые могут быть огромными в приложениях, см. п. 3.3 [11], [59, 60, 61, 103]. Удивительным образом, в сложность внутренней задачи при таком подходе (минимизации по ж) при определенной структуре (как правило, связанной с ограничениями симплексного типа и матрицей В, имеющей комбинаторую [103] или сетевую природу [60]) может не входить размерность вектора ж (т.е. п), что позволяет решать задачи колоссальных размеров по п.

Пример 4 был приведен, прежде всего, потому, что он поясняет одно интересное и достаточно современное направление в численных методах выпуклой оптимизации (см., например, [61, 62, 92, 96, 101, 102]). Грубо говоря, это направление можно охарактеризовать, как попытку ввести оптимальную «алгебру» над алгоритмами выпуклой оптимизации. А именно, если требуется оптимизировать функционал (искать седловую точку), который обладает разными свойствами (гладкости, сильной выпуклости, быстроты вычислимости частных производных и т.п.) по разным группам переменных (такие задачи часто в последнее время возникают в разных приложениях, в частности, в транспортных и экономических [58, 60, 61, 62, 104-107]) и(или) сам представляет собой некоторую суперпозицию других функционалов (с разными свойствами; наиболее популярен случай суммы двух функционалов [9, 14, 43, 55, 59, 63, 96, 101, 102]), то хотелось бы получить такую декомпозицию исходной задачи, чтобы правильное сочетание (правильное чередование с правильными частотами) оптимальных методов для получившихся отдельных подзадач позволило бы получить

27Ниже мы обсудим, как можно избавиться от этого логарифмического фактора для задач с явной формулой для у* (х), например, для задач энтропийно-линейного программирования [55, 97].

оптимальный метод для исходной задачи. В ряде интересных случаев такое оказывается возможным (с оговоркой, что оптимальность понимается с точностью до логарифмического фактора). По-видимому, новым в этом направлении является наблюдение, отмеченное в примере 4 (см. также [61, 62, 92]), что при определенных условиях идея оптимального сочетания различных методов для решения одной сложной по структуре задачи оптимизации, может быть реализована на основе концепции неточного оракула.

Другой способ борьбы с дополнительными ограничениями типа равенств или неравенств в задачах выпуклой оптимизации базируется на прямо-двойственной структуре [27] всех обсуждаемых методов (поскольку они строят модель функции [14]). Это означает, что ограничения вносятся во вспомогательную задачу оптимизации, возникающую на каждом шаге метода и отвечающую за проектирование. В результате на каждом шаге решается более сложная задача. Тем не менее если такие вспомогательные задачи можно эффективно решать (что в общем случае также наталкивается на сложности, описанные ранее) с помощью метода множителей Лагранжа (найдя и сами множители), или когда у исходной задачи есть модель (см. пример 4 и [18, 55, 59-62, 77, 92, 97, 110]), то тогда описанные методы позволяют не только эффективно решать исходную задачу оптимизации с ограничениями, но и находить попутно (по явно выписываемым формулам) решение двойственной задачи.

Основная идея работы [27] состоит в том (здесь мы ограничимся рассмотрением детерминированного случая с точным оракулом, выдающим градиент; в стохастическом случае с неточным оракулом см., например, [55] и лемму 7.7 [79]), что метод генерирует в прямом пространстве на итерациях такую последовательность 28, что зазор двойственности

(duality gap) А ( Л, х; N) удовлетворяет условию

где Sn = Е N=o Лк, Лк > 0, поэтому

f ( у ] Лк хк] — min f (х) < е.

Это следует из выкладки

( 1М \ 1М 1М 1′ (ЕХкжч — ?(и) — •(жк) — $(и)) — (жк) ,жк -и»> ■

Аналогичную точность (для двойственной задачи) дает следующая аппроксимация решения двойственной задачи:

Это сразу следует из того, что зазор двойственности оценивает сверху разность между получившимися значениями целевой функции в прямой задаче и двойственной [27], которую мы будем называть двойственным зазором. Эта разность всегда неотрицательна, и на точных решениях прямой и двойственной задачи (и только на них) равна нулю. Заметим, что контроль онлайн-зазора двойственности

28В двойственном пространстве при этом генерируется последовательность соответствующих множителей Лагранжа [27] или, в случае наличия модели у исходной прямой задачи (см. пример 4), последовательность генерируется по явным или расчетным формулам согласно этой модели [18, 55, 59, 92, 110]. Такой подход также позволяет убрать логарифмический фактор в задачах энтропийно-линейного программирования [55, 97] и аналогичных задачах, см. п. 5.2 [110] и [43, 55, 92].

позволяет в случае, когда удается выбрать Ак = 1, получать оценки регрета (псевдоре-грета в стохастическом случае) в задачах онлайн-оптимизации (см. [32, 45] и конец этого пункта). К сожалению, ограничение Ак = 1 существенно сужает класс методов. Скажем, для рассматриваемых в этом пункте быстрых градиентных методов Ak ~ кр. Кроме того, даже если в онлайн-постановке допустить взвешивание с различными весами, все равно требуется, чтобы способ получения оценки на зазор двойственности допускал бы обобщение на онлайн-постановки. Быстрый градиентный метод, например, этого не допускает, что несложно усмотреть из оценок работы [21].

Описанная выше конструкция, основанная на оценке зазора двойственности, работает в случае ограниченного множества Q. В случае неограниченного Q (это типичная ситуация, когда необходимо решать двойственную задачу, по решению которой требуется восстанавливать решение прямой задачи) можно искусственно компактифицировать Q [55, 60, 61,

110]. Однако в большинстве случаев такая компактификация не позволяет очевидным образом оценивать настоящий (не обрезанный) двойственный зазор в исходной задаче, что часто представляется важным ввиду наличия простых явных формул для этого настоящего зазора, и возможности использования контроля зазора двойственности в качестве критерия останова метода. Несмотря на отмеченную теоретическую проблему, на практике проблема оказывается решаемой [55, 59, 60].

Более общий способ оценки разности между получившимися значениями целевых функций в прямой задаче и двойственной базируется на контроле сертификата точности [110,

111] (accuracy certificate), в который наряду с градиентами функционала входят градиенты нарушенных ограничений или в общем случае вектора нормалей к гиперплоскостям, отделяющим хк от множества Q (в ряде постановок «градиенты» стоит заменить на «субградиенты»). Векторы двойственных множителей формируются из соответствующих (сертификату точности) взвешенных сумм векторов нормалей отделяющих гиперплоскостей. Собственно, такая интерпретация двойственных множителей следует из способа обоснования принципа множителей Лагранжа на основе следствия теоремы Хана-Банаха (теоремы об отделимости) [112]. Причем в работе [111] за счет слейтеровской релаксации ограничений (допущения возможности нарушения ограничений на е [9, 97]) получаются оценки скорости сходимости, не зависящие от размера двойственного решения, который может быть большим.

Во многих (транспортно-) экономических приложениях при поиске равновесных конфигураций требуется решать пару задач (прямую и двойственную), см., например, [58-62, 97, 104-109]. Причем интересны решения обеих задач (решения этих задач имеют содержательную интерпретацию и используются при принятии решений/управлении). Если у этой пары задач, на которую можно смотреть, как на одну седловую задачу, есть определенная структура (проявляющаяся, например, в сильной выпуклости функционала по части переменных, наличии эффективно вычислимого линейного минимизационного оракула и т.п.), то описанный выше формализм позволяет развить идею примера 4 таким образом, чтобы одновременно (без дополнительных затрат) получать решения обеих задач. Даже в случае огромного размера одной из этих задач можно надеяться (при эффективном линейном минимизационном оракуле), что эта размерность не войдет в сложность поиска решения прямой и двойственной задачи [59, 60, 103].

В действительности, выбранный в данной статье класс проекционных методов с построением модели функции далеко не единственный возможный способ строить прямодвой-ственные методы. Скажем, уже упоминавшиеся методы условного градиента также являются прямодвойственными [17, 18]. Еще более удивительным может показаться, что пря-модвойственная интерпретация есть, например, у метода эллипсоидов [110]. Более того, в ряде ситуаций мы можем за линейное время (с геометрической скоростью сходимости) находить одновременно решение прямой и двойственной задачи. Причем речь идет не только о конструкциях типа [74], базирующихся на принципе (см. также замечание 6): сопряженная функция к выпуклой функции с липшицевым градиентом — сильно выпуклая, и обратно,

сопряженная к сильно выпуклой функции — выпуклая функция с липшицевым градиентом; но и о более общем контексте [43, 55, 74, 92, 110].

Возвращаясь к сказанному выше в связи с оценками (7) — (10) интересно заметить, что если множество Q С Мга есть шар В™ (К) радиуса К в д-норме29, то нижние оценки (для случая И = 5 = 0) на точность (по функции), которую можно получить после N

Приведенный результат хорошо соответствует тому, что написано в замечании 2 (см. также [114]).

Для q = те иг/ = 1 (гладкий случай) приведенная оценка с точностью до логарифмического фактора будет иметь вид Q (LR2/N). Эта оценка достигается, например, на методе условного градиента Франк-Вульфа [17, 115]31. Исходя из только что написанного и тезиса о неулучшаемости оценок (7) ((8), (9)) (при D = 5 = у = 0, р = 1), может возникнуть ощущение противоречия. Это ощущение дополнительно усиливается примером 2 из п. 2. Действительно, исходя из этого примера, может сложиться ощущение, что проблема выбора прокс-структуры в задаче не очень актуальна, поскольку можно исходить просто из самой нормы. И это действительно так, если мы ограничиваемся не ускоренными градиентными методами (PGM, метод Франк-Вульфа), которые сходятся как 0(LqR^/N) (здесь Rq = R — диаметр множества Q, посчитанный в g-норме, в нашем случае q = те). Если же мы хотим ускориться и достичь оптимальной оценки О (LR2/N2), то уже необходимо существенно использовать прокс-функцию d (х) > 0 со свойством сильной выпуклости относительно выбранной нормы и с константой сильной выпуклости a > 1 [14]. Скажем (в связи с примером 2), квадрат 1-нормы не есть сильно выпуклая функция относительно 1-нормы, т.е. d (х) = ||х|| 1 не может быть прокс-функцией при выборе 1-нормы для симплекса. В классе удовлетворяющих условию 1-сильной выпуклости прокс-функций (относительно

выбранной нормы) подбирается такая, которая минимизирует R2 := maxd (х). Именно это

R2 входит в оценку FGM О (LR2/N2). И как уже отмечалось (см. п. 2), для Q = B^ (R)

Если о выпуклом замкнутом множестве известно только то, что оно содержит (К), то все сказанное далее также остается в силе.

30В случае достаточной гладкости функции f (х) можно выписать следующее представление для константы Липшица градиента (верхний индекс д соответствует выбору нормы в прямом пространстве):

сказанным ранее относительно того, как может меняться М — обычная константа Липшица / (х) — при изменении нормы в прямом пространстве, поясняют, почему в «устойчивые сочетания» эти константы входят таким образом: М2Н2/е2, ЬН2/е. Если ввести «физические размерности», скажем, считать, что f (х) — это рубли (руб), а х — это килограммы (кг), то е [ руб ], Н [ кг ], М [ руб/кг ], Ь [ руб/кг2 ]. Поскольку число итераций N должно быть безразмерной величиной, то возникновение агрегатов М2К2/е2, ЬК2/е вполне закономерно. Аналогичные рассуждения можно провести и для оценок в сильно выпуклом случае. Все это приводит к довольно интересным следствиям [92]. Например, что шаг метода в негладком случае к ~ е/М2, в гладком случае к определяется из соотношения вида (Ш (),]¥() — какие-то функции) Ш (^г = 1. В стохастическом случае (вместо градиента получаем стохастический градиент с

дисперсией а2) из \¥ (к,НЬ,к^ = 1.

31Отметим также, что этот метод допускает обобщение на случай неточного оракула, и неулучшаемость оценок может быть проинтерпретирована с точки зрения сохранения свойства разреженности решения [17]. Это неудивительно, поскольку аналогичный метод (с линейным минимизационным оракулом, см. пример 4) с аналогичными оценками скорости можно получить (см. п. 5.5.1 [9], [57]) из композитного варианта РОМ в концепции неточного оракула (суть метода в том, что в композитном варианте РОМ на каждой итерации решается задача, в которой коэффициент при прокс-слагаемом равен нулю, т.е. оно просто отсутствует).

имеет место следующая оценка на прокс-диаметр В2 := шах^ (ж) = В20 (п). Отсюда, с учетом того, что N — п, получаем, что оценка О [ЬВ2/Ж) и оценка О [ЬВ2п/N2), приводят, в общем-то, к одному результату, но в случае использования РОМ требуется дополнительно искать оптимальную прокс-структуру. Только в таком случае будет совпадение результатов. Более того, также как и в замечании 2, здесь хорошо видно, что при ц > 2 можно ограничиться рассмотрением только евклидовой прокс-структуры для РОМ и евклидовой нормы для метода Франк-Вульфа. В частности, для Q = ВТ (В), действуя так, мы получим для РОМ оценку О (Ь2В2п/Ж2) вместо ранее полученной оценки О В2п/Ж2), соответствующей при N — п неулучшаемой оценке О(Ь^В2/Ж) (здесь мы проставили верхние индексы у Ь, поскольку они различаются). Дальше можно написать все то же по поводу неулучшаемости оценок, что и в конце замечания 2.

Отметим также, что параметры В и р могут быть не известны априорно или процедуры их оценивания приводят к слишком (соответственно) завышенным и заниженным результатам. Это может быть проблемой, поскольку в ряде случаев знание этих и других параметров требуется методу для расчета величин шагов и условий остановки. Из этой ситуации можно выйти за логарифмическое (по этим параметрам) число рестартов метода. Стартуя, скажем, с В = 1 и делая число шагов, вычисленное из оценки скорости сходимости при выбранном В, мы проверяем, выполняется ли для вектора, выдаваемого алгоритмом, условие е-близости по функции (при условии, что мы можем сделать такую проверку). Если условие е-близости не выполняется, то полагаем В := 2В и т.д. Все эти перезапуски увеличат общее число обращений к оракулу лишь в О (1) раз [14, 31, 38]32. Аналогичное можно сказать про33 Ь, М, р и И. Однако, если убрать стохастичность, тогда Ь, М можно не только эффективнее адаптивно подбирать (аналогично правилу Армихо [16] в независимости от того, можем ли мы сделать проверку условия -близости значения функции в текущей точке к оптимальному) по ходу самих итераций (увеличив в среднем число обращений к оракулу не более чем в 4 раза), но и в некотором смысле оптимально самонастраиваться (используя формулу (10)) на гладкость функционала на текущем участке пребывания метода [116]. Это означает, что в детерминированном случае без учета сильной выпуклости функционала существует универсальный метод, работающий по оценкам (8) с Ь, рассчитанной по формуле (10) (в которой 5 берется из (9)), и оптимальным в смысле скорости сходимости выбором параметра V £ [0,1]. Причем выбор V осуществляется не нами заранее исходя из знания всех констант и минимизации выписанных оценок, а самим алгоритмом (здесь выбрано р = 1):

N (е) = inf ‘ 2 2 LvR Х

Это соответствует (с точностью до логарифмического фактора) нижним оценкам [110], выписанным выше для случая ц £ [1, 2]. Отметим, что здесь при определении В используется соответствующая прокс-функция, см. замечание 2. К сожалению, пока не очень понятно,

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

33Впрочем, в детерминированных постановках мы можем явно наблюдать за последовательностью выдаваемых оракулом субградиентов и отслеживать условие на норму субградиентов. Как только наше предположение нарушилось (при этом мы не успели сделать предписанное текущему М число шагов), мы увеличиваем М в два раза и перезапускаем весь процесс с новым значением М. Число таких перезапусков будет не более чем логарифмическим от истинного значения М. Все эти рассуждения с небольшими оговорками (типа равномерной п.н. ограниченности стохастического субградиента) переносятся и на стохастические постановки, в которых наблюдается стохастический субградиент. Для определенного класса задач, в которые неизвестные параметры входят только в критерий останова, но не в сам метод (к таким задачам, например, относится задача поиска равновесия в модели Бэкмнана методом Франк-Вульфа и неизвестной константе Ь) можно обходиться и без перезапусков [60]. Заметим также, что у ряда популярных методов (например, метода зеркального спуска) есть варианты, в которые входит не оценка супремума нормы субградиента (или градиента), а норма субградиента на текущей итерации, которая известна [9, 27, 60].

можно ли что-то похожее сделать с параметром р и с введенным нами в начале этого пункта параметром метода р £ [0,1] и можно ли идеи универсальности (самонастраиваемо-сти) распространить на задачи стохастической оптимизации. Обзор других работ на тему самонастройки алгоритмов в гладком детерминированном случае имеется в [20].

Приведенную оценку можно обобщить, если дополнительно известно, что функция ( ж) р-сильно выпукла. Можно дополнительно к искусственно введенной игре на неточности оракула допустить, что имеет место и настоящая неточность. В этом случае также можно выписать соответствующие оценки [61]. Не играя на выборе V £ [0,1], можно распространить все, что описано выше в этом абзаце на стохастические постановки. Аналогичное можно сделать для стохастических безградиентных и покомпонентных методов с неточным оракулом (см. п. 4 и [43]). Соответствующие обобщающие формулы собраны в работе [117], мы не будем их здесь приводить. Такие обобщения востребованы, например, в связи с приложениями к поиску равновесий в многостадийных моделях равновесного распределения транспортных потоков [58, 59, 61, 62, 107-109]. В основе этих приложений лежит конструкция, изложенная в примере 4, с универсальным методом [116] вместо РОМ для решения внешней задачи.

Выше мы сделали обременительное предположение о возможности выполнять проверку условия -близости по функции. Такое заведомо возможно только при известном значении функционала в точке оптимума. Как правило, такой информации у нас априорно нет. Один из способов выхода из этой ситуации для задач стохастической оптимизации описан в п. 7.7 работы [79]. Другой способ — контролировать зазор двойственности (со стохастическими градиентами). Для применимости этого способа требуется, чтобы числовая последовательность < Хк/51 >1=о не зависела от неизвестных параметров. Во многих задачах, приходящих из транспортных и экономических приложений, нужно одновременно находить решения прямой и двойственной задачи, которые можно явно выписать. В таких случаях имеется эффективный способ проверки условия -близости по функции. Нужно проверить условие е-малости разницы между полученным (приближенным) значением функционалов прямой и двойственной задачи (т.е. двойственного зазора) [59-61, 109].

Отметим также, что в детерминированном р-сильно выпуклом случае, когда в точке минимума ж* выполняется условие34 V/ (ж*) = 0, критерий е-близости по функции может быть переписан в терминах малости рассчитываемого на итерациях градиента:

!(жк) — /* — 1 (IV / (жк)||2 —

В постановках с сильно выпуклой/вогнутой двойственной задачей (этого можно добиться искусственно, вводя регуляризацию в двойственную задачу, см. главу 3 [79] и [92, 97])

также можно оценивать точность решения прямой задачи по точности решения двойствен» 35

ной задачи, применяя к двойственной задаче неравенство

2Ь IV / (жк)||* — /(жк) — и

В частности, это обстоятельство используется в критерии остановки двойственного метода из [97], см. также пример 4 и [55, 92].

Все сказанное выше, по-видимому, переносится в полной мере на задачи композитной оптимизации [9, 14, 78, 119] и некоторые их обобщения, например, [96, 101, 102].

34От этого условия можно избавиться, используя в приведенных далее формулах вместо градиента градиентное отображение [10, 55].

i Не можете найти то, что вам нужно? Попробуйте сервис подбора литературы.

35В замечании 5 (см. также [92]) был приведен пример, когда ||V/ (xfc)||2 = О (к-2). Из выписанного неравенства мы можем гарантировать лишь ||V f (®fc)||2 = О (к-2). Ситуацию можно улучшить, если ре-гуляризовать функционал (см. конец п. 2 и [92, 97]), сделав его сильно выпуклым, и применить FGM [10, 14, 92, 118] к регуляризованной задаче, тогда ||Vf (xk)||2 = О ((lnk)2 /к2) (если использовать, например,

FGM с оценкой числа итераций oly/L/il [In (ßR2/s)]), i — s/R2). В негладком случае ситуация проще, см. [27].

Замечание 6. Композитные задачи имеют вид: f (х) + Xh (х) ^ min, где Л > 0, h (х)

— выпуклая функция простой структуры, скажем, h (х) = ||х||г Хочется, чтобы сложность решения этой задачи всецело определялась только гладкостью выпуклого функционала /(х), а сильная выпуклость — обоими слагаемыми. Если не лианеризовывать функцию h (х) при подсчете на каждой итерации градиентного отображения [14], а просто оставлять это слагаемое как есть, то, конечно, сложность решения вспомогательной задачи на каждой итерации увеличится (впрочем, ввиду простой структуры функции h (х), ожидается, что не намного), зато в оценку необходимого числа итераций уже не будут входить никакие константы, характеризующие гладкость h (х), только константы, характеризующие сильную выпуклость (если имеется). На такие задачи также можно смотреть следующим

образом (принцип множителей Лагранжа): f (х) ^ min . Поскольку функция h (х)

простой структуры, то проектироваться на множество Лебега этой функции несложно.

Отсюда можно усмотреть независимость числа итераций от h (х). Другой способ «борьбы»

с композитным членом h (х) (А. С. Немировский) заключается в переписывании задачи в

«раздутом» (на одно измерение) пространстве: f (х) + у ^ min . Норма в раздутом

пространстве задается как ||(х, у) || = ||х|| + а \у\. Функционал имеет такой вид, что в независимости от гладкости f (х) в оценки супремума нормы субградиента/константы Липшица градиента не будет входить что-либо, связанное с у. В гладком случае все ясно сразу из определения, а в случае негладкой ( х) это связано с тем, что в действительности в оценку необходимого числа итераций входит не супремум нормы субградиента, а супремум нормы разностей субградиентов [25] (см. также начало п. 2). За счет возможности выбирать сколь угодно маленьким а > 0, можно считать независящим от и прокс-расстояние (от точки старта до решения раздутой задачи), входящее в оценку необходимого числа итераций. Таким образом, можно сделать оценку числа итераций независящей от и h ( х). В связи с написанным выше полезно заметить, что гладкость (липшицевость градиента) и сильная выпуклость функционала являются взаимодвойственными друг к другу для задач безусловной оптимизации (константа Липшица градиента переходит в константу сильной выпуклости и наоборот, отсюда, кстати сказать, можно усмотреть, что оценка скорости сходимости для таких задач должны зависеть от отношения L/ß, другой способ понять это -соображения «физической» размерности), что активно используется в приложениях, см., например, [43, 55, 73, 74]. Однако для задач условной оптимизации остается только один переход: двойственная (сопряженная) задача к сильно выпуклой — гладкая (см., например, [77] и замечание 3), обратное не верно даже в случае сильно выпуклой функции h (х). Собственно, мы уже сталкивались с «неравноправностью» гладкости и сильной выпуклости. При рассмотрении универсального метода мы отмечали, что на гладкость можно настраиваться адаптивно, чего нельзя сказать про сильную выпуклость. Замечание 6 немного проясняет (с учетом лагранжева формализма) соотношения между этими свойствами задачи. Впрочем, до окончательного понимания, к сожалению, сейчас еще довольно далеко. Не ясно даже, принципиальны ли эти различия или их можно в перспективе устранить. По-видимому, принципиальны, но строгого обоснования мы здесь не имеем.

Также нам видится, что сказанное выше переносится на седловые задачи и монотонные вариационные неравенства [4, 14]. Причем речь идет не о том, что было описано в примере 4, а о том, как скажется неточность оракула на оптимальные методы для сед-ловых задач и монотонных вариационных неравенств [4, 14]. Ответ более-менее известен: неточность оракула не будет накапливаться на оптимальных методах (в отличие от задач обычной выпуклой оптимизации). Отметим, что концепцию неточного оракула еще необходимо должным образом определить36 — предположение 1 нуждается в корректировке для

36Например, для монотонного вариационного неравенства: найти такой х € Q, что для всех у € Q выполняется 0, достаточные условия на (5, Ь)-оракул будут иметь вид: для любых х,у € Q —5, \\д (у) — д (ж)||+ < L \\х — у У + 5. Вероятно, в ряде ситуаций эти условия можно ослабить (доказательства в этом случае нам не известны) —5 <

данного класса задач. Отсутствие накопления неточностей связано с тем, что для таких задач оценка (7) будет оптимальна (с некоторыми оговорками) при р = 0. Другие р £ (0,1] рассматривать не стоит (такие оценки просто не достижимы). Впрочем, пока про это имеются лишь частичные результаты [96, 101, 102].

В оценку числа итераций для достижения заданной точности решения в описанных методах не входит явно размерность пространства п. Это наталкивает на мысль (подобные мысли, по-видимому, впервые были высказаны и реализованы для класса обычных градиентных методов в кандидатской диссертации Б. Т. Поляка [1], см. также [2, 15]) о возможности использовать эти методы, например, в гильбертовых пространствах [16, 42]. Оказывается это, действительно, можно делать при определенных условиях (см., например, [117] в контексте использованных в данной работе обозначений). В частности, концепция неточного оракула позволяет привнести сюда элемент новизны, существенно мотивированный практическими нуждами — принципиальной невозможностью (в типичных случаях нет явных формул) решать с абсолютной (очень хорошей) точностью вспомогательную задачу на каждом шаге градиентного спуска. Например, решение такой вспомогательной задачи для класса задач оптимального управления со свободным правым концом приводит к двум начальным задачам Коши для систем обыкновенных дифференциальных уравнений (важно, чтобы СОДУ для фазовых переменных и сопряженных решались, скажем, методом Эйлера, на одной и той же сетке), которые необходимо решить для вычисления градиента функционала [16]. Однако в действительности почти все практически интересные задачи (за редким исключением, к коим можно отнести класс ляпуновских задач [112]) в бесконечномерных пространствах не являются выпуклыми, поэтому здесь имеет смысл говорить лишь о поиске локальных минимумов (локальной теории) [120]. Если ограничиться неускоренными методами (например, PGM), то можно показать, что при весьма общих условиях эти методы могут быть использованы в гильбертовом пространстве в концепции неточного оракула и для невыпуклых (но гладких) функционалов, причем с аналогичными оценками скорости сходимости (отличие от выпуклого случая будет в том, что метод сходится лишь к стационарной точке (локальному экстремуму), в бассейне притяжения которой окажется точка старта). Заметим, что задачи оптимального управления можно численно решать, построив соответствующую (аппроксимирующую) задачу оптимального управления с дискретным временем, что приводит к конечномерным задачам, для решения которых можно использовать конечномерный вариант PGM в невыпуклом случае (с точным оракулом). Этот путь, как правило, и предлагается в большинстве пособий (см., например, [16]). Однако при таком подходе мы должны уметь (по возможности точно) решать сложную задачу оценки качества аппроксимации исходной задачи оптимального управления ее дискретным по времени вариантом. Более теоретически обоснованный способ рассуждений, по сути, приводящий к необходимости решать все те же конечномерные задачи, заключается в рассмотрении исходной задачи оптимального управления и ее решения бесконечномерным вариантом PGM в невыпуклом случае (с неточным оракулом). Неточность оракула существенна. Поскольку на каждой итерации этого градиентного метода необходимо решать две задачи Коши для СОДУ, что в общем случае можно сделать лишь приближенно, но с лучшим контролем точности, чем при подходе с дискретизацией задачи оптимального управления. Отметим, что во многих «физических» приложениях схема Эйлера имеет хорошие теоретические свойства сходимости (устойчивости). Связано это с тем, что на оптимальном режиме, как правило, наблюдается некоторая стабилизация поведения системы управления, что приводит к устойчивости якобиана прямой и обратной системы дифференциальных уравнений.

Покажем в заключение, как приведенные результаты переносятся на задачи стохастической онлайн-оптимизации. Для этого напомним вкратце, в чем состоит постановка задачи (см., например, [9, 26, 32, 45, 121-126]). Требуется подобрать последовательность37

37Если Q = и на это множество сложно проектироваться, то можно обобщить, сохранив оценку (11), конструкцию прямодвойственного метода из работы [111] (см. также [44]) на онлайн-контекст с таким множеством Q.

£ Q так, чтобы минимизировать псевдорегрет:

л £% [л (xk, — ssiig л [лЮ

на основе доступной информации

Методом условного градиента как найти вспомогательное приближение

33. Алгоритм метода условного градиента

Теорема3

Метод условного градиента

OPTIMIZATION OF PARAMETERS OF AERODYNAMIC DEVICE FOR FORMING A NONWOVEN FABRIC BY THE CONDITIONAL GRADIENT METHOD

Текст научной работы на тему «ОПТИМИЗАЦИЯ ПАРАМЕТРОВ АЭРОДИНАМИЧЕСКОГО УСТРОЙСТВА ФОРМИРОВАНИЯ НЕТКАННОГО ПОЛОТНА МЕТОДОМ УСЛОВНОГО ГРАДИЕНТА»

Стохастические градиентные методы с неточным оракулом Текст научной статьи по специальности «Математика»

Аннотация научной статьи по математике, автор научной работы — Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е.

Похожие темы научных работ по математике , автор научной работы — Гасников А.В., Двуреченский П.Е., Нестеров Ю.Е.

Текст научной работы на тему «Стохастические градиентные методы с неточным оракулом»

Добавить комментарий Отменить ответ