On the Redundancy of Hessian Non-Singularity for Linear Convergence Rate of the Newton Method Applied to the Minimization of Convex Functions

Texto integral

В задаче поиска безусловного минимума рассматриваются функции f(.), определенные и достаточно гладкие в окрестности U(x^*) точки минимума функции n вещественных переменных. Всюду далее множество точек минимума функции f обозначается как $X^{*}=Arg\min f$ и предполагается непустым. Необходимое условие минимума функции f в точке x^* задается равенством fʹ(x^*) = 0, при этом матрица вторых производных функции в точке минимума является положительно полуопределенной. Следует отметить, что исследованиям по методу Ньютона посвящено значительное число научных работ, среди которых укажем [1—7]. Со многими работами можно ознакомиться в обзорной статье [8]. В данной работе показывается, что несмотря на возможную вырожденность матрицы Гессе в точке x^*, в окрестности этой точки градиент целевой функции принадлежит образу ее второй производной и, следовательно, ньютоновская система относительно направления спуска разрешима в точках этой окрестности. Это топологическое свойство выпуклости и экстремальности позволяет по-новому взглянуть на численные методы ньютоновского типа и обосновать скорость сходимости этих методов без обременительного предположения относительно невырожденности матрицы Гессе в точке x^*. Для задачи безусловной оптимизации получены свойства, уточняющие неравенство Лоясевича (см. [9—10]). Именно, неравенство обобщено для всего спектра производных до определенного порядка. В работе рассматриваются функции, производные которой равномерны по аргументу и в совокупности по порядку ограничены в некоторой окрестности U(x^*) точки x^*, т. е. для данной окрестности существует положительная константа M такая, что значения ее производных любого порядка не превосходят по абсолютному значению эту константу. Кроме того, объектом рассмотрения в работе будут достаточно гладкие в окрестности точки минимума функции, т. е. функции, имеющие неограниченное число порядков производных. Всюду далее без ограничения общности считаем f(x^*) = 0 и обозначаем f⁽⁰⁾(x) = f(x). Для функции одной переменной справедлива

Лемма 1. Если x^*-точка изолированного локального минимума достаточно гладкой в U(x^*) функции f: R → R, производные которой равномерно по аргументу и в совокупности по порядку ограничены в некоторой окрестности U(x^*), то существует четная степень $2p,p=p_f\in \mathbb{N}$, для которой справедливы неравенства

$f^{\left(2p\right)}\left(x^{*}\right)>\mathrm{0,} f^{\left(k\right)}\left(x^{*}\right)=\mathrm{0,} \frac{f^{\left(k\right)}\left(x\right)}{{(x-x^{*})}^{2p-k}}\ge C_k, k=\mathrm{0,1,2,}\dots , 2p-1$,

при всех x ∈Ů(x^*), где положительные константы , k = 0, 1, 2, ..., 2p − 1, не зависят от x.

