getch 0 12 сентября, 2012 Опубликовано 12 сентября, 2012 (изменено) · Жалоба Приветствую всех! На данном форуме мне очень здорово когда-то помогли в решении некоторых задач. Поэтому решил еще раз обратиться к уважаемому сообществу с просьбой дать дельный совет/рекомендации, как подступиться к решению такой задачи: Определена такая функция для любого вектора: 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)), т.е. решением задачи является вектор коэффициентов, где один элемент равен ±единице, а остальные - нули. Возможно, кому-то известно решение схожей или частного случая этой задачи. Спасибо. Изменено 13 сентября, 2012 пользователем getch Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
DRUID3 0 12 сентября, 2012 Опубликовано 12 сентября, 2012 · Жалоба K1 * V1 это векторные произведения? Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
getch 0 12 сентября, 2012 Опубликовано 12 сентября, 2012 (изменено) · Жалоба это векторные произведения? Это произведение числа на вектор: Ki - вещественные числа. Vi - вектора. V[j] - j-й элемент вектора V. Изменено 13 сентября, 2012 пользователем getch Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
DRUID3 0 13 сентября, 2012 Опубликовано 13 сентября, 2012 · Жалоба Нужно найти вектор NewV = K1 * V1 + K2 * V2 + ... + Kn * Vn, где Sum(Abs(Ki)) = 1, либо Sum(Ki^2) = 1 значение F(NewV) которого было бы максимальным. Словами иными - есть набор векторов(? так, не коэффициентов вектора?) и из набора долей единицы(даже вернее из диапазона +/-1) нужно выбрать числа так что-бы сумма векторов была максимальной? На численно-оптимизационную задачу похоже. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
getch 0 13 сентября, 2012 Опубликовано 13 сентября, 2012 (изменено) · Жалоба Словами иными - есть набор векторов(? так, не коэффициентов вектора?) и из набора долей единицы(даже вернее из диапазона +/-1) нужно выбрать числа так что-бы сумма векторов была максимальной? Только максимизировать надо не саму сумму векторов, а определенную выше функцию F от этой суммы - F(K1 * V1 + ... + Kn * Vn). F - сумма модулей (или квадратов) разностей соседних элементов вектора. Изменено 13 сентября, 2012 пользователем getch Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
DRUID3 0 13 сентября, 2012 Опубликовано 13 сентября, 2012 · Жалоба А какая разница? Вот у Вас целевая функция. Вот вектор коэффициентов. Ну и вперед. Любой градиентный метод или модные сейчас генетические алгоритмы - последние без проблем параллелятся. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
getch 0 13 сентября, 2012 Опубликовано 13 сентября, 2012 (изменено) · Жалоба Понимаю, что решение в лоб всегда существует. В лоб - ГА, примененный к любой целевой функции. Естественно, о подходах к решению задачи спрашивал с другой целью - получить какие-то значительно более быстро-считающие варианты решения. Т.е. в идеале что-то близкое к аналитическому решению. Например, переход от огромной размерности векторов к существенно более компактной их ковариационной матрице. И далее работа уже с ней. Изменено 13 сентября, 2012 пользователем getch Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
DRUID3 0 13 сентября, 2012 Опубликовано 13 сентября, 2012 · Жалоба ...у каждого из которых сумма его элементов равна нулю... ах... я вот это пропустил, т.е. вектора не просто любые случайные... Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
getch 0 13 сентября, 2012 Опубликовано 13 сентября, 2012 · Жалоба Да, вектора относительно удобные для мат. аппарата, которым, к сожалению, владею крайне слабо. Поэтому и прошу помощи. Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
alex_os 0 14 сентября, 2012 Опубликовано 14 сентября, 2012 · Жалоба Нужно найти вектор 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 14 сентября, 2012 Опубликовано 14 сентября, 2012 · Жалоба Может ошибаюсь но для квадратичной 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 14 сентября, 2012 Опубликовано 14 сентября, 2012 (изменено) · Жалоба Подскажите, как выглядит матрица сдвига в данном случае? Вместо нее делал бы сдвиг индексов в самом алгоритме, но в выражении ниже ее надо и транспонировать и другое. Т.е. без явного вида не представляю, как обойтись. Если переписать матрицу 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), значит можно не гадать, как выглядит матрица-сдвига, а делать упомянутый выше сдвиг индексов в самом алгоритме. Скажите, нет ли ошибки в таких рассуждениях? Изменено 14 сентября, 2012 пользователем getch Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
fontp 0 15 сентября, 2012 Опубликовано 15 сентября, 2012 · Жалоба Если переписать матрицу 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 15 сентября, 2012 Опубликовано 15 сентября, 2012 · Жалоба Если нужен циклический сдвиг, то матрицу можно получить сдвигая единичную диагональ направо/налево циклически Условие нормированности k произойдет автоматически, если учесть что собственный вектор нормирован. А условие отсутствия постояннной составляющей действительно оказалось не при делах Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться
getch 0 18 сентября, 2012 Опубликовано 18 сентября, 2012 (изменено) · Жалоба Нет. А чтобы не гадать, матрица сдвига выглядит как единичная, только единицы НАД диагональю (или ПОД, зависит от направления сдвига). Матрица сдвига, конечно, получается огромной - NxN (N - количество элементов в исходном векторе Vi). Т.е. ее для перемножения использовать совсем нерезонно на практике. Проще алгоритмом сразу. Спасибо, задача теперь решена полностью. В выкладках заинтересовал такой нюанс, что если бы использовалась не матрица-сдвига, а матрица любого преобразования, то все равно не потребовалось бы ее искать. Достаточно лишь знать алгоритм преобразования. Выходит, эксплуатируется какое-то фундаментальное свойство, что любое преобразование можно задать умножением на соответствующую матрицу. Не очевидно совсем. Изменено 18 сентября, 2012 пользователем getch Цитата Поделиться сообщением Ссылка на сообщение Поделиться на другие сайты Поделиться