Журнал вычислительной математики и математической физики, 2022, T. 62, № 4, стр. 597-615

ВВЕДЕНИЕ

Настоящая статья является продолжением работы [1], в которой рассматривался прямо-двойственный метод Ньютона для решения линейной задачи полуопределенного программирования и были выведены уравнения для определения направлений перемещений. Основная особенность при получении данных уравнений заключалась в том, что точки, в которых они выводились, могли принадлежать границам допустимых множеств. В таких точках ньютоновская система линейных уравнений для определения направлений перемещений принимает специальный вид. Было показано, что в пространстве симметричных матриц можно выделить четыре подпространства, которым должны принадлежать данные перемещения.

Цель настоящей работы заключается в получении точных аналитических формул для ньютоновских направлений как в пространстве прямых переменных, так и в пространстве слабых двойственных переменных, а также в построении итерационного процесса. Исследуются свойства ньютоновских направлений, рассматривается вопрос о выборе шага перемещения. Показывается, что в ходе итерационного процесса ранг симметризованного произведения прямой переменной и слабой двойственной переменной может только уменьшаться. Данный ранг характеризует выполнение условия комплементарности, которое входит в условия оптимальности для линейных задач полуопределенного программирования.

Приведем некоторые обозначения, введенные ранее в [1] и используемые в данной работе. Ниже ${{\mathbb{S}}^{n}}$ – пространство симметричных матриц порядка $n$, и $\mathbb{S}_{ + }^{n}$ – конус положительно-полуопределенных матриц из ${{\mathbb{S}}^{n}}$. Конус $\mathbb{S}_{ + }^{n}$ самосопряженный и задает в ${{\mathbb{S}}^{n}}$ частичный порядок $ \succcurlyeq $, используя который будем писать $X \succcurlyeq 0$, если $X \in \mathbb{S}_{ + }^{n}$. Размерность пространства ${{\mathbb{S}}^{n}}$ равняется “треугольному” числу ${{n}^{\Delta }} = \frac{1}{2}n(n + 1)$.

Скалярное (внутреннее) произведение между матрицами $X \in {{\mathbb{S}}^{n}}$ и $Y \in {{\mathbb{S}}^{n}}$ определяется по Фробениусу: $X \bullet Y = {\text{tr}}\left( {{{X}^{{\text{т}}}}Y} \right)$. Обычное евклидово скалярное произведение в ${{\mathbb{R}}_{n}}$ обозначается с помощью угловых скобок. Символ ${{J}^{n}}$ обозначает множество индексов от $1$ до $n$. Через $X \circ Y$ обозначается симметризованное произведение между матрицами из ${{\mathbb{S}}^{n}}$, определяемое как $X \circ Y = \frac{1}{2}\left( {XY + YX} \right)$.

Линейная задача полуопределенного программирования ставится стандартным образом

Матрицы $C$, $X$ и ${{A}_{i}}$, $i \in {{J}^{m}}$, принадлежат пространству ${{\mathbb{S}}^{n}}$. Двойственной к (1) является задача в которой $b = \left( {{{b}^{1}};\; \ldots ;\;{{b}^{m}}} \right) \in {{\mathbb{R}}^{m}}$. Предполагается, что решения задач (1) и (2) существуют и что матрицы ${{A}_{i}}$, $i \in {{J}^{m}}$, линейно независимы. Предполагается также, что $C \ne {{0}_{{nn}}}$ и $b = \left[ {{{b}^{1}};\; \ldots ;\;{{b}^{m}}} \right] \ne {{0}_{n}}$. Здесь и ниже ${{0}_{k}}$ есть $k$-мерный нулевой вектор, ${{0}_{{kl}}}$ – нулевая матрица размером $k \times l$. Точка с запятой указывает на то, что компоненты вектора располагаются в виде столбца, т.е. одна компонента под другой.

Пусть ${{\mathcal{F}}_{P}}$ и ${{\mathcal{F}}_{D}}$ – допустимые множества в задачах (1) и (2) соответственно. Если $X \in {{\mathcal{F}}_{P}}$ и $[u,Y] \in {{\mathcal{F}}_{D}}$ – решения (1) и (2), то они удовлетворяют системе равенств

Последнее равенство в (3) можно представить в другом виде, аналогичном равенствам ${{A}_{i}} \bullet X = {{b}^{i}}$. Пусть $l = {{n}^{\Delta }} - m$. Обозначим через ${{K}_{1}},\; \ldots ,\;{{K}_{l}}$, матрицы из ${{\mathbb{S}}^{n}}$, задающий базис в ортогональном дополнении пространства, порождаемого матрицами ${{A}_{i}}$, $i \in {{J}^{m}}$. Тогда, умножая равенство $Y = C - \sum\nolimits_{i = 1}^m \,{{u}^{i}}{{A}_{i}}$ скалярно на ${{K}_{j}}$, $j \in {{J}^{l}}$, получаем ${{K}_{j}} \bullet Y = {{c}^{j}}$, где ${{c}^{j}} = {{K}_{j}} \bullet C$. Условия оптимальности (3) заменяются на следующие: Предлагаемый в [1] метод является вариантом метода Ньютона для решения системы (4).

1. НЬЮТОНОВСКАЯ СИСТЕМА В ВЕКТОРНОМ ВИДЕ

Пусть имеется допустимая пара $[X,Y] \in {{\mathbb{S}}^{n}} \times {{\mathbb{S}}^{n}}$. Это означает, что $X \succcurlyeq 0$, $Y \succcurlyeq 0$ и выполнены последние два равенства из (4). Считаем также, что пара $[X,Y]$ является согласованной, т.е. $X \circ Y \succcurlyeq 0$. Если для $[X,Y]$ первое равенство в (4) не выполняется, другими словами, пара не является комплементарной, то она неоптимальная, т.е. $X$ и $Y$ вместе с соответствующей двойственной переменной $u$ не являются решениями задач (1) и (2). В этом случае желательно перейти в новую допустимую согласованную пару $[\bar {X},\bar {Y}]$, используя для этой цели направления перемещения $\Delta X$ и $\Delta Y$. В качестве $\Delta X$ и $\Delta Y$ могут быть взяты ньютоновские направления, получающиеся из применения метода Ньютона для решения системы (4). В [1] построена специальная система линейных уравнений для нахождения таких $\Delta X$ и $\Delta Y$. Дадим ее краткое описание.

Для симметричной матрицы $X \circ Y$ имеет место разложение: $X \circ Y = UD(\lambda ){{U}^{{\text{т}}}}$, где $U$ – ортогональная матрица порядка $n$, $D(\lambda )$ – диагональная матрица с вектором собственных значений $X \circ Y$ на диагонали. Пусть ${{n}_{P}}$ – ранг матрицы $X \circ Y$ и пусть $\lambda = [{{\lambda }_{P}};{{\lambda }_{O}}]$, где ${{\lambda }_{P}}$ – ненулевые собственные значения, ${{\lambda }_{O}}$ – нулевые собственные значения. Тогда $U = [{{U}_{P}},{{U}_{O}}]$, где подматрица ${{U}_{P}}$ состоит из ${{n}_{P}}$ столбцов $U$.

Введем в рассмотрение еще три матрицы ${{U}_{B}}$, ${{U}_{N}}$ и ${{U}_{Z}}$, зависящие от образов матриц $X \in \mathbb{S}_{ + }^{n}$ и $Y \in \mathbb{S}_{ + }^{n}$, а также от их нуль-пространств. Матрица ${{U}_{B}}$ задает ортонормированный базис в пересечении образа матрицы $X$ с нуль-пространством матрицы $Y$. Соответственно, матрица ${{U}_{N}}$ задает ортонормированный базис в пересечении образа матрицы $Y$ с нуль-пространством матрицы $X$. Если пересечение нуль-пространств матриц $X$ и $Y$ имеет положительную размерность, то такие пары $[X,Y]$ называются особыми, в противном случае они называются неособыми. В неособых парах матрица ${{U}_{Z}}$ отсутствует. Неособая регулярная пара $[X,Y] \in \mathbb{S}_{ + }^{n} \times \mathbb{S}_{ + }^{n}$ – это такая пара, когда ${{U}_{O}} = \left[ {{{U}_{B}},{{U}_{N}}} \right]$. В особой регулярной паре ${{U}_{O}} = \left[ {{{U}_{B}},{{U}_{N}},{{U}_{Z}}} \right]$.

Предположим сначала для простоты, что неоптимальная пара $[X,Y] \in \mathbb{S}_{ + }^{n} \times \mathbb{S}_{ + }^{n}$ регулярная и неособая. В этом случае ${{\lambda }_{P}}{{ > 0}_{{{{n}_{P}}}}}$. При этих предположениях, как показано в [1], матрицы ${{X}_{U}} = {{U}^{{\text{т}}}}XU$ и ${{Y}_{U}} = {{U}^{{\text{т}}}}YU$ имеют блочно-диагональный вид

