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

1. ВВЕДЕНИЕ

Линейная задача полуопределенного программирования в стандартной постановке заключается в минимизации на конусе симметричных положительно полуопределенных матриц линейной целевой функции при линейных ограничениях типа равенства. Численным методам решения таких задач уделяется большое внимание [1]–[7], причем наиболее популярными из них являются методы внутренней точки, главным образом, прямо-двойственные методы центрального пути [8]. При построении таких методов существенным образом используется метод Ньютона, который применяется для решения системы уравнений, описывающих условия оптимальности в задаче.

В настоящей работе также строится прямо-двойственный метод, однако в отличие от упомянутых методов в нем используется наискорейший спуск при выборе шага перемещения и допускается выход на границы допустимых множеств. Это приводит к определенной специфике в вычислении ньютоновских направлений. Чтобы найти эти направления, предлагается в пространстве симметричных матриц выделить подпространство симметричных блочно-диагональных матриц, состоящее из четырех блоков, и определять направления перемещений отдельно в каждом из этих блоков. Размеры блоков зависят от рангов прямой переменной и слабой двойственной переменной, а также от симметризованного произведения этих матриц. Данный прием применялся ранее для решения задач линейного программирования [9], [10].

При разработке предложенного метода используются условия оптимальности, причем условие комплементарности берется в виде равенства нулевой матрице симметризованного произведения прямой переменной со слабой двойственной переменной. Главная идея метода заключалась в том, чтобы постепенно от итерации к итерации добиваться выполнения условия комплементарности. Делается это за счет уменьшения или по крайней мере не увеличения ранга симметризованного произведения. Это приводит к важному отличию предложенного метода от допустимого прямо-двойственного метода внутренней точки, например, [5]. Данное отличие состоит в том, что в ходе вычислений при приближении к решению задач полуопределенного программирования уменьшаются размерности вспомогательных задач, которые требуется решать для определения ньютоновских направлений.

Работа состоит из четырех разделов. В разд. 1 дается постановка задачи и приводятся вспомогательные сведения из теории полуопределенного программирования. В разд. 2 рассматривается симметризованное произведение прямой и слабой двойственной переменных и исследуется вопрос об образе этого произведения и его нуль-пространстве. Выясняется, каким образом образ и нуль-пространство симметризованного произведения связаны с образами и нуль-пространствами прямой и слабой двойственной переменных. Здесь даются также некоторые дополнительные определения, в частности, вводится понятие регулярной согласованной пары прямой и слабой двойственной переменных. В таких парах возможно разбиение пространства симметричных матриц на четыре ортогональных между собой подпространства. В разд. 3 показывается, каким образом при ряде дополнительных предположений о прямых и слабых двойственных переменных можно представить эти переменные в виде симметричных блочно-диагональных матриц. Четвертый раздел посвящен построению ньютоновской системы для определения ньютоновских направлений. Подход к решению этой системы дается в отдельной статье, где приводятся точные формулы, позволяющие вычислить данные направления.

Ниже через ${{0}_{k}}$ обозначается нулевой $k$-мерный вектор, через ${{0}_{{kl}}}$ – нулевая матрица размером $k \times l$, через ${{I}_{k}}$ – единичная матрица порядка $k$. Знак точки с запятой, разделяющий векторы или компоненты векторов, показывает, что эти векторы или компоненты помещаются одни под другими. Остальные обозначения вводятся по ходу изложения.

1. ПОСТАНОВКА ЗАДАЧИ И ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Пусть ${{\mathbb{S}}^{n}}$ обозначает пространство симметричных матриц порядка $n$. Пусть, кроме того, $\mathbb{S}_{ + }^{n}$ и $\mathbb{S}_{{ + + }}^{n}$ – подмножества из ${{\mathbb{S}}^{n}}$, состоящие соответственно из положительно полуопределенных и положительно определенных матриц. Множество $\mathbb{S}_{ + }^{n}$ является конусом в ${{\mathbb{S}}^{n}}$, множество $\mathbb{S}_{{ + + }}^{n}$ является его внутренностью. Для указания на то, что матрица $M \in {{\mathbb{S}}^{n}}$ положительно полуопределена (положительно определена), будем пользоваться также неравенством $M \succcurlyeq 0$ ($M \succ 0$). Конус $\mathbb{S}_{ + }^{n}$ не является полиэдральным, его размерность совпадает с размерностью пространства ${{\mathbb{S}}^{n}}$ и равняется так называемому “треугольному” числу ${{n}^{\Delta }} = \tfrac{1}{2}n(n + 1)$.

Скалярное (внутреннее) произведение между двумя квадратными матрицами $L$ и $M$ порядка $n$ определяется как след матрицы ${{L}^{{\text{T}}}}M$ и обозначается в виде

где ${{l}_{{ij}}}$ и ${{m}_{{ij}}}$ суть $(ij)$-е элементы соответственно матриц $L$ и $M$. Если $L$ и $M$ – две положительно полуопределенные матрицы из ${{\mathbb{S}}^{n}}$, то $L \bullet M \geqslant 0$ и $L \bullet M = 0$ в том и только в том случае, когда $LM = ML = {{0}_{{nn}}}$. Более того, согласно теореме Фейера (о следе), матрица $L \in {{\mathbb{S}}^{n}}$ положительно полуопределена тогда и только тогда, когда $L \bullet M \geqslant 0$ для всех $M \succcurlyeq 0$, т.е. конус $\mathbb{S}_{ + }^{n}$ является самосопряженным.

Рассмотрим задачу полуопределенного программирования:

Здесь и ниже ${{J}^{k}}$ – множество индексов от $1$ до $k$, матрицы $C,\;X$ и ${{A}_{i}}$, $i \in {{J}^{m}}$, принадлежат пространству ${{\mathbb{S}}^{n}}$.

Двойственной к (1) является задача

в которой $b = ({{b}^{1}}; \ldots ;{{b}^{m}}) \in {{\mathbb{R}}^{m}}$, $Y \in {{\mathbb{S}}^{n}}$. Для слабой двойственной переменной $Y$ в дальнейшем используется также обозначение $Y(u) = C - \sum\nolimits_{i = 1}^m \,{{u}^{i}}{{A}_{i}}.$

Предполагается, что задачи (1) и (2) имеют решения и что матрицы ${{A}_{i}}$, $i \in {{J}^{m}}$, линейно независимы. Считаем также, что $C$ – ненулевая матрица, и $b$ – ненулевой вектор.

Обозначим допустимые множества в прямой и двойственной задачах соответственно через ${{\mathcal{F}}_{P}}$ и ${{\mathcal{F}}_{D}}$, т.е.

Через ${{\mathcal{F}}_{{D,u}}}$ и ${{\mathcal{F}}_{{D,Y}}}$ обозначим также проекции множества ${{\mathcal{F}}_{D}}$ на пространство ${{\mathbb{R}}^{m}}$ и конус $\mathbb{S}_{ + }^{n}$ соответственно: Для любых $X \in {{\mathcal{F}}_{P}}$ и $u \in {{\mathcal{F}}_{{D,u}}}$ выполняется соотношение слабой двойственности: $C \bullet X \geqslant \left\langle {b,u} \right\rangle $.

Введем ряд определений, которые потребуются в дальнейшем.

Определение 1. Пара $[X,Y] \in {{\mathbb{S}}^{n}} \times {{\mathbb{S}}^{n}}$ называется внутренней, если $X \succcurlyeq 0$, $Y \succcurlyeq 0$, и строго внутренней, если $X \succ 0$, $Y \succ 0$.

Определение 2. Пара $[X,Y] \in {{\mathbb{S}}^{n}} \times {{\mathbb{S}}^{n}}$ называется допустимой, если $X \in {{\mathcal{F}}_{P}}$ и $Y \in {{\mathcal{F}}_{{D,Y}}}$.

Определение 3. Пара $[X,Y] \in {{\mathbb{S}}^{n}} \times {{\mathbb{S}}^{n}}$ называется комплементарной, если $X \bullet Y = 0$.

Всякая допустимая пара $[X,Y]$ есть внутренняя пара. Допустимую пару $[X,Y]$ назовем оптимальной, если $X$ и $Y$ (вместе с некоторым $u \in {{\mathbb{R}}^{m}}$) являются решениями соответственно задач (1) и (2). Пара $[X,Y]$ оптимальная, если она допустимая и комплементарная.

