производительность — Нахождение оптимального решения системы линейных уравнений в Stack Overflow
Вот проблема:
В настоящее время я пытаюсь создать систему управления, которая должна найти решение ряда сложных линейных уравнений без единственного решения.
Моя проблема возникает потому, что когда-либо будет только шесть уравнений, в то время как может быть свыше 20 неизвестных (обычно более шести неизвестных). Конечно, это не даст точного решения посредством стандартного исключения Гаусса или путем изменения их в матрице в уменьшенном виде ряда строк.
Тем не менее, я думаю, что я смогу оптимизировать ситуацию и получить более точное решение, потому что я знаю, что каждое из неизвестных не может иметь значение меньше нуля или больше единицы, но оно может свободно принимать любое значение между их.
Конечно, я пытаюсь создать код, который нашел бы правильное решение, но в случае, когда есть несколько комбинаций, которые дают удовлетворительные результаты, я бы хотел минимизировать Sum of (value of unknown * efficiency constant) over all unknownsто есть Сигма [хя* ея] от I = 0 до n, но поиск точного решения имеет больший приоритет.
Производительность также важна, потому что этот алгоритм может потребоваться запускать несколько раз в секунду.
Итак, есть ли у кого-нибудь идеи, чтобы помочь мне в реализации этого?
Решение
Изменить: Возможно, вы просто захотите придерживаться линейного программирования с ограничениями равенства и неравенства, но вот интересное точное решение, которое не включает ограничение, что ваши неизвестные находятся между 0 и 1.
Вот powerpoint, обсуждающий вашу проблему: http://see.stanford.edu/materials/lsoeldsee263/08-min-norm.pdf
Я переведу вашу задачу в математику, чтобы вам было легче разобраться:
у вас есть матрица A размером 6×20 и вектор x с 20 элементами. Вы хотите минимизировать (x ^ T) e при условии Ax = y. Согласно слайдам, если вы просто минимизировали сумму x, то ответ будет A ^ T (AA ^ T) ^ (- 1) y. Я еще раз посмотрю на это, как только у меня появится шанс, и посмотрю, каково решение минимизации (x ^ T) e (т.е. вашей конкретной проблемы).
Редактировать: я посмотрел в powerpoint еще немного, и ближе к концу есть слайд, озаглавленный «Общая минимизация норм с ограничениями равенства». Я собираюсь изменить обозначения, чтобы соответствовать слайду:
Ваша проблема в том, что вы хотите минимизировать || Ax-b ||, где b = 0 и A — ваш вектор e, а x — 20 неизвестных. Это зависит от Cx = d. Видимо ответ:
x = (A ^ TA) ^ — 1 (A ^ T b -C ^ T (C (A ^ TA) ^ — 1 C ^ T) ^ — 1 (C (A ^ TA) ^ — 1 A ^ Tb — г))
это не красиво, но не так плохо, как вы думаете. Там действительно не так много расчетов. Например, (A ^ TA) ^ — 1 нужно рассчитать только один раз, и тогда вы сможете повторно использовать ответ. И ваши матрицы не такие большие.
Обратите внимание, что я не включил ограничение, что элементы x находятся в пределах [0,1].
Другие решения
Похоже, что решение для того, что я делаю, с помощью линейного программирования. Он начинает возвращаться ко мне, но если у меня возникнут другие проблемы, я опубликую их в своих собственных специальных вопросах, вместо того чтобы превращать это в энциклопедию.
detector