Минимум квадратичной формы

[Ja_Dron]

Здравствуйте.
Подскажите пожалуйста или укажите литературу где это можно найти ответ на следующий вопрос.
Есть квадратичная форма $R$ размерности $n$, как найти минимум следующего выражения
$bRb'$, где $b$ вектор состоящий из [-1 +1].

Не используя перебор с использованием $2^{n-1}$ комбинаций.
Всем спасибо.

[Kallikanzarid]

Это квадратичная функция.

[jetyb]

Kallikanzarid
Скорее всего имелся ввиду минимум только среди всех комбинаций $b$.

Сомневаюсь, что такая задача разрешима(не считая перебора). Помню как-то обсуждали такую задачу:

"Есть $N$ камней с известными массами. Необходимо так их разложить на двухрычажных весах, чтобы они максимально уравновесились."

Решения так и не нашли, при больших $N$ перебор не катил, бились только над приближенно работающими алгоритмами решения.
Вроде бы даже непереборного решения для этой задачи и не существует.

А она является лишь частным случаем вашей.

[Ja_Dron]

jetyb в сообщении #465975 писал(а):

Kallikanzarid
Скорее всего имелся ввиду минимум только среди всех комбинаций $b$.

Именно это и имелось ввиду. )

jetyb в сообщении #465975 писал(а):

Сомневаюсь, что такая задача разрешима(не считая перебора)

А если R положительно определенная?


Пожалуйста, подскажите литературу по этому вопросу.

[jetyb]

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

А если R положительно определенная?

В приведенной мною задаче полином от $R$ вообще является квадратом линейного выражения.

[ewert]

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

[мат-ламер]

Гуглите по Binary Quadratic Problems. Вторая ссылка по этим словам http://www.maths.lth.se/matematiklth/personal/fredrik/olsson_cvpr07.pdf.
Слово Problems можно заменить на Programming или Minimization.