An efficient algorithm for minimizing a sum of p-norms

We study the problem of minimizing a sum of p-norms where p is a fixed real number in the interval [1, infinity]. Several practical algorithms have be en proposed to solve this problem. However, none of them has a known polyno mial time complexity. In this paper, we transform the problem into standard conic form. Unlike those in most convex optimization problems, the cone fo r the p-norm problem is not self-dual unless p = 2. Nevertheless, we are ab le to construct two logarithmically homogeneous self-concordant barrier fun ctions for this problem. The barrier parameter of the first barrier functio n does not depend on p. The barrier parameter of the second barrier functio n increases with p. Using both barrier functions, we present a primal-dual potential reduction algorithm to compute an epsilon-optimal solution in pol ynomial time that is independent of p. Computational experiences with a Mat lab implementation are also reported.