Линейная комбинация с положительными элементами

[B@R5uk]

Пусть имеется несколько столбцов (например, записанных в виде матрицы A) и строится их линейная комбинация (например, умножением матрицы A на столбец неизвестных X). Высота столбцов как правило больше их количества. Требуется определить, можно ли построить эту линейную комбинацию так, чтобы все элементы результирующего столбца Y были неотрицательны и хотя бы один положителен? То есть, чтобы

$$AX=Y,\qquad y_k\ge 0,\qquad 1\le k\le K$$

где K — количество элементов в столбце.

На вскидку, похоже на задачу линейного программирования: линейная операция, линейные ограничения, только целевой функции для оптимизации не хватает (впрочем, хотелось бы, чтобы сумма координат в результирующем столбце Y была максимальна, но это вовсе необязательно). Однако, линейное программирование — это слишком крупная артиллерия, хотелось бы обойтись калибром по-меньше, например, методами линейной алгебры. Вопрос: можно ли?

Свои попытки решения задачи, пока невразумительны. Для начала было бы неплохо привести примеры "решаемых" и "нерешаемых" исходных матриц A. Вот, две "нерешаемых":

$$A_1^-=\left(\begin{array}{r}1\\-1\end{array}\right),\qquad A_2^-=\left(\begin{array}{rr}1&0\\1&-2\\-1&1\end{array}\right)$$

Для первой очевидно, что нельзя получить ненулевую ЛК без отрицательного элемента; вторую надо чутка покрутить. Теперь пример "решаемых" матриц:

$$A_1^+=\left(\begin{array}{r}2\\1\end{array}\right),\qquad A_2^+=\left(\begin{array}{rr}1&0\\1&-1\\-1&1\end{array}\right)$$

С первой здесь тоже всё очевидно, а у второй надо просто взять сумму столбцов.

Понятно, что если существует столбец, у которого все координаты одного знака, то матрица решаемая. Как бы все эти наблюдения обобщить на произвольных случай?

[lel0lel]

Напрашивается метод Гаусса по столбцам. Потом уже смотреть, что получилось.

[yonkis]

Доброго времени суток!

Вы ищете условие, при котором для заданной матрицы $A$ (размером K x N, состоящей из N столбцов-векторов в $\mathbb{R}^K$) существует такой вектор весов $X$ в $\mathbb{R}^N$, что результирующий вектор $Y = AX$ удовлетворяет двум условиям:
1. Все его компоненты неотрицательны: $Y \ge 0$ (то есть $y_k \ge 0$ для всех $k=1, \dots, K$).
2. Сам вектор $Y$ не является нулевым: $Y \not= 0$ (то есть хотя бы одна компонента $y_k$ строго положительна).

Задача действительно имеет общие черты с задачами линейного программирования (линейные операции, линейные ограничения в виде неравенств), но, как Вы верно заметили, здесь отсутствует целевая функция для оптимизации. Мы имеем дело с задачей о разрешимости определённой системы линейных соотношений. Множество всех возможных линейных комбинаций $Y=AX$ образует образ (или пространство столбцов) матрицы $A$, являющийся линейным подпространством $\mathbb{R}^K$. Вопрос заключается в том, содержит ли это подпространство ненулевые векторы, принадлежащие неотрицательному ортанту $\mathbb{R}^K_{\ge 0}$.

Для анализа таких систем существуют мощные инструменты, известные как теоремы об альтернативе. Наиболее известной из них является лемма Фаркаша, но для Вашей задачи более точно подходит следующая формулировка (иногда связываемая с теоремой Гордана или другими теоремами об альтернативе):

Теорема. Для любой матрицы $A$ (размером K x N) ровно одна из следующих двух систем имеет решение:
1. (Исходная задача) Существует $X$ в $\mathbb{R}^N$ такой, что $AX \ge 0$ и $AX \not= 0$.
2. Существует $Y$ в $\mathbb{R}^K$ такой, что $A^T Y = 0$ и $Y > 0$ (то есть $y_k > 0$ для всех $k=1, \dots, K$).
(Здесь $A^T$ обозначает транспонированную матрицу $A$).

Таким образом, Ваша исходная задача (система 1) имеет решение тогда и только тогда, когда система 2 не имеет решения. Иными словами, критерий разрешимости Вашей задачи таков:
Не должно существовать вектора $Y$ со всеми строго положительными компонентами, который был бы ортогонален всем строкам матрицы $A$ (или, что эквивалентно, принадлежал бы левому ядру матрицы $A$, т.е. $Y^T A = 0$, или ядру $A^T$, т.е. $A^T Y = 0$).

Давайте проверим Ваши примеры с помощью этой теоремы.

Пример $A_1^- = \left( \begin{array}{r} 1 \\ -1 \end{array} \right)$.
Матрица $A^T = \left( \begin{array}{rr} 1 & -1 \end{array} \right)$. Ищем $Y = \left( \begin{array}{c} y_1 \\ y_2 \end{array} \right)$ с $y_1 > 0, y_2 > 0$ такой, что $A^T Y = 0$.
Уравнение: $1 \cdot y_1 + (-1) \cdot y_2 = 0 \implies y_1 = y_2$.
Такой вектор существует, например, $Y = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$ (здесь $y_1=1>0, y_2=1>0$).
Следовательно, система 2 имеет решение, а значит, система 1 (Ваша задача) решения не имеет. Это совпадает с Вашей классификацией "нерешаемая".

