Lifted homotopy continuation for global optimality in nonconvex optimization
Description
In progress (first author project with WPI & MIT).
We are focusing on solving non-convex optimization problems with disjoint subsets to global optimality. This is a famously hard problem in robotics, present in problems like bundle adjustment, motion planning around obstacles, multi-agent pathfinding, and planning with contact.
We are doing this by solving the optimization problem as a system of equations — solving the problem at potential active sets using "homotopy continuation". Naive application of similar algebraic geometry approaches like homotopy continuation to solve for minima of non-convex problems is intractable, as they are exponentially complex.
By careful analysis of these optimization problems, we are able to prove that they have special structure that allows us to drastically reduce the complexity of the problem, making large scale optimization (~6000 constraints, 25 variables) tractable. Current results show us outperforming GCS on cost and solving time, and solving min-acceleration problems with high degrees of continuity.
We are focusing on solving non-convex optimization problems with disjoint subsets to global optimality. This is a famously hard problem in robotics, present in problems like bundle adjustment, motion planning around obstacles, multi-agent pathfinding, and planning with contact.
We are doing this by solving the optimization problem as a system of equations — solving the problem at potential active sets using "homotopy continuation". Naive application of similar algebraic geometry approaches like homotopy continuation to solve for minima of non-convex problems is intractable, as they are exponentially complex.
By careful analysis of these optimization problems, we are able to prove that they have special structure that allows us to drastically reduce the complexity of the problem, making large scale optimization (~6000 constraints, 25 variables) tractable. Current results show us outperforming GCS on cost and solving time, and solving min-acceleration problems with high degrees of continuity.