Thanks for all the feedback people, I was hoping that there would be some kind of simple iterative algorithm (something like GJK) but it seems like I'm out of luck. I knew that the problem could probably be formulated as a LCP but unfortunately I don't think this will be feasible given the number of queries each frame.

Christer, I will look into the analytical solution but I think it will be hard and error prone to extract the intersection curves/points of the capsules.

I'm also toying with the idea of using some kind of Monte Carlo method to find the minimum but perhaps it's faster to just solve the LCP.

Thanks again

Andreas Brinck