What is the difference between Annealing and Homotopy in global optimization?

What do you mean exactly by deterministic annealing? Fully deterministic (including state updates, and if so, how?), or just the temperature schedule?

At a high level, I would say that the main difference between homotopy and annealing, besides the fact they use gradient differently (homotopy uses a full gradient with respect to the joint (parameter,'temperature') to track the solution to a fixed-point equation, annealing, if it uses the gradient at all, would use it to "approximately minimize"/sample an energy function, probably at fixed temperature), is that, at least in simulated annealing, you can often theoretically get to the desired solution by only cooling (although slowly enough).

On the other hand, the homotopy parameter alpha (which, roughly speaking, plays the role of an inverse temperature), may need to alternatively decrease and increase to guarantee convergence to the desired solution. More precisely, the homotopy argument will often guarantee the existence of a curve from (trivial-solution,alpha=0) to (desired-solution,alpha=1), but this curve may go sometimes in the direction of decreasing alpha - see http://uai.sis.pitt.edu/papers/02/p111-corduneanu.pdf figure 2 for a picture).

I am not sure how fully deterministic annealing would get around the need to 'reheat' the system to get to the optimal solution (in the absence of extra structure), but I think a 'naive approach' (alternate between slightly decreasing temperature and using current parameters as initialization to a local optimization) can definitely be made to fail.