ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 9, с. 1493-1502
УДК 519.658
ОБОБЩЕНИЕ МЕТОДА ПРОЕКЦИИ ГРАДИЕНТА И МЕТОДА НЬЮТОНА НА ЭКСТРЕМАЛЬНЫЕ ЗАДАЧИ С ОГРАНИЧЕНИЕМ В ВИДЕ ГЛАДКОЙ ПОВЕРХНОСТИ
© 2015 г. Ю. А. Черняев
(420111 Казань, ул. К. Маркса, 10, КНИТУ им. А.Н. Туполева) e-mail: chernyuri@mail.ru Поступила в редакцию 22.04.2014 г.
Переработанный вариант 17.12.2014 г.
Рассматривается обобщение метода проекции градиента и метода Ньютона на случай невыпуклых множеств ограничений, представленных гладкой поверхностью. Исследуются необходимые условия экстремума и вопросы сходимости рассматриваемых методов. Библ. 20.
Ключевые слова: гладкая поверхность, метод проекции градиента, метод Ньютона, проекция на невыпуклое множество, необходимые условия локального минимума, сходимость алгоритма.
DOI: 10.7868/S0044466915090082
ВВЕДЕНИЕ
Один из подходов к решению задачи вида ф(х) ^ min, x е X с Кn, в случае гладкой функции ф(х) и выпуклого замкнутого допустимого множества Х состоит в построении итерационного процесса по правилу
Х0 е X, xk+1 = Prx(xk - akф' (xk)), k = 0,1,2,...,
где a k — величина итерационного шага, Prx — оператор проектирования на множество Х. Проекция точки на выпуклое замкнутое множество всегда определяется однозначно и если решение задачи проектирования на Х не требует привлечения трудоемких итерационных процедур, то такой подход к решению исходной задачи может оказаться вполне эффективным. В случае невыпуклого допустимого множества задача минимизации существенно усложняется и для ее решения приходится использовать иные, вообще говоря, более трудоемкие методы. Однако за последние годы для некоторых классов задач было разработано обобщение метода проекции градиента. Например, в [1]—[3] рассмотрены невыпуклые множества с непустой внутренностью, представимые в виде теоретико-множественной разности двух выпуклых множеств, а в [4] полученные ранее результаты обобщаются на случай разности выпуклого множества и объединения нескольких выпуклых множеств. Кроме этого, в [1] и [5] рассмотрен случай ограничения в виде выпуклой гладкой поверхности, а в [6] — случай ограничения в виде обобщенного сферического сегмента.
В случае дважды гладкой функции ф(х) еще один подход к решению задачи ф(х) ^ min, x е X с Кn, состоит в построении итерационного процесса по правилу
Х0 е X, Xk+1 = Xk + ak (z(Xk) - Xk), k = 0,1,2,..., где a k — величина итерационного шага, а точка z (xk) есть решение вспомогательной задачи 9k(x) = (ф' (Xk),x - x^ + (1/2)(ф" (Xk)(x - Xk),x - x^ ^ min, x e X.
Если Х выпукло и замкнуто, а ф^) сильно выпукла на Х, то данная вспомогательная задача всегда решается однозначно. Поскольку указанный метод решения задач выпуклого программирования, называемый методом Ньютона, использует квадратичную часть разложения функции ф^) в ряд Тейлора, от него следует ожидать более быстрой сходимости по сравнению с методом про-
екции градиента. В [7] рассмотрено обобщение метода Ньютона на случай ограничений в виде теоретико-множественной разности выпуклого множества и объединения нескольких выпуклых множеств, а в [8] — на случай ограничения в виде выпуклой гладкой поверхности.
В данной статье рассматривается обобщение метода проекции градиента и метода Ньютона на множества ограничений, представленные невыпуклой гладкой поверхностью, задаваемой
аналитически в виде X = {х е [ : g(x) = о}, где g (х) является гладкой на [, а требование выпуклости на g (х) не налагается. Суть предлагаемых алгоритмов состоит в том, что на каждой итерации сначала строится касательная гиперплоскость Л (xk) к поверхности Х в точке xk е X, после чего в первом из методов ищется проекция z (xk) точки xk - (xk), ß = const > 0, на Л (xk), а во втором методе точка z (xk) определяется как решение задачи qk(х) ^ min, х е Л (xk). Далее задается число ak е (0; 1] и определяется проекция точки xk + аk(z(xk) - xk) на Х, которая принимается за следующее приближение xk+1. Задача проектирования на невыпуклое множество решается в общем случае неоднозначно, поэтому последний шаг предполагает нахождение произвольной проекции на Х. В настоящей работе для каждого из методов показано, что при выполнении некоторых дополнительных условий последовательность {xk} с X сходится к точкам, удовлетворяющим необходимым условиям локального минимума.
Задача проектирования точки xk ^ф'х) на гиперплоскость Л (xk) и задача фk(х) ^ min, х е Л(хk), как это показано, соответственно, в [5] и [8], решаются в явном виде. Задача проектирования на множество Х в общем случае является сложной и требует для своего решения привлечения специфических методов. В последние годы появились работы (см. [9]—[11]), посвященные разработке итерационных алгоритмов нахождения проекции точки на множество вида {х е A : g(х) = 0}, где А — выпуклый компакт, а g (х) удовлетворяет тому или иному условию подчинения. В [9] рассмотрен случай, когда g (х) является липшицевой или гельдеровой на А. При использовании алгоритмов, излагаемых в данной работе, на каждой итерации требуется проектировать на поверхность Хразличные точки отрезка [ хк, z (хk) ], при этом расстояние от проектируемой точки до ее проекции не может превосходить величину 11 хк - z (хк) ||, так как хк е X, поэтому в качестве А можно брать замкнутый шар с центром в проектируемой точке и радиусом, не
меньшим этой величины. Если g(х) е C*([*), то g (х) на любом компакте является липшицевой, поэтому для приближенного решения задач проектирования при реализации предлагаемых ниже алгоритмов может быть использован алгоритм, рассмотренный в [9].
Необходимо отметить, что привлечение итерационных процедур для решения задачи проектирования точки на невыпуклое множество Х существенно увеличивает объем вычислений на итерации при использовании предлагаемых в данной работе алгоритмов. В связи с этим следует ожидать, что предлагаемые методы для многих конкретных задач минимизации окажутся менее эффективными по сравнению с методами, учитывающими специфику задач с нелинейными ограничениями типа равенств. Однако каждый из таких методов имеет свои недостатки и ограничения в практическом применении. Например, хорошо известный метод штрафных функций внешней точки, подробно изучаемый, например в [12] и [13], и основанный на сведении исходной задачи к последовательности задач безусловной минимизации, имеет довольно простую вычислительную схему, но он использует неограниченно возрастающие штрафные коэффициенты,
что существенно ухудшает свойства минимизируемых на [ функций и снижает эффективность вычислений. В связи с этим указанный метод целесообразно использовать, вообще говоря, только для нахождения достаточно грубого приближения к точке минимума или к стационарной точке. Различные варианты метода модифицированной функции Лагранжа, рассматриваемые, например, в [14]—[17], несмотря на ряд преимуществ, имеют и недостатки. К числу последних можно отнести, например, требование существования непрерывных частных производных второго или третьего порядка рассматриваемых в задаче функций, локальный характер сходимости алгоритмов, а также зависимость сходимости от выбора параметра итерационного шага (неудачный выбор приводит к отсутствию сходимости или к ее сильному замедлению, а удачный выбор часто оказывается затруднительным). Алгоритмы метода линеаризации, излагаемые, например, в [18]—[20], требуют для своего использования знания некоторых положительных констант или их оценок. Проверка существования этих констант и нахождение их оценок требует изучения особенностей конкретной задачи и на практике может вызвать существенные затруднения.
Проводя анализ различных вариантов существующих методов решения задач с нелинейными ограничениями типа равенств (в том числе методов, упомянутых выше), можно сделать вывод о том, что сходимость их алгоритмов обычно доказывается в предположении о выполнении тех или иных специфических дополнительных условий, налагаемых на исходные данные задачи или параметры алгоритма. Выполнение этих условий на практике далеко не всегда удается обеспечить, и процедура проверки их выполнения может оказаться очень сложной. Кроме этого, использование ряда алгоритмов требует знания некоторых трудновычисляемых констант, а замена последних их грубыми оценками может привести к сильному замедлению сходимости и снижению эффективности вычислений. Следовательно, актуальна проблема разработки методов (эффективность таких методов, однако, может оказаться существенно ниже), доказательство сходимости которых проводилось бы при минимальном наборе достаточно простых предположений, а их использование на практике не требовало бы знания тех или иных констант или их оценок. Предлагаемое в данной работе обобщение метода проекции градиента и метода Ньютона позволяет в некоторой степени решить эту проблему.
1. ОБОБЩЕНИЕ МЕТОДА ПРОЕКЦИИ ГРАДИЕНТА
Рассмотрим задачу вида ф(х) ^ min, х е X = {х е [n : g(x) = 0}, где g (х) е C 1(R"), ||g'(х)| Ф 0 при любом х е X и ф(х) е C 1(X). Предполагается, что множество Хнепусто, тогда в силу гладкости g (х) оно представляет собой гладкую поверхность в «-мерном евклидовом пространстве [n.
Полагая х е X, введем обозначения n(x) = g' (х) ||g' (х)||-1 — орт нормали к поверхности Хв точке х; Л(х) = {y е [n : (п(х), y - х) = о} — касательная гиперплоскость к Хв точке х; z (х) — проекция точки х - ßф'(x) на Л(х), где ß — фиксированное положительное число. В силу гладкости g(х) гиперплоскость Л (х) существует для любого х е X и вектор-функция n (х) непрерывна на Х, а в силу выпуклости и замкнутости Л (х) проекция z&) определяется однозначно.
Для решения поставленной задачи предлагается использовать следующий алгоритм построения последовательных приближений, представляющий собой обобщение алгоритма метода проекции градиента, рассмотренного в [1] и [5].
Алгоритм
Шаг 0. Задается ß > 0 и полагается k = 0.
Шаг 1. Пусть хк е X есть к-е приближение.
Шаг 2. Строятся гиперплоскость Л (хк) и точка z (хк).
Шаг 3. Если хк = zfc), то вычисления заканчиваются, иначе осуществляется переход к шагу 4.
Шаг 4. Задается
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.