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

9

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

которая является приближением разности f(x)- f(x (k) )c точностью до величины о(||х- х к) ||).

Пусть х (к) — решение вспомогательной задачи максимизации функции (46) при ограничениях (22).

Следующее приближение х ( k+1 ’ к оптимальному решению исходной задачи (21)-(22) построим по формуле

x (k+1) = x (k) +h (k) (x (k) -x (k) ), (47)

в которой величину шага смещения h ( k> выберем как

где h (k) выбирается из условия наибольшего роста целевой функции f(x)npn перемещении из точки х ( k> в точку

_Y(k) , iT(k)/_?(k) _ (k) Л I» 11 I A A I •

Тогда, поскольку множество допустимых решений выпукло, h (k) g [0;1], точка х (к+1) (47) останется допустимым решением.

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

ПРИМЕР 2. Требуется найти приближение к оптимальному решению задачи выпуклого программирования (38)-(39) из примера 1, для чего провести три первые итерации метода условного градиента, выбрав в качестве начального приближения вектор

Решение. Как было показано в примере 1, начальное приближение

является допустимым решением.

1-й шаг.

(0) j,(x- х (0) )1 = 14( Xj — 1 )+0( х₂ — 8 ) — 14xj -14 —>max,

Об оценке скорости сходимости проекционно-итерационного метода решения задачи минимизации с ограничениями Текст научной статьи по специальности «Математика»

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

Похожие темы научных работ по математике , автор научной работы — Гарт Л.Л.

Текст научной работы на тему «Об оценке скорости сходимости проекционно-итерационного метода решения задачи минимизации с ограничениями»

Динамические системы, том 2(30), No. 3-4, 211-225 УДК 519.8

Об оценке скорости сходимости проекционно-итерационного метода решения задачи минимизации с ограничениями

Днепропетровский национальный университет им. О. Гончара, Днепропетровск 49044. E-mail: ll_hart@mail.ru

Аннотация. Рассматривается вопрос об оценке скорости сходимости проекционно-итерационно-го метода, основанного на методе условного градиента, для решения задачи минимизации с ограничениями в гильбертовом пространстве и применении названного метода к решению задач оптимального управления гиперболическими системами. Метод позволяет заменить исходную экстремальную задачу некоторой последовательностью вспомогательных аппроксимирующих ее экстремальных задач, заданных в пространствах, изоморфных подпространствам исходного пространства, и для каждой из «приближенных» задач находить с помощью метода условного градиента лишь несколько приближений, последнее из которых использовать как начальное приближение для следующей «приближенной» задачи. Исследована эффективность предложенного подхода на примере решения конкретной задачи.

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

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

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

Ритца или Галеркина и т.д., для приближенного вычисления интегралов используют формулы численного интегрирования [10]. В результате исходная задача оптимального управления заменяется некоторой последовательностью вспомогательных аппроксимирующих ее экстремальных задач. Общефункциональный подход позволяет рассматривать различные проекционные методы с единой точки зрения, поскольку в основе всех этих методов лежит одна и та же идея, заключающаяся в том, что исходная (точная) экстремальная задача, рассматриваемая в каком-то сложном пространстве, аппроксимируется последовательностью «приближенных» экстремальных задач, заданных в подпространствах исходного пространства (либо в некоторых пространствах, изоморфных им). При этом последовательность точных решений «приближенных» задач объявляется последовательностью приближений к решению исходной задачи.

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

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

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

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

2. Основное содержание

2.1. Постановка задачи

Пусть на некотором множестве П вещественного гильбертова пространства H задан ограниченный снизу функционал F(и):

Для решения задачи минимизации F(и) на П

F(и) ^ inf, и е П С H (2)

аппроксимируем функционал F(и) последовательностью более простых «приближенных» функционалов Fn(ün), n =1,2, . , заданных на некоторых множествах ün вещественных гильбертовых пространств Hn соответственно. Будем считать, что пространства Hn изоморфны

подпространствам Hn исходного пространства (H\ С H2 С . С Hn С . С H) и Фп — линейный ограниченный оператор, ставящий во взаимно однозначное соответствие каждому элементу ип е Hn элемент Hn е Нп, причем

где C = const > 0; Ф-1 — оператор, осуществляющий обратное отображение Hn на Hn.

что множества Hn С Hn имеют вид

Заметим при этом, что если исходное множество П ограничено в H, то из ограниченности линейного оператора Фп и условия (3) немедленно вытекает ограниченность каждого из множеств Qn в Hn (n = 1, 2. ).

В дальнейшем будем предполагать, что функционалы Fn(Hn), n = 1, 2. для любых Hn е Qn связаны с исходным функционалом F(и) условием близости

\Fn(un) — F(Ф-1 йп)\< 13п, (4)

где [5п = const > 0, Un ^ 0 при n ^ то.

Для каждого из «приближенных» функционалов Fn(Un), n = 1, 2. будем рассматривать задачу минимизации на соответствующем множестве Un:

Fn(un) ^ inf, un Е Qn С Hn, n = 1, 2. . (5)

Отметим, что из условия близости (4) и ограниченности снизу исходного функционала вытекает соотношение

F* — bn < F(Ф-Un) — Ьп < K(un), n =1, 2. (6)

для любых ün £ ün, откуда, в частности, следует ограниченность снизу на ün каждого из функционалов Fn(ün):

inf Fn(ün) = F* > — ж, n = 1, 2. .

В работе [12], содержащей научные результаты автора, проведены исследования проекционно-итерационного метода решения задачи минимизации (2), основанного на приближенном решении задач минимизации (5) с помощью метода условного градиента. При этом для каждого из «приближенных» функционалов Fn(ün), n =1,2. на множестве ün названным итерационным методом находится лишь несколько приближений ü^ £ ün, k — 1, 2. kn (kn < K целое положительное число) и на основании последнего из них строится начальное приближение для минимизации следующего функционала Fn+ 1(ün+1) на множестве ün+\. Доказано при определенных условиях, что последовательность приближений <Ф-1 ü(nkn)>n=i выступает в качестве минимизирующей для исходного функционала F(и) на множестве Q С H, а также в качестве последовательности приближений к точке и* £ Q минимума F(и) (если такая точка существует).

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

2.2. Метод решения

Предположим, что каждый из «приближенных» функционалов Fn(ün) непрерывно дифференцируем в смысле Фреше на множестве Qn С Hn (n = 1, 2. ). В качестве начального приближения в проекционно-итерационном процессе возьмем некоторый элемент ü10) £ Ü1. Следуя [4], если уже известно приближение Hn ) £ Hn (k = 0, 1. , kn — 1, n = 1, 2. ), то возьмем главную линейную часть

Hn ) (ün) = (Fn (Hn ) ) , ün ün ) ) , ün £ Hn

