2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

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

 
 
 
 Re: Минимум квадратичной формы
Сообщение07.07.2011, 05:12 
Это квадратичная функция.

 
 
 
 Re: Минимум квадратичной формы
Сообщение07.07.2011, 08:29 
Kallikanzarid
Скорее всего имелся ввиду минимум только среди всех комбинаций $b$.

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

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

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

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

 
 
 
 Re: Минимум квадратичной формы
Сообщение07.07.2011, 10:42 
jetyb в сообщении #465975 писал(а):
Kallikanzarid
Скорее всего имелся ввиду минимум только среди всех комбинаций $b$.

Именно это и имелось ввиду. )
jetyb в сообщении #465975 писал(а):
Сомневаюсь, что такая задача разрешима(не считая перебора)

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


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

 
 
 
 Re: Минимум квадратичной формы
Сообщение07.07.2011, 11:01 
Ja_Dron в сообщении #466016 писал(а):
А если R положительно определенная?

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

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

 
 
 
 Re: Минимум квадратичной формы
Сообщение07.07.2011, 20:09 
Аватара пользователя
Гуглите по Binary Quadratic Problems. Вторая ссылка по этим словам http://www.maths.lth.se/matematiklth/personal/fredrik/olsson_cvpr07.pdf.
Слово Problems можно заменить на Programming или Minimization.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group