search

RobotLocomotion / drake

Model-based design and verification for robotics.
https://drake.mit.edu
Other
3.35k stars 1.27k forks source link

Parallelize the generic method for checking boundedness of a convex set. #22084

Closed cohnt closed 2 weeks ago

cohnt commented 3 weeks ago

The generic boundedness check iteratively tries to maximize or minimize the ith component of a vector in a set; a set is unbounded if any of these programs is unbounded. This can naturally be parallelized, which should lead to speedups for convex sets in high-dimensional spaces. (Note that this boundedness check is currently used by Spectrahedron and Intersection, so I've enabled parallelization in the test cases in those files.)

+@hongkai-dai for feature review, if you have the time?

(I've set the default behavior to not use parallelism, since for many cases, I expect the overhead of SolveInParallel will outweigh the speedup resulting from the parallelization. But I could be convinced the other way. @AlexandreAmice let me know if you have thoughts!)

This change is Reviewable

cohnt commented 3 weeks ago

+@sherm1 for platform review per the schedule, please

jwnimmer-tri commented 3 weeks ago

... we could write a proper par-for loop instead of trying to use a helper function with this impedance mismatch.

Indeed, thinking more about it now, the obvious solution is to create a pool N of programs (N is number of threads) and only ever call UpdateCoefficients inside of the par-for loop.

Also, isn't the complexity class of the program the same every time? I would think we want to GetAvailableSolvers on it up front (nixing Ipopt), creating N of the best solver ahead of time, and then just calling Solve on it directly. Doing the ChooseBestSolver logic each time seems wasteful.