приращения Fn (ün) — F^ü^) = (Fn (ü^), ün — ü(n'))+ o(|| ün — ü^W^) и определим вспомогательное приближение и^ £ ün из условия

Fünk)(uik)) = min, ünk)(ün) = min (Fn(üP),ün — ünk)). (7)

Если множества Qn замкнуты, ограничены и выпуклы в гильбертовых пространствах Hn (n = 1, 2. ), то в силу непрерывности линейного (и тем более, выпуклого) функционала Fhk (ün) такой элемент ип^ £ ün существует на основании теоремы 6.1.4 из [4]. При этом, очевидно,

ünk)(иnk)) = min Fnk)(ün) < Fnk)(ünk)) = 0. (8)

ипк+1) = ипк) + &пк)(ипк) — ипк)), к = 0, 1. кп — 1; (9)

где величина аП (0 < аП < 1) определяется так:

-дПК^) = min 1 дПк\ап), д^б) = F^itf + бп^ — ù^)). (11)

Для выпуклого множества Qn, очевидно, будет иП+1) G ùn при всех значениях

Теорема 1 ([12]). Пусть функционал F (и) определен на выпуклом замкнутом ограниченном множестве Q гильбертова пространства H, а функционалы Fn(ùn) — соответственно на выпуклых замкнутых .множествах Ùn гильбертовых пространств Hn (n =1,2, . ). Пусть Fn(ùn) G C1(Ùn), n =1,2, . и для каждого из указанных номеров n градиент F'n(ùn) на множестве Qn удовлетворяет условию Липшица

