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

[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

[DRUID3]

K1 * V1

это векторные произведения?

[getch]

это векторные произведения?

Это произведение числа на вектор:
Ki - вещественные числа.
Vi - вектора.

V[j] - j-й элемент вектора V.

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

[DRUID3]

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

Словами иными - есть набор векторов(? так, не коэффициентов вектора?) и из набора долей единицы(даже вернее из диапазона +/-1) нужно выбрать числа так что-бы сумма векторов была максимальной? На численно-оптимизационную задачу похоже.

[getch]

Словами иными - есть набор векторов(? так, не коэффициентов вектора?) и из набора долей единицы(даже вернее из диапазона +/-1) нужно выбрать числа так что-бы сумма векторов была максимальной?

Только максимизировать надо не саму сумму векторов, а определенную выше функцию F от этой суммы - F(K1 * V1 + ... + Kn * Vn).
F - сумма модулей (или квадратов) разностей соседних элементов вектора.

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

[DRUID3]

А какая разница? Вот у Вас целевая функция. Вот вектор коэффициентов. Ну и вперед. Любой градиентный метод или модные сейчас генетические алгоритмы - последние без проблем параллелятся.

[getch]

Понимаю, что решение в лоб всегда существует. В лоб - ГА, примененный к любой целевой функции.
Естественно, о подходах к решению задачи спрашивал с другой целью - получить какие-то значительно более быстро-считающие варианты решения.
Т.е. в идеале что-то близкое к аналитическому решению. Например, переход от огромной размерности векторов к существенно более компактной их ковариационной матрице. И далее работа уже с ней.

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

[DRUID3]

...у каждого из которых сумма его элементов равна нулю...

ах... я вот это пропустил, т.е. вектора не просто любые случайные...

[getch]

Да, вектора относительно удобные для мат. аппарата, которым, к сожалению, владею крайне слабо. Поэтому и прошу помощи.

[alex_os]

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

Может ошибаюсь но для квадратичной F() как-то так должно быть:

Код

k - искомый вектор столбец,
V - матрица состоящая из заданных векторов столбцов V1, V2, ..Vn
S - матрица сдвига,   т.е.  произведение S*v(1:end) дает сдвинутый на элемент вектор [v(2:end),0]
' - знак транспонирования

new_v = V*k
new_v_shifted = S*V*k

F(new_v) = (new_v-new_v_shifted)' * (new_v-new_v_shifted) =
= (V*k-S*V*k)' * (V*k-S*V*k) = (k'*V' - k'*V'*S') * (V*k-S*V*k) =
= k'*V'*V*k - k'*V*S*V*k -k'*V'*S*V*k + k'*V'*S'*S*V*k =
= k'*(V'*V - V*S*V -V'*S*V + V'*S'*S*V)*k = k'*A*k,
где
A =  (V'*V - V*S*V -V'*S*V + V'*S'*S*V) квадратная матрицы n x n

Далее, максимум квадратичной формы k' * A * k, будет когда k является, одним из собственных
векторов A.

[getch]

Может ошибаюсь но для квадратичной F() как-то так должно быть:

Код

S - матрица сдвига,   т.е.  произведение S*v(1:end) дает сдвинутый на элемент вектор [v(2:end),0]

Спасибо за подробный ответ!
Подскажите, как выглядит матрица сдвига в данном случае? Вместо нее делал бы сдвиг индексов в самом алгоритме, но в выражении ниже ее надо и транспонировать и другое. Т.е. без явного вида не представляю, как обойтись.

F(new_v) = (new_v-new_v_shifted)' * (new_v-new_v_shifted) =
= (V*k-S*V*k)' * (V*k-S*V*k) = (k'*V' - k'*V'*S') * (V*k-S*V*k) =
= k'*V'*V*k - k'*V'*S*V*k -k'*V'*S'*V*k + k'*V'*S'*S*V*k =
= k'*(V'*V - V'*S*V -V'*S'*V + V'*S'*S*V)*k = k'*A*k,
где
A = (V'*V - V'*S*V -V'*S'*V + V'*S'*S*V) квадратная матрицы n x n

Жирным шрифтом подправил неточности.

Далее, максимум квадратичной формы k' * A * k, будет когда k является, одним из собственных
векторов A.

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

[getch]

Подскажите, как выглядит матрица сдвига в данном случае? Вместо нее делал бы сдвиг индексов в самом алгоритме, но в выражении ниже ее надо и транспонировать и другое. Т.е. без явного вида не представляю, как обойтись.

Если переписать матрицу A следующим образом:

Код

A = V'*V - V'*S*V -V'*S'*V + V'*S'*S*V = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V)

то S-матрица-сдвига будет присутствовать только в виде (S*V), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме.

Скажите, нет ли ошибки в таких рассуждениях?

Сообщение отредактировал getch - Sep 14 2012, 19:20

[fontp]

Если переписать матрицу A следующим образом:

CODE

A = V'*V - V'*S*V -V'*S'*V + V'*S'*S*V = V'*V - V'*(S*V) -(S*V)'*V + (S*V)'*(S*V)

то S-матрица-сдвига будет присутствовать только в виде (S*V), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме.

Скажите, нет ли ошибки в таких рассуждениях?

Нет. А чтобы не гадать, матрица сдвига выглядит как единичная, только единицы НАД диагональю (или ПОД, зависит от направления сдвига). Если нужен циклический сдвиг, то матрицу можно получить сдвигая единичную диагональ направо/налево циклически

[fontp]

Если нужен циклический сдвиг, то матрицу можно получить сдвигая единичную диагональ направо/налево циклически

Условие нормированности k произойдет автоматически, если учесть что собственный вектор нормирован. А условие отсутствия постояннной составляющей действительно оказалось не при делах

[getch]

Нет. А чтобы не гадать, матрица сдвига выглядит как единичная, только единицы НАД диагональю (или ПОД, зависит от направления сдвига).

Матрица сдвига, конечно, получается огромной - NxN (N - количество элементов в исходном векторе Vi). Т.е. ее для перемножения использовать совсем нерезонно на практике. Проще алгоритмом сразу.

Спасибо, задача теперь решена полностью.

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

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

Сообщение отредактировал getch - Sep 18 2012, 06:17