с диагональными блоками Тогда в качестве направлений $\Delta X$ и $\Delta Y$ также целесообразно брать блочно-диагональные матрицы с соответственно блоками $\Delta {{X}_{{{{U}_{P}}}}}$, $\Delta {{X}_{{{{U}_{B}}}}}$, $\Delta {{X}_{{{{U}_{N}}}}}$ и $\Delta {{Y}_{{{{U}_{P}}}}}$, $\Delta {{Y}_{{{{U}_{B}}}}}$, $\Delta {{Y}_{{{{U}_{N}}}}}$, т.е. полагать Симметричные матрицы ${{X}_{{{{U}_{P}}}}}$, ${{Y}_{{{{U}_{P}}}}}$ и $\Delta {{X}_{{{{U}_{P}}}}}$, $\Delta {{Y}_{{{{U}_{P}}}}}$ имеют порядок ${{n}_{P}}$ (ранг матрицы $X \circ Y$). У матриц ${{X}_{{{{U}_{B}}}}}$, ${{Y}_{{{{U}_{B}}}}}$ и $\Delta {{X}_{{{{U}_{B}}}}}$, $\Delta {{Y}_{{{{U}_{B}}}}}$ ранг ${{n}_{B}}$, у матриц ${{X}_{{{{U}_{N}}}}}$, ${{Y}_{{{{U}_{N}}}}}$ и $\Delta {{X}_{{{{U}_{N}}}}}$, $\Delta {{Y}_{{{{U}_{N}}}}}$ ранг ${{n}_{N}}$. Пространство блочно-диагональных симметричных матриц с блоками соответственно порядков ${{n}_{P}}$, ${{n}_{B}}$ и ${{n}_{N}}$ обозначим через $\mathbb{S}_{U}^{n}$. Его размерность равняется ${{n}_{U}} = n_{P}^{\Delta } + n_{B}^{\Delta } + n_{N}^{\Delta }$.

В случае блочно-диагональных приращений (6) из ньютоновской системы уравнений для равенств (4) следует, что $\Delta {{X}_{{{{U}_{N}}}}}{{ = 0}_{{{{n}_{N}}}}}$ и $\Delta {{Y}_{{{{U}_{B}}}}}{{ = 0}_{{{{n}_{B}}}}}$, а сама система сводится к следующей:

Матрицы ${{A}_{{i,{{U}_{P}}}}}$, ${{A}_{{i,{{U}_{B}}}}}$ и ${{K}_{{j,{{U}_{P}}}}}$, ${{K}_{{j,{{U}_{N}}}}}$ следующие: где $i \in {{J}^{m}}$, $j \in {{J}^{{{{l}_{U}}}}}$, ${{l}_{U}} = {{n}_{U}} - m$. Блочно-диагональные матрицы с блоками ${{K}_{{j,{{U}_{P}}}}}$, ${{K}_{{j,{{U}_{B}}}}}$ и ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, задают некоторый базис в ортогональном дополнении подпространства из $\mathbb{S}_{U}^{n}$, определяемым блочно-диагональными матрицами с блоками ${{A}_{{i,{{U}_{P}}}}}$, ${{A}_{{i,{{U}_{B}}}}}$, ${{A}_{{i,{{U}_{N}}}}}$, $i \in {{J}^{m}}$.

Чтобы решить систему линейных матричных уравнений (7), представим ее в векторном виде. Для этого введем дополнительные обозначения.

Пусть vec M обозначает вектор длины ${{n}^{2}}$, являющийся прямой суммой столбцов квадратной матрицы $M$ порядка $n$. В случае симметричной матрицы $M$ будем пользоваться также вектором ${\text{svec}}\,M$ длины ${{n}^{\Delta }}$. В данный вектор в отличие от $\operatorname{vec} M$ помещаются столбцы не полностью, а только их части, начинающиеся с главного элемента, причем все элементы, не стоящие на диагонали матрицы $M$, при помещении в ${\text{svec}}\,M$ умножаются на $\sqrt 2 $.

Для перехода от $\operatorname{vec} M$ к $\operatorname{svec} M$ и для обратного перехода нам потребуются специальные элиминационные и дуплицирующие матрицы (см. [2], [3]), которые обозначим как ${{\tilde {\mathcal{L}}}_{n}}$ и ${{\tilde {\mathcal{D}}}_{n}}$ соответственно. Обе матрицы ${{\tilde {\mathcal{L}}}_{n}}$ и ${{\tilde {\mathcal{D}}}_{n}}$ являются матрицами полного ранга и имеют соответственно размеры ${{n}^{\Delta }} \times {{n}^{2}}$ и ${{n}^{2}} \times {{n}^{\Delta }}$. Если $M$ – симметричная матрица порядка $n$, то

Для матриц ${{\tilde {\mathcal{L}}}_{n}}$ и ${{\tilde {\mathcal{D}}}_{n}}$ справедливо равенство ${{\tilde {\mathcal{L}}}_{n}}{{\tilde {\mathcal{D}}}_{n}} = {{I}_{{{{n}^{\Delta }}}}}$. Кроме того, $\tilde {\mathcal{D}}_{n}^{{\text{т}}}{{\tilde {\mathcal{D}}}_{n}} = {{I}_{{{{n}^{\Delta }}}}}$. Здесь и ниже ${{I}_{k}}$ – единичная матрица порядка $k$.

Матрице $M \in {{\mathbb{S}}^{n}}$ можно поставить в соответствие ее кронекеровскую сумму ${{M}^{ \otimes }}$, определяемую как

где знак $ \otimes $ между матрицами обозначает их произведение по Кронекеру. Матрица ${{M}^{ \otimes }}$ симметричная и имеет порядок ${{n}^{2}}$. Ниже через ${{\tilde {M}}^{ \otimes }}$ обозначается квадратная матрица ${{\tilde {\mathcal{L}}}_{n}}{{M}^{ \otimes }}{{\tilde {\mathcal{D}}}_{n}}$, имеющая уже порядок ${{n}^{\Delta }}$. Если $M$ – неособая матрица, то матрицы ${{M}^{ \otimes }}$ и ${{\tilde {M}}^{ \otimes }}$ также неособые. Более того, неособой оказывается и матрица ${{\tilde {\mathcal{L}}}_{n}}(M \otimes M){{\tilde {\mathcal{D}}}_{n}}$, причем для обратной матрицы справедлива формула (см. [2]) Для любых матриц ${{M}_{1}}$, ${{M}_{2}}$ и ${{M}_{3}}$, если определено их произведение ${{M}_{1}}{{M}_{2}}{{M}_{3}}$, имеет место равенство

С помощью формулы (9) получаем, что равенство ${{X}_{{{{U}_{P}}}}} \circ {{Y}_{{{{U}_{P}}}}} = D({{\lambda }_{P}})$ может быть записано следующим образом:

Здесь $\tilde {X}_{{{{U}_{P}}}}^{ \otimes } = {{\tilde {\mathcal{L}}}_{{{{n}_{P}}}}}X_{{{{U}_{P}}}}^{ \otimes }{{\tilde {\mathcal{D}}}_{{{{n}_{P}}}}}$, $\tilde {\mathcal{L}}_{{{{U}_{P}}}}^{ \otimes } = {{L}_{{{{n}_{P}}}}}Y_{{{{U}_{P}}}}^{ \otimes }{{\tilde {\mathcal{D}}}_{{{{n}_{P}}}}}$.

Если матрицы $\tilde {X}_{{{{U}_{P}}}}^{ \otimes }$ и $\tilde {Y}_{{{{U}_{P}}}}^{ \otimes }$ неособые, то неформально через $\tilde {X}_{{{{U}_{P}}}}^{{ - \otimes }}$ и $\tilde {Y}_{{{{U}_{P}}}}^{{ - \otimes }}$ будем обозначать их обратные матрицы, т.е. ${{\left( {\tilde {X}_{{{{U}_{P}}}}^{ \otimes }} \right)}^{{ - 1}}}$ и ${{\left( {\tilde {Y}_{{{{U}_{P}}}}^{ \otimes }} \right)}^{{ - 1}}}$ соответственно. Обозначим также для упрощения записи ${{\mathcal{G}}_{P}} = \tilde {Y}_{{{{U}_{P}}}}^{{ - \otimes }}\tilde {X}_{{{{U}_{P}}}}^{ \otimes }$. Тогда на основании (10) получаем

