Abstract Motivated by localization problems such as cadastral maps refinements, we consider a generic Nonlinear Least Squares (NLS) problem of minimizing an aggregate squared fit across all nonlinear equations (measurements) with respect to the set of unknowns, e.g., coordinates of the unknown points’ locations. In a number of scenarios, NLS problems exhibit a nearly-separable structure: the set of measurements can be partitioned into disjoint groups (blocks), such that the unknowns that correspond to different blocks are only loosely coupled. We propose an efficient parallel method, termed Parallel Inexact Levenberg–Marquardt (PILM), to solve such generic large scale NLS problems. PILM builds upon the classical Levenberg–Marquard (LM) method, with a main novelty in that the nearly-block separable structure is leveraged in order to obtain a scalable parallel method. Therein, the problem-wide system of linear equations that needs to be solved at every LM iteration is tackled iteratively. At each (inner) iteration, the block-wise systems of linear equations are solved in parallel, while the problem-wide system is then handled via sparse, inexpensive inter-block communication. We establish strong convergence guarantees of PILM that are analogous to those of the classical LM; provide PILM implementation in a master-worker parallel computational environment; and demonstrate its efficiency on huge scale cadastral map refinement problems.

Abstract We consider strongly convex distributed consensus optimization over connected networks. EFIX, the proposed method, is derived using quadratic penalty approach. In more detail, we use the standard reformulation—transforming the original problem into a constrained problem in a higher dimensional space—to define a sequence of suitable quadratic penalty subproblems with increasing penalty parameters. For quadratic objectives, the corresponding sequence consists of quadratic penalty subproblems. For generic strongly convex case, the objective function is approximated with a quadratic model and hence the sequence of the resulting penalty subproblems is again quadratic. EFIX is then derived by solving each of the quadratic penalty subproblems via a fixed point (R)-linear solver, e.g., Jacobi Over-Relaxation method. The exact convergence is proved as well as the worst case complexity of order $${{\mathcal {O}}}(\epsilon ^{-1})$$ O ( ϵ - 1 ) for the quadratic case. In the case of strongly convex generic functions, the standard result for penalty methods is obtained. Numerical results indicate that the method is highly competitive with state-of-the-art exact first order methods, requires smaller computational and communication effort, and is robust to the choice of algorithm parameters.