Network Localization and Multi-Dimensional Scaling: Escaping Saddles and a Local Optimality Condition

In this paper, we focus on a class of problems characterized by solving a non-linear least squares minimization, for approximating a norm of a linear transformation. These problems are characterized by their non-convex and non-smooth nature, presenting challenges in finding (locally) optimal solutions. While existing optimization algorithms mostly concentrate on finding critical points of the associated least squares objective function, these functions often possess multiple non-global local minima and saddle points. These problems find wide applications in various domains, and we focus our attention on two challenging problems: Wireless Sensor Network Localization and Multi-Dimensional Scaling. We establish that non-differentiable points correspond to maximum or saddle points, and we provide a constructive approach to determine descent directions at these points. Leveraging this, we propose a straightforward procedure to escape non-differentiable saddle points that is applicable in either centralized or distributed computational setting. Furthermore, we develop a necessary condition for differentiable points to be local minimizers, by exploiting the structure of the objective function of these problems.