Пусть $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}$ и $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ – матрицы, строками которых являются соответственно векторы ${\text{svec}}\;{{A}_{{i,{{U}_{P}}}}}$ и ${\text{svec}}\;{{A}_{{i,{{U}_{B}}}}}$, $i \in {{J}^{m}}$. Аналогично, $\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{P}}}}$ и $\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{N}}}}$ – матрицы, строками которых являются соответственно векторы $\operatorname{svec} {{K}_{{j,{{U}_{P}}}}}$ и $\operatorname{svec} {{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$. Тогда, используя равенства

получающиеся аналогично (11) и (12), приходим к тому, что ньютоновская система (7) может быть представлена в следующем виде:

Обозначим через $\Psi $ матрицу системы (14)–(16), через $f$ – ее правую часть, т.е. положим

Тогда система (14)–(16) перепишется в виде $\Psi z = f,$ где

В [1] дано определение невырожденной пары $[X,Y]$, где $X \in \mathbb{S}_{U}^{n}$, $Y \in \mathbb{S}_{U}^{n}$. В невырожденной паре $[X,Y]$ строки матриц $\left[ {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}},\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}} \right]$ и $\left[ {\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{P}}}},\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{N}}}}} \right]$ линейно независимы. Более того, пара $[X,Y]$ является невырожденной в том и только в том случае, когда выполняются неравенства $m \geqslant n_{B}^{\Delta } \geqslant m - n_{P}^{\Delta }$. Если ${{n}_{B}} > 0$, то матрицы ${{A}_{{i,{{U}_{B}}}}}$, $i \in {{J}^{m}}$, порождают все пространство ${{\mathbb{S}}^{{{{n}_{B}}}}}$. Аналогично, если ${{n}_{N}} > 0$, то матрицы ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, порождают все пространство ${{\mathbb{S}}^{{{{n}_{N}}}}}$.

Утверждение 1. Пусть допустимая пара $[X,Y] \in \mathbb{S}_{U}^{n} \times \mathbb{S}_{U}^{n}$ регулярная и согласованная. Пусть, кроме того, она является невырожденной парой. Тогда матрица $\Psi $ неособая.

Доказательство. Так как при сделанных предположениях матрицы ${{X}_{{{{U}_{P}}}}}$ и ${{Y}_{{{{U}_{P}}}}}$, имеющие порядок ${{n}_{P}}$, неособые, то матрицы $\tilde {X}_{{{{U}_{P}}}}^{ \otimes }$ и $\tilde {Y}_{{{{U}_{P}}}}^{ \otimes }$ также неособые порядка $n_{P}^{\Delta }$. Учитывая это, умножим первую строку матрицы $\Psi $ на матрицу $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}\tilde {Y}_{{{{U}_{P}}}}^{{ - \otimes }}$ и вычтем ее из второй строки. В результате приходим к матрице

Определитель получившейся матрицы ${{\Psi }_{1}}$ совпадает с определителем матрицы $\Psi $. Отсюда следует, что $\det \Psi = \det \tilde {Y}_{{{{U}_{P}}}}^{ \otimes }\det {{\Psi }_{2}}$, где Следовательно, $\det \Psi \ne 0$, если $\det {{\Psi }_{2}} \ne 0$.

В случае, когда ${{n}_{B}} = 0$ и, следовательно, $n_{B}^{\Delta } = 0$, матрица ${{\Psi }_{2}}$ имеет вид

Более того, поскольку $[X,Y]$ – невырожденная пара и ${{n}_{B}} = 0$, то $n_{P}^{\Delta } \geqslant m$. Поэтому матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}$ имеет полный ранг, равный $m$. Матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mathcal{G}}_{P}}$ также имеет полный ранг, равный $m$.

Обратимся к линейной однородной системе

Пусть $\mu = [{{\mu }_{P}};{{\mu }_{N}}]$. Тогда, как следует из уравнения $\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mu }_{P}} + \mathcal{K}_{{{\text{svec}}}}^{{{{U}_{N}}}}{{\mu }_{N}} = 0$, вектор $\mu $ должен принадлежать ортогональному дополнению к подпространству, порожденному строками матрицы $\left[ {K_{{{\text{svec}}}}^{{{{U}_{P}}}},K_{{{\text{svec}}}}^{{{{U}_{N}}}}} \right]$. Но данное ортогональное дополнение согласно определению матриц ${{K}_{{j,{{U}_{P}}}}}$ и ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, порождается строками матрицы $\left[ {A_{{{\text{svec}}}}^{{{{U}_{P}}}},A_{{{\text{svec}}}}^{{{{U}_{N}}}}} \right]$. Поэтому решение $\mu $ должно иметь вид для некоторого вектора $\nu \in {{\mathbb{R}}_{m}}$. Отсюда, в частности, получаем ${{\mu }_{P}} = {{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}\nu $. После подстановки данного ${{\mu }_{P}}$ в уравнение в (17), приходим к заключению, что должно выполняться равенство $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mathcal{G}}_{P}}{{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}\nu {{ = 0}_{m}}$. Так как матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mathcal{G}}_{P}}{{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}$ неособая, то $\nu {{ = 0}_{m}}$. Таким образом, однородная система (17) имеет только нулевое решение. Следовательно, матрица этой системы неособая, ее ранг отличен от нулевого.

Перейдем теперь к рассмотрению общего случая, когда ${{n}_{B}} > 0$. Так как пара $[X,Y]$ невырожденная, то выполняется неравенство $n_{B}^{\Delta } \leqslant m$.

Если $n_{B}^{\Delta } = m$, то матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ квадратная порядка $m$. Опять же в силу невырожденности пары $[X,Y]$ матрицы ${{A}_{{i,{{U}_{B}}}}}$, $i \in {{J}^{m}}$, порождают все пространство ${{\mathbb{S}}^{{{{n}_{B}}}}}$. Поэтому матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$, стоящая в левом верхнем углу ${{\Psi }_{2}}$, обязательно должна быть неособой. Кроме того, матрица $\left[ {\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{P}}}},\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{N}}}}} \right]$, стоящая в нижней строке ${{\Psi }_{2}}$, также оказывается квадратной порядка ${{l}_{U}} = n_{P}^{\Delta } + n_{N}^{\Delta }$, причем в силу линейной независимости матриц $K_{j}^{{{{U}_{N}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, следующей из невырожденности пары $[X,Y]$, она неособая. Поэтому вся матрица ${{\Psi }_{2}}$, будучи квадратной и имеющей порядок $n_{P}^{\Delta } + n_{B}^{\Delta } + n_{N}^{\Delta }$, оказывается неособой.

Рассмотрим наконец случай, когда $0 < n_{B}^{\Delta } < m$, и покажем, что однородная система уравнений ${{\Psi }_{2}}\mu {{ = 0}_{{{{n}_{U}}}}}$ с квадратной матрицей ${{\Psi }_{2}}$ порядка ${{n}_{U}}$ также может иметь только тривиальное решение.

Пусть ${{d}_{B}} = m - n_{B}^{\Delta } > 0$. Разобьем вектор $\mu $ на три подвектора, а именно, $\mu = \left[ {{{\mu }_{B}};{{\mu }_{P}};{{\mu }_{N}}} \right] \in {{\mathbb{R}}^{{{{n}_{U}}}}}$. Система ${{\Psi }_{2}}\mu = 0$ распадается на две подсистемы:

Так как пара $[X,Y]$ невырожденная, то матрица $\left[ {\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{P}}}},\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{N}}}}} \right]$ подсистемы (19) размером ${{l}_{U}} \times ({{l}_{U}} + {{d}_{B}})$ имеет полный ранг, равный ${{l}_{U}}$. Следовательно, общее решение этой подсистемы есть ${{d}_{B}}$-мерное линейное подпространство.

Пусть ${{\mathcal{L}}_{B}}$ – подпространство в ${{\mathbb{R}}^{m}}$, порожденное столбцами матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ и пусть ${{E}_{B}}$ – матрица некоторого базиса в подпространстве $\mathcal{L}_{B}^{ \bot }$, являющeмся ортогональным дополнением ${{\mathcal{L}}_{B}}$. Поскольку опять в силу невырожденности пары $[X,Y]$ матрицы ${{A}_{{i,{{U}_{B}}}}}$, $i \in {{J}^{m}}$, порождают пространство ${{\mathbb{S}}^{{{{n}_{B}}}}}$, то матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ имеет полный ранг, равный $n_{B}^{\Delta }$. Поэтому у матрицы ${{E}_{B}}$ размер $m \times {{d}_{B}}$.

Покажем, что общее решение подсистемы (19) имеет вид

