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.
Revised:
Accepted:
Published online:
Eyal Gur 1; Shoham Sabach 1
CC-BY 4.0
@article{OJMO_2025__6__A7_0,
author = {Eyal Gur and Shoham Sabach},
title = {Network {Localization} and {Multi-Dimensional} {Scaling:} {Escaping} {Saddles} and a {Local} {Optimality} {Condition}},
journal = {Open Journal of Mathematical Optimization},
eid = {6},
pages = {1--18},
publisher = {Universit\'e de Montpellier},
volume = {6},
year = {2025},
doi = {10.5802/ojmo.42},
language = {en},
url = {https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.42/}
}
TY - JOUR AU - Eyal Gur AU - Shoham Sabach TI - Network Localization and Multi-Dimensional Scaling: Escaping Saddles and a Local Optimality Condition JO - Open Journal of Mathematical Optimization PY - 2025 SP - 1 EP - 18 VL - 6 PB - Université de Montpellier UR - https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.42/ DO - 10.5802/ojmo.42 LA - en ID - OJMO_2025__6__A7_0 ER -
%0 Journal Article %A Eyal Gur %A Shoham Sabach %T Network Localization and Multi-Dimensional Scaling: Escaping Saddles and a Local Optimality Condition %J Open Journal of Mathematical Optimization %D 2025 %P 1-18 %V 6 %I Université de Montpellier %U https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.42/ %R 10.5802/ojmo.42 %G en %F OJMO_2025__6__A7_0
Eyal Gur; Shoham Sabach. Network Localization and Multi-Dimensional Scaling: Escaping Saddles and a Local Optimality Condition. Open Journal of Mathematical Optimization, Volume 6 (2025), article no. 6, 18 p. doi : 10.5802/ojmo.42. https://ojmo.centre-mersenne.org/articles/10.5802/ojmo.42/
[1] Global minimizers, strict and non-strict saddle points, and implicit regularization for deep linear neural networks (2021) (https://hal.science/hal-03299887)
[2] The loss landscape of deep linear neural networks: a second-order analysis, J. Mach. Learn. Res., Volume 25 (2024) no. 242, pp. 1-76 | MR
[3] The Art of Wireless Sensor Networks. Volume 1: Fundamentals, Springer, 2014 | DOI
[4] On the convergence of the proximal algorithm for nonsmooth functions involving analytic features, Math. Program., Volume 116 (2009) no. 1-2, pp. 5-16 | DOI | MR | Zbl
[5] Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward–backward splitting, and regularized Gauss–Seidel methods, Math. Program., Volume 137 (2013) no. 1-2, pp. 91-129 | DOI | MR | Zbl
[6] Introduction to Nonlinear Optimization: Theory, Algorithms, and Applications with MATLAB, MOS-SIAM Series on Optimization, 19, Society for Industrial and Applied Mathematics, 2014 | DOI | MR | Zbl
[7] First-Order Methods in Optimization, MOS-SIAM Series on Optimization, 25, Society for Industrial and Applied Mathematics, 2017 | DOI | Numdam | MR | Zbl
[8] On the convergence to stationary points of deterministic and randomized feasible descent directions methods, SIAM J. Optim., Volume 30 (2020) no. 1, pp. 56-79 | DOI | MR | Zbl
[9] Exact and approximate solutions of source localization problems, IEEE Trans. Signal Process., Volume 56 (2008) no. 5, pp. 1770-1778 | DOI | MR | Zbl
[10] Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., Volume 146 (2014) no. 1-2, pp. 459-494 | DOI | Zbl
[11] Exploiting negative curvature in deterministic and stochastic optimization, Math. Program., Volume 176 (2019), pp. 69-94 | DOI | MR | Zbl
[12] An overview of dense eigenvalue solvers for distributed memory systems, 2021 44th International Convention on Information, Communication and Electronic Technology (MIPRO), IEEE (2021), pp. 265-271 | DOI
[13] Applications of Convex Analysis to Multidimensional Scaling, Recent Developments in Statistics, North-Holland, 1977, pp. 133-145
[14] Multidimensional Scaling using majorization: SMACOF in R, J. Stat. Softw., Volume 31 (2009) no. 3, pp. 1-30 | DOI
[15] The numerics of phase retrieval, Acta Numer., Volume 29 (2020), pp. 125-228 | DOI | MR | Zbl
[16] Escaping from saddle points—online stochastic gradient for tensor decomposition, Conference on learning theory, PMLR, 2015, pp. 797-842
[17] Matrix computations, Johns Hopkins Studies in the Mathematical Sciences, The Johns Hopkins University Press, 2013 | DOI | MR
[18] Direct, fast and convergent solvers for the non-convex and non-smooth TDoA localization problem, Digital Signal Process., Volume 139 (2023), 104074
[19] Alternating minimization based first-order method for the wireless sensor network localization problem, IEEE Trans. Signal Process., Volume 68 (2020), pp. 6418-6431 | MR | Zbl
[20] Distributed estimation of all the eigenvalues and eigenvectors of matrices associated with strongly connected digraphs, IEEE Control Sys. Lett., Volume 1 (2017) no. 2, pp. 328-333 | DOI | MR
[21] Matrix Analysis, Cambridge University Press, 2012 | DOI | MR
[22] How to escape saddle points efficiently, International conference on machine learning, PMLR, 2017, pp. 1724-1732
[23] Efficient Saddle Point Evasion and Local Minima Escape in High-Dimensional Non-Convex Optimization (2024) | arXiv
[24] DC programming and DCA: thirty years of developments, Math. Program., Volume 169 (2018) no. 1, pp. 5-68 | DOI | MR | Zbl
[25] First-order methods almost always avoid strict saddle points, Math. Program., Volume 176 (2019), pp. 311-337 | MR | Zbl
[26] A simple globally convergent algorithm for the nonsmooth nonconvex single source localization problem, J. Glob. Optim., Volume 69 (2017) no. 4, pp. 889-909 | DOI | MR | Zbl
[27] Variational Analysis and Generalized Differentiation I: Basic Theory, Grundlehren der Mathematischen Wissenschaften, 330, Springer, 2006 | MR | Zbl
[28] Linear and nonlinear inverse problems with practical applications, Society for Industrial and Applied Mathematics, 2012 | DOI | MR | Zbl
[29] Computing B-stationary points of nonsmooth DC programs, Math. Oper. Res., Volume 42 (2017) no. 1, pp. 95-118 | DOI | MR | Zbl
[30] Alternating DC algorithm for partial DC programming problems, J. Glob. Optim., Volume 82 (2022) no. 4, pp. 897-928 | DOI | MR | Zbl
[31] Cooperative localization in WSNs: A hybrid convex/nonconvex solution, IEEE Trans. Signal Inf. Process. Networks, Volume 4 (2018) no. 1, pp. 162-172 | MR
[32] Numerical methods for large eigenvalue problems: revised edition, Society for Industrial and Applied Mathematics, 2011 | DOI | MR | Zbl
[33] Distributed wireless sensor network localization via sequential greedy optimization algorithm, IEEE Trans. Signal Process., Volume 58 (2010) no. 6, pp. 3328-3340 | MR | Zbl
[34] et al. Algorithms for solving a class of nonconvex optimization problems. Methods of subgradients, Fermat days 85: Mathematics for optimization (North-Holland Mathematics Studies), Volume 129, North-Holland, 1986, pp. 249-271 | Zbl
[35] Duality in DC (difference of convex functions) optimization. Subgradient methods, Trends in Mathematical Optimization: 4th French-German Conference on Optimization (International Series of Numerical Mathematics/Internationale), Volume 84, Springer, 1988, pp. 277-293 | DOI | Zbl
[36] Inverse, shifted inverse, and Rayleigh quotient iteration as Newton’s method, SIAM Rev., Volume 60 (2018) no. 1, pp. 3-55 | DOI | MR | Zbl
[37] The phase retrieval problem, IEEE Trans. Antennas Propag., Volume 29 (1981) no. 2, pp. 386-391 | DOI
[38] Geometric structure of high-dimensional data and dimensionality reduction, Springer, 2012 | DOI | MR | Zbl
[39] A DC programming approach for sensor network localization with uncertainties in anchor positions, J. Ind. Manag. Optim., Volume 10 (2014) no. 3, pp. 817-826 | MR | Zbl
[40] The Loss Landscape of Shallow ReLU-like Neural Networks: Stationary Points, Saddle Escaping, and Network Embedding (2024) | arXiv
[41] The global optimization geometry of shallow linear neural networks, J. Math. Imaging Vis., Volume 62 (2019) no. 3, pp. 279-292 | DOI | MR | Zbl
Cited by Sources: