Sum of euclidean norms with box constraints

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} \quad A_i \in R^{2 \times k})$ 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.

If performance is not a big concern, just cast your problem in this form:

$min_q \sum_{i=1}^n t_i\\ \quad t\geq ||A_i q - b_i||_2,\quad i=i,\ldots,n\\ \quad q_j \in [0,1] \quad j=1,\ldots,k$

then make one more transformation and cast the problem as

$min_q \sum_{i=1}^n t_i\\ \quad (t, A_i q - b_i) \in Q,\quad i=i,\ldots,n\\ \quad q_j \in [0,1] \quad j=1,\ldots,k$

where $Q$ is the second order cone. Not all solver accept this form. For more details you can take a look to

http://docs.mosek.com/generic/modeling-a4.pdf

You can solve using open-source one as CVX or YALMIP. They all use polynomial time algorithms, though maybe not the most efficient one, being them quite generic. If you need more low level interfaces look at MOSEK (commercial but free for academics).

Specialized algorithms are mostly likely faster, but you must implement them and often it takes a while to make them work reliably.