Пример $A_2^- = \left( \begin{array}{rr} 1 & 0 \\ 1 & -2 \\ -1 & -1 \end{array} \right)$.
Матрица $A^T = \left( \begin{array}{rrr} 1 & 1 & -1 \\ 0 & -2 & -1 \end{array} \right)$. Ищем $Y = \left( \begin{array}{c} y_1 \\ y_2 \\ y_3 \end{array} \right)$ с $y_1 > 0, y_2 > 0, y_3 > 0$ такой, что $A^T Y = 0$.
Система уравнений:
$y_1 + y_2 - y_3 = 0$
$-2 y_2 - y_3 = 0$
Из второго уравнения $y_3 = -2 y_2$. Поскольку мы требуем $y_2 > 0$, то $y_3$ должен быть отрицательным ($y_3 < 0$). Это противоречит требованию $y_3 > 0$.
Следовательно, система 2 не имеет решения (невозможно удовлетворить всем условиям одновременно).
Согласно теореме, система 1 (Ваша задача) должна иметь решение. Вы классифицировали эту матрицу как "нерешаемую", что, возможно, является результатом того, что найти подходящий вектор $X$ не всегда очевидно. Однако решение существует. Например, если взять $X = \left( \begin{array}{r} 0 \\ -1 \end{array} \right)$, то $Y = AX = \left( \begin{array}{rr} 1 & 0 \\ 1 & -2 \\ -1 & -1 \end{array} \right) \left( \begin{array}{r} 0 \\ -1 \end{array} \right) = \left( \begin{array}{r} 0 \\ 2 \\ 1 \end{array} \right)$. Этот вектор $Y$ удовлетворяет условиям $Y \ge 0$ и $Y \not= 0$.

Пример $A_1^+ = \left( \begin{array}{r} 1 \\ 1 \end{array} \right)$ (предполагая опечатку в вашем изображении, где $A_1^+ = A_1^-$).
Матрица $A^T = \left( \begin{array}{rr} 1 & 1 \end{array} \right)$. Ищем $Y = \left( \begin{array}{c} y_1 \\ y_2 \end{array} \right)$ с $y_1 > 0, y_2 > 0$ такой, что $A^T Y = 0$.
Уравнение: $y_1 + y_2 = 0$. Это уравнение не имеет решений при $y_1 > 0, y_2 > 0$.
Значит, система 2 не имеет решения, а система 1 имеет решение. Например, $X = \left( \begin{array}{c} 1 \end{array} \right)$, что дает $Y = AX = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$, удовлетворяющий условиям $Y \ge 0$ и $Y \not= 0$. Это совпадает с Вашей классификацией "решаемая".

Пример $A_2^+ = \left( \begin{array}{rr} 1 & 0 \\ 1 & -1 \\ -1 & 1 \end{array} \right)$.
Матрица $A^T = \left( \begin{array}{rrr} 1 & 1 & -1 \\ 0 & -1 & 1 \end{array} \right)$. Ищем $Y = \left( \begin{array}{c} y_1 \\ y_2 \\ y_3 \end{array} \right)$ с $y_1 > 0, y_2 > 0, y_3 > 0$ такой, что $A^T Y = 0$.
Система уравнений:
$y_1 + y_2 - y_3 = 0$
$-y_2 + y_3 = 0 \implies y_2 = y_3$
Подставляя второе уравнение в первое: $y_1 + y_2 - y_2 = 0 \implies y_1 = 0$. Это противоречит требованию $y_1 > 0$.
Значит, система 2 не имеет решения. Следовательно, система 1 (Ваша задача) имеет решение. Ваше наблюдение, что сумма столбцов ($X = \left( \begin{array}{c} 1 \\ 1 \end{array} \right)$) дает $Y = \left( \begin{array}{c} 1 \\ 0 \\ 0 \end{array} \right)$, подтверждает это ($Y \ge 0$ и $Y \not= 0$).

Относительно Вашего наблюдения.
Ваше наблюдение о том, что матрица "решаема", если у нее есть столбец, все элементы которого одного знака (и не все нули), совершенно верно и является достаточным условием.
* Если есть столбец $a_j$ (j-й столбец матрицы $A$) такой, что $a_{kj} \ge 0$ для всех $k$ и $a_j \not= 0$, то можно взять $X = e_j$ (j-й вектор стандартного базиса). Тогда $Y = AX = A e_j = a_j$. Очевидно, $Y = a_j \ge 0$ и $Y \not= 0$.
* Если есть столбец $a_j$ такой, что $a_{kj} \le 0$ для всех $k$ и $a_j \not= 0$, то можно взять $X = -e_j$. Тогда $Y = AX = A (-e_j) = -a_j$. Очевидно, $Y = -a_j \ge 0$ и $Y \not= 0$.
Однако, как показывают примеры $A_2^-$ (который оказался решаемым) и $A_2^+$, это условие не является необходимым. В этих матрицах нет столбцов, удовлетворяющих данному свойству, но задача тем не менее имеет решение.

