Jump to content

    
Sign in to follow this  
getch

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

Recommended Posts

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

 

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

 

Определена такая функция для любого вектора: 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 by getch

Share this post


Link to post
Share on other sites
это векторные произведения?

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

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

Vi - вектора.

 

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

Edited by getch

Share this post


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

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

 

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

Share this post


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

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

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

Edited by getch

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

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

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

Edited by getch

Share this post


Link to post
Share on other sites
Нужно найти вектор 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.

Share this post


Link to post
Share on other sites
Может ошибаюсь но для квадратичной 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 не обязательны?

 

Share this post


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

 

Если переписать матрицу 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 by getch

Share this post


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

 

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

 

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

Share this post


Link to post
Share on other sites

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

 

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

Share this post


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

 

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

 

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

 

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

 

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

Edited by getch

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

Sign in to follow this