F (ùn) — Fn (vn)\\Ën < L\\ùn — Vn\\Ën, L = const > 0 (12)

при всех ùn,vn G Qn. Пусть выполнены условия (1) и (4), причем Y1 ùn <

о?п < ж. Тогда последовательность приближений <й(п"'1>'^)=1, удовлетворяю-

щая условиям (7), (9)-(11), существует и для всех к = 0, 1. кп — 1

Епк)(ипк)) = (Еп(ипк)),ипк) — ипк)) ^ 0 (п ^ж)

при любом выборе й^ Е и1.

Теорема 2. Пусть сохраняют силу все условия теоремы 1. Пусть, кроме того, функционалы F(и) и Fn(ün), n =1,2, . выпуклы на Q С H и ün С Hn соответственно, F (и) Е C (Q) и выполнено условие (А): для каждого и* Ей такого, что F(и*) = F*, существует последовательность элементов <ün>'tt=1, ün Е ün, такая, что lim Ф-1 ün = и*. Пусть ü^ Е й1 выбрано произвольно и последова-

тельность 1 ст,ределена согласно условиям (7), (9)-(11). Тогда

lim Fn(ünk)) = F* (13)

для всех k = 1, 2. kn, последовательность <Ф-1 ün"'l>tt=1 является минимизирующей для F(и) и любая ее слабая предельная точка есть точка минимума F(и) на , причем в случае единственности точки минимума к ней слабо сходится вся последовательность <Ф-1 ün")>^°=1. Справедлива оценка

где an = M П Qj + C2D2-£ а^Ц qj + ü П Qj + 2ßn, Qn = ^ . , ,

j=2 2 i=2 j=i i=2 j=i+1 1 + ankn

M > 0 — постоянная, не зависящая от n, D — диаметр множества Q.

Доказательство теоремы 2. Выпуклые непрерывные функционалы F(и) и Fn(ün), n =1,2, . на замкнутых ограниченных выпуклых множествах Q и Qn гильбертовых пространств H и Hn соответственно достигают на них своей точной нижней грани [4]:

inf Fn (ün) = Fn* = Fn(ü*n), n =1, 2. ,

причем из непрерывности F(и) на Q, условий (А) и (4) вытекает [2], что

Так же, как в работе [4], для выпуклого функционала Fn(ün) Е C^ ün) на выпуклом множестве ün, n =1,2, . с помощью условия (7) можно получить

0 < Fn(ünk+1)) — Fn(ü*n) < Fn(ünk)) — Fn(ü*n) < (Fn(ü(nk)), ünk) — ü*n) =

= -Fnk)(ü*n) <-Fnk)(unk)), k = 0, 1. kn — 1.

На основании этого соотношения и оценки (6) будем иметь

¡Fn(ünk)) — F*\ < \Fn(ünk)) — Fn(ü*n)\ + \Fn(ü*n) — F*\ < -Fnk-1)(ünk-1))+ ßn (15)

для всех k = 1, 2. , kn, n = 1, 2, . Поскольку ßn ^ 0 при n ^ ж ив силу теоремы 1 F'hk ^(u* ^ ^ 0 при n ^ ж для всех k =1,2. , kn, то, переходя к пределу в неравенстве (15), получаем предельное соотношение (13).

Далее, из очевидного равенства

F (Ф-1 Unkn)) — F * = F (Ф-1 Hnkn)) — K(rtnkn)) + K(Hnkn)) — F *, n =1, 2. (16)

