Tag Archives: Nonlinear Optimization

Variation of the Newton-Rhapson algorithm that copes with noise, with some illustrative applications such as robotics

October 6, 2023 09:05 ,

D. Fu et al. Modified Newton Integration Algorithm With Noise Tolerance Applied to Robotics, IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 52, no. 4, pp. 2134-2144 DOI: 10.1109/TSMC.2021.3049386.

Currently, the Newton\u2013Raphson iterative algorithm has been extensively employed in the fields of basic research and engineering. However, when noise components exist in a system, its performance is largely affected. To remedy shortcomings that the conventional computing methods have encountered in a noisy workspace, a novel modified Newton integration (MNI) algorithm is proposed in this article. In addition, the steady-state error of the proposed MNI algorithm is smaller than that of the Newton\u2013Raphson algorithm under a noise-free or noisy workspace. To lay the foundations for the corresponding theoretical analyses, the proposed MNI algorithm is first converted into a homogeneous linear equation with a residual term. Then, the related theoretical analyses are carried out, which indicate that the MNI algorithm possesses noise-tolerance ability under various noisy environments. Finally, multiple computer simulations and physical experiments on robot control applications are performed to verify the feasibility and advantage of the proposed MNI algorithm.

Posted in: Mathematics , Tagged: ,

A new pose-graph optimization algorithm for SLAM and other problems whose, through a formulation as global optimization in SE(3), results are certifiable and more robust than standard approaches, and a curious relation between this problem and the clock synchronization problem

March 6, 2019 17:53 ,

Rosen, D. M., Carlone, L., Bandeira, A. S., & Leonard, J. J., SE-Sync: A certifiably correct algorithm for synchronization over the special Euclidean group, The International Journal of Robotics Research, 38(2–3), 95–125, 2019 DOI: 10.1177/0278364918784361.

Many important geometric estimation problems naturally take the form of synchronization over the special Euclidean group: estimate the values of a set of unknown group elements x1,…,xn∈SE(d) given noisy measurements of a subset of their pairwise relative transforms x−1ixj. Examples of this class include the foundational problems of pose-graph simultaneous localization and mapping (SLAM) (in robotics), camera motion estimation (in computer vision), and sensor network localization (in distributed sensing), among others. This inference problem is typically formulated as a non-convex maximum-likelihood estimation that is computationally hard to solve in general. Nevertheless, in this paper we present an algorithm that is able to efficiently recover certifiably globally optimal solutions of the special Euclidean synchronization problem in a non-adversarial noise regime. The crux of our approach is the development of a semidefinite relaxation of the maximum-likelihood estimation (MLE) whose minimizer provides an exact maximum-likelihood estimate so long as the magnitude of the noise corrupting the available measurements falls below a certain critical threshold; furthermore, whenever exactness obtains, it is possible to verify this fact a posteriori, thereby certifying the optimality of the recovered estimate. We develop a specialized optimization scheme for solving large-scale instances of this semidefinite relaxation by exploiting its low-rank, geometric, and graph-theoretic structure to reduce it to an equivalent optimization problem defined on a low-dimensional Riemannian manifold, and then design a Riemannian truncated-Newton trust-region method to solve this reduction efficiently. Finally, we combine this fast optimization approach with a simple rounding procedure to produce our algorithm, SE-Sync. Experimental evaluation on a variety of simulated and real-world pose-graph SLAM datasets shows that SE-Sync is capable of recovering certifiably globally optimal solutions when the available measurements are corrupted by noise up to an order of magnitude greater than that typically encountered in robotics and computer vision applications, and does so significantly faster than the Gauss–Newton-based approach that forms the basis of current state-of-the-art techniques.

Posted in: Mobile robot SLAM , Tagged: , ,

A new method for nonlinear optimization aimed to embedded computers, and a nice state of the art of that problem

December 7, 2017 09:08 ,

N. Y. Chiang, R. Huang and V. M. Zavala, An Augmented Lagrangian Filter Method for Real-Time Embedded Optimization, IEEE Transactions on Automatic Control, vol. 62, no. 12, pp. 6110-6121, DOI: 10.1109/TAC.2017.2694806.

We present a filter line-search algorithm for nonconvex continuous optimization that combines an augmented Lagrangian function and a constraint violation metric to accept and reject steps. The approach is motivated by real-time optimization applications that need to be executed on embedded computing platforms with limited memory and processor speeds. The proposed method enables primal-dual regularization of the linear algebra system that in turn permits the use of solution strategies with lower computing overheads. We prove that the proposed algorithm is globally convergent and we demonstrate the developments using a nonconvex real-time optimization application for a building heating, ventilation, and air conditioning system. Our numerical tests are performed on a standard processor and on an embedded platform. We demonstrate that the approach reduces solution times by a factor of over 1000.

Posted in: Mathematics, Real-Time Systems , Tagged: ,