Возьмем произвольную внутреннюю пару $[X,Y]$. Так как матрицы $X$ и $Y$ симметричные, то для них имеют место разложения:

где $Q$ и $H$ – ортогональные матрицы, $D(\eta )$ и $D(\theta )$ – диагональные матрицы с векторами собственных значений $\eta [{{\eta }^{1}}; \ldots ;{{\eta }^{n}}]$ и $\theta = [{{\theta }^{1}}; \ldots ;{{\theta }^{n}}]$ на диагоналях.

Пусть ранг матрицы $X$ равен $0 < {{r}_{X}} < n$. Тогда матрицу $Q$ и вектор $\eta $ можно разбить на две части. Не умаляя общности, считаем, что

причем матрица ${{Q}_{B}}$ имеет размер $n \times {{r}_{X}}$, матрица ${{Q}_{N}}$ – размер $n \times {{d}_{X}}$. Аналогично, если матрица $Y$ имеет ранг $0 < {{r}_{Y}} < n$, то $H$ и $\theta $ можно представить соответственно в виде: где ${{H}_{B}}$ есть ($n \times {{d}_{Y}}$)-матрица, ${{H}_{N}}$ есть ($n \times {{r}_{Y}}$)-матрица.

Ниже для произвольной матрицы $M$ через $\mathcal{R}(M)$ обозначается ее образ, через $\mathcal{N}(M)$ – ее ядро (нуль-пространство). Тогда $\mathcal{R}(X) = \mathcal{R}({{Q}_{B}})$, $\mathcal{N}(X) = \mathcal{R}({{Q}_{N}})$. Для образа и ядра $Y$ имеем соответственно: $\mathcal{R}(Y) = \mathcal{R}({{H}_{N}})$, $\mathcal{N}(Y) = \mathcal{R}({{H}_{B}})$.

Проведем дальнейшее разбиение матриц $Q$ и $H$ на подматрицы. Данное разбиение зависит от пересечений подпространств $\mathcal{R}({{Q}_{B}})$, $\mathcal{R}({{Q}_{N}})$, $\mathcal{R}({{H}_{B}})$ и $\mathcal{R}({{H}_{N}})$ друг с другом, при этом некоторые из них могут оказаться пустыми.

В матрице ${{Q}_{B}}$ выделяем две подматрицы. Подматрица ${{Q}_{{BB}}}$ состоит из тех столбцов ${{q}_{i}}$ из ${{Q}_{B}}$, которые одновременно принадлежат $\mathcal{R}({{H}_{B}})$. Оставшиеся столбцы матрицы ${{Q}_{B}}$ помещаем в матрицу ${{Q}_{{BN}}}$. Точно так же поступаем с матрицей ${{H}_{N}}$. В ней выделяем подматрицу ${{H}_{{NN}}}$, содержащую те и только те столбцы ${{h}_{j}}$ из ${{H}_{N}}$, которые одновременно принадлежат подпространству $\mathcal{R}({{Q}_{N}})$. Столбцы ${{h}_{j}}$, не обладающие этим свойством, составляют подматрицу ${{H}_{{NB}}}$ матрицы ${{H}_{N}}$.

Обратимся теперь к подматрицам ${{Q}_{N}}$ и ${{H}_{B}}$ и также каждую из них разобьем на две подматрицы (опять отметим, что некоторые из подматриц могут быть пустыми). К подматрице ${{Q}_{{NN}}}$ отнесем те столбцы ${{q}_{i}}$ матрицы ${{Q}_{N}}$, которые принадлежат подпространству $\mathcal{R}({{H}_{N}})$, а остальные столбцы поместим в матрицу ${{Q}_{{NB}}}$. Аналогично, если столбец ${{h}_{j}}$ матрицы ${{H}_{B}}$ принадлежит подпространству $\mathcal{R}({{Q}_{B}})$, то его помещаем в подматрицу ${{H}_{{BB}}}$, иначе – в подматрицу ${{H}_{{BN}}}$. Заметим, что при таком разбиении матриц ${{Q}_{N}}$ и ${{H}_{B}}$ не оказывается столбцов матриц ${{H}_{N}}$ и ${{Q}_{B}}$, которые принадлежат соответственно подпространствам $\mathcal{R}({{Q}_{{NB}}})$ и $\mathcal{R}({{H}_{{BN}}})$. В самом деле, если, например, вектор ${{h}_{j}}$, являющийся столбцом матрицы ${{H}_{N}}$, оказался в $\mathcal{R}({{Q}_{{NB}}})$, то он принадлежал бы некоторому подпространству пространства $\mathcal{R}({{Q}_{{NB}}})$. В этом случае можно так повернуть векторы из ${{Q}_{{NB}}}$, образующие базис в указанном подпространстве, чтобы они, оставаясь в нем, были ортогональными друг к другу, и чтобы один из векторов совпадал с ${{h}_{j}}$. По построению, мы должны такой вектор ${{h}_{j}}$ поместить в качестве столбца в матрицу ${{Q}_{{NN}}}$.

Отметим, что столбцы матриц ${{Q}_{N}}$ и ${{H}_{B}}$ можно выбирать достаточно произвольно, важно только, чтобы они образовывали базис в соответственно подпространствах $\mathcal{N}(X)$ и $\mathcal{N}(Y)$. Если какие-то столбцы ${{q}_{i}}$ матрицы ${{Q}_{B}}$ принадлежат подпространству $\mathcal{R}({{H}_{B}})$ (столбцы матрицы ${{Q}_{{BB}}}$), то, поскольку все они ортогональны между собой, их можно включить в матрицу ${{H}_{B}}$, доопределив остальные столбцы ${{H}_{B}}$ так, чтобы в совокупности все они образовывали ортогональный базис в $\mathcal{N}(Y)$. Соответствующим образом поступим и с матрицей ${{Q}_{N}}$, т.е. считаем, что столбцы матрицы ${{H}_{{NN}}}$ являются одновременно и столбцами матрицы ${{Q}_{{NN}}}$. Таким образом, получаем фактически: $\mathcal{R}({{Q}_{{BB}}}) = \mathcal{R}({{H}_{{BB}}})$ и $\mathcal{R}({{Q}_{{NN}}}) = \mathcal{R}({{H}_{{NN}}})$, что с учетом вышесказанного означает:

В дальнейшем, не ограничивая общности, считаем для определенности, что Точно так же поступим и с матрицами ${{H}_{B}}$ и ${{H}_{N}}$, разбив их на подматрицы: Разбиениям матриц ${{Q}_{B}}$ и ${{H}_{N}}$ соответствуют разбиения векторов собственных значений ${{\eta }_{B}}$ и ${{\theta }_{N}}$, а именно: ${{\eta }_{B}}[{{\eta }_{{BB}}};{{\eta }_{{BN}}}]$, ${{\theta }_{N}} = [{{\theta }_{{NB}}};{{\theta }_{{NN}}}]$.

По своему построению все четыре подпространства $\mathcal{R}({{Q}_{{BB}}})$, $\mathcal{R}({{Q}_{{BN}}})$, $\mathcal{R}({{Q}_{{NB}}})$ и $\mathcal{R}({{Q}_{{NN}}})$ ортогональны друг другу. Аналогично, подпространства $\mathcal{R}({{H}_{{BB}}})$, $\mathcal{R}({{H}_{{BN}}})$, $\mathcal{R}({{H}_{{NB}}})$ и $\mathcal{R}({{H}_{{NN}}})$ также ортогональны друг другу.

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

Тогда пара $[X,Y]$ оптимальная.

Доказательство. В силу (9) ортогональные друг другу подпространства $\mathcal{R}({{Q}_{{BB}}})$ и $\mathcal{R}({{H}_{{NN}}})$ в совокупности составляют все пространство ${{\mathbb{R}}^{n}}$. Пара $[X,Y]$ является допустимой и комплементарной. Такая пара, как уже отмечалось, является оптимальной.

При выполнении равенства (9) подпространства $\mathcal{R}({{Q}_{{BN}}})$, $\mathcal{R}({{Q}_{{NB}}})$ и $\mathcal{R}({{H}_{{BN}}})$, $\mathcal{R}({{H}_{{NB}}})$ оказываются пустыми. Таким образом, если будет найдена допустимая пара $[X,Y]$, в которой ранг матрицы $[{{Q}_{{BB}}},{{Q}_{{NN}}}]$ или, что одно и то же, ранг матрицы $[{{H}_{{BB}}},{{H}_{{NN}}}]$ равняется $n$, то данная пара будет оптимальной.

