##
An Efficient Algorithm for Minimizing a Sum of P-Norms

###
Guoliang Xue and Yinyu Ye

We study the problem of minimizing a sum of $p$-norms
where $p$ is a fixed real number in the interval
$[1, \infty]$. Several practical algorithms have been
proposed to solve this problem.
However, none of them has a known polynomial time
complexity. In this paper, we transform the problem
into standard conic form. Unlike those in most convex
optimization problems, the cone for the $p$-norm
problem is {\em not} self-dual unless $p=2$.
Nevertheless, we are able to construct two
logarithmically homogeneous self-concordant barrier
functions for this problem. The barrier parameter of
the first barrier function does not depend on $p$.
The barrier parameter of the second barrier function
increases with $p$. Using both barrier functions,
we present a primal-dual potential reduction
algorithm to compute an $\epsilon$-optimal solution
in polynomial time that is independent of $p$.
Computational experiences of a Matlab implementation
are also reported.
Working Paper, Department of Computer Science,
The University of Vermont, Burlington, VT 05405-0156.

Contact: yinyu-ye@uiowa.edu