A smoothing Newton method or minimizing a sum of Euclidean norms

Authors
Citation
Lq. Qi et Gl. Zhou, A smoothing Newton method or minimizing a sum of Euclidean norms, SIAM J OPTI, 11(2), 2000, pp. 389-410
Citations number
38
Categorie Soggetti
Mathematics
Journal title
SIAM JOURNAL ON OPTIMIZATION
ISSN journal
10526234 → ACNP
Volume
11
Issue
2
Year of publication
2000
Pages
389 - 410
Database
ISI
SICI code
1052-6234(20001110)11:2<389:ASNMOM>2.0.ZU;2-V
Abstract
We consider the problem of minimizing a sum of Euclidean norms, f (x) = Sig ma (m)(i=1) \\b(i) - A(i)(T) x\\. This problem is a nonsmooth problem becau se f is not differentiable at a point x when one of the norms is zero. In t his paper we present a smoothing Newton method for this problem by applying the smoothing Newton method proposed by Qi, Sun, and Zhou [Math. Programmi ng, 87 (2000), pp. 1-35] directly to a system of strongly semismooth equati ons derived from primal and dual feasibility and a complementarity conditio n. This method is globally and quadratically convergent. As applications to this problem, smoothing Newton methods are presented for the Euclidean fac ilities location problem and the Steiner minimal tree problem under a given topology. Preliminary numerical results indicate that this method is extre mely promising.