2. СИММЕТРИЗОВАННОЕ ПРОИЗВЕДЕНИЕ МАТРИЦ $X$ И $Y$

Ниже помимо матриц $X \in {{\mathbb{S}}^{n}}$ и $Y \in {{\mathbb{S}}^{n}}$ нам потребуется их симметризованное произведение $X \circ Y$, определяемое как

Данное произведение обладает следующим свойством.

Утверждение 2. Внутренняя пара матриц $[X,Y]$ удовлетворяет равенству

в том и только том случае, когда $XY = YX = {{0}_{{nn}}}$.

Таким образом, если выполнено равенство (11), то матрицы $X$ и $Y$ коммутируют между собой. Однако в общем случае, когда для внутренней пары $[X,Y]$ равенство (11) нарушено, и матрицы $X$ и $Y$ не коммутируют между собой, матрица $X \circ Y$ не обязательно является знакоопределенной.

Определение 4. Внутренняя пара $[X,Y]$ называется согласованной, если

Строго внутренняя неоптимальная пара $[X,Y]$ такая, что $XY = \mu {{I}_{n}}$, где $\mu > 0$, будет согласованной, причем $X \circ Y \succ 0$. Оптимальная пара $[X,Y]$ также является согласованной.

Так как $X \circ Y$ – симметричная матрица, то для нее справедливо разложение

где $U$ – ортогональная матрица, $\lambda $ – вектор собственных значений $X \circ Y$. Пусть ранг матрицы $X \circ Y$ равняется ${{r}_{{X \circ Y}}}$ и пусть $U = [{{U}_{P}},{{U}_{O}}]$, где ${{U}_{P}}$ – подматрица матрицы $U$, состоящая из ее первых ${{r}_{{X \circ Y}}}$ столбцов. Считаем, что столбцы ${{U}_{P}}$ являются собственными векторами матрицы $X \circ Y$, соответствующие ее ненулевым собственным значениям. Считаем также, что эти ненулевые собственные значения собраны в вектор ${{\lambda }_{P}}$ размерности ${{r}_{{X \circ Y}}}$, который является первым подвектором вектора $\lambda = [{{\lambda }_{P}};{{\lambda }_{O}}]$. Второй подвектор ${{\lambda }_{O}}$, имеющий размерность ${{d}_{{X \circ Y}}} = n - {{r}_{{X \circ Y}}}$, нулевой. Столбцы матрицы ${{U}_{O}}$ принадлежат нуль-пространству матрицы $X \circ Y$, размерность которого равна ${{d}_{{X \circ Y}}}$.

Рассмотрим подпространства $\mathcal{R}(X \circ Y)$ и $\mathcal{N}(X \circ Y)$. Матрица $X \circ Y$ симметричная, поэтому подпространство $\mathcal{N}(X \circ Y)$ ортогонально $\mathcal{R}(X \circ Y)$. Выясним, каким образом данные подпространства $\mathcal{R}(X \circ Y)$ и $\mathcal{N}(X \circ Y)$ связаны с подпространствами, определяемыми подматрицами матриц $Q$ и $H$ из (6)–(8). Имеет место следующее утверждение.

Лемма 1. Матрицы $XY$ и $YX$ могут быть представлены соответственно в виде

если, разумеется, ${{Q}_{{BN}}}$ и ${{H}_{{NB}}}$ – непустые матрицы.

Доказательство. Рассмотрим сначала матрицу $XY$, имеющую согласно разложениям (3) и разбиениям (4), (5) представление

Отсюда следует, что образ матрицы $XY$ принадлежит образу матрицы ${{Q}_{B}}$. Кроме того, если найдется столбец ${{q}_{i}}$ матрицы ${{Q}_{B}}$ такой, что $H_{N}^{{\text{T}}}{{q}_{i}} = 0$, то появляется нулевая строка в матрице $D({{\eta }_{B}})Q_{B}^{{\text{T}}}{{H}_{N}}$ и, значит, столбец ${{q}_{i}}$ не может принадлежать образу матрицы $XY$, его можно удалить. Но равенство $H_{N}^{{\text{T}}}{{q}_{i}} = 0$ указывает на то, что столбец ${{q}_{i}}$ принадлежит $\mathcal{N}(Y) = \mathcal{R}({{H}_{B}})$. Такой столбец, как уже говорилось, мы помещаем в матрицу ${{Q}_{{BB}}}$. Таким образом, вместо (15) можем записать следующее:

Далее, если обратиться к матрице ${{H}_{N}}$, то для ее столбцов ${{h}_{j}}$, входящих в подматрицу ${{H}_{{NN}}}$, выполняется $Q_{B}^{{\text{T}}}{{h}_{j}} = 0$. Тем более выполняется равенство $Q_{{BN}}^{{\text{T}}}{{h}_{j}} = 0$. Поэтому в матрице ${{H}_{N}}$ можно оставить только столбцы, входящие в подматрицу ${{H}_{{NB}}}$, а остальные столбцы (входящие в подматрицу ${{H}_{{NN}}}$) могут быть удалены. В результате приходим к представлению (13) матрицы $XY$.

Справедливость представления (14) матрицы $YX$ обосновывается аналогичным образом. Лемма доказана.

Ниже для сокращения записи через ${{\mathcal{R}}^{I}}({\kern 1pt} \cdot {\kern 1pt} )$ обозначается пересечение образов нескольких матриц, которые перечислены в скобках. Через ${{\mathcal{R}}^{S}}({\kern 1pt} \cdot {\kern 1pt} )$ обозначается их сумма (по Минковскому), например,

Оценим ранг матрицы $X \circ Y$. Имеем $\mathcal{R}(X \circ Y) \subseteq {{\mathcal{R}}^{S}}(XY,YX)$. Но $YX = {{(XY)}^{{\text{T}}}}$, поэтому

где ${{\mathcal{N}}^{ \bot }}(XY)$ – ортогональное дополнение к $\mathcal{N}(XY)$, или, что то же самое, Более точное включение для $\mathcal{R}(X \circ Y)$ можно получить с помощью леммы 1.

Утверждение 3. Для образа $\mathcal{R}(X \circ Y)$ матрицы $X \circ Y$ имеет место включение

а для его размерности, равной рангу ${{r}_{{X \circ Y}}}$ матрицы $X \circ Y$, – неравенствогде ${{r}_{{{{Q}_{{BN}}}}}}$ и ${{r}_{{{{H}_{{NB}}}}}}$ – ранги матриц ${{Q}_{{BN}}}$ и ${{H}_{{NB}}}$ соответственно.

Доказательство. Как следует из определения (10) симметризованного произведения, образ матрицы $X \circ Y$ принадлежит сумме образов матриц $XY$ и $YX$ соответственно. Но согласно утверждению леммы 1 имеем $\mathcal{R}(XY) \subseteq \mathcal{R}({{Q}_{{BN}}})$, $\mathcal{R}(YX) \subseteq \mathcal{R}({{H}_{{NB}}})$. Отсюда приходим к включению (16).

Кроме того, для ранга матрицы $XY$ получаем оценку сверху

Матрица $YX$ является транспонированной к матрице $XY$ . Поэтому ранг $YX$ совпадает с рангом матрицы $XY$ и для него также справедлива оценка (18). Неравенство (17) следует из (18) и неравенства для ранга суммы двух матриц. Утверждение доказано.

Следствие 1. Для матрицы ${{U}_{P}}$ имеет место разложение

где ${{W}_{P}}$ – матрица полного ранга размером $({{r}_{{{{Q}_{{BN}}}}}} + {{r}_{{{{H}_{{NB}}}}}}) \times {{r}_{{X \circ Y}}}$.

В случае, когда подпространства $\mathcal{R}({{Q}_{{NB}}})$ или $\mathcal{R}({{H}_{{BN}}})$ непустые, можно уточнить оценку сверху (17) на ранг матрицы $X \circ Y$.

Утверждение 4. Пусть

Тогда обязательно $dim\mathcal{R}({{Q}_{{NB}}}) > 0$, $dim\mathcal{R}({{H}_{{BN}}}) > 0$ и

