ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2014, том 54, № 2, с. 208-223
УДК 519.658
РЕЛАКСАЦИОННЫЙ МЕТОД МИНИМИЗАЦИИ ГЛАДКОЙ ФУНКЦИИ НА ОБОБЩЕННОМ СЕГМЕНТЕ СФЕРЫ
© 2014 г. А. М. Дуллиев
(420111 Казань, ул. К. Маркса, 10, КНИТУим. А.Н. Туполева (КАИ)) e-mail: dulliev@yandex.ru Поступила в редакцию 14.01.2013 г.
Рассматривается минимизация гладкого функционала на обобщенном сферическом сегменте в конечномерном евклидовом пространстве. Предлагается релаксационный метод минимизации, заключающийся в последовательном проектировании антиградиента на вспомогательные множества более простой структуры. Показывается, что при некоторых естественных предположениях такой метод сходится к стационарной точке. Библ. 6. Фиг. 1.
Ключевые слова: невыпуклые задачи оптимизации, метод проекции градиента, релаксационный метод, сходимость, условие Липшица, сферический сегмент, касательный конус.
DOI: 10.7868/S0044466914020045
1. ВВЕДЕНИЕ
Рассмотрим задачу минимизации гладкой функции в конечномерном евклидовом пространстве :
f(x) ^ min, x е X с R". (1.1)
В зависимости от структуры допустимого множества X существует несколько подходов ее численного решения с привлечением градиента в качестве инструмента, позволяющего подобрать направление спуска на X. Например, в случае, когда множество X является выпуклым и замкнутым, итерационная процедура строится классическим образом по правилу
Xk+1 = Prx(xk - akf \xk)), k = 0,1,2,..., (1.2)
где Prx обозначает оператор проектирования на множество X, ak — величину шага. Однако в случае невыпуклого допустимого множества задача существенно усложняется и приходится привлекать иные, как правило более трудоемкие, методы, уже непроекционного типа: методы возможных направлений, методы линеаризации, методы отсечений и т.п. Вместе с тем, для некоторых типов задач метод проекции градиента все-таки допускает обобщение. Здесь можно выделить ряд работ, появившихся в последние десять лет (см. [1]—[4]). Например, в [2], [3] допустимое множество с непустой внутренностью выбирается из класса предвыпуклых множеств, т.е. таких, которые можно представить в виде теоретико-множественной разности замкнутого выпуклого тела и объединения конечного числа открытых выпуклых тел.
Особый интерес представляют те задачи, в которых допустимое множество не содержит внутренних точек. Здесь конус возможных направлений для текущего приближения является пустым, поэтому приходится довольствоваться лишь конусом касательных направлений, которые, вообще говоря, могут и не иметь общих точек с допустимым множеством, кроме текущей, т.е. могут выводить за пределы допустимого множества. Более того, при использовании правила (1.2) возникает трудно решаемая проблема проектирования на допустимое множество, которое, в сущности, может быть и невыпуклым. Несмотря на это, опять же имеются методы проекционного типа минимизации на множества специального вида. Среди них можно упомянуть методы минимизации на выпуклую гладкую поверхность, понимаемую как граница выпуклого тела (см., например, работу [4] и библиографию к ней). В настоящей статье также предлагается метод минимизации проекционного типа, но на множестве X , вырезаемом выпуклым телесным конусом из сферы, вершина которого расположена внутри этой сферы. (Далее это множество нами назы-
вается "обобщенным сферическим сегментом"). Данный метод можно отнести к группе методов допустимых точек, так как последовательность, им генерируемая, начиная с исходной допустимой точки х0 е X, состоит из точек хк е X, к = 1,2,....
Вкратце идею метода можно описать следующим образом. Пусть уже получена точка хк е X. Вначале производится спуск вдоль конуса касательных направлений к допустимому множеству в этой точке. При этом величина шага вдоль направления убывания выбирается таким образом, чтобы полученная в результате точка $к была "незначительно" удалена от конуса. Подробнее говоря, функция расстояния от точки $к до конуса должна иметь более высокий порядок малости относительно длины вектора спуска $к - хк, когда последняя стремится к нулю. Очевидно, что выполнение данного условия можно обеспечить, потребовав от конуса гладкости, кроме того, можно также заметить, что в этом случае касательный конус превращается в гиперплоскость или полугиперплоскость. Далее, проектированием точки $к на исходный конус находится точка 1к. После этого осуществляется возврат на допустимое множество путем восстановления луча, исходящего из вершины конуса через точку 1к, и тем самым определяется следующее приближение хк+1. Как будет показано далее, при довольно естественных предположениях относительно целевой функции и допустимого множества, расстояние между точками 1к и хк+1 будет снова величиной более высокого порядка малости относительно длины вектора спуска, когда последняя стремится к нулю, т.е. возвращение на допустимое множество можно интерпретировать как "почти проектирование" на него.
2. ОПИСАНИЕ МЕТОДА
Всюду далее рассматривается задача (1.1) в предположении, что К* — п-мерное евклидовое
пространство со скалярным произведением ( ,) и индуцированной с ним нормой || ||; / : Кп ^ К,
/ е С 1Д(Кп) — гладкая функция, производная которой на всем Кп, удовлетворяет условию Липшица с константой Ь > 0:
УХ1, Х2 е К* /4x1) - /4x2) < Ь||Х1 - х2|; (2.1)
X = К п £ — обобщенный сферический сегмент; £ с Кп — (п - 1) -мерная сфера радиуса Я с центром в 0; К с Кп — выпуклый гладкий телесный конус с вершиной с £ К, лежащей внутри сферы £; с1 К = К и {с}; К = К и (2с - К) и {с}. При этом будем считать, что конус К задается неравенством В(х) < 0, причем функция В е С и(К) с константой М при удовлетворении условию Vх е £
'(х)|| > С > 0. Очевидно, что последнее условие в силу компактности сферы £ будет всегда выполняться, если дополнительно от функции В потребовать непрерывности на £. Из определения множества X явствует, что оно является компактом, а значит, функция /(х) достигает минимума на нем. Как мы увидим далее, требование липшицевости производной / 'функции / на всем пространстве Кп можно ослабить до липшицевости на некотором множестве У ^ X.
Пусть хк е £. Везде ниже, если не оговорено иное, будем придерживаться следующих обозначений и допущений:
Г к — опорная гиперплоскость к £ в точке хк,
Нк — замкнутое полупространство к К в точке хк, содержащее К, если хк е 1г К; Нк = Кп — иначе (здесь и далее символами с1, Ш и 1г обозначаются соответственно операторы топологического замыкания, внутренности и границы),
П к = Г к п Нк, 2 к =Г к п & Нк,
sk = РгПк(хк - ак/ (хк)), 1к = РгК$к, (2 2)
хк+1 = {с + - с№> 0} п £, .
Рк = РгПк (хк - / '(хк)), дк = Рг,к Рк, К = РгГк (хк - /' (хк)),
к Ьк - хЛ\Рк - хк\\'
в _Ыр{|3|Хк + Фк - Хк) е К, 0 <ц<р}, при Рк £ & Яь Рк _ 1п
[0 - иначе,
1 ( 1 , М) „ 2Я,
В _ 2ЯЬ ^|/Чхс)|, Б _ + О _ В2(Я --С),
(2.3)
4Ё = шт(Я-IН
МВ У B2 б
1/21
ВМ (1 + ЫЁ) 1М 2В 2Ё 2ВБ(Я + ¡4 + В гОЁ) ЬВ 2ЁР 2(Я + ||с|| + В гОЁ)
У + 4у2 + \ + ?
2
В(1 + ьЮ) (2 Я2 + 2 Я||с|| + В2 О) ЬОВ2 (2 Я2 + 2 Я||с|| + В2 О)2
А 2 = 2я2с + ш4? ' (2'4)
0 < С < С, 0 < у < С, С — у < С - С, 0 <С< Я - ||с||, 0 < V < 1, £> 0.
Как было сказано выше, каждая итерация предлагаемого метода состоит в двукратном проектировании: сначала на полугиперплоскость П к, а затем на конус К — с последующим возвращением на допустимое множество. Здесь имеет смысл выделить два случая местоположения текущего приближения хк: либо хк £ Гг К, либо хк е Гг К. В первом случае достаточно произвести спуск по множеству П к, по возможности вплоть до границы конуса, не выходя за его пределы. Во втором случае можно поступить аналогичным образом при условии, что хк е Гг К и рк £ Гг Нк, т.е. когда направление убывания эк - хк проходит через внутренность конуса. Однако здесь возможна ситуация, когда вектор эк - хк с началом в точке хк будет почти касаться множества Гг Нк, и тогда величина рк может оказаться очень малой, и, как следствие, длина шага ак будет очень малой и сходимость алгоритма окажется под вопросом. Поэтому, во избежание подобной ситуации, при формулировке алгоритма целесообразно отрегулировать составляющие его операции таким образом, чтобы длина шага была ограниченной не только сверху, но и снизу некоторым положительным числом. Например, можно осуществлять спуск в глубь конуса только тогда, когда направление эк - хк достаточно удалено по угловому расстоянию от Е к. Если же имеет место условие хк е Гг К и рк е Гг Нк, то необходимо реализовать продвижение вдоль направления эк - хк настолько, чтобы результат такого перемещения не вывел нас далеко за пределы конуса К.
С учетом сделанных замечаний для решения задачи (1.1) в настоящей работе предлагается нижеследующий алгоритм. Чтобы упростить его описание и обоснование сходимости, условие, при котором выполняется соответствующая операция, мы, следуя нотации Айверсона, записываем в квадратных скобках.
Алгоритм
Шаг 0. Выбрать начальную точку х0 е X и задать параметры С, у, £ метода, исходя из условий (2.4). Вычислить В, Б, Ё, О по формулам (2.3) и задать А, V, 60 и а, удовлетворяющие условиям, приведенным в лемме 7 (см. ниже). Установить к := 0.
Шаг 1. Найти множества П к, Е к и определить рк, дк, дк.
Шаг 2. Последовательно проверять условия, приведенные ниже в квадратных скобках, и при первом выполнении одного из них осуществить соответствующую операцию, после чего перейти к шагу 3. При необходимости предварительно вычислить р к.
2.1. [хк е Гг К а рк е ГгНк]. Принять ак = а и найти sk, 1к по формулам (2.2).
2.2. [хк е ГгК а рк £ ГгНк а рк > А]. Принять ак = а и найти sk из формул (2.2), положить
Iк = Эк.
2.3. [xk е fr K л pk £ fr Hk л pk < A л Qk < 1 - v]. Принять ak = pk и найти sk из формул (2.2), положить tk = sk.
2.4. [xk e fr K л pk £ fr Hk л pk < A л Qk > 1 - v]. Положить sk = xk + ak(gk - xk), вычислить tk по формулам (2.2) и положить a k = a.
2.5. [.xk £ fr K л pk > A]. Принять ak = a, найти Sk из формул (2.2), положить tk = sk.
2.5. [xk £ fr K л pk < A]. Принять ak = pk, найти sk по формулам (2.2), положить tk = sk.
Шаг 3. Определить xk+1 из (2.2). Если xk+1 = xk, т
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.