Доказательство. Поскольку x^* — точка локального минимума функции f, то fʹ(x^*) = 0. Сначала покажем, что в условиях леммы невозможна ситуация, когда производные f^(k)(x^*) = 0 при любом порядке k, k = 1, 2, .... Действительно в этом случае для фиксированной точки x = x^* + t ∈U(x^*) в силу ограниченности производных в окрестности x^* из формулы Тэйлора при нулевых производных до любого фиксированного порядка k следует неравенство $\left|f\text{'}\left(x^{*}+\theta t\right)\right|\le \frac{M{\left(\left|\theta t\right|\right)}^k}{k!}$, где M ‒ обозначенная выше верхняя грань для множества значений производных функции f в указанной окрестности и θ ∈(0, 1). Отсюда и из условия изолированности локального минимума x^* значение

$f\left(x^{*}+t\right)={\int }_0^1{f}^{\text{'}}\left(x^{*}+\theta t\right)d\theta \le M/\left(k+1\right)!$

При достаточно больших k это означает противоречие с возможным предположением fʹ(x) ≠ 0, x ≠ x^* что противоречит изолированности локального минимума x^*. Следовательно, существует конечное

$k>1:f^{\left(k\right)}\left(x^{*}\right)\ne \mathrm{0,} f^{\left(l\right)}\left(x^{*}\right)=0, l=\mathrm{1,} \mathrm{2,} \dots , k-1$.

При этом порядок k может быть только четным: $k=2p, p\in \mathbb{N}$ и f^(2p)(x^*) > 0 поскольку x^* — точка локального минимума функции f. Теперь для завершения доказательства достаточно обозначить через C₀ значение $\frac{1}{\left(2p+1\right)!}{f}^{\left(2p\right)}\left(x^{*}\right)$, тогда из формулы Тэйлора и ограниченности производной порядка 2p + 1 в окрестности U(x^*) будет вытекать первое неравенство леммы. Разложение в окрестности x^* по формуле Тэйлора производной  f^(k)(x) дает остальные неравенства леммы при любом k = 1, 2, ..., 2p ‒ 1, если через C_k обозначить $\frac{1}{\left(2p+1-k\right)!}{f}^{\left(2p\right)}\left(x^{*}\right)$.

Следствие 1. При выполнении условий леммы 1 функция f локально выпукла.

Действительно, если f⁽²⁾(x^*) > 0 то в малой окрестности x^* вторая производная будет оставаться положительной, что означает локальную выпуклость f(x). Если же f⁽²⁾(x^*) = 0 то, как показано в лемме 1, f^(2p)(x^*) > 0 для некоторого $p=p=p_f\in \mathrm{\mathbb{N}}, p>1$ и при этом f^(k)(x^*) > 0, k = 1, 2, ..., 2p ‒ 1. Тогда $f^{\left(2\right)}\left(x\right)\ge C_2{(x-x^{*})}^{2p-2}$ для любого x ∈U(x^*), положительная константа C₂ определена ранее в лемме 1. Последнее неравенство также означает локальную выпуклость f.

Для функции n переменных производную k-го порядка по направлению h в точке x будем обозначать как $f_h^{\left(k\right)}\left(x\right)$.

Следствие 2. Если достаточно гладкая функция f: Rⁿ → R производные которой равномерно по аргументу и в совокупности по порядку ограничены в некоторой окрестности U(x^*) изолированной точки минимума x^*, то для каждого h ∈Rⁿ: ||h|| = 1, существует четная степень $2p_{h,f},p_{h,f}\in \mathrm{\mathbb{N}}$, для которой справедливы неравенства

$f^{\left(2p_{h,f}\right)}\left(x^{*}\right)>0, f^{\left(k\right)}\left(x^{*}\right)=0, \frac{f^{\left(k\right)}\left(x^{*}+th\right)}{t^{2p_{h,f}-k}}\ge C_k$,

где $k=\mathrm{0,} 1, \mathrm{2,} \dots , 2p_{h,f}-1$ при всех t ∈ (0, δ_h] положительные константы C_k = C_k,h,f, $k=\mathrm{0,} 1, \mathrm{2,} \dots , 2p_{h,f}-1$ не зависят от t, x^* + δ_h ∈U(x^*) при этом сама функция локально выпукла вдоль направления h.

Здесь элемент $p=p_{h,f}\in \mathrm{\mathbb{N}}$ определяется направлением h, ||h|| = 1 и не зависит от малых t, для которых x^* + δ_h ∈U(x^*), но значение δ_h > 0 зависит от h и в общем случае эта величина может быть бесконечно малой относительно h. Далее в лемме 2 будет показано, что для случая выпуклой функции f можно гарантировать существование верхней границы для величины $p_{h,f}\in \mathrm{\mathbb{N}}$ и положительной нижней границы для δ_h на множестве векторов h: ||h|| = 1.

Из леммы 1 вытекает, что в точках достаточно малой выколотой окрестности решения корректно определен оператор Ньютона $\psi \left(x\right)=x-f^{\left(2\right)}{\left(x\right)}^{-1}f\text{'}\left(x\right)$. Для случая произвольной размерности пространства Rⁿ лемма 1 означает выпуклость функции f вдоль любой прямой, проходящей через точку x^*, при условии достаточной гладкости функции на пересечении прямой и окрестности U(x^*)). Кроме того, для любой прямой, проходящей через точку x^* вдоль вектора h, справедливо неравенство $f_h^{\left(2m\right)}\left(x^{*}\right)\ge C_2$ для некоторой степени 2p, $p=p_h\in \mathrm{\mathbb{N}}$, и некоторой константы C₂ = C_2,h > 0. Неравенство Лоясевича гарантирует выполнимость данного неравенства в случае аналитичности в окрестности U(x^*) функции при некоторых p, C₂, не зависящих от h. Выпуклость в указанной окрестности функции позволяет требовать лишь достаточную гладкость функции и получить свойство “устойчивости” неравенства Лоясевича, что расширяет область применения метода Ньютона. Имеет место

Лемма 2. Если выпуклая достаточно гладкая функция f: Rⁿ = R, производные которой равномерно по аргументу и в совокупности по порядку ограничены в некоторой окрестности U(x^*) изолированной точки минимума x^*, то существует четная степень $2p,p=p_f\in \mathrm{\mathbb{N}}$, константа C = C_f > 0 и величина δ = δ_f > 0 для которых

$f\left(x^{*}+th\right)\ge C{t}^{2p}$

при всех h: ||h|| = 1, t ∈ (0, δ].

Доказательство. Докажем существование такого $p=p_f\in \mathrm{\mathbb{N}}$, обладающего свойством: если $f_h^{\left(i\right)}\left(x^{*}\right)=\mathrm{0,} i=\mathrm{0,} \mathrm{1,} \mathrm{2,} \dots , 2p\text{'}\left(h\right)-\mathrm{1,} f_h^{\left(2p\text{'}\left(h\right)\right)}\left(x^{*}\right)>0$, то p'(h) ≤ p. Предположим противное, тогда для некоторых последовательностей $h_k:||h_k||=\mathrm{1,} t_k:t_k\to +0$ имеет место неравенство $f\left(x^{*}+t_k{h}_k\right)<C_k{t}^{m_k}$, где C_k > 0 — элементы некоторой ограниченной, а $m_k\in \mathbb{N}$ — возрастающей последовательностей. Без ограничения общности можно считать, что h_k → h, C_k → C, k → ∞. Обозначим $conv\left\{h_k, h_{k+1}, h_{k+2},\dots ,h_{k+n}\right\}$ через V_k. В случае dimV_k < n указанный набор векторов изменяется путем прибавления к n ‒ dimV_k векторам линейно независимых приращений длины порядка C_kt^2p, C_k → 0, k → ∞ после чего можно считать dimV_k = n. Пусть далее $h_k^{\text{'}}\in \mathrm{int}{V}_k, h_k^{\text{'}\text{'}}=h+{\alpha }_k\left(h_k^{\text{'}}-h\right), {\alpha }_k\in \left(\mathrm{0,1}\right), {\alpha }_k=\inf \{\alpha >0:h+\alpha \left(h_k^{\text{'}}-h\right)\in V_k\}$. Из выпуклости и непрерывности f следует $f\left(x^{*}+t_k{h}_k^{\text{'}\text{'}}\right)\le 2C{t}^{m_k}$. С другой стороны, из леммы 1 следует, что для некоторого $p=p_h\in \mathrm{\mathbb{N}}$ существует степень $k\in \mathrm{\mathbb{N}}, k\le p$, для которой производная $f_h^{\left(2k\right)}\left(x^{*}\right)\ge C_2>0$ для некоторого C₂ > 0. Поскольку h_k'' → h, k → ∞, то при достаточно больших номерах k будут выполняться неравенства $f\left(x^{*}+t_k{h}_k^{\text{'}\text{'}}\right)\ge C_2{t}^{2k}$, что противоречит предположению.