Доказательство. Согласно неравенству (19) оба подпространства $\mathcal{R}({{Q}_{N}})$ и $\mathcal{R}({{H}_{B}})$ непустые и отличны от нулевых. Возьмем произвольный ненулевой вектор $z \in {{\mathbb{R}}^{n}}$ такой, что $z \in {{\mathcal{R}}^{I}}({{Q}_{N}},{{H}_{B}})$. Покажем, что в этом случае обязательно $z \in \mathcal{R}({{Q}_{{NB}}})$. Отсюда, в частности, следует ненулевая размерность пространства $\mathcal{R}({{Q}_{{NB}}})$.

Так как $z \in \mathcal{R}({{Q}_{N}})$ и $\mathcal{R}({{Q}_{N}}) = {{\mathcal{R}}^{S}}({{Q}_{{NB}}},{{Q}_{{NN}}})$, то для $z$ справедливо разложение $z = {{z}_{1}} + {{z}_{2}}$, где ${{z}_{1}} \in \mathcal{R}({{Q}_{{NB}}})$, ${{z}_{2}} \in \mathcal{R}({{Q}_{{NN}}})$. Оба подпространства $\mathcal{R}({{Q}_{{NB}}})$ и $\mathcal{R}({{Q}_{{NN}}})$ ортогональны друг другу. Считаем для общности, что второе подпространство $\mathcal{R}({{Q}_{{NN}}})$ непустое и ${{z}_{2}} \ne {{0}_{n}}$.

Но одновременно $z \in \mathcal{R}({{H}_{B}}) = {{\mathcal{R}}^{S}}({{H}_{{BB}}},{{H}_{{BN}}})$, причем оба подпространства $\mathcal{R}({{H}_{{BB}}})$ и $\mathcal{R}({{H}_{{BN}}})$ также ортогональны друг другу. Поэтому для $z$ справедливо может быть разложение только в виде суммы двух компонент, одна из которых принадлежит подпространству $\mathcal{R}({{H}_{{BB}}})$, а другая – подпространству $\mathcal{R}({{H}_{{BN}}})$. Согласно (6) имеем ${{Q}_{{NN}}} = {{H}_{{NN}}}$, что влечет $\mathcal{R}({{Q}_{{NN}}}) = \mathcal{R}({{H}_{{NN}}})$. Таким образом, предположение, что ${{z}_{2}} \in \mathcal{R}({{Q}_{{NN}}})$, приводит к тому, что ${{z}_{2}} \in \mathcal{R}({{H}_{{NN}}})$, т.е. ${{z}_{2}}$ принадлежит ортогональному дополнению к подпространству $\mathcal{R}({{H}_{B}})$, что невозможно. Поэтому обязательно $z \in \mathcal{R}({{Q}_{{NB}}})$.

Схожим образом убеждаемся, что $dim\mathcal{R}({{H}_{{BN}}}) > 0$ и $z \in \mathcal{R}({{H}_{{BN}}})$. Следовательно, справедливо равенство (20) Утверждение доказано.

Пусть непустое подпространство ${{\mathcal{R}}^{I}}({{Q}_{{NB}}},{{H}_{{BN}}})$ ненулевое. Обозначим через $Q_{{NB}}^{Z}$ матрицу, для которой подпространство $\mathcal{R}(Q_{{NB}}^{Z})$ совпадает с ${{\mathcal{R}}^{I}}({{Q}_{{NB}}},{{H}_{{BN}}})$. Аналогично, пусть $H_{{BN}}^{Z}$ – матрица, для которой подпространство $\mathcal{R}(H_{{BN}}^{Z})$ совпадает с ${{\mathcal{R}}^{I}}({{Q}_{{NB}}},{{H}_{{BN}}})$. Так как обе матрицы $Q_{{NB}}^{Z}$, $H_{{BN}}^{Z}$ состоят из собственных векторов матриц $X$ и $Y$, которые одновременно принадлежат их нуль-пространствам, то в качестве $Q_{{NB}}^{Z}$ и $H_{{BN}}^{Z}$ можно взять одинаковые матрицы, определив нужным образом соответствующие собственные векторы из нуль-пространств. Другими словами, можно считать, что $Q_{{NB}}^{Z}H_{{BN}}^{Z}$. Оставшиеся подматрицы матриц ${{Q}_{{NB}}}$ и ${{H}_{{BN}}}$ обозначим соответственно через $Q_{{NB}}^{P}$ и $H_{{BN}}^{P}$. Опять отмечаем, что некоторые из них могут оказаться пустыми. Если подпространство ${{\mathcal{R}}^{I}}({{Q}_{{NB}}},{{H}_{{BN}}})$ нулевое, то в качестве $Q_{{NB}}^{P}$ и $H_{{BN}}^{P}$ берутся сами матрицы ${{Q}_{{NB}}}$ и ${{H}_{{BN}}}$. Таким образом, выполняются следующие разложения:

Поскольку $\mathcal{R}({{Q}_{N}}) = {{\mathcal{R}}^{S}}({{Q}_{{NN}}},{{Q}_{{NB}}})$, то из (21) следует, что если подпространство $\mathcal{N}(Q)$ ненулевое, то в общем случае его можно представить как сумму трех подпространств, а именно,

причем все три составляющие подпространства $\mathcal{R}({{Q}_{{NN}}})$, $\mathcal{R}(Q_{{NB}}^{P})$ и $\mathcal{R}(Q_{{NB}}^{Z})$ ортогональны между собой. То же самое можно сказать и про подпространство $\mathcal{N}(H)$, для которого справедлива формула

Имеем в силу вышесказанного $\mathcal{R}(Q_{{NB}}^{Z}) = \mathcal{R}(H_{{BN}}^{Z})$. Кроме того, согласно своим определениям $\mathcal{R}({{Q}_{{BB}}}) = \mathcal{R}({{H}_{{BB}}})$ и $\mathcal{R}({{Q}_{{NN}}}) = \mathcal{R}({{H}_{{NN}}})$. Поэтому

Отсюда, в частности, следует, что Это равенство вытекает из того, что подпространства, стоящие в левой и правой частях (23), являются дополнениями подпространств (22) до всего пространства ${{\mathbb{R}}^{n}}$.

Схематично разбиение матриц $Q$ и $H$ на подматрицы (6)–(8), а также разбиение матриц ${{Q}_{{NB}}}$ и ${{H}_{{BN}}}$ на соответственно подматрицы $Q_{{NB}}^{P}$, $Q_{{NB}}^{Z}$ и $H_{{BN}}^{P}$, $H_{{BN}}^{Z}$ представлено на фиг. 1. Там же опять схематично указано на равенство между образами матриц ${{Q}_{{BB}}}$ и ${{Q}_{{NN}}}$ с образами соответственно матриц ${{H}_{{BB}}}$ и ${{H}_{{NN}}}$. Обращено также внимание на совпадение образов матриц $Q_{{NB}}^{Z}$ и $H_{{BN}}^{Z}$.

Утверждение 5. Пусть $\dim {{\mathcal{R}}^{I}}({{H}_{{NB}}},{{Q}_{{NB}}}) > 0$. Тогда

Аналогично, если $\dim {{\mathcal{R}}^{I}}({{Q}_{{BN}}},{{H}_{{BN}}}) > 0$.

Доказательство. Убедимся только в равенстве (24). При этом считаем, не умаляя общности, что подпространство $\mathcal{R}(Q_{{NB}}^{Z})$ непустое, иначе, так как ${{Q}_{{NB}}} = Q_{{NB}}^{P}$, равенство (24) очевидно.

Возьмем произвольный ненулевой вектор $y \in {{\mathcal{R}}^{I}}({{H}_{{NB}}},{{Q}_{{NB}}})$ и покажем, что обязательно $y \in \mathcal{R}(Q_{{NB}}^{P})$. Допустим, что $y = {{y}_{1}} + {{y}_{2}}$, где ${{y}_{1}} \in \mathcal{R}(Q_{{NB}}^{P})$, ${{y}_{2}} \in \mathcal{R}(Q_{{NB}}^{Z})$ и ${{y}_{2}} \ne 0$. Имеем $\mathcal{R}(Q_{{NB}}^{Z}) = \mathcal{R}(H_{{BN}}^{Z})$. Отсюда с учетом того, что $\mathcal{R}({{H}_{{BN}}}) \bot \mathcal{R}({{H}_{{NB}}})$ получаем ${{y}_{2}} \notin \mathcal{R}({{H}_{{NB}}})$. Так как $y \in \mathcal{R}({{H}_{{NB}}})$, то ${{y}_{2}} = 0$. Мы пришли к противоречию. Следовательно, $y = {{y}_{1}} \in \mathcal{R}(Q_{{NB}}^{P})$. Утверждение доказано.