где $\nu \in {{\mathbb{R}}^{{{{d}_{B}}}}}$. Действительно, подставляя данное решение в (19), в силу ортогональности матриц $\tilde {A}_{i}^{U}$ и $\tilde {K}_{j}^{U}$, $i \in {{J}^{m}}$, $j \in {{J}^{{{{l}_{U}}}}}$, получаем При этом матрица ${{\left[ {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}},\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{N}}}}} \right]}^{{\text{т}}}}{{E}_{B}}$ имеет полный ранг, равный ${{d}_{B}}$. Чтобы в этом убедиться, достаточно показать, что полный ранг, равный ${{d}_{B}}$, имеет подматрица ${{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}{{E}_{B}}$.

Число столбцов матрицы ${{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}{{E}_{B}}$ не больше числа строк. Действительно, иначе выполнялось бы неравенство ${{d}_{B}} = m - n_{B}^{\Delta } > n_{P}^{\Delta }$ или $m > n_{B}^{\Delta } + n_{P}^{\Delta }$, которое противоречит неравенству $m \leqslant n_{B}^{\Delta } + n_{P}^{\Delta }$, следующему из предположения о невырожденности пары $[X,Y]$. Таким образом, ранг матрицы ${{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}{{E}_{B}}$ не превышает ${{d}_{B}}$. На самом деле, он равен ${{d}_{B}}$. Пусть это не так, тогда ${{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}{{E}_{B}}h{{ = 0}_{{n_{P}^{\Delta }}}}$ для некоторого ненулевого вектора $h \in {{\mathbb{R}}^{{{{d}_{B}}}}}$. Но это означает, что ненулевой вектор ${{E}_{B}}h$, принадлежащий нуль-пространству матрицы ${{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}} \right)}^{{\text{т}}}}$, принадлежит одновременно нуль-пространству матрицы ${{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}$. Последнее невозможно, из-за того, что в силу предположения о невырожденности пары $[X,Y]$ строки матрицы $\left[ {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}},\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}} \right]$ линейно независимы.

Подставим найденное выражение для ${{\mu }_{P}}$ в подсистему (18), в результате получаем следующее уравнение:

которое после умножения слева на матрицу $E_{B}^{{\text{т}}}$ принимает вид Матрица этой системы, как следует из вышесказанного, неособая, поэтому $\nu {{ = 0}_{{{{d}_{B}}}}}$.

Мы установили, что ${{\mu }_{P}}{{ = 0}_{{n_{P}^{\Delta }}}}$ и ${{\mu }_{N}}{{ = 0}_{{n_{N}^{\Delta }}}}$. Кроме того, из (20) в силу линейной независимости столбцов матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ получаем, что ${{\mu }_{B}}{{ = 0}_{{n_{B}^{\Delta }}}}$. Таким образом, однородная система ${{\Psi }_{2}}\mu {{ = 0}_{{{{n}_{U}}}}}$ имеет только нулевое решение. Следовательно, матрица ${{\Psi }_{2}}$ неособая. Утверждение доказано.

2. РЕШЕНИЕ НЬЮТОНОВСКОЙ СИСТЕМЫ

Рассмотрим разные случаи решения системы (14)–(16) в зависимости от ранга ${{n}_{B}}$ матрицы ${{U}_{B}}$. Предполагаем, что текущая допустимая пара $[X,Y] \in \mathbb{S}_{U}^{n} \times \mathbb{S}_{U}^{n}$ является невырожденной, а также регулярной и согласованной.

Случай 1: $n_{B}^{\Delta } = m$. При выполнении этого равенства матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ квадратная порядка $m$, причем из-за предположения о невырожденности пары $[X,Y]$ данная матрица неособая. Имеем

для некоторого $\Delta u = \left[ {\Delta {{u}^{1}};\; \ldots ,\;\Delta {{u}^{m}}} \right] \in {{\mathbb{R}}^{m}}$. Кроме того, как уже отмечалось, $\Delta {{Y}_{{{{U}_{B}}}}}{{ = 0}_{{{{n}_{B}}{{n}_{B}}}}}$. Отсюда, поскольку квадратные симметричные матрицы ${{A}_{{i,{{U}_{B}}}}}$ порядка ${{n}_{B}}$ линейно независимые и их ровно $m$ штук, приходим к выводу, что $\Delta u{{ = 0}_{m}}$. В этом случае согласно (21) выполняется следующее: $\Delta {{Y}_{U}} = 0$ и, в частности, $\Delta {{Y}_{{{{U}_{P}}}}}{{ = 0}_{{{{n}_{P}}{{n}_{P}}}}}$. Таким образом, первое уравнение (14) сводится к $\tilde {Y}_{{{{U}_{P}}}}^{ \otimes }\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}} = - \operatorname{svec} D({{\lambda }_{P}})$, разрешая которое, получаем $\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}} = - \tilde {Y}_{{{{U}_{P}}}}^{{ - \otimes }}\operatorname{svec} D({{\lambda }_{P}})$.

Так как $D({{\lambda }_{P}}) = {{X}_{{{{U}_{P}}}}} \circ {{Y}_{{{{U}_{P}}}}}$, то в силу (10) $\operatorname{svec} D({{\lambda }_{P}}) = \tilde {Y}_{{{{U}_{P}}}}^{ \otimes }\operatorname{svec} {{X}_{{{{U}_{P}}}}}$. Поэтому выражение для $\operatorname{svec} \Delta {{X}^{{{{U}_{P}}}}}$ упрощается

Зная ${\text{svec}}\;\Delta {{X}_{{{{U}_{P}}}}}$, из второго уравнения (15) находим

Случай 2: $0 < n_{B}^{\Delta } < m$. При этом предположении матрица $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ становится прямоугольной, причем число столбцов в ней меньше числа строк. Обозначим через $\mathcal{M}$ пространство столбцов матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$, через ${{\mathcal{M}}^{ \bot }}$ – его ортогональное дополнение. Пусть ${{E}_{B}}$ – матрица некоторого базиса в подпространстве ${{\mathcal{M}}^{ \bot }}$, она имеет размер $m \times {{d}_{B}}$, где ${{d}_{B}} = m - n_{B}^{\Delta }$. Так как, по-прежнему, $\Delta {{Y}_{{{{U}_{B}}}}}{{ = 0}_{{{{n}_{B}}{{n}_{B}}}}}$, то

Отсюда следует, что $\Delta u = {{E}_{B}}q$ для некоторого $q \in {{\mathbb{R}}^{{{{d}_{B}}}}}$. Поэтому

Умножим обе части уравнения (14) слева на матрицу $\tilde {Y}_{{{{U}_{P}}}}^{{ - \otimes }}$ и подставим в получившееся уравнение $\operatorname{svec} \Delta {{Y}_{{{{U}_{P}}}}}$ из (24). В результате приходим к следующему выражению для $\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}}$:

Если учесть (11), то

Подставляя найденное $\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}}$ в уравнение (15) и умножая далее (15) слева на матрицу $E_{B}^{{\text{т}}}$, с учетом того, что $E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}{{ = 0}_{{{{d}_{B}}}}}$, получаем

Отсюда находим $q = \Phi _{P}^{{ - 1}}E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}\operatorname{svec} {{X}_{{{{U}_{P}}}}}$, где ${{\Phi }_{P}} = E_{B}^{{\text{т}}}{{\mathcal{H}}_{P}}{{E}_{B}}$, ${{\mathcal{H}}_{P}} = \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mathcal{G}}_{P}}{{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}$. Таким образом, вводя еще одно обозначение $\tilde {\Phi }_{P}^{{ - 1}} = {{E}_{B}}\Phi _{P}^{{ - 1}}E_{B}^{{\text{т}}}$, приходим к следующей формуле для приращения $\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}}$: Но $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}\operatorname{svec} {{X}_{{{{U}_{P}}}}} = b - \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}\operatorname{svec} {{X}_{{{{U}_{B}}}}}$, поэтому

Кроме того, из (15) получаем

Следовательно, согласно (26), что влечет

Далее, используя соотношение ${\text{svec}}\;\Delta {{Y}_{U}} = - {{\left( {\mathcal{A}_{{{\text{svec}}}}^{U}} \right)}^{{\text{т}}}}\Delta u$, вычисляем соответствующие направления в $Y$-пространстве:

Как уже отмечалось, $\operatorname{svec} \Delta {{X}_{{{{U}_{N}}}}}{{ = 0}_{{n_{N}^{\Delta }}}}$ и $\operatorname{svec} \Delta {{Y}_{{{{U}_{B}}}}}{{ = 0}_{{n_{B}^{\Delta }}}}$.

