Методы с суженной матрицей Гессе как возмущенный метод Ньютона–Лагранжа

Full Text

Введение

Методы последовательного квадратичного программирования, использующие вместо настоящей (полной) матрицы Гессе функции Лагранжа ее суженную на ядро матрицы Якоби ограничений версию, направлены на снижения стоимости итерации таких методов, и являются важным инструментом практической условной оптимизации. В данной работе обсуждается возможность интерпретации таких методов как возмущенного метода Ньютона для системы уравнений Лагранжа. Будет показано, что такая интерпретация с нужными оценками на возмущения возможна для определенных последовательностей, генерируемых вариантами метода с поправками второго порядка. Это позволяет с общих позиций установить сверхлинейную скорость сходимости таких последовательностей, вообще говоря отсутствующую для основных последовательностей рассматриваемых методов.

Рассматривается задача оптимизации с ограничениями-равенствами

$f\left(x\right)\to \min ,h\left(x\right)=\mathrm{0,}$ (0.1)

где $f:{ℝ}^n\to ℝ$ и $h:{ℝ}^n\to {ℝ}^l$ дважды дифференцируемы вблизи $\overline{x}\in {ℝ}^n\mathrm{.}$ Метод последовательного квадратичного программирования для задачи (0.1) состоит в следующем [1, разд. 18.1], [2, разд. 4.3.1, 4.4.1], [3, разд. 4.1.1]: для текущего приближения $(x^k,{\lambda }^k)\in {ℝ}^n\times {ℝ}^l$ следующее приближение определяется как $(x^{k+1},{\lambda }^{k+1}),$ где $x^{k+1}=x^k+{\xi }^k,$ ${\xi }^k$ является стационарной точкой квадратичной задачи

