A CONIC FORMULATION FOR L_P-NORM OPTIMIZATION

In this paper, we formulate the l_p-norm optimization problem as a conic
optimization problem, derive its standard duality properties and show it can
be solved in polynomial time.

We first define an ad hoc closed convex cone PC, study its properties and
derive its dual. This allows us to express the standard l_p-norm optimization
primal problem as a conic problem involving PC. Using convex conic duality and
our knowledge about PC, we proceed to derive the dual of this problem and
prove the well-known regularity properties of this primal-dual pair, i.e. zero
duality gap and primal attainment. Finally, we prove that the class of
l_p-norm optimization of problems can be solved up to a given accuracy in
polynomial time, using the framework of interior-point algorithms and
self-concordant barriers.