An entropy regularization technique for minimizing a sum of Tchebycheff norms

In this paper, we consider the problem of minimizing a sum of Tchebycheff norms Φ ( x ) = ∑ i = 1 m ‖ b i − A i T x ‖ ∞ , where A i ∈ R n × d and b i ∈ R d . We derive a smooth approximation of Φ ( x ) by the entropy regularization technique, and convert the problem into a parametric family of strictly convex minimization. It turns out that the minimizers of these problems generate a trajectory that will go to the primal–dual solution set of the original problem as the parameter tends to zero. By this, we propose a smoothing algorithm to compute an ϵ-optimal primal–dual solution pair. The algorithm is globally convergent and has a quadratic rate of convergence. Numerical results are reported for a path-following version of the algorithm and made comparisons with those yielded by the primal–dual path-following interior point algorithm, which indicate that the proposed algorithm can yield the solutions with favorable accuracy and is comparable with the interior point method in terms of CPU time for those problems with m ≫ max { n , d } .