с учетом условия близости (4) и неравенства (15) можно получить

0 < F(Ф-1 Ukn)) — F* < -Hnkn

1)) + 2ßn, n =1, 2. , (17)

откуда при n ^ ж вытекает предельное соотношение lim F(Ф-1 йп"^) = F*,

В силу теоремы 6.1.2 из [4] выпуклое замкнутое ограниченное множество П в гильбертовом пространстве H слабо компактно, поэтому существует хотя бы одна подпоследовательность <Ф- Un" последовательности <Ф-1 Un"^>^=1 е П, которая слабо сходится к некоторому элементу v* е П. Поскольку выпуклый непрерывный функционал F( ) на выпуклом множестве С H слабо полунепрерывен снизу [4], то

F* = lim F(Ф-1 п(к")) = lim F(Ф-U^4)) > F(v*) > F*, nг

т.е. F(v*) = F*. Если F(и) достигает своего минимума в единственной точке и* е е П, то вся последовательность <Ф-1 Uk"")>c^=1 слабо сходится к и*. Докажем оценку (14). Обозначим через

D = sup \\и v\\h, Dn = sup \\Un — Vn\\ü" диаметры множеств С H

и Un С Hn (n — 1, 2. ) соответственно. Поскольку множества Пи Qn ограничены, то D < ж, D n < ж и, кроме того,

где с > 0 — константа из неравенства (3) [12].

Так же, как в [4], при минимизации функционала Fn(Un) на множестве Qn С Hn методом условного градиента с учетом условий (8), (11), (12) можно получить

Fn(Un )) — Fn(Un )) < Oin(F n (Un )), Un ) — Un )) + 2 an\\Un ) — Un k)\jj" <

при всех k = 0,1. , kn — 1, 0 < an < 1. Пользуясь этим неравенством, запишем для произвольного n > 1 :

n n — n- 1 n- 1 n n — n n n n — n- 1 n- 1

< an / J \Fn ( ün )\ + 2 с D ankn + \Fn( Un ) Fn-1( Un-1 ) k=0

В силу условия близости (4) и формулы (10) будем иметь

Рп(й^) — к- ) = Рп№) — р(ф-1 и^) + р(ф-1 йШ)) — Р(ф-\ й

йп-и П> 1, поэтому для всех указанных номеров п будет

1ип(йПк")) — Рп-1(йПк—1)) < -йп^ \РПк)(иПк))1 + 2 С2П2а2пкп + йп + йп-1.

С помощью этого неравенства и условия близости (4) можно получить

р (Ф-1 йпкп)) — р (Ф-\ йпкп-1)) = р (Ф-1 йк)) — К(йпкп)) + К(йпкп))-

< -an \Fnk)(unk))\ + -C2D2a2nkn + 2ßn + 2ßn-1, n> 1,

или, с учетом обозначения ап = Р(Ф- 1 йпп^) — Р*,

ап — а-1 < -йп^ \йпк)(ипк))\ + ^С2В2а2пкп + 2/п + 2/3—1, п> 1. к=0

Поскольку Рпк (ипк) ^ 0 с ростом к при каждом фиксированном п [4], то при условии \рпк)(ип:))\ > \Рпкп-1)(ип:п-1))\, к = 0, 1. ,кп — 1, получим

ап — а-1 < -апкп\Рпкп-1) (ипкп-1))\ + ЬС2В2а^п + 2/п + 2вп-1, п> 1.

