Решение задачи наименьших квадратов с линейными ограничениями в Python

Мне нужно решить

\begin{aligned} min_{x} ‖ A x - b ‖_{2}^{2}, \\ s . t . & \sum_{i} x_{i} = 1, \\ x_{i} \geq 0, \forall i . \end{aligned}

$\begin{alignat}{1} & \min_{x}\|Ax - b\|^2_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat}$

Я думаю, что это квадратичная проблема, которая должна быть решена с помощью CVXOPT , но я не могу понять, как.

optimization python convex-optimization least-squares quadratic-programming tillsten
источник

Я надеюсь, что этот вопрос не слишком специфичен для compsci.

Tillsten

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

Tillsten

Кстати, другие правки великолепны!

Tillsten

Вы можете легко решить эту проблему с помощью собственного кода очень эффективным способом. Нет необходимости в CVXOPT.

Рой

Ответы:

Я написал полный ответ (ниже строки), прежде чем обнаружил CVXPY , который (как и CVX для MATLAB) делает всю сложную работу за вас и имеет очень короткий пример, почти идентичный вашему здесь . Вам нужно только заменить соответствующую строку на

 p = program(minimize(norm2(A*x-b)),[equals(sum(x),1),geq(x,0)])

Мой старый ответ, делать это сложнее с CVXOPT:

Следуя предложению Джеффа возвести в квадрат вашу целевую функцию,

‖ A x - b ‖_{2}^{2} = ⟨ x^{T} A^{T} - b^{T}, A x - b ⟩ = x^{T} A^{T} A x - b^{T} A x - x^{T} A b - b^{T} b

$\|Ax-b\|^2_2 = \langle x^TA^T - b^T,Ax-b\rangle = x^TA^TAx - b^TAx - x^TAb - b^Tb$

Конечно, все термины являются скалярами, так что вы можете транспонировать третий и отбросить последний (так как он не зависит от и, следовательно, не изменится, какой дает вам минимум, хотя вам нужно будет добавить его обратно в после решения, чтобы получить правильное значение вашей цели), чтобы получить Это (включая ваши ограничения) имеет форму квадратичной программы, как указано в документация CVXOPT здесь , где также есть пример кода для решения такой проблемы. $x$ $x$

x^{T} A^{T} A x - b^{T} (A + A^{T}) x

$x^TA^TAx - b^T(A + A^T)x$

Дэвид Кетчесон
источник

Вместо того, чтобы решить проблему, решите

\begin{aligned} min_{x} ‖ A x - b ‖_{2}^{2}, \\ s . t . & \sum_{i} x_{i} = 1, \\ x_{i} \geq 0, \forall i . \end{aligned}

$\begin{alignat}{1} & \min_{x}\|Ax - b\|^{2}_{2}, \\ \mathrm{s.t.} & \quad\sum_{i}x_{i} = 1, \\ & \quad x_{i} \geq 0, \quad \forall{i}. \end{alignat}$

Эта проблема представляет собой дифференцируемую выпуклую нелинейную задачу оптимизации, которая может быть решена в CVXOPT, IPOPT или любом другом решении выпуклой оптимизации.

Джефф Оксберри
источник