Multiple Start Branch and Prune Filtering Algorithm for Nonconvex Optimization

Arun Srivatsan Rangaprasad and Howie Choset
Workshop Paper, The 12th International Workshop on The Algorithmic Foundations of Robotics, December, 2016

View Publication

Copyright notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. These works may not be reposted without the explicit permission of the copyright holder.


Automatic control systems, electronic circuit design, image registration, SLAM and several other engineering problems all require nonconvex optimization. Many approaches have been developed to carry out such nonconvex optimization, but they suff er drawbacks including large computation time, require tuning of multiple unintuitive parameters and are unable to fi nd multiple local/global minima. In this work we introduce multiple start branch and prune filtering algorithm (MSBP), a Kalman fi ltering-based method for solving nonconvex optimization problems. MSBP starts o with a number of initial state estimates, which are branched and pruned based on the state uncertainty and innovation respectively. We show that compared to popular methods used for solving nonconvex optimization problems, MSBP has fewer parameters to tune, making it easier to use. Through a case study of point set registration, we demonstrate the efficiency of MSBP in estimating multiple global minima, and show that MSBP is robust to initial estimation error in the presence of noise and incomplete data. The results are compared to other popular methods for nonconvex optimization using standard datasets. Overall MSBP o ffers a better success rate at fi nding the optimal solution with less computation time.


author = {Arun Srivatsan Rangaprasad and Howie Choset},
title = {Multiple Start Branch and Prune Filtering Algorithm for Nonconvex Optimization},
booktitle = {The 12th International Workshop on The Algorithmic Foundations of Robotics},
year = {2016},
month = {December},
publisher = {Springer},
} 2019-06-26T15:36:58-04:00