I recall playing with this general problem some time ago. The ad hoc scheme I came up with was to use an optimization that would vary the angle of the major axis, as well as the eccentricity of the ellipse. That yields a coordinate transformation to turn the problem into that of finding a minimum radius enclosing circle, which I have code to do. Given the circle and other parameters, recover the classic parameters of an ellipse.
The above scheme should work reasonably well, though developed without any search to see if the problem has been solved before. I'm sure it has.
I'd also suggest a search on the file exchange, as I think I recall seeing a minimum enclosing ellipse tool there. A quick search with the string "enclosing ellipse" finds this as a start:
There are probably others.