Следствие 3. Из доказательства леммы 2 следует существование степени 2p, $p=p_f\in \mathbb{N}$, а также констант $C_k=C_{k,f}, k=\mathrm{1,} \mathrm{2,} \dots , 2p\text{'}-1$, для которых

$f_h^{\left(2p\text{'}\right)}\left(x^{*}\right)>\mathrm{0,} f_h^{\left(k\right)}\left(x^{*}\right)=\mathrm{0,} k=\mathrm{0,1,}\dots \mathrm{,2}p\text{'}-\mathrm{1,} f_h^{\left(k\right)}\left(x^{*}+th\right)\ge C_k{t}^{2p-k}, 0<t\le \delta$,

при этом p' = p'(h) ≤ p при всех h: ||h|| = 1.

Для точки $x=x^{*}+th\in U\left(x^{*}\right), ||h||=1$, определим базис $G=G\left(h\right)=\left\{g_1,g_2,\dots ,g_n\right\}$ пространства Rⁿ и соответствующий индекс q = q(h) следующим образом. Рассмотрим матрицы

$a_k=\frac{1}{\left(k-1\right)!}{f}^{\left(k\right)}\left(x^{*}\right){\left[h\right]}^{k-2}, k=2, \mathrm{3,} \dots$.

Тогда в точке x = x^* + th для достаточно гладкой функции f справедливы соотношения

$f^{\left(2\right)}\left(x\right)th=\sum _{k\ge 2}\left(k-1\right)a_{k}h{t}^{k-1}, f^{\text{'}}\left(x\right)=\sum _{k\ge 2}{a}_{k}h{t}^{k-1}, f\left(x\right)=\sum _{k\ge 2}\frac{a_k{\left[h\right]}^2{t}^k}{k}$. (1)

Далее определим номер k₁ ≥ 2 как минимальный среди тех номеров k, для которых одномерное пространство $L_1=L_{k_1}=Lin\left\{a_{k}h\right\}\ne \left\{0\right\}$. Прямую L₁ переобозначим через L¹, вектор g₁ определим как $\frac{a_{k_1}h}{||a_{k_1}h||}$ и далее номер k₂ ≥ k₁ определим как минимальный номер k, для которого Lin{a_kh} не содержится в L¹. Тогда $L_{k_2}=Lin\left\{a_{k_2}h\right\}, \dim \left(L_{k_2}\oplus L^1\right)=2$, одномерное подпространство L₂ определяется как ${\mathrm{Pr}}_{{\left(L^1\right)}^{\perp }}{L}_{k_2}$, вектор g₂ определяется как нормированный вектор ${\mathrm{Pr}}_{L_2}{a}_{k_2}h$. При этом ${\mathrm{Pr}}_{L_2}{a}_{k_2}h\subseteq {\mathrm{Pr}}_{L_2}\mathrm{Im}{a}_{k_2}$. Далее пространство L² определим $L^1\oplus L_2$. Далее для каждого $j=\mathrm{3,} \mathrm{4,} \dots , q=q\left(h\right)$ аналогично определяются прямые $L_j={\mathrm{Pr}}_{{\left(L^{j-1}\right)}^{\perp }}{L}_{k_j}, j=\mathrm{3,} \mathrm{4,} \dots , q$, и соответствующие единичные векторы g_j, j = 1, 2, ..., q. Номер $q=q\left(h\right)=\dim Lin\left\{a_{1}h,a_{2}h,\dots \right\}\le n$, прямая сумма $L^{j-1}\oplus L_j$ обозначается как L^j и является подпространством в Rⁿ размерности j. На конечном этапе построено подпространство L^q размерности q = q(h) ≤ n. Обозначим ортогональное дополнение подпространства L^q через $H:H={\left(L^q\right)}^{\perp }$ в случае q < n и H = {0} при q = n. Определим базис G(h) пространства Rⁿ как набор построенных единичных взаимно ортогональных векторов g₁, g₂, ..., g_q, направленных вдоль построенных ортогональных прямых L_l , l = 1, 2, ..., q, и произвольного ортогонального базиса g_q+1, g_q+2, ..., g_n подпространства H.

Справедлива

Теорема 1. Если для достаточно гладкой функции f:: Rⁿ → R производные равномерно по аргументу и в совокупности по порядку ограничены в некоторой окрестности U(x^*) изолированной точки минимума x^*, то для любого фиксированного h: ||h|| = 1, система

$f^{\left(2\right)}\left(x^{*}+th\right)s=f^{\text{'}}\left(x^{*}+th\right)$ (2)

разрешима относительно s при достаточно малых t.

Доказательство. Решение системы s в базисе G при любом фиксированном векторе h определим покоординатно следующим образом. Положим Pr_HS = 0 далее координата s_q в соответствии с (1) определяется из условия ${\mathrm{Pr}}_{L_q}\left(\left(k_q-1\right)a_{k_q}{t}^{k_q-2}s\right)={\mathrm{Pr}}_{L_q}{f}^{\text{'}}\left(x\right)={\mathrm{Pr}}_{L_q}{\sum }_{k\ge k_q}{a}_{k}h{t}^{k-1}$. При этом $s_q={\mathrm{Pr}}_{L_q}ht/\left(k_q-1\right)+o\left(t\right)$. Подстановка координаты s_q в систему (2) позволяет получить координату $s_{q-1}={\mathrm{Pr}}_{L_{q-1}}ht/\left(k_{q-1}-1\right)+o\left(t\right)$. Далее последовательно определяются координаты $s_l, l=q-\mathrm{2,} q-\mathrm{3,} \dots , 1$. Решение системы (2) вообще говоря, не единственно, но из (1) следует, что координаты любого решения s в базисе G = G(h) имеют вид

$s_j=\frac{{\mathrm{Pr}}_{L_j}ht}{k_j-1}+o\left(t\right), j=\mathrm{1,} \mathrm{2,} \dots , q$. (3)

Замечание 1. Для получения единственного решения системы (2) определим задачу

${\left|s\right|}^2\to {\min }_s, f^{\left(2\right)}\left(x\right)s=f^{\text{'}}\left(x\right)$, (4)

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

Пример 1. Для невыпуклой функции $f\left(x\right)=x_1^4+{(x_2-x_1^2)}^2$ вывод теоремы 1 нарушается для точек параболы $x_2=4x_1^2$. Таким образом, длина интервала, для которого имеет место теорема 1, стремится к нулю, по мере приближения вектора h к (1, 0).

Далее будет показано, что в случае выпуклой функции можно указать общий для всех векторов единичной сферы радиус окрестности переменной t, в пределах которой задача (4) разрешима. Из вида целевой функции задачи (4) следует, что ее решение $s=f^{\left(2\right)}{\left(x\right)}^{+}{f}^{\text{'}}\left(x\right)$, где (.)⁺ означает псевдообратный оператор на своем образе. Координаты решения этой задачи в базисе G удовлетворяют условию Pr_HS = 0.

Теорема 2. При выполнении условий леммы 2 при всех x достаточно близких к x^* задача (4) разрешима и ее решение удовлетворяет условиям

$\left(f\text{'}\left(x\right),s\right)\ge M_1{||x-x^{*}||}^{2p}, \left(f^{\text{'}\text{'}}\left(x\right)s,s\right)\ge M_2{||x-x^{*}||}^{2p}$, (5)

где степень 2p определена в лемме 2, константы $M_1=M_{\mathrm{1,}f}, M_2=M_{\mathrm{2,}f}>0$ не зависят от x.

Доказательство. Из леммы 2 и (1) следует, что при всяком h: ||h|| = 1 номера k_j, определяющие базис G удовлетворяют условию: существует индекс $l_1\in \left\{k_1, k_1+\mathrm{1,} \dots , 2p\right\}$, для которого $a_{l_1}{\left[h\right]}^2\ge C>0$, степень 2p определена в лемме 2 и от h не зависит, константа C > 0 также не зависит от h и определяется в следствии к лемме 2. Последнее неравенство эквивалентно условию $\frac{a_{l_1}{\left[h\right]}^2}{l_1-1}\ge C_1{t}^{2p}$ при малых t. Обозначая $\frac{C}{2p-1}$ через M₁, получим неравенство в утверждении теоремы. Аналогично из следствия к лемме 2 получается и второе неравенство.

Следствие 4. При выполнении условий леммы 2 для выпуклой функции f при всех x достаточно близких к x^* имеет место разрешимость относительно s системы

$f^{\left(2\right)}\left(x\right)s=f\text{'}\left(x\right)$, (6)

что равносильно справедливости включения

$f\text{'}\left(x\right)\in \mathrm{Im}{f}^{\left(2\right)}\left(x\right)$ (7)

независимо от величины ранга матрицы f²(x).

Далее будем обозначать множество $\left\{x\in R^n:f\left(x\right)\le f\left(x^{*}\right)+\epsilon \right\}$ как $X_{\epsilon }^{*}$, диаметр множества A как diamA. Справедлива

Теорема 3. При выполнении условий леммы 2 существует натуральное p и константа $\overline{C}<\infty$, для которых справедливо неравенство

$diam{X}_{\epsilon }^{*}<\overline{C}{\epsilon }^{\frac{1}{2p}}$. (8)

Замечание 2. Указанные ранее свойства справедливы в предположении, что множество точек минимума функции f(x) представляет изолированную точку. Если отказаться от данного предположения, то при выполнении остальных предположений теоремы 1 справедливо представление

$Arg\min f=\left\{x^{*}\right\}+L$, (9)

где L — собственное подпространство Rⁿ, которое определяется условием $f^k\left(x^{*}\right){\left[h\right]}^k=0$ для всякого натурального

Из теорем 1, 2 не следует положительная определенность матрицы f²(x) в окрестности точки минимума x^*. Тем не менее они гарантируют применимость метода Ньютона для поиска точки минимума гладкой функции при условии подходящей начальной точки, поскольку задача (1) позволяет получить вектор перехода в итерационной схеме без предположения выпуклости целевой функции. Кроме того, в данном случае удается получить монотонность по аргументу метода Ньютона, а при более сильных предположениях — линейную скорость сходимости. В случае же выпуклости целевой функции полученное свойство справедливо без дополнительных предположений.

Рассмотрим сначала применение результата теоремы 1 для доказательства монотонности по аргументу схемы метода Ньютона. Именно, определим оператор Ньютона $\psi \left(x,s\right)=x-f^{\left(2\right)}{\left(x\right)}^{+}f\text{'}\left(x\right)$, где $f^{\left(2\right)}{\left(x\right)}^{+}f\text{'}\left(x\right)=s$ — решение задачи (4). Из процесса построения решения s в теореме 1, и замечания к теореме следует, что для любого фиксированного h: ||h|| = 1 при достаточно малых значениях t данный оператор корректно определен без предположения выпуклости функции f. Для получения оценки скорости сходимости дополнительно к предположениям теоремы 1 естественно определяется следующее свойство.

Определение 1. Функция f слабо регулярна в точке x^*, если существует константа d = d_f > 0, для которой ${\max }_{j\le q}\left|h_j\right|\ge d$ для всякого h, ||h|| = 1. Здесь, как и ранее $q=q\left(h\right)=\dim Lin\left\{a_{2}h, a_{3}h, \dots \right\}, h_j$ — координата вектора h с номером j базисе G.

Теорема 4. Если функция f слабо регулярна в точке x^*, то при выполнении условий теоремы 1 существует λ ∈ (0, 1) для которого $||\psi \left(x^{*}+th,s\right)-x^{*}||\le \lambda t$ при всех достаточно малых t.

Доказательство. Для любого решения системы (1) в силу предположения слабой регулярности в точке x^* существует номер j, для которого $||{\mathrm{Pr}}_{L_{k_j}}h||>d$. Отсюда

$$\begin{gathered} ||th-s||\le ||t\sum _{l=\mathrm{1,}l\ne k_j}^q{\mathrm{Pr}}_{L_l}h-{\mathrm{Pr}}_{L_l}s||+t||{\mathrm{Pr}}_{H}h||+\left|t{\mathrm{Pr}}_{L_{k_j}}h-{\mathrm{Pr}}_{L_{k_j}}s\right|\le \\ \le t\left(1-\alpha \right)+t\alpha \left(1-\frac{{\displaystyle 1}}{{\displaystyle k_j-1}}\right)\le t\left(1-\frac{{\displaystyle d}}{{\displaystyle k_j-1}}\right)=\lambda t, \\ \lambda =\lambda \left(h\right)=1-\frac{{\displaystyle d}}{{\displaystyle k_j-1}}\in \left(\mathrm{0,1}\right), \alpha =\alpha \left(h\right)\ge d. \end{gathered}$$

Замечание 3. Полученное неравенство не означает линейной сходимости метода Ньютона, поскольку знаменатель λ который участвует в оценке, вообще говоря, зависит от h. В случае выпуклой функции полученный результат справедлив в более сильном виде: $||\psi \left(x,s\right)-x^{*}||\le \lambda ||x-x^{*}||$ при всех  из достаточно малой окрестности x^*, поскольку для выпуклых функций справедливо следущее свойство.

Определение 2. Функция f равномерно регулярна в точке x^*, если существуют номер $m=m_f\in \mathrm{\mathbb{N}}$ и константа d = d_f > 0, для которых найдется индекс j ≤ q: k_j ≤ m, такой что $||{\mathrm{Pr}}_{L_j}h||\ge d$.

Имеет место

Теорема 5. Если функция f равномерно регулярна в точке x^*, то при выполнении условий теоремы 1 существует λ ∈ (0, 1), для которого $\left|\left|\psi \left(x,s\right)-x^{*}\left|\left|\le \lambda \right|\right|x-x^{*}\right|\right|$ при всех x из достаточно малой окрестности x^*.

Доказательство. Из теоремы 4 следует, что полученный знаменатель λ = λ(h) ограничен сверху равномерно по h, $\left|\left|h\right|\right|=1:\lambda \left(h\right)=1-\frac{d}{k_j-1}\le \lambda \text{'}<1$, где j, k_j ≤ m . Такой номер j существует, как показано в теореме 1. Кроме того, из условия равномерной регулярности следует, что $\left|\left|h_H^{\perp }\right|\right|>d$ для некоторого d > 0, не зависящего от h, где h_A — проекция вектора h на подпространство A. Отсюда следует оценка для знаменателя λ, не зависящая от h.

Замечание 4. Из леммы 2 следует, выпуклая функция равномерно регулярна в точке x^*: $k_j=k_j\left(h\right)\le m=2p,\left|\left|h\right|\right|=1$. Условие равномерной регулярности является необходимым и достаточным условием линейной скорости сходимости метода Ньютона при выполнении условий теоремы 1 без предположения о выпуклости функции f. Итерационная схема метода Ньютона имеет вид

$x_{k+1}=x_k-f^{\left(2\right)}{\left(x_k\right)}^{+}f\text{'}\left(x_k\right)$,

а оценка скорости сходимости метода будет линейная:

$||x_{k+1}-x^{*}||\le \lambda ||x_k-x^{*}||, \lambda \in \left(\mathrm{0,1}\right), k=\mathrm{0,} \mathrm{1,} \mathrm{2,} \dots$,

при начальном приближении достаточно близком к решению x^* в случае равномерно регулярной в точке минимума функции f.

Следствие 5. При выполнении условий теоремы 2 для выпуклой функции скорость сходимости итерационной схемы метода Ньютона является линейной при любом выборе начальной точки x из достаточно малой окрестности решения. Действительно, из теоремы 2 следует, что выпуклая функция является равномерно регулярной в решении x^* откуда вытекает линейная оценка скорости сходимости.

Для получения сходимости метода Ньютона с более высокой скоростью, чем линейная, рассмотрим модифицированный оператор ψ₁(x, s) покоординатная запись которого в базисе G представляет собой ${\psi }_1{(x,s)}_j=x-\left(k_j-1\right)s_j, j=\mathrm{1,} \mathrm{2,} \dots , q; {\psi }_1{(x,s)}_H=x_H-g\left(x,h\right)$, где вектор-функция $g\left(x,h\right):H\to H, s=f^{\left(2\right)}{\left(x\right)}^{+}f\text{'}\left(x\right)$. Оператор ψ₁(x, s)_H позволяет определить модифицированную схему Ньютона $x_{k+1}={\psi }_1\left(x_k, s_k\right)$. Из теоремы 1 следует

Теорема 6. Модифицированная схема Ньютона гарантирует сверхлинейную оценку скорости сходимости при хорошем начальном приближении в том и только том случае, когда функция g(x, h) удовлетворяет условию $||g\left(x,h\right)-h_H||=o\left(t\right)$.

Sobre autores

Yu. Evtushenko

Information Science and Control Federal Research Center, Russian Academy of Sciences; Moscow Institute of Physics and Technology

Autor responsável pela correspondência
Email: yuri-evtushenko@yandex.ru
Rússia, Moscow; Dolgoprudny

A. Tretyakov

Information Science and Control Federal Research Center, Russian Academy of Sciences; Siedlce University

Email: prof.tretyakov@gmail.com
Rússia, Moscow; Siedlce, Poland

Bibliografia

Arquivos suplementares