Положительная определенность матрицы

[Ja_Dron]

Добрый вечер.
Подскажите пожалуйста ответ на следующий вопрос.
Есть квадратичная форма
$xRx'$,
где $R$ - квадратная матрица, $x$ - вектор принадлежащий множеству [+1 -1 ].
Согласно критерию Сильвестра можно определить её положительную определенность.
Вопрос. Есть ли какой-нибудь другой критерий, для определения положительной определенности, который учитывал бы, что вектор $x$ принадлежит множеству [+1 -1]?
Или множеству [+1 +3 -1 -3]? И т. д.

Если есть возможность подскажите пожалуйста литературу.

Заранее благодарен.

[ИСН]

Вы что понимаете под множеством [+1 -1 ]? Так обычно обозначают отрезок, но у отрезка слева должен быть, эээ, левый конец, а не правый.

[Евгений Машеров]

Элементы вектора Х принадлежат к множеству дискретных значений?
Мучает меня смутное сомнение - а это не NP-полная задача вообще?

[Ja_Dron]

ИСН в сообщении #479788 писал(а):

Вы что понимаете под множеством [+1 -1 ]? Так обычно обозначают отрезок, но у отрезка слева должен быть, эээ, левый конец, а не правый.

Что элементы вектора $x$ могут принимать значения либо +1, либо -1.

[ИСН]

Дак это называется $x\in\{-1,1\}^n$

-- Пт, 2011-09-02, 21:45 --

Слушайте, да тут тыком перебрать...

[Ja_Dron]

Евгений Машеров в сообщении #479794 писал(а):

Элементы вектора Х принадлежат к множеству дискретных значений?
Мучает меня смутное сомнение - а это не NP-полная задача вообще?

В общем случае могут принадлежать множеству дискретных значений, но ограничимся $+1$ и $-1$.

Если это NP-полная задача, то я расстроен...

[ИСН]

NP-полной она быть не может, потому что есть же критерий Сильвестра. Или Вы хотели что-то быстрее именно его? Тогда это вопроооооос...

[Ja_Dron]

ИСН в сообщении #479815 писал(а):

Дак это называется $x\in\{-1,1\}^n$

-- Пт, 2011-09-02, 21:45 --

Слушайте, да тут тыком перебрать...

Спасибо за указание :)
Тык охватывает мало.
Я думал, может существует какой-нибудь "частный случай" критерия Сильвестра или что-нибудь в этом духе.

-- 02.09.2011, 21:55 --

ИСН в сообщении #479821 писал(а):

NP-полной она быть не может, потому что есть же критерий Сильвестра. Или Вы хотели что-то быстрее именно его? Тогда это вопроооооос...

Не надо быстрее критерия Сильвестра.
Вот в чем проблема.
Бывает, критерий Сильвестра говорит - она не положительна определенная, но в случае, когда $x\in\{-1,1\}^n$ данная квадратичная форма остается положительной.
А необходимо знать, когда именно при $x\in\{-1,1\}^n$ станет не положительно определенной.

[ewert]

ИСН в сообщении #479821 писал(а):

потому что есть же критерий Сильвестра.

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

Ja_Dron в сообщении #479822 писал(а):

но в случае, когда $x\in\{-1,1\}^n$ данная квадратичная форма остается положительной.

Ну только почему бы не формулировать грамотно? Форма по определению задаётся на каком-то пространстве или в крайнем случае на подпространстве, но никак не на произвольном подмножестве, тем более дискретном. Поэтому и говорить надо не о "положительности формы", а о том, что эта форма принимает положительные значения на данном множестве. Пустячок, казалось бы, но с толку сбивает сильно.

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

[Ja_Dron]

ewert в сообщении #479888 писал(а):

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

Правильно, ли я понимаю из вашего высказывания, что положительность главных миноров квадратичной формы, еще не означает её положительной определенности?

[ewert]

Ja_Dron в сообщении #479925 писал(а):

положительность главных миноров квадратичной формы, еще не означает её положительной определенности?

Означает. Просто Вы путаетесь в терминологии: понятие "положительно определённая матрица" имеет смысл только для всего пространства.

[Евгений Машеров]

Моё подозрение на NP-полноту основывается на том. что задача уж очень похожа на целочисленное квадратическое программирование. То есть её можно рассматривать. как ДКП, искать минимум и проверять, положителен ли минимум. а она точно не полиномиальна. С другой стороны, тут задача более ограничена, не надо искать доставляющий минимум вектор - но спасает ли? Похоже, можно построить алгоритм на основе динамического программирования, но он будет псевдополиномиален.

[Kallikanzarid]

Очевидно, что если $\lambda_1, \ldots, \lambda_n$ - собственные значения матрицы, $v_1, \ldots, v_n$ - соответствующий базис, составленный из собственных векторов, то выразив вектор $x \in \{0, 1\}^n$ как $x = y^i v_i$, получим, что $x \cdot Rx = \sum_{i,j=1}^n \lambda_j y^i y^j (v_i \cdot v_j)$.

Частный случай: $v_i \cdot v_j = \delta_{ij}$. Тогда $x \cdot Rx = \sum_{i = 1}^n \lambda_i (y^i)^2$, и положительная определенность эквивалентна положительной определенности в вашем смысле (ортогональная замена базиса не меняет собственные значения). Кажется, я запутался :(

В общем же случае непонятно, что можно сделать: видимо, без вычисления собственных значений и собственных векторов не обойтись, а это даже приближенно делать довольно долго :(

[Евгений Машеров]

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

[Евгений Машеров]

Похоже, что задача проверки "дискретной положительной определённости" примерно по сложности соответствует дискретному квадратичному программированию, а оно, видимо, не проще линейного целочисленного.
Напрашиваются "ветви и границы". Ветвление по значению i-того элемента вектора, оценивание с.з. матрицы, оставшейся после фиксации значений вектора x, отбрасывание ветвей, на которых с.з. (плюс вклад от ранее зафиксированных значений вектора) положительна, пока все не переберутся.