Общий и точный критерий разрешимости Вашей задачи сводится к проверке несуществования строго положительного вектора $Y$ в (левом) ядре матрицы $A$ (или, эквивалентно, в ядре $A^T$). Проверка этого условия может быть выполнена, например, с помощью методов линейного программирования (попытаться найти такой $Y$, минимизируя, скажем, $0$ при условиях $A^T Y = 0$, $Y \ge \varepsilon$ для некоторого малого $\varepsilon > 0$).

[lel0lel]

yonkis в сообщении #1681436 писал(а):

Не должно существовать вектора $Y$ со всеми строго положительными компонентами, который был бы ортогонален всем строкам матрицы $A$ (или, что эквивалентно, принадлежал бы левому ядру матрицы $A$, т.е. $Y^T A = 0$

Уточните пожалуйста, не идёт ли речь о столбцах в выделенном мной месте)

[B@R5uk]

Я тут наткнулся на Метод Фурье-Моцкина с рекурсивной природой. Но что-то он не очень. Каждый следующий шаг вызывает функцию для матрицы с количеством столбцов на единицу меньшим, но с количеством строк равным

$$N_{l+1}=N_l^-N_l^++N_l^0$$

где верхние индексы означают количество отрицательных, положительных и нулевых элементов в первом столбце матрицы. Если нулевых нет вообще, а положительных и отрицательных поровну, то получаем

$$N_{l+1}=\frac{\bigl(N_0\bigr)^2}{4},\qquad N_K=\frac{\bigl(N_0\bigr)^{2^K}}{2^K}$$

то есть гиперэкспоненциальную сложность. Никуда не годится. Особенно, если у меня под сотню столбцов в матрице A будет.

-- 08.04.2025, 03:04 --

yonkis в сообщении #1681436 писал(а):

Проверка этого условия может быть выполнена, например, с помощью методов линейного программирования

То есть без ЛП всё-таки никак?

-- 08.04.2025, 03:57 --

lel0lel в сообщении #1681434 писал(а):

Напрашивается метод Гаусса по столбцам. Потом уже смотреть, что получилось.

Это позволит перейти к новым переменным

$$A'X'=Y'\ge 0,\qquad X'\ge 0$$

где теперь на аргумент тоже накладывается условие неотрицательности, так же как и на результат, но число строк в новой матрице уменьшится на число столбцов. Не знаю, на сколько это улучшит ситуацию и куда дальше плясать.

[B@R5uk]

ОК, вроде бы у меня немного проясняется в голове. Вот есть альтернатива:

yonkis в сообщении #1681436 писал(а):

Теорема. Для любой матрицы $A$ (размером K x N) ровно одна из следующих двух систем имеет решение:
1. (Исходная задача) Существует $X$ в $\mathbb{R}^N$ такой, что $AX \ge 0$ и $AX \not= 0$.
2. Существует $Y$ в $\mathbb{R}^K$ такой, что $A^T Y = 0$ и $Y > 0$ (то есть $y_k > 0$ для всех $k=1, \dots, K$).

Если в первом случае матрица A недоопределена или обратима, то мы можем сделать результат умножения на X таким, каким захотим, поэтому исходная задача разрешима. Пусть матрица A переопределена, тогда её транспонированная матрица в альтернативе недоопределена, и некоторое ненулевое решение (не обязательно удовлетворяющее условию положительности) будет всегда иметься. Методом Гаусса система приводится к такому виду

$$A^TY=0\quad\Longleftrightarrow\quad\left(\begin{matrix}I&-B\end{matrix}\right)PY=0$$

где I — это единичная матрица, B — некоторая остаточная матрица и P — матрица перестановки (в каждой строке и столбце только одна 1, а все остальные элементы — 0), наличие которой связано с тем, что на каждом этапе метода Гаусса в строке в качестве ведущего выбирается элемент с максимальным по модулю значением (для наилучшей обусловленности решения). Эта матрица имеет свойство

$$P^{-1}=P^T$$

Решение альтернативы теперь можно записать в виде

$$Y=P^T\left(\begin{matrix}B\\I\end{matrix}\right)Z$$

Проверяем:

$$\left(\begin{matrix}I&-B\end{matrix}\right)PY=\left(\begin{matrix}I&-B\end{matrix}\right)PP^T\left(\begin{matrix}B\\I\end{matrix}\right)Z=IBZ-BIZ=0$$

То есть одно условие альтернативы удовлетворено, а второе можно удовлетворить, если можно найти ненулевой столбец Z такой, что

$$BZ\ge 0$$

То есть получается исходная задача. Почти. На столбец Z теперь наложено ограничение положительности, чего в исходной альтернативе нет. Чёрт! Почти получилось. Я хотел свести исходную задачу с ней же, но с меньшей матрицей.