Лемма 2. Пусть матрицы $X$ и $Y$ таковы, что

Тогда ${{r}_{{XY}}} = {{r}_{{{{H}_{{NB}}}}}} - {{k}_{{XY}}}$.

Доказательство. Воспользуемся формулой для ранга произведения $XY$:

справедливой, вообще говоря, для произведения произвольных матриц $X$ и $Y$. Если применить ее к матрице $XY$ вида (13), то приходим к следующему значению для ее ранга:

Учтем далее, что ядро $\mathcal{N}(Q_{{BN}}^{{\text{T}}})$ матрицы $Q_{{BN}}^{{\text{T}}}$ есть ортогональное дополнение к подпространству $\mathcal{R}({{Q}_{{BN}}})$. Тогда $\mathcal{N}(Q_{{BN}}^{{\text{T}}}) = {{\mathcal{R}}^{S}}({{Q}_{{BB}}},{{Q}_{{NN}}},{{Q}_{{NB}}})$ или, если воспользоваться (21),

Но, как уже отмечалось, выполняются следующие равенства для подпространств: Более того, все эти подпространства $\mathcal{R}({{H}_{{BB}}})$, $\mathcal{R}({{H}_{{NN}}})$ и $\mathcal{R}(H_{{BN}}^{Z})$ ортогональны $\mathcal{R}({{H}_{{NB}}})$. Поэтому остается только пересечение $\mathcal{R}({{H}_{{NB}}}) \cap \mathcal{N}(Q_{{BN}}^{{\text{T}}}) = {{\mathcal{R}}^{I}}({{H}_{{NB}}},Q_{{NB}}^{P}).$ Отсюда приходим к требуемому утверждению.

Схожим образом доказывается

Лемма 3. Пусть матрицы $X$ и $Y$ таковы, что

Тогда ${{r}_{{YX}}} = {{r}_{{{{Q}_{{BN}}}}}} - {{k}_{{YX}}}$.

Замечание 1. Любое подпространство ${{\mathcal{R}}^{S}}({{h}_{{{{i}_{1}}}}}, \ldots ,{{h}_{{{{i}_{k}}}}})$, где ${{h}_{{{{i}_{j}}}}}$, $1 \leqslant j \leqslant k$, – столбцы матрицы ${{H}_{{NB}}}$, не может принадлежать $\mathcal{R}({{Q}_{{NB}}})$. Действительно, иначе эти столбцы были бы включены в матрицу ${{H}_{{NN}}}$. Аналогично, любое подпространство ${{\mathcal{R}}^{S}}({{q}_{{{{i}_{1}}}}}, \ldots ,{{q}_{{{{i}_{l}}}}})$, где ${{q}_{{{{i}_{j}}}}}$, $1 \leqslant j \leqslant l$, – столбцы матрицы ${{Q}_{{BN}}}$, не может принадлежать $\mathcal{R}({{H}_{{NB}}})$.

Обратимся теперь к нуль-пространству матрицы $X \circ Y$. Оно совпадает с нуль-пространством матрицы ${{U}_{P}}$, а его размерность ${{d}_{{X \circ Y}}}$ равняется рангу матрицы ${{U}_{O}}$. Подпространство $\mathcal{R}(Q_{{NB}}^{Z}) = \mathcal{R}(H_{{BN}}^{Z})$, если непустое, в силу своего определения обязательно принадлежит $\mathcal{R}({{U}_{O}})$.

Утверждение 6. Пусть подпространства $\mathcal{R}({{Q}_{{BB}}})$, $\mathcal{R}({{Q}_{{NN}}})$ и $\mathcal{R}(Q_{{NB}}^{Z})$ непустые. Тогда

Доказательство. Прежде всего отметим, что подпространства $\mathcal{R}({{Q}_{{BB}}})$, $\mathcal{R}({{Q}_{{NN}}})$ и $\mathcal{R}(Q_{{NB}}^{Z})$ согласно своим определениям ортогональны подпространству $\mathcal{R}({{Q}_{{BN}}})$ и, следовательно,

Кроме того, имеет место совпадение подпространств Поскольку опять, согласно своим определениям, все три подпространства $\mathcal{R}({{H}_{{BB}}})$, $\mathcal{R}({{H}_{{NN}}})$ и $\mathcal{R}(H_{{BN}}^{Z})$ ортогональны подпространству $\mathcal{R}({{H}_{{NB}}})$, то верно следующее:

Из (29) и (30) с учетом представлений (13), (14) приходим к выводу, что

что приводит к включению (28). Утверждение доказано.

Следствие 2. Пусть выполнены предположения утверждения 6. Тогда подпространства $\mathcal{R}({{H}_{{BB}}})$, $\mathcal{R}({{H}_{{NN}}})$, $\mathcal{R}(H_{{BN}}^{Z})$ непустые и имеет место включение

Доказательство. Включение (31) равносильно включению (28) из-за совпадения подпространства ${{\mathcal{R}}^{S}}({{H}_{{BB}}},{{H}_{{NN}}},H_{{BN}}^{Z})$ с подпространством ${{\mathcal{R}}^{S}}({{Q}_{{BB}}},{{Q}_{{NN}}},Q_{{NB}}^{Z})$.

Из утверждения 6 и следствия к нему вытекает, что

причем согласно (23) правые части в обеих включениях совпадают между собой.

Составим матрицы

в которых все столбцы нормированы и ортогональны друг к другу. Подпространство $\mathcal{R}({{Q}_{P}})$ является ортогональным дополнением к подпространству ${{\mathcal{R}}^{S}}({{Q}_{{BB}}},{{Q}_{{NN}}},Q_{{NB}}^{Z})$, которое согласно утверждению 6 принадлежит подпространству $\mathcal{R}({{U}_{O}})$. В свою очередь, подпространство $\mathcal{R}({{H}_{P}})$ является ортогональным дополнением к подпространству ${{\mathcal{R}}^{S}}({{H}_{{NN}}},{{H}_{{BB}}},H_{{BN}}^{Z})$. Последнее подпространство, как было показано, совпадает с подпространством ${{\mathcal{R}}^{S}}({{Q}_{{BB}}},{{Q}_{{NN}}},Q_{{NB}}^{Z})$, что позволяет говорить о равенстве $\mathcal{R}({{Q}_{P}}) = \mathcal{R}({{H}_{P}})$ и включениях $\mathcal{R}({{U}_{P}}) \subseteq \mathcal{R}({{Q}_{P}})$, $\mathcal{R}({{U}_{P}}) \subseteq \mathcal{R}({{H}_{P}})$.

Определение 5. Внутренняя пара $[X,Y]$ называется регулярной, если имеет место равенство $\mathcal{R}({{Q}_{P}}) = \mathcal{R}({{H}_{P}}) = \mathcal{R}({{U}_{P}})$.

В регулярной паре $[X,Y]$ подпространство $\mathcal{N}(X \circ Y)$ есть пространство столбцов матрицы ${{U}_{O}}$. Учтем также, что столбцы матриц ${{Q}_{{BB}}}$ и ${{H}_{{NN}}}$ образуют часть базиса пространства $\mathcal{R}({{U}_{O}})$. Тогда для матрицы ${{U}_{O}}$ без ограничения общности справедливо разложение

где и ${{U}_{Z}}$ – произвольная матрица, задающая ортонормированный базис в подпространстве $\mathcal{R}(Q_{{NB}}^{Z}) = \mathcal{R}(H_{{BN}}^{Z})$, т.е. совпадающая с $Q_{{NB}}^{Z} = H_{{BN}}^{Z}$, если, разумеется, эта матрица непустая. Кроме того, в случае, когда матрица ${{U}_{P}}$ непустая, всю матрицу $U$ опять, не ограничивая общность, можно записать в виде Ранги матриц ${{U}_{P}}$, ${{U}_{B}}$, ${{U}_{N}}$ и ${{U}_{Z}}$ в дальнейшем будем обозначать соответственно через ${{n}_{P}}$, ${{n}_{B}}$, ${{n}_{N}}$ и ${{n}_{Z}}$. Если какая-то из матриц оказывается пустой, то считаем, что она нулевого ранга.

