Solving the discrete lp-approximation problem by a method of centers

摘要

The discrete lp-approximation problem is a basic problem in approximation theory and optimization. This problem is normally solved by Newton-type methods which are complicated by the nondifferentiability of the gradient function for p∈[1,2). This paper discusses a scheme and its implementation for solving this problem by a method of analytic centers, which provides a unified treatment for all p⩾1 and has a polynomial bound of complexity. The original problem is reformulated as a constrained convex programming problem which admits a self-concordant logarithmic barrier. A special structure of the Newton system derived from minimizing the potential function is utilized to reduce the amount of computation. Some other implementation techniques are also presented. Computational results show that the method of centers is robust for all p.