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

[getch 0]

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

 

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

 

Определена такая функция для любого вектора: 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)), т.е. решением задачи является вектор коэффициентов, где один элемент равен ±единице, а остальные - нули.

 

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

Edited September 13, 2012 by getch

[DRUID3 0]

K1 * V1

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

[getch 0]

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

Это произведение числа на вектор:

Ki - вещественные числа.

Vi - вектора.

 

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

Edited September 13, 2012 by getch

[DRUID3 0]

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

значение F(NewV) которого было бы максимальным.

 

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

[getch 0]

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

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

F - сумма модулей (или квадратов) разностей соседних элементов вектора.

Edited September 13, 2012 by getch

[DRUID3 0]

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

[getch 0]

Понимаю, что решение в лоб всегда существует. В лоб - ГА, примененный к любой целевой функции.

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

Т.е. в идеале что-то близкое к аналитическому решению. Например, переход от огромной размерности векторов к существенно более компактной их ковариационной матрице. И далее работа уже с ней.

Edited September 13, 2012 by getch

[DRUID3 0]

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

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

[getch 0]

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

[alex_os 0]

Нужно найти вектор 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 0]

Может ошибаюсь но для квадратичной 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 0]

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

 

Если переписать матрицу 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), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме.

 

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

Edited September 14, 2012 by getch

[fontp 0]

Если переписать матрицу 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), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме.

 

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

 

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

[fontp 0]

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

 

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

[getch 0]

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

 

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

 

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

 

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

 

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

Edited September 18, 2012 by getch