  We consider the problem of mutually unbiased bases as a polynomial
optimization problem over the reals. We heavily reduce it using known
symmetries before exploring it using two methods, combining a number of
optimization techniques. The first of these is a search for bases using
Lagrange-multipliers that converges rapidly in case of MUB existence, whilst
the second combines a hierarchy of semidefinite programs with branch-and-bound
techniques to perform a global search. We demonstrate that such an algorithm
would eventually solve the open question regarding dimension 6 with finite
memory, although it still remains intractable. We explore the idea that to show
the inexistence of bases, it suffices to search for orthonormal vector sets of
certain smaller sizes, rather than full bases. We use our two methods to
conjecture the minimum set sizes required to show infeasibility, proving it for
dimensions 3. The fact that such sub-problems seem to also be infeasible
heavily reduces the number of variables, by 66\% in the case of the open
problem, potentially providing an large speedup for other algorithms and
bringing them into the realm of tractability.