Утверждение 7. Все непустые подпространства $\mathcal{R}({{U}_{B}})$, $\mathcal{R}({{U}_{N}})$ и $\mathcal{R}({{U}_{Z}})$ ортогональны друг другу, а также ортогональны подпространству $\mathcal{R}({{U}_{P}})$, если оно непустое.

Доказательство. Ортогональность данных подпространств следует из их определения.

Утверждение 8. Пусть пара $[X,Y]$ регулярная. Тогда для матрицы ${{U}_{P}}$ справедливы следующие разложения:

где ${{F}_{{{{X}_{P}}}}}$ и ${{F}_{{{{Y}_{P}}}}}$ – ортогональные матрицы порядка ${{n}_{P}}{{r}_{{X \circ Y}}}$.

Доказательство. Справедливость разложений (35) следует из определения регулярной пары. Кроме того, поскольку $U_{P}^{{\text{T}}}{{U}_{P}}{{I}_{{{{n}_{P}}}}}$ и

то для матриц ${{F}_{{{{X}_{P}}}}}$ и ${{F}_{{{{Y}_{P}}}}}$ получаем ${{F}_{{{{X}_{P}}}}}F_{{{{X}_{P}}}}^{{\text{T}}} = {{I}_{{{{n}_{P}}}}}$, ${{F}_{{{{Y}_{P}}}}}F_{{{{Y}_{P}}}}^{{\text{T}}}{{I}_{{{{n}_{P}}}}}$, т.е. обе эти матрицы ортогональные. Утверждение доказано.

Замечание 2. Требование внутренности пары $[X,Y]$ по существу в приведенных доказательствах нигде не использовалось.

Введем еще одно определение.

Определение 6. Внутренняя пара $[X,Y]$ называется неособой, если ${{n}_{Z}} = 0$. В противном случае, когда ${{n}_{Z}} > 0$, она называется особой.

В неособой паре $[X,Y]$ матрица ${{U}_{Z}}$ в представлении (34) матрицы $U$ пропадает, матрица ${{Q}_{P}}$ переходит в ${{Q}_{P}} = [{{Q}_{{BN}}},{{Q}_{{NB}}}]$, а ${{H}_{P}}$ – в матрицу ${{H}_{P}} = [{{H}_{{NB}}},{{H}_{{BN}}}]$. В дальнейшем, пока не оговорено противное, считаем, что рассматриваемые пары неособые.

3. ДОПУСТИМЫЕ РЕГУЛЯРНЫЕ СОГЛАСОВАННЫЕ ПАРЫ

Если внутренняя пара помимо того, что она регулярная, является еще согласованной, то можно уточнить вид пространства столбцов матрицы ${{U}_{P}}$, а именно, $\mathcal{R}({{U}_{P}})$ определяется только пространствами столбцов матрицы ${{Q}_{{BN}}}$ или пространством столбцов матрицы ${{H}_{{NB}}}$.

Теорема 1. Пусть допустимая пара $[X,Y]$ регулярная и согласованная. Пусть, кроме того, $X \bullet Y > 0$. Тогда матрицы ${{Q}_{{NB}}}$ и ${{H}_{{BN}}}$ пустые и верно

Доказательство. Прежде всего отметим, что поскольку пара $[X,Y]$ не комплементарная, то матрица ${{U}_{P}}$ непустая, и, следовательно, имеет положительный ранг ${{n}_{P}} > 0$. Согласно определению регулярной неособой пары $\mathcal{R}({{U}_{P}}) = \mathcal{R}({{Q}_{P}})$, где ${{Q}_{P}} = [{{Q}_{{BN}}},{{Q}_{{NB}}}]$. Покажем, что на самом деле $\mathcal{R}({{U}_{P}}) = \mathcal{R}({{Q}_{{BN}}})$.

Допустим противное, что матрица ${{Q}_{{NB}}}$ непустая. Положим ${{\eta }_{P}} = [{{\eta }_{{BN}}};{{\eta }_{{NB}}}],$ где ${{\eta }_{{NB}}}$ – нулевой вектор, размерность которого совпадает с числом столбцов в матрице ${{Q}_{{NB}}}$. Так как в этом случае ${{Q}_{{BN}}}D({{\eta }_{{BN}}})Q_{{BN}}^{{\text{T}}} = {{Q}_{P}}D({{\eta }_{P}})Q_{P}^{{\text{T}}}$, то в силу леммы 1 и разложения (12) имеем

где ${{\lambda }_{P}} > {{0}_{{{{n}_{P}}}}}$. Воспользуемся утверждением 8 и умножим данное равенство слева и справа на матрицы $F_{{{{X}_{P}}}}^{{\text{T}}}U_{P}^{{\text{T}}}$ и ${{U}_{P}}{{F}_{{{{X}_{P}}}}}$ соответственно. С учетом равенств (35) получаем

В диагональной матрице $D({{\eta }_{P}})$ имеется по крайней мере один нулевой диагональный элемент, который входит в вектор ${{\eta }_{{NB}}}$. Пусть, для определенности, это будет элемент с номером $k$, т.е. $\eta _{P}^{k} = 0$. Тогда $k$-я строка и $k$-й столбец матрицы $D({{\eta }_{P}})$ нулевые. Отсюда следует, что $k$-й диагональный элемент матрицы, стоящей в левой части равенства (37), нулевой.

С другой стороны, если обратиться к матрице $F_{{{{X}_{P}}}}^{{\text{T}}}D({{\lambda }_{P}}){{F}_{{{{X}_{P}}}}}$, то она представима в виде

где ${{f}_{i}}$ есть $i$-я строка ортогональной матрицы ${{F}_{{{{X}_{P}}}}}$, $1 \leqslant i \leqslant {{n}_{P}}$. Поэтому $k$-й диагональный элемент матрицы $F$ равен Так как ${{\lambda }_{P}} > {{0}_{{{{n}_{P}}}}}$, то для того, чтобы равенство ${{F}^{{kk}}} = 0$ имело место, должно выполняться следующее: $f_{i}^{k} = 0$, $1 \leqslant i \leqslant {{n}_{P}}$, т.е. $k$-й столбец матрицы ${{F}_{{{{X}_{P}}}}}$ нулевой. Это противоречит ортогональности матрицы ${{F}_{{{{X}_{P}}}}}$.

Схожим образом убеждаемся, что в такой паре $[X,Y]$ матрица ${{H}_{{BN}}}$ отсутствует и имеет место равенство $\mathcal{R}({{U}_{P}}) = \mathcal{R}({{H}_{{NB}}})$. Утверждение доказано.

Следствие 3. В регулярной согласованной паре $[X,Y]$ матрица ${{U}_{P}}$ представима в виде ${{U}_{P}} = {{Q}_{{BN}}}F_{{{{X}_{P}}}}^{{\text{T}}}$ или в виде ${{U}_{P}} = {{H}_{{NB}}}F_{{{{Y}_{P}}}}^{{\text{T}}}.$

Утверждение 9. Пусть $[X,Y]$ – допустимая регулярная согласованная пара. Для того, чтобы она была оптимальной, необходимо и достаточно, чтобы ${{n}_{P}} = 0$.

Доказательство. Достаточность. При ${{n}_{P}} = 0$ получаем, что матрица $X \circ Y$ нулевая. Так как $X \succcurlyeq 0$, $Y \succcurlyeq 0$, то отсюда следует выполнение условия комплементарности $X \bullet Y = 0$. Выполнение данного условия вместе с допустимостью точек $X$ и $Y$ гарантирует оптимальность пары $[X,Y]$.

Необходимость. Оптимальная пара $[X,Y]$ комплементарная. Но, поскольку она внутренняя, то имеет место равенство $XY = YX = {{0}_{{nn}}}$, откуда $X \circ Y = {{0}_{{nn}}}$. Поэтому подматрица ${{U}_{P}}$ обязательно должна быть пустой, т.е. ${{n}_{P}} = 0$. Утверждение доказано.

Из утверждения 9 следует, что любая допустимая пара $[X,Y]$, в которой ${{n}_{P}} > 0$, не может быть оптимальной.

Возьмем произвольную допустимую регулярную согласованную пару $[X,Y]$, для которой справедливо разложение (12) с ортогональной матрицей $U$. Если пара $[X,Y]$ не является оптимальной, то в ортонормированном базисе, задаваемым столбцами матрицы $U$, матрицы $X$ и $Y$ оказываются блочно-диагональными с блоками соответственно порядков ${{n}_{P}}$, ${{n}_{B}}$ и ${{n}_{N}}$, причем некоторые из них могут оказаться пустыми.