Согласно оценке (17) \Рпп 1 (ипп ^^ > ап — 2/п, поэтому

Решение этого неравенства относительно ап дает

0 < ап < 1 + а к (а-1 + ЬС2В2а2пкп + 2Р—1) + 2/п, п> 1. (18) айпкп 2

an-1 — an > ankn(an — 2ßn) — — C2D2a2nkn — 2ßn — 2ßn-1, n> 1.

Принимая в формуле (18) обозначение qn =-—, получаем

an < Qn(an-1 + 2ßn-1) + —C2D2qna2nk,n + 2ßn <

< QnQn-1(an-2 + 2ßn-2) + —C2D2 (qnQn-1a2n_1kn-1 + qna2nkn) + 4qnßn-1 + 2ßn < n — n n n-1 n

ß1)W qj + — C 2D2Y; a*kil[ qj + 4^ ßi П Qj + 2ßn, n> 1.

j=2 i=2 j=i i=2 j=i+1

Наконец, пользуясь теоремой 6.2.3 из [4], условием (4) и оценкой (6), находим

«1 + 2й1 = Е (Ф-1 й[к1)) — Р1(й[к1)) + Р1(й[к1)) — Р* +

Таким образом, справедливость оценки (14) установлена. Остается заметить, что 0 < дп =-—— < 1 при всех п > 1, так что ап — 0 при п — ж.

В самом деле, при дп < д < 1, 1 < кп < К (п = 1, 2. ) для величины ап из (14) будем иметь

0 < ап < Мдп—1 + СС2В2К^^ а2гдп—г+1 + йгдп

Если числовая последовательность ап — а (0 < а < 1) при п — ж, то для

любого малого е > 0 найдется номер М1(е) такой, что для всех п > М будет \ап — а\ < е и тогда

Аналогично, для сходящейся последовательности [5п — 0 (п — ж) при том же е > 0 найдется номер М2(е) такой, что для всех п > Ы2 будет йп < е и

Обозначим через N = тах<М1, М2>. Тогда с учетом двух последних неравенств соотношение (19) перепишется в виде

Устремляя здесь n ^ ж, будем иметь:

О < lim an< C2Ü2К- а2

Отсюда при а — 0 получаем, что ап — 0 при п — ж, что и требовалось доказать. □

Замечание 1. В условиях теоремы 2 может быть получена оценка, характеризующая скорость сходимости последовательности ^=1 к F*. А именно, из соотношения (16) с учетом условия близости (4) и оценки (14) следует

Теорема 3. Пусть выполнены все условия теоремы 1. Пусть, кроме того, F(й) — непрерывный сильно выпуклый функционал на Q С H, а функционалы Fn(Un) выпуклы на Qn С Hn, n = 1, 2, . соответственно и выполнено условие (А). Тогда последовательность <Ф-1йп"где йпП определяются согласно условиям (7), (9)-(11), сходится к единственной точке й* .минимума F(й) на Q по норме пространства H при любом выборе й^ Е Q и справедлива оценка

\\Ф-1й^п) — й*\\2н < — an, n > 1, (20)

где an > 0 определяется (формулой (14), X = const > 0.

Доказательство теоремы 3. Из сильной выпуклости непрерывного функционала F(й) следует его выпуклость и ограниченность снизу на замкнутом выпуклом множестве Q С H [4], так что выполняются все условия теоремы 2. Кроме того, F(й) достигает минимума на Q в единственной точке й* и при этом справедливо неравенство

K4kn) — й*\\н < — (F (Ф- tinkn)) — F (й*)) , n =1, 2. X

где х > 0 — константа сильной выпуклости F(й) на Q [4]. Отсюда в силу теоремы 2 вытекает сходимость <Ф-1йпП>^=1 к й* по норме пространства H. Оценка (20) является следствием последнего неравенства и оценки (14). □

2.3. Применение метода к решению задачи оптимального управления

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

Пусть имеется однородная упругая гибкая струна 0 < s < l, один конец которой свободен, на другой ее конец действует внешняя сила p = p(t) и, кроме того, к каждой точке струны также приложена внешняя сила f = f (s,t). Требуется,

управляя указанными внешними силами, к заданному моменту времени Т привести струну в состояние, как можно меньше отличающееся от некоторого заданного состояния (например, состояния покоя) [5].

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

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

