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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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


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


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

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

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

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

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

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

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

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

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

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

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

Очевидно, что любое линейное

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

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


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

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

Я запомнил данный Вами замечательный итерационный алгоритм нахождения собственного вектора, соответствующего максимальному собственному значению матрицы. Поэтому данная ранее перефломулировка задачи через матрицу 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

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