Имеем в общем случае следующее:

Здесь в первой матрице диагональные блоки согласно (33) и следствию к теореме 1 имеют вид Для второй матрицы ${{Y}_{U}}$ выполняется соответственно следующее:

Обозначим через Пусть $\mathbb{S}_{U}^{n}$ подпространство пространства ${{\mathbb{S}}^{n}}$, образованное блочно-диагональными матрицами с блоками соответственно размеров ${{n}_{P}}$, ${{n}_{B}}$ и ${{n}_{N}}$. Размерность подпространства $\mathbb{S}_{U}^{n}$ равна

Из вышесказанного следует, что ${{X}_{U}}$ и ${{Y}_{U}}$ принадлежат $\mathbb{S}_{U}^{n}$. Пусть Согласно (38)–(40) имеем ${{X}_{U}} = {{F}_{{{{X}_{U}}}}}D({{\eta }_{U}})F_{{{{X}_{U}}}}^{{\text{T}}}$, ${{Y}_{U}} = {{F}_{{{{Y}_{U}}}}}D({{\theta }_{U}})F_{{{{Y}_{U}}}}^{{\text{T}}}$, где Обе матрицы ${{F}_{{{{X}_{U}}}}}$ и ${{F}_{{{{Y}_{U}}}}}$ ортогональные.

Рассмотрим дополнительно матрицы ${{C}_{U}} = {{U}^{{\text{T}}}}CU \in {{\mathbb{S}}^{n}}$ и ${{A}_{{i,U}}} = {{U}^{{\text{T}}}}{{A}_{i}}U \in {{\mathbb{S}}^{n}}$, являющиеся представлением матриц $C$ и ${{A}_{i}}$, $i \in {{J}^{m}}$, в базисе, задаваемым столбцами ортогональной матрицы $U$. Кроме того, произведем “сужение” этих матриц до блочно-диагональных матриц ${{\tilde {C}}_{U}}$ и ${{\tilde {A}}_{{i,U}}}$ из $\mathbb{S}_{U}^{n}$, оставив только в ${{C}_{U}}$ и ${{A}_{{i,U}}}$ их диагональные блоки, а остальные блоки взяв нулевыми, например,

где ${{A}_{{i,{{U}_{P}}}}} = U_{P}^{{\text{T}}}{{A}_{i}}{{U}_{P}}$, ${{A}_{{i,{{U}_{B}}}}} = U_{B}^{{\text{T}}}{{A}_{i}}{{U}_{B}}$, ${{A}_{{i,{{U}_{N}}}}} = U_{N}^{{\text{T}}}{{A}_{i}}{{U}_{N}}$.

