minimizing the sum of euclidean norms with box constraints
I am a graduate student in computer science, making a thesis on uncertainty geometry. During my thesis I came across the following optimization problem:
$q \in R^k$ and $\forall {1 \leq i \leq n} A_i \in R^{2xn})$ and $b_i \in R^2$
Target: min $\sum_{i=1}^n ||A_iq-b_i||_2$
Subject to constrains: $\forall 1 \leq j \leq k \hspace {10 mm} 0 \leq q_{j} \leq 1$
To finish my work I need to find a solution (exact or close to Epsilon arbitrarily small) in polynomial time complexity. Are there any solutions to this problem which have already appeared in previous articles, or is this still an open problem in optimization?
I found some articles that gave numerical solutions for the problem but without explicit definition of run time complexity:
2007 - A quadratically convergent method for minimizing a sum of euclidean norms.
2001 - Semismooth newton methods for Minimizing a Sum of Euclidean Norms with linear constraints.
2000 - A Smoothing Newton Method for Minimizing a Sum of Euclidean Norms.
1995 - A newton barrier method for minimizing a sum of euclidean norms subject to linear equality constraints.
And other articles that solve Similar problems but none of them fits my case (box constrains):
2006 - Smoothing techniques in euclidean jordan algebras.
2000 - An efficient primal dual interior point method for minimizing a sum of euclidean norms.
1998 - A newton acceleration of the weiszfeld algorithm for minimizing the sum of euclidean distances.
1997 - A primal dual algorithm for minimizing a sum of euclidean norms.
1995 - symmetric primal dual newton methods for minimizing a sum of norms.
The two articles:
2000 - An efficient algorithm for minimizing a sum of p-norms.
1997 - An efficient algorithm for minimizing a sum of euclidean norms with applications.
Gave polynomial time solution(close to Epsilon arbitrarily small) but for the unconstrained problem.
Please help me. links to articles with solutions are welcome.