Случай 3: ${{n}_{B}} = 0$. При этом предположении $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}\operatorname{svec} {{X}_{{{{U}_{P}}}}} = b$, а из уравнения (15) следует, что $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}}{{ = 0}_{m}}$. Имеем $\operatorname{svec} \Delta {{Y}_{{{{U}_{P}}}}} = - {{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}\Delta u$ для некоторого $m$-мерного вектора $\Delta u$. Тогда уравнение (14) с учетом (11) сводится к

Умножим уравнение (29) слева на матрицу $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}$, в результате находим $\Delta u = \mathcal{H}_{P}^{{ - 1}}b$. После подстановки найденного $\Delta u$ в (29) получаем Отсюда, в частности, следует, что $\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}}{{ = 0}_{{n_{P}^{\Delta }}}}$, когда $n_{P}^{\Delta } = m$. Для $\operatorname{svec} \Delta {{X}_{{{{U}_{N}}}}}$ по-прежнему имеем ${\text{svec}}\;\Delta {{X}_{{{{U}_{N}}}}}{{ = 0}_{{n_{N}^{\Delta }}}}$.

С помощью соотношения $\operatorname{svec} \Delta {{Y}_{U}} = - {{\left( {\mathcal{A}_{{{\text{svec}}}}^{U}} \right)}^{{\text{т}}}}\Delta u$ определяем дополнительно

Обратим внимание, что матрица $\mathcal{H}_{P}^{{ - 1}}$ переходит в введенную ранее матрицу $\tilde {\Phi }_{P}^{{ - 1}}$, если в последней взять ${{E}_{B}} = {{I}_{m}}$.

Нами получены формулы для приращений $\Delta X$ и $\Delta Y$, в которых присутствуют матрицы ${{A}_{{i,{{U}_{P}}}}}$ и ${{A}_{{i,{{U}_{B}}}}}$, $i \in {{J}^{m}}$. Можно также вывести формулы для приращений $\Delta X$ и $\Delta Y$, в которых присутствуют только матрицы ${{K}_{{j,{{U}_{P}}}}}$ и ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$. При нахождении таких приращений вместо (15) используется уравнение (16).

3. СВОЙСТВА НЬЮТОНОВСКИХ НАПРАВЛЕНИЙ

Рассмотрим некоторые простейшие свойства, которыми обладают ньютоновские направления $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$. Эти свойства являются характерными для метода Ньютона, когда он используется для решения оптимизационных задач.

Утверждение 2. Направления $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ ортогональны друг другу, т.е.

Доказательство. Равенство (31) в эквивалентной форме записывается в виде

Учтем далее, что $\operatorname{svec} \Delta {{X}_{{{{U}_{N}}}}}{{ = 0}_{{n_{N}^{\Delta }}}}$ и $\operatorname{svec} \Delta {{Y}_{{{{U}_{B}}}}}{{ = 0}_{{n_{B}^{\Delta }}}}$. Тогда (32) выполняется, если

Покажем, что равенство (33) действительно имеет место, причем считаем, что направления ${\text{svec}}\;\Delta {{X}_{{{{U}_{P}}}}}$ и ${\text{svec}}\;\Delta {{Y}_{{{{U}_{P}}}}}$ берутся равными соответственно (26) и (28). Подставляя их, получаем

так как $\tilde {\Phi }_{P}^{{ - 1}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mathcal{G}}_{P}}{{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}\tilde {\Phi }_{P}^{{ - 1}} = \tilde {\Phi }_{P}^{{ - 1}}$. Мы пришли к (33) и, следовательно, к (31). Утверждение доказано.

Введем в рассмотрение функцию

где $\alpha \geqslant 0$.

Утверждение 3. Пусть $[X,Y]$ – регулярная допустимая согласованная пара. Тогда

Доказательство. Поскольку $X \succcurlyeq 0$, $Y \succcurlyeq 0$, то $\varphi (0) = X \bullet Y \geqslant 0$, причем равенство возможно только в том случае, когда пара $[X,Y]$ оптимальная. Имеем

или, если учесть (31), Примем далее во внимание, что ${{X}_{{{{U}_{N}}}}} = 0$, $\Delta {{X}_{{{{U}_{N}}}}} = 0$ и ${{Y}_{{{{U}_{B}}}}} = 0$, $\Delta {{Y}_{{{{U}_{B}}}}} = 0$. Тогда $\varphi (\alpha ) = {{X}_{{{{U}_{P}}}}} \bullet {{Y}_{{{{U}_{P}}}}} + \alpha h$, где $h = {{Y}_{{{{U}_{P}}}}} \bullet \Delta {{X}_{{{{U}_{P}}}}} + {{X}_{{{{U}_{P}}}}} \bullet \Delta {{Y}_{{{{U}_{P}}}}}$.

Так как

и то $h = \operatorname{tr} \left( {{{Y}_{{{{U}_{P}}}}} \circ \Delta {{X}_{{{{U}_{P}}}}}} \right) + \operatorname{tr} \left( {{{X}_{{{{U}_{P}}}}} \circ \Delta {{Y}_{{{{U}_{P}}}}}} \right)$. Поэтому в силу первого уравнения из (7) справедливо равенство $h = - \operatorname{tr} D({{\lambda }_{P}}) = - \sum\nolimits_{i = 1}^{{{n}_{P}}} {\lambda _{P}^{i}} $. Поскольку $\operatorname{tr} D({{\lambda }_{P}}) = \operatorname{tr} \left( {{{X}_{{{{U}_{P}}}}} \circ {{Y}_{{{{U}_{P}}}}}} \right) = \varphi (0)$, то выполняется (34). Утверждение доказано.

Приращение $\operatorname{svec} \Delta {{Y}_{U}}$ связано с приращением двойственной переменной $\Delta u$ формулой: $\operatorname{svec} \Delta {{Y}_{U}} = - {{\left( {A_{{{\text{svec}}}}^{U}} \right)}^{{\text{т}}}}\Delta u$, причем, как следует из вышесказанного, имеем

Покажем, что направление $\Delta u$ приводит к увеличению значения целевой функции в двойственной задаче (2). Для этого сделаем дополнительное предположение относительно задачи (1). Пусть

Условие ${{A}_{1}}$. Не существует матрицы $Z \in {{\mathcal{F}}_{A}}$ ранга $r$ такой, что ${{r}^{\Delta }} < m$.

Утверждение 4. Пусть $[X,Y] \in \mathbb{S}_{U}^{n} \times \mathbb{S}_{U}^{n}$ – регулярная допустимая согласованная пара. Пусть, кроме того, выполнено условие ${{A}_{1}}$. Тогда $\left\langle {b,\Delta u} \right\rangle \geqslant 0$, причем равенство возможно только при $\Delta u{{ = 0}_{m}}$.

Доказательство. Рассмотрим только общий случай формулы (35) для приращения $\Delta u$, когда $0 < n_{B}^{\Delta } < m$. Как уже отмечалось, третий случай $n_{B}^{\Delta } = m$ сводится ко второму, если в качестве матрицы ${{E}_{B}}$ взять единичную матрицу ${{I}_{m}}$. Имеем

поскольку матрица ${{\Phi }_{P}}$ положительно определена. Неравенство (36) переходит в равенство, когда $E_{B}^{{\text{т}}}b{{ = 0}_{{{{d}_{B}}}}}$. Но выполнение данного равенства означает, что вектор $b$ принадлежит нуль-пространству матрицы $E_{B}^{{\text{т}}}$, совпадающему с пространством столбцов матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$. Но тогда для некоторого ненулевого $z \in {{\mathbb{R}}^{{n_{B}^{\Delta }}}}$ имеет место равенство

Пусть $Z \in {{\mathbb{S}}^{n}}$ – матрица, у которой соответствующая матрица ${{Z}_{U}} = {{U}^{{\text{т}}}}ZU$ принадлежит пространству $\mathbb{S}_{U}^{n}$, является блочно-диагональной, причем с единственным ненулевым диагональным блоком ${{Z}_{{{{U}_{B}}}}}$. Считаем также, что $\operatorname{svec} {{Z}_{{{{U}_{B}}}}} = z$. Ранг $r$ матрицы $Z$ не больше, чем ${{n}_{B}}$, и на основании (37) получаем

т.е. $Z \in {{\mathcal{F}}_{\mathcal{A}}}$. Но ${{r}^{\Delta }} \leqslant n_{B}^{\Delta } < m$, что противоречит условию ${{A}_{1}}$. Таким образом, возможен только случай, когда ${{n}_{B}} = m$. Но согласно (35) тогда выполняется равенство $\Delta u{{ = 0}_{m}}$. Утверждение доказано.

Утверждение 5. Пусть $[X,Y]$ – регулярная допустимая согласованная пара. Тогда верно

причем равенство возможно только при $\Delta {{X}_{U}} = 0$.

Доказательство. Рассмотрим общий случай, когда направления $\operatorname{svec} \Delta {{X}_{{{{U}_{P}}}}}$ и $\operatorname{svec} \Delta {{Y}_{{{{U}_{P}}}}}$ вычисляются согласно (26) и (28). Неравенство (38) перепишем в виде

Так как $\Delta {{X}_{{{{U}_{N}}}}}{{ = 0}_{{{{n}_{N}}{{n}_{N}}}}}$, то

Имеем c учетом того, что ${{Y}_{{{{U}_{B}}}}}{{ = 0}_{{{{n}_{B}}{{n}_{B}}}}}$,

Следовательно, причем $\operatorname{svec} {{Y}_{{{{U}_{P}}}}}$ удовлетворяют равенству (12).

Для второго слогаемого в (40) выполняется

Подставляя (42), (43) в (40) и учитывая (15), получаем

На основании (26) имеем

Здесь мы учли, что $b = \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}\operatorname{svec} {{X}_{{{{U}_{P}}}}} + \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}\operatorname{svec} {{X}_{{{{U}_{B}}}}}.$

