Globalizing convergence of piecewise Newton methods

Full Text

Введение

Рассматривается уравнение с ограничением

$\Phi uu\in P\mathrm{,}$ (0.1)

 где $\Phi {ℝ}^p\to {ℝ}^q$ — заданное отображение, а $P\subset {ℝ}^p$ — заданное непустое замкнутое множество. Целью данной работы является глобализация сходимости ньютоновских методов для задачи (0.1) в пониженных требованиях гладкости. Основным объектом интереса является случай, когда отображение  в (0.1) является кусочно-гладким, т. е. оно непрерывно, и существует конечный набор гладких (в том или ином смысле; точные требования гладкости будут приводиться в каждом формулируемом ниже утверждении)  кусочных отображений ${\Phi }^1\mathrm{,}\dots \mathrm{,}{\Phi }^s{ℝ}^p\to {ℝ}^q$ таких, что

 $\Phi u\in {\Phi }^{1}u\dots \mathrm{,}{\Phi }^{s}u\forall u\in {ℝ}^p\mathrm{.}$

Случай $s=1$ соответствует гладкому отображению  Согласно [1, теорема 2.1], любое кусочно-гладкое отображение с непрерывно дифференцируемыми кусочными отображениями является локально липшицевым.

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

$a\left(u\right)=\mathrm{0,}b\left(u\right)⩾\mathrm{0,}c\left(u\right)⩾\mathrm{0,}d\left(u\right)⩾\mathrm{0,}⟨c\left(u\right),d\left(u\right)⟩=\mathrm{0,}$   (0.2)

с заданными непрерывно дифференцируемыми отображениями $a{ℝ}^p\to {ℝ}^l\mathrm{,}$ $b{ℝ}^p\to {ℝ}^m\mathrm{,}$ $c{ℝ}^p\to {ℝ}^r\mathrm{,}$ $d{ℝ}^p\to {ℝ}^r\mathrm{.}$ Система (0.2) может быть эквивалентным образом записана в виде (0.1) с кусочно-гладким $\Phi \left(u\right)=\left(a\right(u),\min \{c\left(u\right),d\left(u\right)\left\}\right),$ где минимум берется покомпонентно, и с $P=\{u\in {ℝ}^p|b\left(u\right)⩾\mathrm{0,}c\left(u\right)⩾\mathrm{0,}d\left(u\right)⩾0\},$ или просто с $P=\{u\in {ℝ}^p|b\left(u\right)⩾0\}.$ Ограничения, задающие  можно заменить простыми, а именно, условиями неотрицательности на дополнительные переменные («слэки»; детали см., например, в [2]).

Для каждого $u\in {ℝ}^p$ определим множество

$\mathcal{A}\left(u\right)=\{j\in \{\mathrm{1,}\dots ,s\left\}\right|\Phi \left(u\right)={\Phi }^j\left(u\right)\}$    (0.3)

индексов кусочных отображений  активных в точке $u\mathrm{.}$ Пусть $G{ℝ}^p\to {ℝ}^{q\times p}$ — любое отображение, удовлетворяющее

