A conic formulation for $l_p$-norm optimization

François Glineur (Francois.Glineurfpms.ac.be)
Tamás Terlaky (terlakycas.mcmaster.ca)

Abstract: 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.

Keywords: convex optimization, conic optimization, $l_p$-norm optimization

Category 1: Convex and Nonsmooth Optimization (Convex Optimization )

Category 2: Linear, Cone and Semidefinite Programming (Other )

Citation: IMAGE0005, Service MATHRO, Faculté Polytechnique de Mons, Mons, Belgium, May/00

Download: [Compressed Postscript]

Entry Submitted: 03/08/2001
Entry Accepted: 03/08/2001
Entry Last Modified: 03/08/2001

Modify/Update this entry