A smoothing newton method for minimizing a sum of Euclidean norms

Liqun Qi, Guanglu Zhou

Research output: Journal article publicationJournal articleAcademic researchpeer-review

24 Citations (Scopus)

Abstract

We consider the problem of minimizing a sum of Euclidean norms, f(cursive Greek chi) = ∑mi=1 ∥bi-ATi cursive Greek chi∥. This problem is a nonsmooth problem because f is not differentiable at a point cursive Greek chi when one of the norms is zero. In this paper we present a smoothing Newton method for this problem by applying the smoothing Newton method proposed by Qi, Sun, and Zhou [Math. Programming, 87 (2000), pp. 1-35] directly to a system of strongly semismooth equations derived from primal and dual feasibility and a complementarity condition. This method is globally and quadratically convergent. As applications to this problem, smoothing Newton methods are presented for the Euclidean facilities location problem and the Steiner minimal tree problem under a given topology. Preliminary numerical results indicate that this method is extremely promising.
Original languageEnglish
Pages (from-to)389-410
Number of pages22
JournalSIAM Journal on Optimization
Volume11
Issue number2
DOIs
Publication statusPublished - 1 Jan 2000

Keywords

  • Euclidean facilities location
  • Semismoothness
  • Shortest networks
  • Smoothing Newton method
  • Steiner minimum trees
  • Sum of norms

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Software

Cite this