$G\left(u\right)\in \left\{\right({\Phi }^j{)}^{\text{'}}\left(u\right)|j\in \mathcal{A}(u\left)\right\}\forall u\in {ℝ}^p.$   (0.4)

Кусочные ньютоновские методы — это общее название для класса алгоритмов, каждая итерация которого в текущем приближении $u^k$ состоит в осуществлении итерации соответствующего ньютоновского метода для гладкого уравнения с ограничением

${\Phi }^j\left(u\right)=\mathrm{0,}u\in P,$   (0.5)

для некоторого $j\in \mathcal{A}\left(u^k\right).$ Разумеется, индекс $j$ на разных итерациях может быть разным. Иными словами, это ньютоновский метод, в котором (вообще говоря не существующая) производная ${\Phi }^{\text{'}}\left(u^k\right)$ заменяется ее кусочным «суррогатом» $G\left(u^k\right).$

Ключевую роль в анализе глобальной сходимости ниже будет играть следующее предположение, которое уже появлялось в [3, (4.8)], [4, (32)]:

$\parallel \Phi \left(u\right)\parallel ⩽\parallel {\Phi }^j\left(u\right)\parallel \forall j\in \{\mathrm{1,}\dots ,s\}\forall u\in P.$   (0.6)

Для определенности здесь и далее будем считать, что используется евклидова норма.

В этой связи заметим, что ограничения $c\left(u\right)⩾0$ и $d\left(u\right)⩾0$ в определении $P$ для переформулировки комплементарной системы (0.2) могут показаться излишними: если их опустить, то множество решений соответствующей задачи (0.1) не изменится. Однако, как легко видеть, именно наличие этих ограничений обеспечивает выполнение в данном случае условия (0.6); см. примеры 1.1 и 1.2 ниже, а также обсуждения этого вопроса в [2–4].

1.   Кусочный метод Ньютона

В этом разделе будем рассматривать случай, когда число уравнений равно числу переменных, и ограничений нет: пусть $p=q$ и $P={ℝ}^p.$ Для текущего приближения $u^k\in {ℝ}^p$ итерация  кусочного метода Ньютона генерирует следующее приближение как $u^k+v^k,$ где $v^k$ определяется как решение линейного уравнения

$\Phi \left(u^k\right)+G\left(u^k\right)v=\mathrm{0,}$   (1.1)

а $G$ задается соотношениями (0.3) и (0.4). Иными словами, $v^k$ является решением линейного уравнения

${\Phi }^j\left(u^k\right)+\left({\Phi }^j{)}^{\text{'}}\right(u^k)v=0$   (1.2)

с некоторым $j\in \mathcal{A}\left(u^k\right),$ а такая итерация есть итерация базового метода Ньютона для соответствующего гладкого уравнения в (0.5).

Для функции ${\phi }_j{ℝ}^p\to ℝ\mathrm{,}$

${\phi }_j\left(u\right)=\frac{1}{2}\parallel {\Phi }^j\left(u\right){\parallel }^2,$   (1.3)

имеет место 

${\phi }_{j^{\text{'}}}\left(u^k\right)={\left(\right({\Phi }^j{)}^{\text{'}}\left(u^k\right))}^{\top }{\Phi }^j\left(u^k\right),$   (1.4)

и поэтому 

$⟨{\phi }_{j^{\text{'}}}\left(u^k\right),v^k⟩=⟨{\left(\right({\Phi }^j{)}^{\text{'}}\left(u^k\right))}^{\top }{\Phi }^j\left(u^k\right),v^k⟩=⟨{\Phi }^j\left(u^k\right),\left({\Phi }^j{)}^{\text{'}}\right(u^k)v^k⟩=-\parallel {\Phi }^j(u^k){\parallel }^2,$   (1.5)

где последнее равенство следует из (1.2). Отсюда получаем, что $v^k$ является направлением убывания для функции ${\phi }_j$ в точке $u^k\mathrm{,}$ если только ${\Phi }^j\left(u^k\right)=\Phi \left(u^k\right)\cancel{=}\mathrm{0,}$ т. е. если текущее приближение $u^k$ не является решением уравнения в (0.1). Это соображение служит основанием для использования одномерного поиска по направлению $v^k$ с целью глобализации сходимости кусочного метода Ньютона, реализованной в алгоритме 1 ниже.

Заметим, однако, что матрица $G\left(u^k\right)$ в (1.1) может оказываться вырожденной, и тогда это уравнение может не иметь решений. Более того, даже если $v^k$существует, его «качество» как направления убывания может быть недостаточным для обеспечения разумных свойств глобальной сходимости такого алгоритма. В таких случаях (а именно, в тех случаях, когда направление $v^k$ оказывается «слишком длинным») алгоритм использует страховочный градиентный шаг для функции ${\phi }_j\mathrm{.}$ Для гладких уравнений данная стратегия глобализации сходимости метода Ньютона обсуждалась в [5, разд. 5.1].

Алгоритм 1. Фиксируем параметры $C>\mathrm{0,}$ $\tau >\mathrm{0,}$ $\epsilon \in \left(\mathrm{0,}1\right)$ и $\varkappa \in \text{\hspace{0.05em}(0, 1)}$. Выбираем $u^0\in {ℝ}^p$ и полагаем $k=0.$   

1. Если $\Phi \left(u^k\right)=\mathrm{0,}$ стоп.
2. Вычисляем $v^k$ как решение линейного уравнения (1.1). Если $v^k$ не удается вычислить, или $v^k$ нарушает неравенство

$\parallel v^k\parallel ⩽\max \{C,1/\parallel \Phi (u^k\left){\parallel }^{\tau }\right\},$   (1.6)

переходим к шагу 4. 

     3. Полагаем $\alpha =1.$ Если выполняется неравенство 

$\parallel \Phi (u^k+\alpha v^k)\parallel ⩽(1-\epsilon \alpha )\parallel \Phi \left(u^k\right)\parallel ,$   (1.7)

полагаем ${\alpha }_k=\alpha$ и переходим к шагу 6. В противном случае заменяем $\alpha$ на $\varkappa \alpha$ и проверяем снова неравенство (1.7) до тех пор, пока оно не выполнится, после чего полагаем ${\alpha }_k=\alpha$ и переходим к шагу 6.

     4. Полагаем $\alpha =1.$ Если выполняется неравенство Армихо

${\phi }_j(u^k+\alpha v^k)⩽{\phi }_j\left(u^k\right)-\epsilon \alpha \parallel v^k{\parallel }^2,$   (1.8)

полагаем ${\alpha }_k=\alpha .$ В противном случае заменяем $\alpha$ на $\varkappa \alpha$ и проверяем снова неравенство (1.8) до тех пор, пока оно не выполнится, после чего полагаем ${\alpha }_k=\alpha .$

     5. Полагаем $u^{k+1}=u^k+{\alpha }_k{v}^k,$ увеличиваем $k$ на  и переходим к шагу 1.

Если заменить $\Phi$ в (1.7) на ${\Phi }^j$ для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k)$ (что при выполнении (0.6) дает неравенство, из которого следует (1.7)), то, согласно (1.3) и (1.4), получим

${\phi }_j(u^k+\alpha v^k)⩽{(1-\epsilon \alpha )}^2{\phi }_j\left(u^k\right)={\phi }_j\left(u^k\right)-\epsilon \alpha \parallel {\Phi }^j\left(u^k\right){\parallel }^2+\frac{1}{2}{\alpha }^2\parallel {\Phi }^j\left(u^k\right){\parallel }^2$

$={\phi }_j\left(u^k\right)-\epsilon \alpha ⟨{\phi }_{j^{\text{'}}}\left(u^k\right),v^k⟩+\frac{1}{2}{\alpha }^2\parallel \Phi \left(u^k\right){\parallel }^2,$

что автоматически выполняется в случае выполнения соответствующей формы неравенства Армихо

${\phi }_j(u^k+\alpha v^k)⩽{\phi }_j\left(u^k\right)+\epsilon \alpha ⟨{\phi }_{j^{\text{'}}}\left(u^k\right),v^k⟩.$   (1.9)

Иными словами, в п. 3 алгоритма 1 вместо (1.7) можно было бы, как и в п. 5, использовать неравенство Армихо (1.9) для ${\phi }_j\mathrm{,}$ но это приводило бы, вообще говоря, к более ограничительному требованию на параметр длины шага ${\alpha }_k\mathrm{.}$

Теорема 1.1. Пусть $\Phi :{ℝ}^p\to {ℝ}^p$ — кусочно-гладкое отображение с непрерывно дифференцируемыми кусочными отображениями ${\Phi }^1\mathrm{,}\dots \mathrm{,}{\Phi }^s\mathrm{.}$ Пусть для $P={ℝ}^p$ выполняется предположение (0.6). Пусть $G:{ℝ}^p\to {ℝ}^{p\times p}$ — любое отображение, удовлетворяющее (0.4).

Тогда алгоритм 1 либо останавливается в точке $u^k\mathrm{,}$ удовлетворяющей

${\left(\right({\Phi }^j{)}^{\text{'}}\left(u^k\right))}^{\top }\Phi \left(u^k\right)=0$   (1.10)

по крайней мере для одного $j\in \mathcal{A}\left(u^k\right),$ либо генерирует бесконечную последовательность $\left\{u^k\right\},$ любая предельная точка  которой удовлетворяет

${\left(\right({\Phi }^j{)}^{\text{'}}\left(\overline{u}\right))}^{\top }\Phi \left(\overline{u}\right)=0$   (1.11)

по крайней мере для одного $j\in \mathcal{A}\left(\overline{u}\right).$

Доказательство. Согласно (1.4), алгоритм может остановиться на некоторой итерации $k\mathrm{,}$ только если либо $u^k$ удовлетворяет $\Phi \left(u^k\right)=\mathrm{0,}$ либо выполняется (1.10) для некоторого $j\in \mathcal{A}\left(u^k\right),$ причем в первом случае, согласно (0.3), ${\Phi }^j\left(u^k\right)=\Phi \left(u^k\right)=\mathrm{0,}$ и равенство (1.10) тоже выполняется (для любого $j\in \mathcal{A}\left(u^k\right)$).

Вместе с тем, если (1.10) не выполняется для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k),$ то при любом выборе $v^k$ в алгоритме 1, из (1.5) следует, что $⟨{\phi }_{j^{\text{'}}}\left(u^k\right),v^k⟩<0.$ Но тогда, с учетом обсуждения перед формулировкой теоремы, стандартным образом получаем (см., например, [6, лемма 3.1.2]), что подходящее значение ${\alpha }_k>0$ в п. 3 или 5 алгоритма будет найдено после конечного числа дроблений (умножений текущего $\alpha$ на $\varkappa$), а значит, алгоритм успешно определит $u^{k+1}\mathrm{.}$

Пусть теперь (1.10) не выполняется для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k),$ ни для какого $k\mathrm{,}$ а значит, алгоритм генерирует бесконечную последовательность $\left\{u^k\right\}.$ Для любой предельной точки $\overline{u}$ этой последовательности, в силу включения $\mathcal{A}\left(u\right)\subset \mathcal{A}\left(\overline{u}\right)$ для всех $u\in {ℝ}^p$ достаточно близких к $\overline{u}\mathrm{,}$ и в силу конечности множества $\mathcal{A}\left(\overline{u}\right),$ a также с учетом (0.4), найдется сходящаяся к $\overline{u}$ подпоследовательность $\left\{u^{k_i}\right\}$ такая, что $G\left(u^{k_i}\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^{k_i})$ для всех $i\mathrm{,}$ для некоторого фиксированного $j\in \mathcal{A}\left(\overline{u}\right).$

Если бесконечную подпоследовательность $u^{k_i}$ выше можно выбрать так, что ньютоновское направление принимается на шаге 2 алгоритма для любого $i\mathrm{,}$то дальнейшее рассуждение повторяет доказательство в [7, теорема 3.1] применительно к ${\Phi }^j$ (вместо $\Phi$).

Остается рассмотреть случай, когда ньютоновское направление не принимается на шаге 2 алгоритма в точках подпоследовательности $\left\{u^{k_i}\right\}$ ни для какого $i\mathrm{.}$ Заметим, что в силу (0.6) и (1.7), (1.8), для всякого  выполняется

${\phi }_j\left(u^{k_i}\right)⩾{\phi }_j\left(u^{k_i+1}\right)⩾\frac{1}{2}\parallel \Phi \left(u^{k_i+1}\right){\parallel }^2⩾\frac{1}{2}\parallel \Phi \left(u^{k_i+2}\right){\parallel }^2⩾\dots$

$⩾\frac{1}{2}\parallel \Phi \left(u^{k_{i+1}}\right){\parallel }^2={\phi }_j\left(u^{k_{i+1}}\right)⩾{\phi }_j\left(u^{k_{i+1}+1}\right)⩾\dots ,$   (1.12)

т. е. последовательность $\{\dots {\phi }_j(u^{k_i}),{\phi }_j(u^{k_i+1}),\dots \}$ монотонно невозрастает. При этом подпоследовательность $\left\{{\phi }_j\right(u^{k_i+1}\left)\right\}$ этой последовательности  сгенерирована градиентными шагами с использованием правила Армихо. Тогда, согласно [8, теорема 1.16], любая предельная точка последовательности $\left\{u^{k_i}\right\},$ т.е. $\overline{u}\mathrm{,}$ удовлетворяет ${\phi }_{j^{\text{'}}}\left(\overline{u}\right)=\mathrm{0,}$ что, согласно (0.3) и (1.4), и есть (1.11).

Теорема 1.2. Пусть $\Phi :{ℝ}^p\to {ℝ}^p$ — кусочно-гладкое отображение с дифференцируемыми вблизи точки $\overline{u}\in {ℝ}^p$ кусочными отображениями ${\Phi }^1\mathrm{,}\dots \mathrm{,}{\Phi }^s\mathrm{,}$ причем производные ${\Phi }^j\mathrm{,}$ $j\in \mathcal{A}\left(\overline{u}\right),$ непрерывны в этой точке. Пусть $\overline{u}$ является решением уравнения в (0.1), причем матрицы Якоби $\left({\Phi }^j{)}^{\text{'}}\right(\overline{u})$ невырождены для всех $j\in \mathcal{A}\left(\overline{u}\right).$ Пусть $G:{ℝ}^p\to {ℝ}^{p\times p}$ — любое отображение, удовлетворяющее (0.4).

Тогда, если алгоритм 1 генерирует приближение достаточно близкое к $\overline{u}\mathrm{,}$ то либо он останавливается с $u^k=\overline{u},$ либо генерирует бесконечную последовательность $\left\{u^k\right\},$ которая сходится к $\overline{u}$ сверхлинейно. Если производные ${\Phi }^j\mathrm{,}$ $j\in \mathcal{A}\left(\overline{u}\right),$ удовлетворяют условию Липшица относительно $\overline{u}\mathrm{,}$ то скорость сходимости квадратичная.

Доказательство. При достаточной близости $u^k$ к $\overline{u}\mathrm{,}$ с учетом включения $\mathcal{A}\left(u^k\right)\subset \mathcal{A}\left(\overline{u}\right)$ и (0.4), и невырожденности $\left({\Phi }^j{)}^{\text{'}}\right(\overline{u})$ для всех $j\in \mathcal{A}\left(\overline{u}\right)$ из стандартных результатов о локальной сверхлинейной сходимости метода Ньютона (например [5, теорема 2.2]) для уравнения в (0.5), и из конечности множества $\mathcal{A}\left(\overline{u}\right),$вытекает существование и единственность $v^k\mathrm{,}$ удовлетворяющего (1.1), причем

$u^k+v^k-\overline{u}=o(\parallel u^k-\overline{u}\parallel )$   (1.13)

при $u^k\to \overline{u}\mathrm{.}$ Очевидным последствием этого является то, что при достаточной близости $u^k$ к $\overline{u}$ направление $v^k$ принимается тестом (1.6) на шаге 2 алгоритма 1.

Далее, из [5, предложение 1.32] и $\left({\Phi }^j{)}^{\text{'}}\right(\overline{u})$ для всех $j\in \mathcal{A}\left(\overline{u}\right)$ вытекает оценка

$u^k-\overline{u}=O(\parallel {\Phi }^j(u^k)\parallel )$

при $u^k\to \overline{u}\mathrm{,}$ для всех таких $j\mathrm{.}$ Из этой оценки, из включения $\mathcal{A}{u}^k\subset \mathcal{A}\overline{u}$ и (0.3), с учетом локальной липшицевости $\Phi$ и (1.13) вытекает, что при любом выборе $j\in \mathcal{A}\left(u^k\right)$

$\Phi (u^k+v^k)=\Phi (u^k+v^k)-\Phi \left(\overline{u}\right)=O(\parallel u^k+v^k-\overline{u}\parallel )=o(\parallel u^k-\overline{u}\parallel )$

$=o(\parallel {\Phi }^j(u^k)\parallel )=o(\parallel \Phi (u^k)\parallel )$  (1.14)

при $u^k\to \overline{u}\mathrm{.}$ Отсюда следует, что при достаточной близости $u^k$ к $\overline{u}$ имеет место 

$\parallel \Phi (u^k+v^k)\parallel ⩽(1-\epsilon )\parallel \Phi \left(u^k\right)\parallel ,$

т. е. $\alpha =1$ принимается тестом (1.7) на шаге 3 алгоритма 1.

Таким образом, итерация алгоритма 1 в этом случае принимает вид итерации базового метода Ньютона для уравнения в (0.5) с соответствующим $j\in \mathcal{A}\left(u^k\right)\subset \mathcal{A}\left(\overline{u}\right),$ и утверждение о сверхлинейной сходимости $\left\{u^k\right\}$ к  вытекает из (1.13). Детали см. в [5, теорема 2.2], где также приводится доказательство квадратичной скорости сходимости в случае липшицевости производных относительно  которое легко распространяется на рассматриваемый здесь кусочно-гладкий случай, опять же с использованием конечности $\mathcal{A}\left(\overline{u}\right).$

 

Рис. 1. Пример 1.1

 

Роль предположения (0.6) в этом анализе демонстрируется следующим простым примером: в случаях, когда $\mathcal{A}\left(u^k\right)$ не является одноточечным, при нарушении (0.6) направления кусочного метода Ньютона могут не быть направлениями убывания для функции $\parallel \Phi (\cdot )\parallel$ в точке $u^k\mathrm{.}$

 Пример 1.1. Рассмотрим нелинейную комплементарную задачу

$u⩾\mathrm{0,}F\left(u\right)⩾\mathrm{0,}⟨u,F\left(u\right)⟩=\mathrm{0,}$   (1.15)

с отображением $F:{ℝ}^p\to {ℝ}^p.$ Эта задача является частным случаем (0.2) при $l=m=\mathrm{0,}$ $r=p,$ $c\left(u\right)=u,$ $d\left(u\right)=F\left(u\right).$ Эквивалентной переформулировкой (1.15) является (0.1) с кусочно-гладким $\Phi \left(u\right)=\min \{u,F(u\left)\right\},$ где можно взять $P={ℝ}^p.$

Пусть, например, $p=\mathrm{1,}$ $F\left(u\right)=-u-2.$ Тогда естественные соответствующие кусочные отображения имеют вид ${\Phi }^1\left(u\right)=u$ и ${\Phi }^2\left(u\right)=-u-2$ (см. графики на рис. 1a). В точке $u^k=-\mathrm{1,}$ которая не является решением (у задачи (1.15) с указанным $F$ вообще нет решений), выполняется $\mathcal{A}\left(u^k\right)=\left\{\mathrm{1,}2\right\}.$ Если удовлетворяющее (0.4) отображение $G:ℝ\to ℝ$ выбрано так, что $G\left(u^k\right)=\left({\Phi }^1{)}^{\text{'}}\right(u^k)=\mathrm{1,}$ то уравнение (1.1) принимает вид $-1+v=\mathrm{0,}$ т. е. $v^k=1.$ Тогда для любого $\alpha >0$

$\left|\Phi \right(u^k+\alpha v^k\left)\right|=\left|\min \right\{-1+\alpha ,1-\alpha -2\left\}\right|=\left|\min \right\{-1+\alpha ,-1-\alpha \left\}\right|$

$=|-1-\alpha |=1+\alpha >1=\left|\Phi \right(u^k\left)\right|.$

Аналогично, если $G\left(u^k\right)=\left({\Phi }^2{)}^{\text{'}}\right(u^k)=-\mathrm{1,}$ то уравнение (1.1) принимает вид $-1-v=\mathrm{0,}$ т. е. $v^k=-\mathrm{1,}$ и для любого $\alpha >0$

$\left|\Phi \right(u^k+\alpha v^k\left)\right|=\left|\min \right\{-1-\alpha ,1+\alpha -2\left\}\right|=\left|\min \right\{-1-\alpha ,-1+\alpha \left\}\right|$

$=|-1-\alpha |=1+\alpha >1=\left|\Phi \right(u^k\left)\right|.$

Таким образом, при любом допустимом выборе $G\left(u^k\right)$ направление $v^k$ не является направлением убывания для $\left|\Phi \right(\cdot \left)\right|$ в точке $u^k\mathrm{,}$ и, в частности, (1.7) не выполняется ни для какого $\alpha >0.$

Объяснение этого эффекта состоит в нарушении (0.6): если, например, $u>-\mathrm{1,}$ то

 $\left|{\Phi }^1\right(u\left)\right|=\left|u\right|<u+2=|-u-2|=\left|\Phi \right(u\left)\right|,$

а для $u<-1$ аналогичное неравенство выполняется с ${\Phi }^2$ вместо ${\Phi }^1\mathrm{.}$

Заметим, что здесь $u^k=F\left(u^k\right)=-1<0:$ в точках $u⩾\mathrm{0,}$ в которых $F\left(u\right)⩾\mathrm{0,}$ неравенство из (0.6) для кусочно-гладкого $\Phi$ из указанной переформулировки задачи (1.15) выполняется автоматически. См. обсуждение роли множества $P$ для выполнения (0.6) в конце введения.

Поскольку множество точек $u^k\in {ℝ}^p\mathrm{,}$ в которых $\mathcal{A}\left(u^k\right)$ содержит более одного индекса, обычно является тощим, то может возникнуть впечатление, что даже при нарушении (0.6) указанный эффект не должен создавать практических проблем: алгоритм не может сделать шаг только из таких точек $u^k\mathrm{,}$попадание в которые является нетипичным исходом. Однако, это не так: для задачи из примера 1.1 из любого начального приближения алгоритм 1 сходится к точке $\overline{u}=-1$ (обычно попадает точно в нее за один или два шага), выбраться из которой уже не может по причинам, указанным в этом примере. Несмотря на то, что в этой точке $\overline{u}$ (1.11) не выполняется ни для одного $j\in \mathcal{A}\left(\overline{u}\right)=\left\{\mathrm{1,}2\right\},$ такой исход можно рассматривать как благоприятный, поскольку  минимизирует невязку задачи (см. рис. 1a). Как показывает следующий пример, из широких областей начальных точек алгоритм 1 может генерировать бесконечные последовательности,  сходящиеся к таким проблемным тощим множествам все более короткими шагами, и в итоге «застревающие» вблизи таких множеств, что в итоге приводит к неудачным запускам для практических реализаций алгоритма, причем предельные точки могут не быть точками минимума невязки.

Пример 1.2. Рассмотрим нелинейную комплементарную задачу (1.15) из [9, пример 6.1], с отображением $F:{ℝ}^2\to {ℝ}^2,$ $F\left(u\right)=({(u_1-1)}^2,u_1+u_2+u_2^2-1),$ и ее эквивалентную переформулировку (0.1) с $\Phi \left(u\right)=\min \{u,F(u\left)\right\}$ и $P={ℝ}^2.$

На рис. 2–4 синими точками показаны два решения $\left(\mathrm{0,}\right(\sqrt{5}-1)/2)$ и  данной задачи, а синие линии являются линиями уровня функции $\parallel \Phi (\cdot )\parallel .$ Красные линии соответствуют границам между областями активности разных гладких кусочных отображений, и, в частности, состоят из точек $u\in {ℝ}^2\mathrm{,}$ в которых $\mathcal{A}\left(u\right)$ содержит более одного индекса.

 

Рис. 2. Пример 1.2: начальные точки, порождающие неудачные запуски

 

Запуск алгоритма 1 объявлялся неудачным в случаях, когда на шаге 3 алгоритма реализовывалось неравенство $\alpha \parallel v^k\parallel ⩽{10}^{-12}.$ Рис. 2, 3 демонстрируют начальные точки (которые выбирались случайным образом в области, изображенной на этих рисунках), запуски из которых были неудачыми в указанном смысле, для разных значений параметра $\epsilon$ в тесте (1.7). Рис. 4 содержит некоторые примеры конкретных неудачных запусков.

Причиной такого поведения является существование точек $u\in P={ℝ}^2,$ в которых нарушаются какие-то из неравенств $u_1⩾\mathrm{0,}$ $u_2⩾\mathrm{0,}$ $u_1+u_2+u_2^2-1⩾\mathrm{0,}$ что приводит к невыполнению (0.6). Например, для естественных кусочных отображений ${\Phi }^1\left(u\right)=(u_1,u_2)$ и ${\Phi }^2\left(u\right)=(u_1,u_1+u_2+u_2^2-1)$ в точках $u=(1-t-t^2,t)$при $t<0$ имеем: ${\Phi }^1\left(u\right)=(1-t-t^2,t),$ ${\Phi }^2\left(u\right)=(1-t-t^2,0),$ причем если $t^4+2t^3+2t^2+t>\mathrm{1,}$ то $\Phi \left(u\right)={\Phi }^1\left(u\right),$ и при этом $\parallel {\Phi }^2\left(u\right)\parallel <\parallel \Phi \left(u\right)\parallel .$

 

Рис. 3. Пример 1.2: начальные точки, порождающие неудачные запуски

 

Рис. 4. Пример 1.2: некоторые неудачные запуски

 

Ситуация в примере 1.2 не сохраняется, если заменить $\Phi$ в (1.7) на ${\Phi }^j\mathrm{,}$ или заменить (1.7) на (1.9), для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k).$ Заметим, однако, что при нарушении (0.6) эти модификации не гарантируют выполнение (1.7), и при этом на них не распространяется приведенное в теореме 1.1 обоснование глобальной сходимости. Для задачи из примера 1.1 последовательность алгоритма с заменой $\Phi$ в (1.7) на ${\Phi }^j$ «скачет» между точками 0 и -2 где первая является нулем ${\Phi }^1$ и, соответственно, минимизирует ${\phi }_1\mathrm{,}$ а вторая является нулем ${\Phi }^2$ и ${\phi }_2\mathrm{,}$ но ${\Phi }^1$ не является активным в точке 0, а ${\Phi }^2$ — в точке -2 (см. рис. 1). Алгоритм с заменой (1.7) на (1.9) ведет себя аналогично, но также периодически «посещает» и точку -1.

2. Кусочный метод Гаусса–Ньютона

Возвращаясь к общей постановке задачи (0.1), для текущего приближения $u^k\in P$ кусочный метод Гаусса–Ньютона (с ограничением) генерирует следующее приближение как $u^k+v^k,$ где $v^k$ минимизирует невязку (в квадрате) «линеаризованного» уравнения из (0.1) на $P-u^k,$ а именно, $v^k$определяется как решение задачи оптимизации 

$\frac{1}{2}\parallel \Phi \left(u^k\right)+G\left(u^k\right)v{\parallel }^2\to \min ,u^k+v\in P,$   (2.1)

где $G$ задается соотношениями (0.3) и (0.4). Целевая функция в (2.1) является выпуклой квадратичной функцией, и, согласно теореме Фрэнка–Вулфа [10], эта подзадача всегда имеет решение в случае полиэдрального $P\mathrm{,}$ но решение может быть не единственным. Учитывая определение $G\mathrm{,}$ подзадача (2.1) может быть записана в виде

$\frac{1}{2}\parallel {\Phi }^j\left(u^k\right)+\left({\Phi }^j{)}^{\text{'}}\right(u^k)v{\parallel }^2\to \min ,u^k+v\in P,$

с некоторым $j\text{}\in \text{}\mathcal{A}\left(u^k\right),$ т. е. итерация такого метода есть итерация метода Гаусса–Ньютона для соответствующего гладкого уравнения с ограничением (0.5).

Следующий алгоритм реализует гибридную глобализацию сходимости кусочного метода Гаусса–Ньютона, основанную на объединении этого алгоритма в качестве локальной фазы с методом проекции градиента в качестве глобальной фазы, в духе [11, алгоритм 2.12] для метода Левенберга–Марквардта. Пусть $P$ выпукло, и через ${\pi }_P\left(u\right)$ обозначается проекция точки $u\in {ℝ}^p$ на $P\mathrm{.}$

Алгоритм 2. Фиксируем параметры $\rho \in \left(\mathrm{0,}1\right),$ $\widehat{\alpha }>\mathrm{0,}$ $\epsilon \in \left(\mathrm{0,}1\right)$ и $\varkappa \in \text{\hspace{0.05em}(0,1)}$ Выбираем $u^0\in P$ и полагаем $k=0.$ 

1. Если $\Phi \left(u^k\right)=\mathrm{0,}$ стоп.
2. Вычисляем $v^k$ как некоторое решение задачи (2.1). Если $v^k$ не удается вычислить, переходим к шагу 4.
3. Если

$\parallel \Phi (u^k+v^k)\parallel ⩽\rho \parallel \Phi \left(u^k\right)\parallel ,$  (2.2)

 полагаем $u^{k+1}=u^k+v^k,$ увеличиваем к на 1 и переходим к шагу 1.

4. Для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k)$ (см. (0.4)), полагаем $v^k=-{\phi }_{j^{\text{'}}}\left(u^k\right),$ где функция ${\phi }_j$ определена в (1.3) (см. (1.4)). Если ${\pi }_P(u^k-\widehat{\alpha }{v}^k)=u^k,$ стоп.
5. Полагаем $\alpha =\widehat{\alpha }.$ Если выполняется неравенство Армихо

${\phi }_j\left({\pi }_P\right(u^k-\alpha v^k\left)\right)⩽{\phi }_j\left(u^k\right)+\epsilon ⟨{\phi }_{j^{\text{'}}}\left(u^k\right),{\pi }_P(u^k-\alpha v^k)-u^k⟩,$  (2.3)

 полагаем ${\alpha }_k=\alpha .$ В противном случае заменяем $\alpha$ на $\varkappa \alpha$ и проверяем снова неравенство (2.3) до тех пор, пока оно не выполнится, после чего полагаем ${\alpha }_k=\alpha .$

6. Полагаем $u^{k+1}={\pi }_P(u^k-{\alpha }_k{v}^k),$ увеличиваем к на 1 и переходим к шагу 1.

Следующий результат обобщает [8, теорема 1.16] (оно же [12, предложение 1.2.6] с градиентных методов безусловной оптимизации на методы проекции градиента. Его обоснование получается по сути повторением доказательства в [12, предложение 2.3.3 (b)] для соответствующей подпоследовательности.

Предложение 2.1. Пусть $P\subset {ℝ}^p$ — замкнутое выпуклое множество, а $\phi :{ℝ}^p\to ℝ$ — непрерывно дифференцируемая на Р функция. Пусть последовательность $\left\{u^k\right\}\subset {ℝ}^p$ такова, что для некоторой ее бесконечной подпоследовательности $\left\{u^{k_i}\right\}\subset P$ последовательность $\{\dots \phi (u^{k_i}),\phi (u^{k_i+1}),\dots \}$ монотонно невозрастает. Пусть, кроме того, $\widehat{\alpha }>\mathrm{0,}$ $\epsilon \in \left(\mathrm{0,}1\right)$ и $\varkappa \in \text{\hspace{0.05em}(0,1)}$ фиксированы, и для каждого $i$ точка $u^{k_i+1}$ получена шагом метода проекции градиента с выбором параметра длины шага по правилу Армихо, а именно, $u^{k_i+1}={\pi }_P(u^{k_i}-{\alpha }_{k_i}{\phi }^{\text{'}}(u^{k_i}\left)\right),$ где ${\alpha }_{k_i}$ есть $\alpha ={\varkappa }^r\widehat{\alpha }$ с минимальным $r\in \{\mathrm{0,}\mathrm{1,}\dots \},$ для которого выполняется

$\phi \left({\pi }_P\right(u^{k_i}-\alpha {\phi }^{\text{'}}\left(u^{k_i}\right)\left)\right)⩽\phi \left(u^{k_i}\right)+\epsilon ⟨{\phi }^{\text{'}}\left(u^{k_i}\right),{\pi }_P(u^{k_i}-\alpha {\phi }^{\text{'}}(u^{k_i}\left)\right)-u^{k_i}⟩.$

Тогда любая предельная точка $\overline{u}$ подпоследовательности $\left\{u^{k_i}\right\}$ стационарна в задаче оптимизации

$\phi \left(u\right)\to \min ,u\in P,$

т. е. $\overline{u}\in P$ и

$⟨{\phi }^{\text{'}}\left(\overline{u}\right),u-\overline{u}⟩⩾0\forall u\in P,$

что равносильно выполнению равенства 

${\pi }_P(\overline{u}-t{\phi }^{\text{'}}(\overline{u}\left)\right)=\overline{u}$

для некоторого $t>\mathrm{0,}$ а значит и для любого $t>0.$

Теорема 2.1. Пусть $\Phi :{ℝ}^p\to {ℝ}^p$ — кусочно-гладкое отображение с непрерывнодифференцируемыми кусочными отображениями ${\Phi }^1\mathrm{,}\dots \mathrm{,}{\Phi }^s\mathrm{.}$ Пусть для $P\subset {ℝ}^p$ —выпуклое замкнутое множество, причем выполняется предположение (0.6). Пусть $G:{ℝ}^p\to {ℝ}^{q\times p}$ — любое отображение, удовлетворяющее (0.4).

Тогда алгоритм 2 либо останавливается в точке $u^k\in P\mathrm{,}$ удовлетворяющей

$⟨{\left(\right({\Phi }^j{)}^{\text{'}}\left(u^k\right))}^{\top }\Phi \left(u^k\right),u-u^k⟩⩾0\forall u\in P$    (2.4)

 по крайней мере для одного $j\in \mathcal{A}\left(u^k\right),$ либо генерирует бесконечную последовательность $\left\{u^k\right\},$ любая предельная точка $\overline{u}$ которой лежит в Р и удовлетворяет

$⟨{\left(\right({\Phi }^j{)}^{\text{'}}\left(\overline{u}\right))}^{\top }\Phi \left(\overline{u}\right),u-\overline{u}⟩⩾0\forall u\in P$   (2,5)

по крайней мере для одного $j\in \mathcal{A}\left(\overline{u}\right).$

Доказательство. Согласно (1.4), алгоритм может остановиться на некоторой итерации к только если либо $u^k\in P$ удовлетворяет $\Phi \left(u^k\right)=\mathrm{0,}$ либо выполняется (2.4) для некоторого $j\in \mathcal{A}\left(u^k\right),$ причем в первом случае, согласно (0.3), ${\Phi }^j\left(u^k\right)=\Phi \left(u^k\right)=\mathrm{0,}$ и (2.4) тоже выполняется (как равенство, для любого $j\in \mathcal{A}\left(u^k\right)$).

Вместе с тем, если (2.4) не выполняется для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k),$ то либо на шаге 3 алгоритма 1 принимается шаг метода Гаусса–Ньютона (т. е. для соответствующего $v^k$ выполняется (2.2)), либо, согласно [12, предложение 2.3.3 (a)], на шаге 5 алгоритма подходящее значение ${\alpha }_k>0$ будет найдено после конечного числа дроблений, а значит, алгоритм успешно определит $u^{k+1}\in P\mathrm{.}$

Пусть теперь (2.4) не выполняется для $j\in \mathcal{A}\left(u^k\right)$ такого, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k),$ ни для какого к а значит, алгоритм генерирует бесконечную последовательность $u^k\subset P\mathrm{.}$ Из (0.3), (0.6) и из (2.2), (2.3) при этом вытекает монотонное невозрастание последовательности $\{\parallel \Phi (u^k)\parallel \}.$ Но тогда, если (2.2) выполняется для бесконечного количества номеров к то эта последовательность стремится к 0 и поэтому, с учетом замкнутости Р всякая предельная точка $\overline{u}$ последовательности $u^k\subset P$ является решением (0.1), а значит, в частности, удовлетворяет (2.5) (как равенству, для любого $j\in \mathcal{A}\left(\overline{u}\right)$).

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

${\phi }_j\left(u\right)\to \min ,u\in P,$

с некоторым $j\in \mathcal{A}\left(u^k\right)$ таким, что $G\left(u^k\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^k).$ Для любой предельной точки $\overline{u}$ последовательности $\left\{u^k\right\},$ в силу включения $\mathcal{A}u\subset \mathcal{A}\overline{u}$ для всех $u\in {ℝ}^p$достаточно близких к $\overline{u}\mathrm{,}$ и в силу конечности множества $\mathcal{A}\left(\overline{u}\right),$ a также с учетом (0.4), найдется сходящаяся к $\overline{u}$ подпоследовательность $\left\{u^{k_i}\right\}$ такая, что $G\left(u^{k_i}\right)=\left({\Phi }^j{)}^{\text{'}}\right(u^{k_i})$ для всех $i\mathrm{,}$ для некоторого фиксированного $j\in \mathcal{A}\left(\overline{u}\right).$

В силу (0.6) и (2.3), поскольку последовательность $\{\parallel \Phi (u^k)\parallel \}$ монотонно невозрастает, снова выводим цепочку неравенств (1.12), откуда следует, что последовательность $\{\dots {\phi }_j(u^{k_i}),{\phi }_j(u^{k_i+1}),\dots \}$ монотонно невозрастает. Остается воспользоваться предложением 2.1, согласно которому $\overline{u}\in P$ и

$⟨{\phi }_{j^{\text{'}}}\left(\overline{u}\right),u-\overline{u}⟩⩾0\forall u\in P,$

что, согласно (0.3) и (1.4), и есть (2.5). 

Следующая теорема устанавливает сверхлинейную скорость сходимости алгоритма 2 в случае $p=q,$ $P={ℝ}^p.$ 

Теорема 2.2. Теорема 1.2 остается справедливой, если алгоритм 1 в ней заменить на алгоритм 2.

Доказательство. Из рассуждений в доказательстве теоремы 1.2 вытекает, что в предположениях этой теоремы алгоритм 2 локально (для $u^k$ достаточно близкого к $\overline{u}$) генерирует то же самое $u^{k+1}\mathrm{,}$ что и алгоритм 1: в силу (1.14), тест (2.2) на шаге 3 алгоритма 2 при этом выполняется, а итерационная подзадача (2.1) кусочного метода Гаусса–Ньютона эквивалентна итерационному уравнению (1.1) кусочного метода Ньютона. Это дает требуемое.

Интересный вопрос состоит в возможности получения результатов о сверхлинейной скорости сходимости для алгоритма 2 при $p\cancel{=}q,$ или при $P\cancel{=}{ℝ}^p.$ Если решения могут быть неизолированы (что естественным образом реализуется при $p>q$), в предположении о естественных предположениях о выполнении локальной липшицевой оценки расстояния до множества решений с этим вопросом нет полной ясности даже в случае $P={ℝ}^p$ и гладкого $\Phi \mathrm{.}$ Точнее, известные результаты о локальной квадратичной сходимости метода Гаусса–Ньютона [13] (даже при выборе единственного решения подзадачи (2.1) минимальной нормы) основаны на ограничительных формах оценок расстояния, и на требованиях на поведение сингулярных чисел производной, необходимость которых в этом анализе даже при $p=q$ и $P={ℝ}^p$ демонстрируется в [13, пример 4.5]. Результаты такого рода в случае $P\cancel{=}{ℝ}^p$ даже при $p=q$ авторам не известны.

About the authors

Dmitriy I. Dorovskikh

Lomonosov Moscow State University

Author for correspondence.
Email: deamterr@gmail.com

Student, Operations Research Department

Russian Federation, 1 Leninskiye Gory, Moscow 119991

Alexey F. Izmailov

Lomonosov Moscow State University

Email: izmaf@cs.msu.ru

Doctor of Physical and Mathematical Sciences, Professor of the Operations Research Department

Russian Federation, 1 Leninskiye Gory, Moscow 119991

Evgeniy I. Uskov

Derzhavin Tambov State University

Email: euskov@cs.msu.ru

Researcher

Russian Federation, 33 Internatsionalnaya St., Tambov 392000

References

Supplementary files