Из (12) и (26) следует, что

или, обозначая $z = \mathcal{G}_{P}^{{ - 1}}\operatorname{svec} {{X}_{{{{U}_{P}}}}}$, $Z = {{Z}_{1}} - {{\mathcal{G}}_{P}}$, ${{Z}_{1}} = {{\mathcal{G}}_{P}}{{\left( {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}} \right)}^{{\text{т}}}}\tilde {\Phi }_{P}^{{ - 1}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}{{\mathcal{G}}_{P}}$,

Найдем собственные значения $\xi $ матрицы $Z$. Они удовлетворяют уравнению

где $y$ – ненулевой собственный вектор $Z$. Умножая равенство (44) слева на матрицу $E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}$, приходим к равенству $\xi E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}y = 0$. Следовательно, если $E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}y \ne 0$, т.е. вектор $y$ не принадлежит нуль-пространству матрицы $E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}$, то $\xi = 0$.

Предположим далее, что $E_{B}^{{\text{т}}}\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}y = 0$. В этом случае вектор $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}y$ принадлежит подпространству $\mathcal{M}$, являющемся пространством столбцов матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$, т.е. $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}y = \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}\rho $ для некоторого $\rho $.

Умножим скалярно равенство (44) на вектор $\mathcal{G}_{P}^{{ - T}}y$. Тогда

Так как $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{P}}}}y = \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}\rho $, то данное равенство сводится к $\left\langle {y,y} \right\rangle + \xi \left\langle {\mathcal{G}_{P}^{{ - T}}y,y} \right\rangle = 0$. Откуда $\xi = - {{{{{\left\| y \right\|}}^{2}}} \mathord{\left/ {\vphantom {{{{{\left\| y \right\|}}^{2}}} {\left\langle {\mathcal{G}_{P}^{{ - T}}y,y} \right\rangle }}} \right. \kern-0em} {\left\langle {\mathcal{G}_{P}^{{ - T}}y,y} \right\rangle }} < 0$.

Таким образом, у матрицы $Z$ все собственные значения действительные и неположительные. Следовательно, неравенство $C \bullet \Delta X \leqslant 0$ действительно имеет место.

Равенство $C \bullet \Delta X = 0$ выполняется тогда и только тогда, когда $Zz = 0$. В этом случае

Отсюда согласно (25) ${\text{svec}}\;\Delta {{X}_{{{{U}_{P}}}}} = 0$. Поэтому согласно (15) имеем Поскольку в невырожденной паре $[X,Y]$ столбцы матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$ линейно независимы, то ${\kern 1pt} \operatorname{svec} \Delta {{X}_{{{{U}_{B}}}}} = 0$. Таким образом, $\Delta {{X}_{U}} = 0$. Утверждение доказано.

4. ИТЕРАЦИОННЫЙ ПРОЦЕСС И ВЫБОР ШАГА

Предположим, что задана начальная допустимая регулярная согласованная пара $\left[ {{{X}^{0}},{{Y}^{0}}} \right]$. Пусть, кроме того, на $k$-м шаге итерационного процесса найдена пара $\left[ {{{X}^{k}},{{Y}^{k}}} \right]$, также являющаяся допустимой регулярной согласованной парой. Обозначим через $U$ ортогональную матрицу порядка $n$ такую, что ${{X}^{k}} \circ {{Y}^{k}} = UD(\lambda ){{U}^{{\text{т}}}}$. Считаем, для определенности, что $U = [{{U}_{P}},{{U}_{B}},{{U}_{N}}]$, где ранги матриц ${{U}_{P}}$, ${{U}_{B}}$ и ${{U}_{N}}$ равны соответственно ${{n}_{P}}$, ${{n}_{B}}$ и ${{n}_{N}}$. Для вектора собственных значений $\lambda $ матрицы $U$ выполняется: $\lambda = [{{\lambda }_{P}};0]$, ${{\lambda }_{P}} \in {{\mathbb{R}}^{{{{n}_{P}}}}}$. Для ${{X}^{k}}$ и ${{Y}^{k}}$ справедливы представления

где и

Возьмем симметричные блочно-диагональные матрицы

которым соответствуют векторы ${\text{svec}}\;\Delta X_{{{{U}_{P}}}}^{k}$, ${\text{svec}}\;\Delta X_{{{{U}_{B}}}}^{k}$ и ${\text{svec}}\;\Delta Y_{{{{U}_{P}}}}^{k}$, ${\text{svec}}\;\Delta Y_{{{{U}_{N}}}}^{k}$.

Имея формулы для ньютоновских направлений $\Delta X_{U}^{k}$ и $\Delta Y_{U}^{k}$, построим итерационный процесс

где шаг ${{\alpha }_{k}} \geqslant 0$ подбирается таким образом, чтобы он был максимально возможным при выполнении следующих условий: $X_{U}^{{k + 1}} \succcurlyeq 0$, $Y_{U}^{{k + 1}} \succcurlyeq 0$ и $X_{U}^{{k + 1}} \circ Y_{U}^{{k + 1}} \succcurlyeq 0$. Тогда, если все пары $\left[ {{{X}^{k}},{{Y}^{k}}} \right]$, $k \geqslant 0$, оказываются допустимыми, регулярными, согласованными и неособыми, то итерационный процесс (46) полностью определен.

Для того, чтобы $X_{U}^{{k + 1}} \succcurlyeq 0$, должны выполняться неравенства

Для матриц $X_{{{{U}_{P}}}}^{k}$ и $X_{{{{U}_{B}}}}^{k}$ справедливы представления (см. [1]): где ${{F}_{{{{X}_{P}}}}}$ – ортогональная матрица порядка ${{n}_{P}}$, ${{\eta }_{{BN}}}$ и ${{\eta }_{{BB}}}$ – векторы собственных значений матрицы ${{X}^{k}}$ со всеми строго положительными компонентами.

Пусть

Тогда на основании (22), (26) и (30) имеем а на основании (23) и (27), получаем В введенных обозначениях первое рекуррентное соотношение в итерационном процессе (46) расщепляется на следующие два: Тогда, как следует из (48), имеем где через ${{W}_{{{{X}_{P}}}}}$ обозначена матрица ${{W}_{{{{X}_{P}}}}} = F_{{{{X}_{P}}}}^{{\text{т}}}\hat {\Delta }X_{{{{U}_{P}}}}^{k}{{F}_{{{{X}_{P}}}}}$.

Обе матрицы $D({{\eta }_{{BN}}})$ и ${{W}_{{{{X}_{P}}}}}$ являются симметричными, причем первая матрица положительно-определенная. Поэтому с помощью конгруэнтного преобразования обе они могут быть приведены к диагональному виду [16]. Пусть ${{\mathcal{T}}_{{{{X}_{P}}}}}$ – неособая матрица, осуществляющая такое преобразование:

где $\bar {e}$ есть ${{n}_{P}}$-мерный вектор, состоящий из единиц. Тогда Схожим образом получаем где ${{\mathcal{T}}_{{{{X}_{B}}}}}$ – неособая матрица, осуществляющая конгруэнтное преобразование: Теперь $\bar {e}$ есть ${{n}_{B}}$-мерный вектор, состоящий из единиц. Из (49) и (50) видно, что если минимальная из компонент векторов ${{\sigma }_{P}}$ и ${{\sigma }_{B}}$ меньше единицы, то шаг ${{\alpha }_{k}}$ конечный. Более того, если среди компонент векторов ${{\sigma }_{P}}$ и ${{\sigma }_{B}}$ имеются отрицательные, то обязательно шаг ${{\alpha }_{k}}$ удовлетворяет неравенству: $0 < {{\alpha }_{k}} < 1$.