Матрицы ${{\tilde {A}}_{{1,U}}}, \ldots ,{{\tilde {A}}_{{m,U}}}$ порождают в $\mathbb{S}_{U}^{n}$ подпространство, которое обозначим через ${{\mathcal{E}}_{{\tilde {A}}}}$. Через $\mathcal{E}_{{\tilde {A}}}^{ \bot }$ обозначим его ортогональное дополнение в $\mathbb{S}_{U}^{n}$. Размерность подпространства $\mathcal{E}_{{\tilde {A}}}^{ \bot }$ равна ${{l}_{U}} = {{n}_{U}} - m$. Пусть ${{\tilde {K}}_{{j,U}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, – произвольные матрицы из $\mathbb{S}_{U}^{n}$, задающие базис в подпространстве $\mathcal{E}_{{\tilde {A}}}^{ \bot }$. Все матрицы ${{\tilde {K}}_{{j,U}}}$ имеют вид, аналогичный (42), а именно:

где ${{K}_{{j,{{U}_{P}}}}} = U_{P}^{{\text{T}}}{{K}_{j}}{{U}_{P}}$, ${{K}_{{j,{{U}_{B}}}}} = U_{B}^{{\text{T}}}{{K}_{j}}{{U}_{B}}$, ${{K}_{{j,{{U}_{N}}}}} = U_{N}^{{\text{T}}}{{K}_{j}}{{U}_{N}}$.

Введем определение невырожденности для допустимой пары $[{{X}_{U}},{{Y}_{U}}] \in \mathbb{S}_{U}^{n} \times Y_{U}^{n}$, считая, по-прежнему, что она согласованная и регулярная.

Определение 7. Допустимая пара $[{{X}_{U}},{{Y}_{U}}] \in \mathbb{S}_{U}^{n} \times \mathbb{S}_{U}^{n}$ называется $X$-невырожденной, если матрицы

линейно независимы. Соответственно, пара $[{{X}_{U}},{{Y}_{U}}] \in \mathbb{S}_{U}^{n} \times \mathbb{S}_{U}^{n}$ называется $Y$-невырожденной, если матрицы линейно независимы. В случае, когда пара $[{{X}_{U}},{{Y}_{U}}] \in \mathbb{S}_{U}^{n} \times Y_{U}^{n}$ является одновременно $X$-невырожденной и $Y$-невырожденной, о ней будем говорить как о невырожденной паре.

Принимая во внимание размерности диагональных блоков в матрицах (43) и (44), получаем, что пара $[X,Y]$ может быть невырожденной в том и только том случае, когда выполняются неравенства:

Если учесть, что ${{l}_{U}} = {{n}_{U}} - m$, то второе неравенство принимает вид $n_{B}^{\Delta } \leqslant m$.

Утверждение 10. Пусть допустимая регулярная согласованная пара $[{{X}_{U}},{{Y}_{U}}] \in \mathbb{S}_{U}^{n} \times S_{U}^{n}$ является невырожденной. Тогда, если ${{n}_{N}} > 0$, то матрицы ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, порождают пространство ${{\mathbb{S}}^{{{{n}_{N}}}}}$. С другой стороны, если ${{n}_{B}} > 0$, то матрицы ${{A}_{{i,{{U}_{B}}}}}$, $i \in {{J}^{m}}$, порождают пространство ${{\mathbb{S}}^{{{{n}_{B}}}}}$.

Доказательство. Предположим, что ${{n}_{N}} > 0$ и докажем первое утверждение. Введем в рассмотрение подпространство ${{\mathcal{T}}_{{{\text{tan}}}}}({{X}_{U}}\,|\,\mathbb{S}_{{U, + }}^{n})$ пространства $\mathbb{S}_{U}^{n}$, определив его следующим образом:

где $\mathbb{S}_{{U, + }}^{n} = \mathbb{S}_{U}^{n} \cap \mathbb{S}_{ + }^{n}$. Множество ${{\mathcal{T}}_{{{\text{tan}}}}}({{X}_{U}}\,|\,\mathbb{S}_{{U, + }}^{n})$ является касательным подпространством к конусу $\mathbb{S}_{{U, + }}^{n}$ в ${{X}_{U}}$. Ортогональным дополнением $\mathcal{T}_{{{\text{tan}}}}^{ \bot }({{X}_{U}}\,|\,\mathbb{S}_{{U, + }}^{n})$ к ${{\mathcal{T}}_{{{\text{tan}}}}}({{X}_{U}}\,|\,\mathbb{S}_{{U, + }}^{n})$ является множество Кроме того, через ${{\mathcal{R}}_{{\tilde {A},U}}}$ обозначим подпространство пространства $\mathbb{S}_{U}^{n}$, порожденное матрицами ${{\tilde {A}}_{{i,U}}}$, $i \in {{J}^{m}}$. Его ортогональным дополнением в $\mathbb{S}_{U}^{n}$ будет множество

Положим

Отсюда получаем, что для матриц ${{\tilde {A}}_{{i,U}}}$, $i \in {{J}^{m}}$, справедливо разложение где Так как матрицы (43) линейно независимы, то матрицы ${{\hat {B}}_{{i,U}}}$, $i \in {{J}^{m}}$, также линейно независимы.

Покажем, что выполняется равенство

От противного, пусть данное пересечение содержит ненулевую матрицу $\hat {Z}$. Тогда найдутся коэффициенты ${{\alpha }_{i}}$, $i \in {{J}^{m}}$, в совокупности не равные нулю, такие, что Поэтому на основании (46) и (47) имеем $\sum\nolimits_{i = 1}^m \,{{\alpha }_{i}}{{\hat {B}}_{{i,U}}} = {{0}_{{nn}}},$ что противоречит линейной независимости матриц ${{\hat {B}}_{{i,U}}}$, $i \in {{J}^{m}}$.

Пусть ${{\mathcal{L}}_{{K,{{U}_{N}}}}}$ – подпространство в ${{\mathbb{S}}^{{{{n}_{N}}}}}$, порождаемое матрицами ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$. Если оно не совпадает с ${{\mathbb{S}}^{{{{n}_{N}}}}}$, то ортогональное в ${{\mathbb{S}}^{{{{n}_{N}}}}}$ к ${{\mathcal{L}}_{{K,{{U}_{N}}}}}$ подпространство содержит ненулевую матрицу ${{Z}_{{{{U}_{N}}}}}$ порядка ${{n}_{N}}$. Имеем ${{Z}_{{{{U}_{N}}}}} \bullet {{K}_{{j,{{U}_{N}}}}} = 0$, $j \in {{J}^{{{{l}_{U}}}}}$. Данные равенства можно переписать в виде

где причем ранг матрицы ${{\tilde {Z}}_{U}}$ совпадает с рангом матрицы ${{Z}_{{{{U}_{N}}}}}$, т.е. ${{\tilde {Z}}_{U}}$ – ненулевая матрица. Кроме того, из (49) следует, что ${{\tilde {Z}}_{U}} \in {{\mathcal{R}}_{{\tilde {A},U}}}$. Таким образом, что противоречит (48). Поэтому на самом деле матрицы ${{K}_{{j,{{U}_{N}}}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, порождают все пространство ${{\mathbb{S}}^{{{{n}_{N}}}}}$.

Второе утверждение доказывается аналогично.

4. НЬЮТОНОВСКАЯ СИСТЕМА

Из предположения о существовании решений у пары задач (1) и (2) следует, что эти решения должны удовлетворять условиям оптимальности:

Но равенство $X \bullet Y = 0$ при $X \succcurlyeq 0$, $Y \succcurlyeq 0$ выполняется тогда и только тогда, когда $XY = YX = {{0}_{{nn}}}$. Поэтому первое равенство из (50) может быть заменено на $X \circ Y = {{0}_{{nn}}}$ и решение задач (1) и (2), таким образом, сводится к отысканию решений системы причем $X$ и $Y$ должны принадлежать конусу $\mathbb{S}_{ + }^{n}$.

Наша цель заключается в решении системы (51) методом Ньютона при условии, что стартовые точки $X$ и $Y$ берутся допустимыми и согласованными. Более того, все последующие точки в ходе итерационного процесса остаются такими же.

Далее для простоты считаем, что $[X,Y]$ – допустимая регулярная согласованная пара. Кроме того, считаем, что она неоптимальная и неособая. Построим ньютоновскую систему уравнений для определения направлений перемещений $\Delta X$ и $\Delta Y$ (ньютоновских направлений) в этой паре. Воспользуемся базисом, определяемым столбцами ортогональной матрицы $U$ из разложения (12). Тогда условия оптимальности (51) в этом базисе запишутся в виде

где ${{C}_{U}} = {{U}^{{\text{T}}}}CU$, ${{A}_{{i,U}}} = {{U}^{{\text{T}}}}{{A}_{i}}U$, $i \in {{J}^{m}}$, и ${{X}_{U}} = {{U}^{{\text{T}}}}XU \succcurlyeq 0$, ${{Y}_{U}} = {{U}^{{\text{T}}}}YU \succcurlyeq 0.$

Согласно (38) текущие матрицы ${{X}_{U}}$ и ${{Y}_{U}}$ в базисе, задаваемом матрицей $U$, являются блочно-диагональными. Кроме того, они допустимые, следовательно, удовлетворяют второму и третьему равенствам из (51). Эти равенства с учетом блочной диагональности ${{X}_{U}}$ и ${{Y}_{U}}$ можно переписать в виде

Так как пара $[X,Y]$ неоптимальная, то первое равенство из (52), разумеется, не выполняется.

С целью упрощения дальнейшего изложения, хотя это и не принципиально, освободимся от двойственной переменной $u$ во втором равенстве (53). Для этого воспользуемся введенными ранее матрицами ${{\tilde {K}}_{{j,U}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, задающими базис в подпространстве $\mathcal{E}_{{\tilde {A}}}^{ \bot }$. Тогда, умножая скалярным образом равенство ${{Y}_{U}} = {{\tilde {C}}_{U}} - \sum\nolimits_{i = 1}^m \,{{u}^{i}}{{\tilde {A}}_{{i,U}}}$ последовательно на матрицы ${{\tilde {K}}_{{j,U}}}$, получаем

где ${{c}^{j}} = {{\tilde {K}}_{{j,U}}} \bullet {{\tilde {C}}_{U}}$. Заметим также, что матрицы ${{\tilde {K}}_{{j,U}}}$, $j \in {{J}^{{{{l}_{U}}}}}$, порождают в $\mathbb{S}_{U}^{n}$ подпространство, которое обозначим через ${{\mathcal{E}}_{{\tilde {K}}}}$. По своему определению ${{\mathcal{E}}_{{\tilde {K}}}}$ совпадает с $\mathcal{E}_{{\tilde {A}}}^{ \bot }$. Подставляя (54) вместо третьего равенства в условиях (51), приходим к следующей системе уравнений относительно ${{X}_{U}}$ и ${{Y}_{U}}$:

Составим теперь систему для нахождения ньютоновских направлений $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$, решающих систему (55). Так как матрицы ${{X}_{U}}$ и ${{Y}_{U}}$ симметричные, то чтобы сохранить их симметричность при перемещении вдоль направлений $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ будем также в качестве последних брать симметричные матрицы. Кроме того, поскольку матрицы ${{X}_{U}}$, ${{Y}_{U}}$ и все матрицы ${{\tilde {C}}_{U}}$, ${{\tilde {A}}_{{i,U}}}$, ${{\tilde {K}}_{{j,U}}}$, где $i \in {{J}^{m}}$ и $j \in {{J}^{{{{l}_{U}}}}}$, принадлежат подпространству $\mathbb{S}_{U}^{n}$, то целесообразно и ньютоновские направления $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ брать из этого подпространства, т.е. полагать

Тогда линейная система алгебраических уравнений для нахождения ньютоновских направлений $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ в паре $[X,Y]$ имеет вид

Более того, если принять во внимание, что ${{X}_{U}} \circ {{Y}_{U}}D(\lambda )$, то первое уравнение (57) можно также переписать следующим образом:

Из (57) следует, что матрицы $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ должны принадлежать подпространствам, ортогональным соответственно к подпространствам ${{\mathcal{E}}_{{\tilde {A}}}}$ и ${{\mathcal{E}}_{{\tilde {K}}}}$. Другими словами, $\Delta {{X}_{U}} \in {{\mathcal{E}}_{{\tilde {K}}}}$, $\Delta {{Y}_{U}} \in {{\mathcal{E}}_{{\tilde {A}}}}$.

Так как матрицы $\Delta {{X}_{U}}$ и $\Delta {{Y}_{U}}$ имеют вид (56), то матричное уравнение (58) распадается на три уравнения, а именно:

причем из двух последних сразу получаем

Второе и третье уравнения из (55) в развернутом виде переписываются следующим образом:

где $i \in {{J}^{m}}$, $j \in {{J}^{{{{l}_{U}}}}}$. Кроме того, если учесть (60), то они принимают следующий более простой вид:

Объединяя первое уравнение из (59) с (61) и (62), окончательно приходим к системе

Так как ${{l}_{U}} = {{n}_{U}} - m$ и число ${{n}_{U}}$ определяется (41), то общее число уравнений в системе (63) равно $2n_{P}^{\Delta } + n_{B}^{\Delta } + n_{N}^{\Delta }$. Оно совпадает с общим числом неизвестных.

Разрешая систему (63), можно найти приращения $\Delta {{X}_{{{{U}_{P}}}}}$, $\Delta {{Y}_{{{{U}_{P}}}}}$, $\Delta {{X}_{{{{U}_{B}}}}}$ и $\Delta {{Y}_{{{{U}_{N}}}}}$ и перейти к новым точкам. Конкретные выражения для этих приращений будут получены в отдельной статье. Там же будет дано описание итерационного процесса и предложен способ выбора шага перемещения.