Нахождение максимальной суммы разностей модулей соседних значений вектора, Несколько векторов нужно сложить для максимизации искомой суммы Опции

[getch]

Приветствую всех!

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

Определена такая функция для любого вектора: F(V) = Sum(Abs(V[j] - V[j + 1])) , либо F(V) = Sum((V[j] - V[j + 1])^2))
Даны одинаковой размерности вектора V1, V2, ..., Vn, у каждого из которых сумма его элементов равна нулю.

Нужно найти вектор NewV = K1 * V1 + K2 * V2 + ... + Kn * Vn, где Sum(Abs(Ki)) = 1, либо Sum(Ki^2) = 1
значение F(NewV) которого было бы максимальным.

У меня есть гипотеза, что всегда верно неравенство F(NewV) <= max(F(V1), F(V1), ...., F(Vn)), т.е. решением задачи является вектор коэффициентов, где один элемент равен ±единице, а остальные - нули.

Возможно, кому-то известно решение схожей или частного случая этой задачи. Спасибо.

Сообщение отредактировал getch - Sep 13 2012, 07:35

[Oldring]

Гуглите понятие "induced matrix norm".
Dixi.

[getch]

Гуглите понятие "induced matrix norm".
Dixi.

Спасибо, посмотрел книгу. Срезюмировав:


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

Но как приведенные выше свойства индуцированной матричной нормы помогут решить задачу?

Я запомнил данный Вами замечательный итерационный алгоритм нахождения собственного вектора, соответствующего максимальному собственному значению матрицы. Поэтому данная ранее перефломулировка задачи через матрицу A = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) видится наиболее оптимальной на данный момент.

[iiv]

Поэтому данная ранее перефломулировка задачи через матрицу A = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) видится наиболее оптимальной на данный момент.

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

1. матрица маленькая - эдак до 100 строк/столбцов. Влоб ее вычислить, вызвать лапак, радоваться.
2. матрица средних размеров примерно до 5000 строк/столбцов. Влоб ее посчитать, дальше либо методом простой итерации, либо методом Ланцоша посчитать ее максимальное собственнное значение и соответствующий вектор.
3. матрица больших размеров (вся в память не влезет). В этом случае, скорее всего Вы как-то можете сохранить V, и можно программно реализовать умножение матрицы в форме A = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V) на вектор без вычисления A. В этом случае, достаточно методом Ланцоша получить искомый собственный вектор.

Про Ланцоша в Википедии понятно написано.
Про лапак - на http://www.netlib.org/lapack

если что не понятно, спрашивайте, постораюсь помочь.