Optimization Online


Iterative Minimization Schemes for Solving the Single Source Localization Problem

Amir Beck(becka***at***ie.technion.ac.il)
Marc Teboulle(teboulle***at***post.tau.ac.il)
Zahar Chikishev(nosound***at***tx.technion.ac.il)

Abstract: We consider the problem of locating a single radiating source from several noisy measurements using a maximum likelihood (ML) criteria. The resulting optimization problem is nonconvex and nonsmooth and thus finding its global solution is in principal a hard task. Exploiting the special structure of the objective function, we introduce and analyze two iterative schemes for solving this problem. The first algorithm is a very simple explicit fixed-point-based formula, and the second is based on solving at each iteration a nonlinear least squares problem which can be solved globally and efficiently after transforming it into and equivalent quadratic minimization problem with a single quadratic constraint. We show that the nonsmoothness of the problem can be avoided by choosing a specific "good" starting point for both algorithms, and we prove the convergence of the two schemes to stationary points. We present empirical results that support the underlying theoretical analysis and suggest that despite of its nonconvexity, the ML problem can effectively be solved globally using the devised schemes.

Keywords: Single source location problem, Weiszfield algorithm, nonsmooth and nonconvex minimization, fixed point methods, nonlinear least squares, generalized trust region, semidefinite relaxation.

Category 1: Nonlinear Optimization (Unconstrained Optimization )

Category 2: Global Optimization (Theory )

Category 3: Applications -- Science and Engineering (Other )

Citation: Technical Report IE/OR-2007-05, Department of Industrial Engineering and Management, Technion - Israel Institute of Technology, Haifa 32000, Israel.

Download: [PDF]

Entry Submitted: 07/23/2007
Entry Accepted: 07/23/2007
Entry Last Modified: 07/23/2007

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Programming Society