An entropy regularization technique for minimizing a sum of Tchebycheff norms

• Autores: Suyan He, Yuxi Jiang, Shaohua Pan
• Localización: Applied numerical mathematics, ISSN-e 0168-9274, Vol. 60, Nº. 3, 2010, págs. 208-223
• Idioma: inglés
• DOI: 10.1016/j.apnum.2009.11.005
• Texto completo no disponible (Saber más ...)
• Resumen

  • In this paper, we consider the problem of minimizing a sum of Tchebycheff norms View the MathML source, where View the MathML source and View the MathML source. 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 epsilon (Porson)-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 mmuch greater-thanmax{n,d}.