Обратимся ко второму рекуррентному соотношению из (46). Наряду с (47) должны выполняться соотношения

причем для матриц $Y_{{{{U}_{P}}}}^{k}$ и $Y_{{{{U}_{N}}}}^{k}$ справедливы представления, аналогичные (48): где ${{F}_{{{{Y}_{P}}}}}$ – ортогональная матрица порядка ${{n}_{P}}$, ${{\theta }_{{NB}}}$ и ${{\theta }_{{NN}}}$ – векторы собственных значений матрицы ${{Y}^{k}}$ со всеми строго положительными компонентами.

Проведем с помощью неособых матриц ${{\mathcal{T}}_{{{{Y}_{P}}}}}$ и ${{\mathcal{T}}_{{{{Y}_{N}}}}}$ конгруэнтные преобразования:

где ${{W}_{{{{Y}_{P}}}}} = F_{{{{Y}_{P}}}}^{{\text{т}}}\Delta Y_{{{{U}_{P}}}}^{k}{{F}_{{{{Y}_{P}}}}}$. Тогда получаем Таким образом, шаг ${{\alpha }_{k}}$ должен быть ограничен, если среди компонент векторов ${{\omega }_{P}}$ или ${{\omega }_{N}}$ имеются отрицательные. Более того, если какая-либо компонента ${{\omega }_{P}}$ или ${{\omega }_{N}}$ окажется меньше $ - 1$, то $0 < {{\alpha }_{k}} < 1$. Так как $\Delta Y{{ = 0}_{{nn}}}$ при $n_{B}^{\Delta } = m$, то в данном случае ограничение на шаг ${{\alpha }_{k}}$ становится несущественным.

Пусть ${{Z}^{k}} = {{X}^{k}} \circ {{Y}^{k}}$. Из разложения ${{Z}^{k}} = {{U}_{P}}D({{\lambda }_{P}})U_{P}^{{\text{т}}}$ и равенства

следует, что $\Delta Z_{{{{U}_{P}}}}^{k} = U_{P}^{{\text{т}}}\Delta {{Z}^{k}}{{U}_{P}} = - D({{\lambda }_{P}})$. Поэтому ${{Z}^{k}} + {{\alpha }_{k}}\Delta {{Z}^{k}} \succcurlyeq 0$ для $0 \leqslant {{\alpha }_{k}} \leqslant 1$.

На основании вышесказанного приходим к следующему результату.

Утверждение 6. Пусть $0 \leqslant {{\alpha }_{k}} \leqslant 1$. Тогда

Более того, $\operatorname{rank} {{Z}^{{k + 1}}} \leqslant \operatorname{rank} {{Z}^{k}}$, т.е. ранг матрицы $Z = X \circ Y$ не увеличивается в ходе итераций.

Определение 1. $k$-ю итерацию назовем активной, если $\operatorname{rank} {{Z}^{{k + 1}}} < \operatorname{rank} {{Z}^{k}}$.

Так как допустимая пара $[X,Y]$ является оптимальной, если ${\text{rank}}\;X \circ Y = 0$, то в случае, когда метод находит решение задач (1) и (2), то он находит это решение за не более чем $n$ активных итераций.

Согласно утверждению 7, если пара $\left[ {{{X}^{k}},{{Y}^{k}}} \right]$ была допустимой, регулярной, согласованной и неособой, то следующая пара $\left[ {{{X}^{{k + 1}}},{{Y}^{{k + 1}}}} \right]$ является допустимой, регулярной и согласованной. Однако она может оказаться особой. В этом случае, следует решить вспомогательную линейную полуопределенную задачу дополнительности, о которой пойдет речь в следующем разделе.

В заключение данного раздела рассмотрим вопрос о матрице $\tilde {\Phi }_{P}^{{ - 1}}$. Чтобы ее вычислить, надо знать матрицу ${{\mathcal{G}}_{P}} = \tilde {Y}_{{{{U}_{P}}}}^{{ - \otimes }}\tilde {X}_{{{{U}_{P}}}}^{ \otimes }$. Найдем выражение для $Y_{{{{U}_{P}}}}^{{ - \otimes }}$.

Матрица $\tilde {Y}_{{{{U}_{P}}}}^{ \otimes }$ представима в виде

причем, так как ${{F}_{{{{Y}_{P}}}}}$ – ортогональная матрица, то справедлива следующая формула: где матрица ${{F}_{{{{Y}_{P}}}}} \otimes {{F}_{{{{Y}_{P}}}}}$ также ортогональная, ${{({{F}_{{{{Y}_{P}}}}} \otimes {{F}_{{{{Y}_{P}}}}})}^{{ - 1}}} = F_{{{{Y}_{P}}}}^{{\text{т}}} \otimes F_{{{{Y}_{P}}}}^{{\text{т}}}$.

Воспользуемся далее формулами, имеющими место для любой квадратной матрицы $M$ порядка ${{n}_{P}}$ (см. [2]):

Тогда согласно (51), (52) и (53) получаем Отсюда, используя формулу (8), приходим к следующему выражению для обратной матрицы: где введено обозначение $\mathcal{W} = {{\tilde {\mathcal{L}}}_{{{{n}_{P}}}}}({{F}_{{{{Y}_{P}}}}} \otimes {{F}_{{{{Y}_{P}}}}}){{\tilde {\mathcal{D}}}_{{{{n}_{P}}}}}$, причем для обратной матрицы ${{\mathcal{W}}^{{ - 1}}}$ выполняется следующее: ${{\mathcal{W}}^{{ - 1}}} = {{\tilde {\mathcal{L}}}_{{{{n}_{P}}}}}\left( {F_{{{{Y}_{P}}}}^{{\text{т}}} \otimes F_{{{{Y}_{P}}}}^{{\text{т}}}} \right){{\tilde {\mathcal{D}}}_{{{{n}_{P}}}}} = {{\mathcal{W}}^{{\text{т}}}}$. Матрица ${{\tilde {\mathcal{L}}}_{{{{n}_{P}}}}}{{D}^{ \otimes }}({{\theta }_{{NB}}}){{\tilde {\mathcal{D}}}_{{{{n}_{P}}}}}$ – диагональная порядка $n_{P}^{\Delta }$ со строго положительными диагональными элементами.

5. ВСПОМОГАТЕЛЬНАЯ ЗАДАЧА ДОПОЛНИТЕЛЬНОСТИ

Полученные в разд. $2$ ньютоновские направления $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ вычислялись в парах $[X,Y]$, которые являлись неособыми, т.е. пересечение нуль-пространств матриц $X$ и $Y$ имело нулевую размерность. Предположим, теперь, что пара $[X,Y]$ особая, в таких парах размерность указанного подпространства положительная. Предполагаем также, что $U = [{{U}_{P}},{{U}_{B}},{{U}_{N}},{{U}_{Z}}]$ и ранг матрицы ${{U}_{Z}}$ равен ${{n}_{Z}} > 0$.

Ньютоновская система (7) в особой паре видоизменяется

Здесь ${{A}_{{i,{{U}_{Z}}}}} = U_{Z}^{{\text{т}}}{{A}_{i}}{{U}_{Z}}$, ${{K}_{{j,{{U}_{Z}}}}} = U_{Z}^{{\text{т}}}{{K}_{j}}{{U}_{Z}}$, $\Delta {{X}_{{{{U}_{Z}}}}} = U_{Z}^{{\text{т}}}\Delta X{{U}_{Z}}$, $\Delta {{Y}_{{{{U}_{Z}}}}} = U_{Z}^{{\text{т}}}\Delta Y{{U}_{Z}}$. Векторное представление системы следующее: где $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{Z}}}}$ и $\mathcal{K}_{{{\text{svec}}}}^{{{{U}_{Z}}}}$ – матрицы, строками которых являются соответственно векторы $\operatorname{svec} A_{i}^{{{{U}_{Z}}}}$ и $\operatorname{svec} K_{j}^{{{{U}_{Z}}}}$.

Система (55)–(57) недоопределена и, следовательно, имеет целое множество решений. Зафиксируем $\operatorname{svec} \Delta {{X}_{{{{U}_{Z}}}}}$ и $\operatorname{svec} \Delta {{Y}_{{{{U}_{Z}}}}}$. Тогда решение системы относительно остальных переменных единственное и может быть получено аналогично тому, как это делается в разд. 2. При этом выражения для $\Delta {{X}_{{{{U}_{P}}}}}$, $\Delta {{X}_{{{{U}_{B}}}}}$, $\Delta {{Y}_{{{{U}_{P}}}}}$ и $\Delta {{Y}_{{{{U}_{N}}}}}$ полностью сохраняются с единственной заменой $b$ на ${{b}_{1}} = b - \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{Z}}}}\operatorname{svec} \Delta {{X}_{{{{U}_{Z}}}}}$, т.е. становятся зависимыми от ${\text{svec}}\;\Delta {{X}_{{{{U}_{Z}}}}}$.