$⟨f^{\text{'}}\left(x^k\right),\xi ⟩+\frac{1}{2}⟨\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k)\xi ,\xi ⟩\to \min ,h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =\mathrm{0,}$ (0.2)

а ${\lambda }^{k+1}$ — отвечающим этой стационарной точке множителем Лагранжа. Здесь $L:{ℝ}^n\times {ℝ}^l\to ℝ$ — функция Лагранжа задачи (0.1):

$L(x,\lambda )=f\left(x\right)+⟨\lambda ,h\left(x\right)⟩.$

Система уравнений Лагранжа задачи (0.2), характеризующая ее стационарные точки и отвечающие им множители, имеет вид

$f^{\text{'}}\left(x^k\right)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k)\xi +{\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda =\mathrm{0,}h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =0.$ (0.3)

Отсюда следует, что итерация метода последовательного квадратичного программирования есть ни что иное, как итерация метода Ньютона–Лагранжа, т. е. метода Ньютона, применяемого к системе уравнений Лагранжа

$\frac{\partial L}{\partial x}(x,\lambda )=\mathrm{0,}h\left(x\right)=0$ (0.4)

исходной задачи (0.1): уравнения в (0.3) получаются линеаризацией в текущем приближении $(x^k,{\lambda }^k)$ уравнений из (0.4).

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

Точнее, согласно 3предложение 4.4], для сохранения сверхлинейной скорости сходимости генерируемой прямой последовательности $\left\{x^k\right\}$ к стационарной точке $\overline{x}\in {ℝ}^n$ задачи (0.1) (при наличии сходимости прямодвойственной последовательности $\left\{\right(x^k,{\lambda }^k\left)\right\}$ к $(\overline{x},\overline{\lambda }),$ где $\overline{\lambda }\in {ℝ}^l$ — некоторый отвечающий $\overline{x}$ множитель Лагранжа) должны удовлетворять итерационной системе

$f^{\text{'}}\left(x^k\right)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k)(x-x^k)+{\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda +{\omega }_1^k=\mathrm{0,}h\left(x^k\right)+h^{\text{'}}\left(x^k\right)(x-x^k)+{\omega }_2^k=\mathrm{0,}$ (0.5)

возмущенного метода Ньютона–Лагранжа, получаемой добавлением к уравнениям в (0.3) параметров возмущения ${\omega }_1^k\in {ℝ}^n$ и ${\omega }_2^k\in {ℝ}^l\mathrm{,}$ которые должны удовлетворять оценкам

$P{\omega }_1^k=o(\parallel x^{k+1}-x^k\parallel +\parallel x^k-\overline{x}\parallel ),$ (0.6)

${\omega }_2^k=o(\parallel x^{k+1}-x^k\parallel +\parallel x^k-\overline{x}\parallel )$ (0.7)

при $k\to \infty$ см. [3, (4.12), (4.13)]. Здесь P — оператор ортогонального проектирования на $\ker h^{\text{'}}\left(\overline{x}\right).$ Более того, при выполнении в стационарной точке $\overline{x}$ с множителем $\overline{\lambda }$ достаточного условия второго порядка оптимальности оценки (0.6), (0.7) являются и достаточными для сверхлинейной сходимости.

Методы с суженной матрицей Гессе, рассматриваемые в данной работе, позволяют избежать необходимости вычисления полной матрицы Гессе функции Лагранжа, поскольку на их итерациях используется только вводимая в разд. 1 так называемая суженная матрица Гессе, размерность которой определяется размерностью $\ker h^{\text{'}}\left(x^k\right),$ что может быть (и обычно является) гораздо меньшим числом, чем n. Интерпретация этих методов как возмущенного метода Ньютона–Лагранжа не позволяет получить оценки (0.6), (0.7), и действительно, как демонстрирует пример, предложенный в [4] (см. пример 2.1 ниже), эти методы, вообще говоря, обладают лишь двухшаговой сверхлинейной скоростью сходимости, что является более слабым свойством, чем обычная (одношаговая) сверхлинейная скорость сходимости. (Отметим также аналогичный пример, построенный в [5]. Однако, корректность его конструкции и приведенные численные результаты вызывают определенные сомнения, главным образом в связи с очевидной ошибочностью выражений для производных по первой переменной в (2.14).)

Вместе с тем, как будет показано в разд. 2, если снабдить метод так называемыми поправками второго порядка, предназначенными для того, чтобы генерируемые прямые приближения были ближе к допустимому множеству задачи (0.1), то получаемый процесс можно интерпретировать как возмущенный метод Ньютона–Лагранжа с требуемыми оценками (0.6), (0.7), но не для основной последовательности метода, а для некоторой последовательности вспомогательных приближений, также генерируемых методом. Это позволяет получить новое общее понимание результата о сверхлинейной скорости сходимости последовательности таких вспомогательных приближений, доказанного в [6].

1. Методы с суженной матрицей Гессе

Обозначим через $P_k$ оператор ортогонального проектирования на $\ker h^{\text{'}}\left(x^k\right),$ и для всякого $\xi \in {ℝ}^n$ будем использовать разложение $\xi ={\xi }_1+{\xi }_2,$ ${\xi }_1=(I-P_k)\xi ,$ ${\xi }_2=P_k\xi .$ Тогда ограничение в (0.2) принимает вид

$h\left(x^k\right)+h^{\text{'}}\left(x^k\right){\xi }_1=\mathrm{0,}$ (1.1)

и если $rank{h}^{\text{'}}\left(x^k\right)=$ (условие, которое всюду далее предполагается выполненным), то это уравнение однозначно определяет

${\xi }_1^k=-{\left(h^{\text{'}}\right(x^k\left)\right)}^T{\left(h^{\text{'}}\right(x^k\left){\left(h^{\text{'}}\right(x^k\left)\right)}^T\right)}^{-1}h\left(x^k\right)$ (1.2)

как единственное нормальное решение уравнения в ограничении задачи (0.2). Фиксируя это ${\xi }_1^k\mathrm{,}$ из (2) получаем задачу для определения ${\xi }_2^k$:

$⟨f^{\text{'}}\left(x^k\right)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k){\xi }_1^k,{\xi }_2⟩+\frac{1}{2}⟨\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k){\xi }_2,{\xi }_2⟩\to \min ,{\xi }_2\in \ker h^{\text{'}}\left(x^k\right).$ (1.3)

Ключевой момент в конструкции методов с суженной матрицей Гессе состоит в том, что слагаемое в (1.3), содержащее ${\xi }_1^k$ и ${\xi }_2\mathrm{,}$ опускается. Используя равенство ${\xi }_2=P_k\xi ,$ так модифицированная задача (1.3) вместе с уравнением (1.1) сводится к задаче

$⟨f^{\text{'}}\left(x^k\right),\xi ⟩+\frac{1}{2}⟨P\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k)P\xi ,\xi ⟩\to \min ,h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =\mathrm{0,}$ (1.4)

записанной снова относительно исходной переменной $\xi$ задачи (0.2).

Чтобы привести задачу (1.4) к более «практической» форме, потребуется конкретное представление проектора $P_k\mathrm{.}$ Пусть столбцы матрицы $Z_k$ размеров $n\times (n-l)$ образуют некоторый базис линейного подпространства $\ker h^{\text{'}}\left(x^k\right).$ (Напомним, что предполагается выполненным условие $rank{h}^{\text{'}}\left(x^k\right)=l,$ и значит, $\mathrm{dimker}{h}^{\text{'}}\left(x^k\right)=n-l.$) Тогда, как нетрудно видеть, $P_k=Z_k{\left(Z_k^T{Z}_k\right)}^{-1}{Z}_k^T,$ и задача (1.4) принимает вид

$⟨f^{\text{'}}\left(x^k\right),\xi ⟩+\frac{1}{2}⟨Z_k{\left(Z_k^T{Z}_k\right)}^{-1}{H}_k{\left(Z_k^T{Z}_k\right)}^{-1}{Z}_k^T\xi ,\xi ⟩\to \min ,h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =\mathrm{0,}$ (1.5)

где симметричная $(n-l)\times (n-l)$ матрица

$H_k=Z_k^T\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k)Z_k$ (1.6)

и есть суженная матрица Гессе функции Лагранжа.

Если столбцы матрицы $Z_k$ образуют ортонормированную систему, то $Z_k^T{Z}_k=I,$ $P_k=Z_k{Z}_k^T,$ и задача (1.5) принимает вид

$⟨f^{\text{'}}\left(x^k\right),\xi ⟩+\frac{1}{2}⟨Z_k{H}_k{Z}_k^T\xi ,\xi ⟩\to \min ,h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =0.$ (1.7)

Это в точности соответствует подзадаче, использованной в [7, (1.2)]. Заметим, что указанное свойство столбцов матрицы $Z_k$ всегда выполняется, если матрица $\left(Y_k{Z}_k\right)$ с некоторой $n\times l$ матрицей $Y_k$ получена QR-факторизацией ${\left(h^{\text{'}}\right(x^k\left)\right)}^T,$ что дает практический способ вычисления $Z_k$ [1, разд. 15.3]. При этом столбцы $Y_k$ образуют ортонормированный базис в ${\left(\ker h^{\text{'}}\right(x^k\left)\right)}^{\perp },$ и $I-P_k=Y_k{Y}_k^T.$

Из сказанного выше ясно, что подзадача (1.4), а значит, и ее «практические» версии (1.5) и (1.7), отличаются от подзадачи (0.2) базового метода последовательного квадратичного программирования по существу только отсутствием в целевой функции слагаемого, содержащего оба ${\xi }_1$ и ${\xi }_2\mathrm{.}$ В частности, эти методы совпадают, если для каждого k. 

$⟨\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k){\xi }_1,{\xi }_2⟩=0\forall \xi \in {ℝ}^n$

(факт, отмеченный в [7, с. 286]). Если же

$⟨\frac{{\partial }^{2}L}{\partial x^2}(\overline{x},\overline{\lambda }){\xi }_1,{\xi }_2⟩=0\forall \xi \in {ℝ}^n$ (1.8)

для предельной пары $(\overline{x},\overline{\lambda }),$ то методы, вообще говоря, не совпадают, но методы с суженной матрицей Гессе могут быть интерпретированы как возмущенный метод Ньютона–Лагранжа с требуемыми оценками (0.6), (0.7) (см. разд. 2), а значит, имеют в соответствующих предположениях сверхлинейную скорость сходимости (что соответствует сказанному в [5, с. 231]).

$⟨f^{\text{'}}\left(x^k\right),\xi ⟩+\frac{1}{2}⟨H_k\xi ,\xi ⟩\to \min ,h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =\mathrm{0,}$ (1.9)

в которой используется матрица $H_k\mathrm{,}$ задаваемая равенством

${\left(Z_k{Y}_k\right)}^T{H}_k\left(Z_k{Y}_k\right)=\left(\begin{array}{cc}{H}_k& 0\\ 0& I\end{array}\right),$

где $H_k$ введено в (13). Если столбцы $Z_k$ и $Y_k$ ортонормированы, то

$\left(Z_k{Y}_k\right){\left(Z_k{Y}_k\right)}^T=Z_k{Z}_k^T+Y_k{Y}_k^T=I,$

и поэтому

$\begin{array}{c}⟨H_k\xi ,\xi ⟩=⟨H_k\left(Z_k{Y}_k\right){\left(Z_k{Y}_k\right)}^T\xi ,\left(Z_k{Y}_k\right){\left(Z_k{Y}_k\right)}^T\xi ⟩\\ =⟨{\left(Z_k{Y}_k\right)}^T{H}_k\left(Z_k{Y}_k\right){\left(Z_k{Y}_k\right)}^T\xi ,{\left(Z_k{Y}_k\right)}^T\xi ⟩=⟨(H_k{Z}_k^T\xi ,Y_k^T\xi ),(Z_k^T\xi ,Y_k^T\xi )⟩\\ =⟨Z_k{H}_k{Z}_k^T\xi ,\xi ⟩+⟨Y_k^T\xi ,Y_k^T\xi ⟩,\end{array}$              (1.10)

причем

$⟨Y_k^T\xi ,Y_k^T\xi ⟩=⟨Y_k^T{Y}_k{Y}_k^T\xi ,Y_k^T\xi ⟩=⟨Y_k{Y}_k^T\xi ,Y_k{Y}_k^T\xi ⟩=\parallel (I-P_k)\xi {\parallel }^2=\parallel {\xi }_1{\parallel }^2.$

Вспоминая, что, как обсуждалось выше, ${\xi }_1^k$ однозначно определяется ограничением в (1.7), а значит и идентичным ему в (1.9), отсюда получаем, что второе слагаемое в правой части (1.10) не играет в целевой функции подзадачи (1.9) никакой роли, и эта подзадача сводится к (1.7).

Далее, умножением обеих частей первого уравнения в системе Лагранжа

$f^{\text{'}}\left(x^k\right)+Z_k{H}_k{Z}_k^T\xi +{\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda =\mathrm{0,}h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =0$ (1.11)

задачи (1.7) на $Z_k^T\mathrm{,}$ необходимые условия первого порядка оптимальности для этой задачи могут быть записаны в следующей «прямой» форме, не использующей $\lambda$:

$Z_k^T{f}^{\text{'}}\left(x^k\right)+H_k{Z}_k^T\xi =\mathrm{0,}h\left(x^k\right)+h^{\text{'}}\left(x^k\right)\xi =\mathrm{0,}$ (1.12)

откуда следует выполнение равенства (1.2), а в дополнительном предположении о невырожденности $H_k$ и равенства

$Z_k^T{\xi }_2^k=-H_k^{-1}{Z}_k^T{f}^{\text{'}}\left(x^k\right).$

Последнее также можно записать в виде явного выражения

${\xi }_2^k=P_k{\xi }_2^k=Z_k{Z}_k^T{\xi }_2=-Z_k{H}_k^{-1}{Z}_k^T{f}^{\text{'}}\left(x^k\right).$ (1.13)

Вместе с тем, умножая обе части первого уравнения в (1.11) на $Y_k^T\mathrm{,}$ получаем

$Y_k^T{f}^{\text{'}}\left(x^k\right)+Y_k^T{\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda =\mathrm{0,}$ (1.14)

Дальнейшее умножение на $Y_k$ приводит это уравнение к «инвариантому» виду

$(I-P_k)f^{\text{'}}\left(x^k\right)+{\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda =0$

(поскольку $(I-P_k){\left(h^{\text{'}}\right(x^k\left)\right)}^T={\left(h^{\text{'}}\right(x^k\left)\right(I-P_k\left)\right)}^T={\left(h^{\text{'}}\right(x^k\left)\right)}^T$), не зависящему от выбора $Y_k\mathrm{.}$ Если взять, например, $Y_k={\left(h^{\text{'}}\right(x^k\left)\right)}^T,$ что обеспечивается требуемую здесь базисность столбцов этой матрицы в $\ker h^{\text{'}}\left(x^k\right)$ (но, разумеется, не их ортонормированность), то из (1.14) получаем уравнение

$h^{\text{'}}{\left(x^k\right)}^T{f}^{\text{'}}\left(x^k\right)+h^{\text{'}}\left(x^k\right){\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda =0.$ (1.15)

Отсюда следует явное выражение

${\lambda }^{k+1}=-{\left(h^{\text{'}}\right(x^k\left){\left(h^{\text{'}}\right(x^k\left)\right)}^T\right)}^{-1}{h}^{\text{'}}\left(x^k\right)f^{\text{'}}\left(x^k\right).$ (1.16)

Это соответствует [7, (2.13)], где, правда, $x^k$ заменяется на $x^{k+1}$: ${\lambda }^{k+1}$ (и $x^{k+1}$) используются для определения $H_{k+1}\mathrm{,}$ и это возможно, поскольку здесь, в отличие от обычного метода Ньютона–Лагранжа, итерация естественным образом разделяется на прямую и двойственную фазы. Использование (1.16) также соответствует выбору ${\lambda }^{k+1}$ как решения задачи квадратичной задачи безусловной оптимизации

$\parallel f^{\text{'}}\left(x^k\right)+{\left(h^{\text{'}}\right(x^k\left)\right)}^T\lambda {\parallel }^2\to \min$

относительно $\lambda \in {ℝ}^l\mathrm{.}$ Существуют и другие способы задания ${\lambda }^{k+1}\mathrm{,}$ например [7, (2.14)], где, впрочем, этот способ приводится без объяснения его происхождения.

Уравнения (1.12) и (1.15), порождающие явные выражения (1.2), (1.13) и (1.16), характеризуют класс методов последовательного квадратичного программирования, в форме методов Ньютона–Лагранжа, с суженной матрицей Гессе. В частности, (1.12) соответствует методу в [5, (1.5), (1.6)], который, в свою очередь, был взят из [8, алгоритм 4.1], где, собственно, и была установлена двухшаговая сверхлинейная сходимость методов такого типа. См. также [9, (14.41), теорема~14.7]. Следует также упомянуть так называемый «горизонтально-вертикальный» алгоритм из [10], который также рассматривался в [4](cм. также [9, (14.40)]): в нем используются выражения (1.2), (1.13), но только сначала вычисляется ${\xi }_2^k$ согласно (1.13), и затем ${\xi }_1^k$ согласно (1.2), где вместо $h\left(x^k\right)$ используется $h(x^k+{\xi }_2^k).$

Разные варианты методов указанного класса могут отличаться способами выбора $Z_k\mathrm{.}$ Кроме того, важнейшее значение имеют методы, использующие не саму суженную матрицу Гессе из (1.6), а ее аппроксимации, и прежде всего квазиньютоновские. Эти вопросы обсуждаются [8] и в последующих цитированных публикациях, но здесь они не рассматриваются.

В некоторых изложениях (см., например, [1, разд. 18.3]) методов с суженной матрицей Гессе используют представления ${\xi }_1=Y_k\eta$ и ${\xi }_2=Z_k\zeta ,$ где $\eta \in {ℝ}^l$ и $\zeta \in {ℝ}^{n-l}$ однозначно определяются. Если столбцы $Z_k$ ортонормированы, то, подставляя эти выражения в (1.12), получаем уравнения $Z_k^T{f}^{\text{'}}\left(x^k\right)+H_k\zeta =\mathrm{0,}h\left(x^k\right)+h^{\text{'}}\left(x^k\right)Y_k\eta =\mathrm{0,}$

для определения $\eta$ и $\zeta \mathrm{.}$

2. Методы с поправками второго порядка

Помимо метода из [10], обсуждавшегося в [4], в [6] рассматривается вариант метода последовательного квадратичного программирования с суженной матрицей Гессе, снабженный так называемыми поправками второго порядка [1, разд. 15.6], [2, разд. 5.4.2], [3, разд. 4.3.6, 6.2.2]. А именно, следующее приближение определяется равенством $x^{k+1}=x^k+{\xi }^k+{\overline{\xi }}^k,$ где ${\xi }^k$ — стационарная точка подзадачи (1.7), т. е. решение системы (1.12), а ${\overline{\xi }}^k$ — нормальное решение уравнения

$h(x^k+{\xi }^k)+h^{\text{'}}\left(x^k\right)\xi =\mathrm{0,}$ (2.1)

т. е.

${\overline{\xi }}^k=-{\left(h^{\text{'}}\right(x^k\left)\right)}^T{\left(h^{\text{'}}\right(x^k\left){\left(h^{\text{'}}\right(x^k\left)\right)}^T\right)}^{-1}h(x^k+{\xi }^k).$ (2.2)

Заметим, что при этом ${\overline{\xi }}^k\in {im\left(h^{\text{'}}\right(x^k\left)\right)}^T={\left(\ker h^{\text{'}}\right(x^k\left)\right)}^{\perp },$ т. е. ${\overline{\xi }}_2^k=0.$ Новое двойственное приближение ${\lambda }^{k+1}$ по-прежнему определяется уравнением (1.15).

Лемма 2.1. Пусть функция $f:{ℝ}^n\to ℝ$ и отображение $h:{ℝ}^n\to {ℝ}^l$ дважды непрерывно дифференцируемы вблизи точки $\overline{x}\in {ℝ}^n\mathrm{.}$ Пусть $\overline{x}$ является стационарной точкой задачи (0.1), а $\overline{\lambda }\in {ℝ}^l$ — отвечающим ей множителем Лагранжа, причем выполнено условие регулярности ограничений $rank{h}^{\text{'}}\left(\overline{x}\right)=l$ и достаточное условие второго порядка оптимальности

$⟨\frac{{\partial }^{2}L}{\partial x^2}(\overline{x},\overline{\lambda })\xi ,\xi ⟩>0\forall \xi \in \ker h^{\text{'}}\left(\overline{x}\right)\backslash \left\{0\right\}.$ (2.3)

Пусть последовательность $\left\{\right(x^k,{\lambda }^k\left)\right\},$ сгенерированная описанной выше процедурой, сходится к $(\overline{x},\overline{\lambda }).$

Тогда

${\xi }^k=O(\parallel x^k-\overline{x}\parallel ),$ (2.4)

$h(x^k+{\xi }^k)=O(\parallel x^k-\overline{x}{\parallel }^2),$ (2.5)

${\overline{\xi }}^k=O(\parallel x^k-\overline{x}{\parallel }^2),$ (2.6)

при $k\to \infty \mathrm{.}$ 

Доказательство. Оценка (2.4) следует из (1.2) и (1.13), поскольку в сделанных предположениях матрицы $h^{\text{'}}\left(x^k\right){\left(h^{\text{'}}\right(x^k\left)\right)}^T$ и $H_k$ равномерно обратимы для $(x^k,{\lambda }^k)$ достаточно близких к $(\overline{x},\overline{\lambda }).$

Кроме того, в силу второго уравнения в (1.12),

$h(x^k+{\xi }^k)=h\left(x^k\right)+h^{\text{'}}\left(x^k\right){\xi }^k+O(\parallel {\xi }^k{\parallel }^2)=O(\parallel {\xi }^k{\parallel }^2),$

и поэтому, согласно (2.2),

${\overline{\xi }}^k=O(\parallel h(x^k+{\xi }^k)\parallel )=O(\parallel {\xi }^k{\parallel }^2).$

Из последних двух оценок и из (2.4) следуют оценки (2.5), (2.6).

Согласно первому равенству в (0.5), используя представление $P_k=Z_k{Z}_k^T$ и оценку (2.6), выводим

$\begin{array}{c}{P}_k{\omega }_1^k=-P_k\left(f^{\text{'}}\right(x^k)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k\left)\right({\xi }^k+{\overline{\xi }}^k)+{\left(h^{\text{'}}\right(x^k\left)\right)}^T{\lambda }^{k+1})\\ =Z_k\left(Z_k^T{f}^{\text{'}}\right(x^k)+Z_k^T\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k)Z_k{Z}_k^T{\xi }^k+Z_k^T\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k\left){\xi }_1^k\right)+O(\parallel x^k-\overline{x}{\parallel }^2)\\ =P_k\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k){\xi }_1^k+O(\parallel x^k-\overline{x}{\parallel }^2),\end{array}$ (2.7)

где в последнем равенстве использовано определение $H_k$ в (1.6) и первое уравнение в (1.12). Заметим, что в обеих частях этой оценки $P_k$ можно заменить на $P\mathrm{,}$ поскольку

$P_k-P=O(\parallel x^k-\overline{x}\parallel )$ (2.8)

при $k\to \infty \mathrm{.}$ Это следует, например, из явного представления

$P_k=(I-{\left(h^{\text{'}}\right(x^k\left)\right)}^T{\left(h^{\text{'}}\right(x^k\left){\left(h^{\text{'}}\right(x^k\left)\right)}^T\right)}^{-1}{h}^{\text{'}}(x^k)$ (2.9)

и равномерной обратимости матриц $\left(h^{\text{'}}\right(x^k){\left(h^{\text{'}}\right(x^k\left)\right)}^T$ для $x^k$ близких к $\overline{x}\mathrm{.}$

Далее, согласно второму равенству в (0.5), используя второе уравнение в (1.12), (2.1), и оценку (2.5), выводим

${\omega }_2^k=-h\left(x^k\right)-h^{\text{'}}\left(x^k\right)({\xi }^k+{\overline{\xi }}^k)=-h^{\text{'}}\left(x^k\right){\overline{\xi }}^k=-h(x^k+{\xi }^k)=O(\parallel x^k-\overline{x}{\parallel }^2).$

Таким образом, оценка (0.7) имеет место, а вот (0.6) можно гарантировать лишь при выполнении (1.8), причем эти рассуждения тем более проходят и при использовании ${\overline{\xi }}^k=\mathrm{0,}$ т. е. сделанные выводы верны как для метода без поправок второго порядка, так и с такими поправками. В частности, гарантировать сверхлинейную скорость сходимости последовательности $\left\{x^k\right\}$ по-прежнему нельзя и для метода с поправками второго порядка.

Теперь обратимся к поведению последовательности $\left\{{\tilde{x}}^k\right\},$ генерируемой по правилу

${\tilde{x}}^{k+1}=x^k+{\xi }^k=x^{k-1}+{\xi }^{k-1}+{\overline{\xi }}^{k-1}+{\xi }^k={\tilde{x}}^k+{\overline{\xi }}^{k-1}+{\xi }^k.$

Иными словами, будем рассматривать следующий двухшаговый процесс:

$\begin{array}{c}{x}^{k-1}\\ \downarrow 0.5em\\ {\tilde{x}}^k=x^{k-1}+{\xi }^{k-1}\\ \downarrow 0.5em\\ x^k={\tilde{x}}^k+{\overline{\xi }}^{k-1}=x^{k-1}+{\xi }^{k-1}+{\overline{\xi }}^{k-1}\\ \downarrow 0.5em\\ {\tilde{x}}^{k+1}=x^k+{\xi }^k={\tilde{x}}^k+{\overline{\xi }}^{k-1}+{\xi }^k.\end{array}$

Из оценок в лемме 2.1 вытекает, что последовательности $\left\{{\tilde{x}}^k\right\}$ сходится к тому же пределу $\overline{x}\mathrm{,}$ что и последовательность $\left\{x^k\right\}.$

Помимо оценок из леммы 2.1, приведем некоторые дополнительные оценки на ингредиенты рассматриваемого итерационного процесса, следующие из [6, леммы 3.1, 3.3].

Лемма 2.2. В предположениях леммы 2.1

${\overline{\xi }}^{k-1}=O(\parallel {\tilde{x}}^k-\overline{x}\parallel ),$ (2.10)

$h^{\text{'}}\left(x^k\right){\xi }^k=o(\parallel {\tilde{x}}^k-\overline{x}\parallel )$ (2.11)

при $k\to \infty \mathrm{.}$ 

Теорема 2.1. В предположениях леммы 2 для

${\tilde{\omega }}_1^k=-f^{\text{'}}\left(x^k\right)-\frac{{\partial }^{2}L}{\partial x^2}({\tilde{x}}^k,{\lambda }^k)({\tilde{x}}^{k+1}-{\tilde{x}}^k)-{\left(h^{\text{'}}\right({\tilde{x}}^k\left)\right)}^T{\lambda }^{k+1}$ (2.12)

и

${\tilde{\omega }}_2^k=-h\left({\tilde{x}}^k\right)-h^{\text{'}}\left({\tilde{x}}^k\right)({\tilde{x}}^{k+1}-{\tilde{x}}^k)$ (2.13)

выполняются оценки

$P{\tilde{\omega }}_1^k=o(\parallel {\tilde{x}}^k-\overline{x}\parallel ),$ (2.14)

${\tilde{\omega }}_2^k=o(\parallel {\tilde{x}}^k-\overline{x}\parallel )$ (2.15)

при $k\to \infty \mathrm{,}$ и, в частности, последовательность $\left\{{\tilde{x}}^k\right\}$ сходится к $\overline{x}$ со сверхлинейной скоростью.

Последнее утверждение теоремы согласуется с [6, теорема 3.5].

Доказательство. Согласно (2.12), привлекая теорему о среднем, выводим

$\begin{array}{c}{P}_k{\tilde{\omega }}_1^k=-P_k\left(f^{\text{'}}\right(x^{k-1}+{\xi }^{k-1})+\frac{{\partial }^{2}L}{\partial x^2}(x^{k-1}+{\xi }^{k-1},{\lambda }^k\left)\right({\overline{\xi }}^{k-1}+{\xi }^k)+{\left(h^{\text{'}}\right(x^{k-1}+{\xi }^{k-1}\left)\right)}^T{\lambda }^{k+1})\\ =-P_k\left(\frac{\partial L}{\partial x}\right(x^{k-1}+{\xi }^{k-1},{\lambda }^k)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k\left)\right({\overline{\xi }}^{k-1}+{\xi }^k)+{\left(h^{\text{'}}\right(x^k\left)\right)}^T({\lambda }^{k+1}-{\lambda }^k\left)\right)\\ +O(\parallel {\xi }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\lambda }^{k+1}-{\lambda }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\overline{\xi }}^{k-1}{\parallel }^2)\\ =P_k\left(\frac{\partial L}{\partial x}\right(x^{k-1}+{\xi }^{k-1}+{\overline{\xi }}^{k-1},{\lambda }^k)-\frac{\partial L}{\partial x}(x^{k-1}+{\xi }^{k-1},{\lambda }^k)-\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k\left){\overline{\xi }}^{k-1}\right)\\ -P_k\left(\frac{\partial L}{\partial x}\right(x^{k-1}+{\xi }^{k-1}+{\overline{\xi }}^{k-1},{\lambda }^k)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k\left){\xi }^k\right)\\ \end{array}$

$\begin{array}{c}+O(\parallel {\xi }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\lambda }^{k+1}-{\lambda }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\overline{\xi }}^{k-1}{\parallel }^2)\\ =-P_k\left(\frac{\partial L}{\partial x}\right(x^k,{\lambda }^k)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k\left){\xi }^k\right)\\ +O(\parallel {\xi }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\lambda }^{k+1}-{\lambda }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\overline{\xi }}^{k-1}{\parallel }^2)\\ =-P_k\left(f^{\text{'}}\right(x^k)+\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k){\xi }^k+{\left(h^{\text{'}}\right(x^k\left)\right)}^T{\lambda }^k)\\ +O(\parallel {\xi }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\lambda }^{k+1}-{\lambda }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\overline{\xi }}^{k-1}{\parallel }^2)\\ =-P_k\frac{{\partial }^{2}L}{\partial x^2}(x^k,{\lambda }^k){\xi }_1^k+O(\parallel {\xi }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\lambda }^{k+1}-{\lambda }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\overline{\xi }}^{k-1}{\parallel }^2),\end{array}$

где последнее равенство выводится по аналогии с (2.7). Замечая, что согласно (2.9),

${\xi }_1^k=(I-P_k){\xi }^k={\left(h^{\text{'}}\right(x^k\left)\right)}^T{\left(h^{\text{'}}\right(x^k\left){\left(h^{\text{'}}\right(x^k\left)\right)}^T\right)}^{-1}{h}^{\text{'}}\left(x^k\right){\xi }^k,$

отсюда и из оценок (2.10), (2.11) следует оценка

$P_k{\tilde{\omega }}_1^k=o(\parallel {\tilde{x}}^k-\overline{x}\parallel ).$ (2.16)

Принимая во внимание (2.8) и вытекающую из (2.10) оценку,

$x^k-\overline{x}={\tilde{x}}^k-\overline{x}+{\overline{\xi }}^{k-1}=O(\parallel {\tilde{x}}^k-\overline{x}\parallel ),$

имеем

$P_k-P=O(\parallel {\tilde{x}}^k-\overline{x}\parallel ),$

откуда и из (2.16) следует оценка (2.14).

Далее, согласно (2.13), используя (2.1), выводим

$\begin{array}{c}{\tilde{\omega }}_2^k=-h(x^{k-1}+{\xi }^{k-1})-h^{\text{'}}(x^{k-1}+{\xi }^{k-1})({\overline{\xi }}^{k-1}+{\xi }^k)\\ =-h(x^{k-1}+{\xi }^{k-1})-h^{\text{'}}\left(x^{k-1}\right){\overline{\xi }}^{k-1}-\left(h^{\text{'}}\right(x^{k-1}+{\xi }^{k-1})-h^{\text{'}}(x^{k-1}\left)\right){\overline{\xi }}^{k-1}-h^{\text{'}}(x^{k-1}+{\xi }^{k-1}){\xi }^k\\ =-\left(h^{\text{'}}\right(x^{k-1}+{\xi }^{k-1})-h^{\text{'}}(x^k\left)\right){\xi }^k-h^{\text{'}}\left(x^k\right){\xi }^k+O(\parallel {\xi }^{k-1}\parallel \parallel {\overline{\xi }}^{k-1}\parallel )\\ =-h^{\text{'}}\left(x^k\right){\xi }^k+O(\parallel {\xi }^{k-1}\parallel \parallel {\overline{\xi }}^{k-1}\parallel )+O(\parallel {\xi }^k\parallel \parallel {\overline{\xi }}^{k-1}\parallel ),\end{array}$

откуда и из оценок (2.10), (2.11) следует оценка (2.15).

Последнее утверждение теоремы вытекает из полученных оценок (2.14), (2.15) и из[3, предложение 4.4].

Следующий пример был предложен в [4, пример 2].

Пример 2.1. Рассмотрим задачу (0.1), в которой $n=\mathrm{2,}$ $l=\mathrm{1,}$

$f\left(x\right)=\frac{1}{2}{x}_1^2-\alpha x_1{x}_2+\frac{1}{2}{x}_2^2+\frac{1}{3\alpha }{(x_1-\alpha )}^3,$

$h\left(x\right)=\frac{1}{{(x_2-2)}^2}-\mathrm{1,}$  

где $\alpha$ — вещественный параметр. Вблизи локального решения $\overline{x}=(\alpha ,1)$ такие f и h бесконечно дифференцируемы, причем в этом решении выполняется условие регулярности $rank{h}^{\text{'}}\left(\overline{x}\right)=l$ (поскольку $h^{\text{'}}\left(\overline{x}\right)\cancel{=}0$) и достаточное условие второго порядка оптимальности (2.3) с единственным отвечающим $\overline{x}$ множителем Лагранжа $\overline{\lambda }={\alpha }^2-1.$  

В таблицах 1, 2 для каждой итерации  и полученного на ней приближения $(x^k,{\lambda }^k)$ (и ${\tilde{x}}^k$ для метода с поправками второго порядка) приводятся следующие сведения: 

• “Pert” есть величина $\parallel P_k{\omega }_1^{k-1}\parallel /(\parallel x^k-x^{k-1}\parallel +\parallel x^{k-1}-\overline{x}\parallel )$ (см. (6); нормы везде евклидовы);
• “Res” есть невязка системы Лагранжа (4);
• “Dist” есть расстояние $\parallel x^k-\overline{x}\parallel$ до прямого решения;
• “PR” (от “primal ratio”) есть величина $\parallel x^k-\overline{x}\parallel /\parallel x^{k-1}-\overline{x}\parallel ;$
• “PDR” (от “primal-dual ratio”) есть величина $\parallel (x^k-\overline{x},{\lambda }^k-\overline{\lambda })\parallel /\parallel (x^{k-1}-\overline{x},{\lambda }^{k-1}-\overline{\lambda })\parallel ;$
• “PR-SOC” есть величина $\parallel {\tilde{x}}^k-\overline{x}\parallel /\parallel {\tilde{x}}^{k-1}-\overline{x}\parallel$ (для метода с поправками второго порядка).

 

Таблица 1. Численные результаты для примера 2.1: метод без поправок второго порядка

k	Pert	Res	Dist	PR	PDR
0	–	5.8e+0	1.0e-1	–	–
1	7.4e-1	6.7e+0	5.0e-1	5.0e+0	4.7e+1
2	4.9e-2	2.0e+0	1.0e-4	2.0e-4	4.2e-1
3	8.2e-1	7.4e-3	5.0e-4	5.0e+0	2.5e-3
4	5.0e-5	2.5e-3	9.2e-16	1.8e-12	5.1e-1
5	9.7e-1	1.1e-14	8.9e-16	9.7e-1	2.9e-12
6	0	3.6e-15	0.0e+0	0.0e+0	5.0e-1

 

Таблица 2. Численные результаты для примера 2.1: метод с поправками второго порядка

k	Pert	Res	Dist	PR	PDR	PR-SOC
0	–	5.8e+0	1.0e-1	–	–	–
1	7.4e-1	7.1e+0	5.0e-1	5.0e+0	4.7e+1	–
2	8.6e-3	2.7e+0	5.1e-2	1.0e-1	5.1e-1	5.1e-2
3	5.9e-7	2.5e-1	5.1e-4	1.0e-2	1.0e-1	8.5e-4
4	0.0e+0	2.5e-3	5.3e-8	1.0e-4	1.0e-2	1.0e-6
5	0.0e+0	2.6e-7	8.9e-16	1.7e-8	1.0e-4	1.7e-12
6	0.0e+0	3.6e-15	0.0e+0	0.0e+0	1.4e-8	0.0e+0

 

Результаты в таблицах 1, 2 получены с использованием $\alpha =5$ и начального приближения $x^0=\overline{x}+\left(\mathrm{0,}0.1\right),$ ${\lambda }^0=\overline{\lambda }.$  

Таблица 1 демонстрирует наличие у метода последовательного квадратичного программирования с суженной матрицей Гессе двухшаговой сверхлинейной сходимости, но отсутствие настоящей сверхлинейной сходимости: на каждой второй итерации расстояние до прямого решения (см. столбцы “Dist” и “PR”) возрастает, по крайней мере пока приближения не попадают в достаточно малую окрестность решения, где существенную роль начинают играть ошибки округления. Это согласуется с поведением величин в столбце “Pert”.

Согласно таблице 2, для варианта метода с поправками второго порядка очевидно имеет место сверхлинейная (квадратичная) сходимость последовательности $\left\{{\tilde{x}}^k\right\}$ (столбец “PR-SOC”). Основная последовательность $\left\{x^k\right\}$ здесь тоже асимптотически сходится сверхлинейно (и даже квадратично; столбцы “Dist” и “PR”). Вместе с тем, шаг из точки $x^0$ в точку $x^1$ увеличивает расстояние до решения (примерно в 5 раз; столбцы “Dist” и “PR”), и эта ситуация сохраняется, каким бы близким $x^0$ не было к $\overline{x}\mathrm{.}$ Это является свидетельством принципиальных трудностей доказательства сверхлинейной сходимости основной последовательности метода последовательного квадратичного программирования с суженной матрицей Гессе, снабженного поправками второго порядка. Вместе с тем, примеры, демонстрирующие отсутствие сверхлинейной сходимости таких последовательностей, авторам не известны.

About the authors

Andrey A. Volkov

Lomonosov Moscow State University

Email: and_rei99@mail.ru

Master, Operations Research Department

Russian Federation, 1 Leninskiye Gory, Moscow 119991

Alexey F. Izmailov

Lomonosov Moscow State University

Author for correspondence.
Email: izmaf@cs.msu.ru
ORCID iD: 0000-0001-9851-0524

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
ORCID iD: 0000-0002-3639-0317

Researcher

Russian Federation, 33 Internatsionalnaya St., Tambov 392000

References

Supplementary files