UPD. В комментариях пишут, что на некоторых браузерах и в мобильном приложении формулы не отображаются. К сожалению, не знаю, как с этим бороться. Могу лишь сказать, что использовал макросы «inline» и «display» хабравского редактора. Если вдруг знаете, как это исправить — напишите в комментариях, пожалуйста.

Примечание от автора

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

Постановка задачи

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

Немного математики

Еще в 17 веке Пьером Ферма был придуман критерий, который позволял решать простые задачи оптимизации, а именно, еcли — точка минимума , то

где — производная . Этот критерий основан на линейном приближении

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

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

Стоит отметить, что указанные условия являются необходимыми, но не достаточными, самый простой пример — 0 для и

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

Квадратичные функции

Для экономии места (да и чтобы меньше возиться с индексами) такую функцию обычно записывают в матричной форме:

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

Зачем я об этом рассказываю? Дело в том, что квадратичные функции важны в оптимизации по двум причинам:

1. Они тоже встречаются на практике, например при построении линейной регрессии методом наименьших квадратов
2. Градиент квадратичной функции — линейная функция, в частности для функции выше

Или в матричной форме

Полезные свойства градиента

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

Попробуем пока решить более простую задачу: дана точка , найти точку такую, что . Давайте возьмем точку рядом с , опять же используя линейное приближение . Если взять , то мы получим

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

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

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

Градиентный спуск

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

для всех , то гарантирует убывание .

Анализ для квадратичных функций

где — единичная матрица, т.е. для всех . Если же , то получится

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

Модификации градиентного спуска

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

Инерционные или ускоренные градиентные методы

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

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

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

Метод Чебышева

где — некоторый многочлен степени . Почему бы не попробовать подобрать таким образом, чтобы было поменьше? Один уз универсальных многочленов, которые меньше всего отклоняются от нуля — многочлен Чебышева. Метод Чебышева по сути заключается в том, чтобы подобрать параметры спуска так, чтобы был многочленом Чебышева. Есть правда одна небольшая проблема: для обычного градиентного спуска это просто невозможно. Однако для инерционных методов это оказывается возможным. В основном это происходит из-за того, что многочлены Чебышева удовлетворяют рекуррентному соотношению второго порядка

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

Метод сопряженных градиентов

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

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

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

Метод Нестерова

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

Стохастический градиентный спуск

— это некоторый случайный параметр, на который мы не влияем, но при этом в среднем мы идем против градиента. В качестве примера рассмотрим функции

Если принимает значения равновероятно, то как раз в среднем — это градиент . Этот пример показателен еще и следующим: сложность вычисления градиента в раз больше, чем сложность вычисления . Это позволяет стохастическому градиентному спуску делать за одно и то же время в раз больше итераций. Несмотря на то, что стохастический градиентный спуск обычно сходится медленней обычного, за счет такого большого увеличения числа итераций получается улучшить скорость сходимости на единицу времени. Насколько мне известно — на данный момент стохастический градиентный спуск является базовым методом обучения большинства нейронных сетей, реализован во всех основных библиотеках по ML: tensorflow, torch, caffe, CNTK, и т.д.

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

Субградиентный спуск

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

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

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

1. Допустим мы начали из точки .
2. Шаг субградиентного спуска:

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

Proximal методы

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

В этом случае — это проекция на множество , то есть «ближайшая к точка множества ». Таким образом, мы ограничиваем градиентный спуск только на множество , что позволяет решать задачи с ограничениями. К сожалению, вычисление проекции в общем случае может быть еще более сложной задачей, поэтому обычно такой метод применяется, если ограничения имеют простой вид, например так называемые box-ограничения: по каждой координате

Заключение

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

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

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

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

. (1)

Легко увидеть, что при сделанных выше предположениях задача (1) имеет решение, обозначим его . Далее, положим .

Если , то согласно определению точки имеем . Таким образом, в точке выполняется необходимое условие условного минимума функции на множестве . Если, кроме того, функция – выпуклая на множестве , то это условие также и достаточно ([1], 2.6, теорема 5).

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

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