Неотрицательность решения системы линейных уравнений

[Андрей1]

Есть ли теория, которая дает необходимые и достаточные условия для матрицы A и столбца B линейной системы уравнений A X = B, (где X, B - столбцы одной размерности) для выполнения условия X>0 (x_n>0)?

[maxal]

Да, теория линейного программирования (линейных неравенств) дает полиномиальный ответ на эту задачу. В ее терминах эта задача формулируется как проверка принадлежности вектора $B$ конусу $C = \{ Ax \mid x\geq 0\}$.

P.S. Вот тут диссер вроде есть с обзором результатов: http://polnolunie.baikal.ru/me/mat_prog.htm

[Fgolm]

Вот, реализовал метод сопряженных направлений решения СЛАУ, описанный в работах по приведенной ссылке.
Вот что получилось:
Имеем СЛАУ с несимметричной неположительно определенной матрицей
$Ax = b$
Задается итерационный процесс:
нулевой шаг: $ \ \ x^0 = A^T b$, $ \ \ \beta _0 = 0$, $ \Rightarrow $ $ \ \ \Delta x^1 = A^T Ax^0 - A^T b$.

$t$-тый шаг: $\beta _t = \frac{{\left( {A^T Ax^{t - 1} - A^T b} \right)^T A^T A\Delta x^{t - 1} }}{{\left( {\Delta x^{t - 1} } \right)^T A^T A\Delta x^{t - 1} }}$
$|\ \ \ \ \ \ \ \ \ \ \Delta x^t = A^T Ax^{t - 1} - A^T b - \beta _t \Delta x^{t - 1} $
$| \ \ \ \ \ \ \ \ \ \ \alpha _t = - \frac{{\left( {A^T Ax^{t - 1} - A^T b} \right)^T \Delta x^t }}{{\left( {\Delta x^t } \right)^T A^T A\Delta x^t }}$
$| \ \ \ \ \ \ \ \ \ \ \ x^t = x^{t - 1} + \alpha _t \Delta x^t $
Я не очень разобрал, этот метод является собственной разработкой автора или это стандартная его реализация? Дело в том, что он приводится наряду со стандартными методами Гаусса и Халецкого, но с другой стороны выбор чисел $\alpha _t $ и $\beta _t $, если я правильно понял, предложен автором.

[Андрей1]

maxal писал(а):

Да, теория линейного программирования (линейных неравенств) дает полиномиальный ответ на эту задачу. В ее терминах эта задача формулируется как проверка принадлежности вектора $B$ конусу $C = \{ Ax \mid x\geq 0\}$.

P.S. Вот тут диссер вроде есть с обзором результатов: http://polnolunie.baikal.ru/me/mat_prog.htm

Спасибо.
А нет ли каких-либо условий (полученных теоретически), которым должны удовлетворять матрицы A и B, чтобы x_i \ge 0 (возможно, достаточно только частных условий)?

[maxal]

Вот еще почитайте:
Ермолаев Ю.Б. (2003) Линейные неравенства (препринт)

[Андрей1]

maxal писал(а):

Вот еще почитайте:
Ермолаев Ю.Б. (2003) Линейные неравенства (препринт)

Спасибо. То, что нужно.

[Alik]

Андрей1, если Вы окончательно разобрались с этими критериями, можете рассказать, вкратце?
Может в интернете Вы встречали реализацию алгоритма в MATLAB?
Меня интересует еще один критерий для столбца неизвестных: нужно чтобы все решения имели общий делитель, который находится среди них

[Андрей1]

Alik писал(а):

Андрей1, если Вы окончательно разобрались с этими критериями, можете рассказать, вкратце?

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

Alik писал(а):

Может в интернете Вы встречали реализацию алгоритма в MATLAB?
Меня интересует еще один критерий для столбца неизвестных: нужно чтобы все решения имели общий делитель, который находится среди них

Mathematica функция NMinimize гарантирует, что минимум будет глобальным для квадратичной и линейной целевой функции и линейных ограничениях.

[maxal]

Наткнулся еще на такую статью о решении линейных неравенств в целых числах:

D. Chubarov and A. Voronkov "Basis of Solutions for a System of Linear Inequalities in Integers: Computation and Applications"
http://dx.doi.org/10.1007/11549345_23