Пусть $\Delta {{X}_{{{{U}_{Z}}}}}$ и $\Delta {{Y}_{{{{U}_{Z}}}}}$ – матрицы, которым соответствуют векторы $\operatorname{svec} \Delta {{X}_{{{{U}_{Z}}}}}$ и ${\text{svec}}\;\Delta {{Y}_{{{{U}_{Z}}}}}$. Распорядимся приращением $\Delta {{X}_{{{{U}_{Z}}}}}$ таким образом, чтобы

Обозначим через ${{\mathcal{A}}_{{{{U}_{Z}}}}}$ матрицу ${{\mathcal{A}}_{{{{U}_{Z}}}}} = \left[ {{{A}_{{1,{{U}_{Z}}}}};\; \ldots ;\;{{A}_{{m,{{U}_{Z}}}}}} \right]$. Здесь, как и в случае с векторами, знак точки с запятой между матрицами означает, что эти матрицы помещаются одна под другой в виде матрицы-столбца. Под ${{\mathcal{A}}_{{{{U}_{Z}}}}} \bullet \Delta {{X}_{{{{U}_{Z}}}}}$ будем понимать $m$-мерный вектор

Согласно своему определению

Теперь для $\Delta u$ при $0 \leqslant n_{B}^{\Delta } < m$ выполняется причем матрица $\tilde {\Phi }_{P}^{{ - 1}}$ заменяется на $\mathcal{H}_{P}^{{ - 1}}$, когда ${{n}_{B}} = 0$. Поэтому верно

Обозначим далее

и определим линейное относительно $\Delta {{X}_{{{{U}_{Z}}}}}$ отображение ${{\Lambda }_{{\mathcal{A},{{{\tilde {\Phi }}}_{P}}}}}(\Delta {{X}_{{{{U}_{Z}}}}}):{{S}^{{{{n}_{Z}}}}} \to {{S}^{{{{n}_{Z}}}}}$, положив Тогда согласно (58) имеем $\Delta {{Y}_{{{{U}_{Z}}}}} = {{\Lambda }_{{\mathcal{A},{{{\tilde {\Phi }}}_{P}}}}}(\Delta {{X}_{{{{U}_{Z}}}}}) + \Theta .$

Введем в рассмотрение вспомогательную задачу, которая является линейной полуопределенной задачей дополнительности

Утверждение 7. Пусть допустимая особая пара $[X,Y]$ такова, что матрицы

линейно независимы. Тогда решение задачи (59) существует, причем единственное.

Доказательство. Поставим в соответствие задаче дополнительности (59) задачу квадратичного программирования

Если взять $q = {{\mathcal{A}}_{{{{U}_{Z}}}}} \bullet \Delta {{X}_{{{{U}_{Z}}}}} \in {{\mathbb{R}}^{m}}$, то целевую функцию в задаче (61) можно записать как $\tilde {f}(q) = \left\langle {q,\tilde {\Phi }_{P}^{{ - 1}}q} \right\rangle - \left\langle {\tilde {\Phi }_{P}^{{ - 1}}b,q} \right\rangle $.

Покажем, что матрица $\tilde {\Phi }_{P}^{{ - 1}}$ такова, что $\left\langle {q,\tilde {\Phi }_{P}^{{ - 1}}q} \right\rangle > 0$ для любых ненулевых $q$. Действительно, так как матрица $\Phi _{P}^{{ - 1}}$ положительно определена, то $\left\langle {q,\tilde {\Phi }_{P}^{{ - 1}}q} \right\rangle = 0$ в том и только в том случае, когда $E_{B}^{{\text{т}}}q = 0$, т.е. вектор $q = {{\mathcal{A}}_{{{{U}_{Z}}}}} \bullet \Delta {{X}_{{{{U}_{Z}}}}} = \mathcal{A}_{{{\text{svec}}}}^{{{{U}_{Z}}}}\operatorname{svec} \Delta {{X}_{{{{U}_{Z}}}}}$ принадлежит ядру матрицы $E_{B}^{{\text{т}}}$. Но данное ядро совпадает с образом матрицы $\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}}$. Поэтому столбцы матрицы $\left[ {\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{B}}}},\mathcal{A}_{{{\text{svec}}}}^{{{{U}_{Z}}}}} \right]$ оказываются линейно зависимыми, что противоречит предположению о линейной независимости матриц (60).

Матрица $\Phi _{P}^{{ - 1}}$ является положительно-определенной, поэтому квадратичная функция $\left\langle {w,\Phi _{P}^{{ - 1}}w} \right\rangle $, где $w = E_{B}^{{\text{т}}}q$, является сильно выпуклой и, следовательно, достигает своего минимального значения по $w$, причем единственного, на любом выпуклом замкнутом множестве. Отсюда следует достижение минимального значения функции

на допустимом множестве в задаче (61), т.е. задача (61) также имеет решение.

Согласно необходимым условиям минимума

где ${{f}_{{\Delta {{X}_{{{{U}_{Z}}}}}}}}\left( {\Delta {{X}_{{{{U}_{Z}}}}}} \right)$ – градиент функции $f\left( {\Delta {{X}_{{{{U}_{Z}}}}}} \right)$ по $\Delta {{X}_{{{{U}_{Z}}}}}$. Данные условия можно переписать в виде Таким образом, решение задачи квадратичного программирования (61) является одновременно решением задачи дополнительности (59). Утверждение доказано.

Замечание 1. Пусть $\tilde {\Phi }_{P}^{{ - 1}} = \left[ {{{\phi }^{{kl}}}} \right]$, $1 \leqslant k$, $l \leqslant m$. Тогда производная компоненты $\lambda _{{\mathcal{A},{{{\tilde {\Phi }}}_{P}}}}^{i}\left( {\Delta {{X}_{{{{U}_{Z}}}}}} \right)$ по $\Delta X_{{{{U}_{Z}}}}^{{pq}}$, $1 \leqslant p$, $1 \leqslant p,q, \leqslant {{n}_{Z}}$, равна

Отсюда следует, что $(k,l)$-й элемент градиента линейной функции ${{\Lambda }_{{\mathcal{A},{{{\tilde {\Phi }}}_{P}}}}}(\Delta {{X}_{{{{U}_{Z}}}}}) \bullet \Delta {{X}_{{{{U}_{Z}}}}}$ по $\Delta X_{{{{U}_{Z}}}}^{{pq}}$ равняется $\sum\nolimits_{i,j = 1}^m {{{\phi }^{{ij}}}} A_{i}^{{kl}}A_{j}^{{pq}}$.

Замечание 2. Если пара $[X,Y]$ невырожденная, то $n_{P}^{\Delta } + n_{B}^{\Delta } \geqslant m$. При выполнении предположения (60) должно выполняться неравенство $n_{B}^{\Delta } + n_{Z}^{\Delta } \leqslant m$. Отсюда следует оценка сверху на число ${{n}_{Z}}$, определяющее размерность задачи дополнительности (59), а именно, ${{n}_{Z}} \leqslant {{n}_{P}}$.

Решение задачи дополнительности (59) единственное. Подставляя найденные $\Delta {{X}_{{{{U}_{Z}}}}}$ и $\Delta {{Y}_{{{{U}_{Z}}}}}$ в систему (54), получаем, что она становится зависимой только от остальных переменных и однозначным образом разрешима относительно них. Как уже отмечалось, формулы для определения этих направлений отличаются от полученных в разд. $2$ только заменой вектора правых частей $b$ на вектор ${{b}_{1}}$.

ЗАКЛЮЧЕНИЕ

Предложенный алгоритм предназначен для решения линейных задач полуопределенного программирования в стандартной постановке. Вычисления ведутся в пространствах прямых переменных и слабых двойственных переменных, хотя несложно переписать формулы для вычислений в пространстве двойственных переменных. Все текущие приближения в итерационном процессе принадлежат допустимым множествам, поэтому метод можно трактовать как метод внутренней точки, но не строго внутренней точки, так как точки могут принадлежать границам допустимых множеств. Это принципиальное отличие от методов внутренней точки в традиционном понимании позволяет уменьшать вычислительные затраты при приближении к решениям прямой и двойственной задач. Делается это за счет более точного выполнения условия комплементарности между ними. Поэтому особенно эффективно алгоритм должен работать на конечной стадии вычислений, когда текущие точки находятся вблизи решений задач.