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, 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 this cone. Using convex conic duality and our knowledge about this cone, 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.
Citation
IMAGE0005, Service MATHRO, Facult▒ Polytechnique de Mons, Mons, Belgium, May/00