How to solve $Ax = b$ using Simulated Annealing?

Question

I have an idea how the Simulated-Annealing algorithm works w/ TSP, but I have no idea how to solve $Ax = b$, given an $n \times n$ matrix $A$ and a vector $b$. I know that it might sound stupid, but I really need some help.

Answer 1

It works the same way as for the traveling salesman problem. Start with any candidate solution $x$ and

1. Generate a new possible value for $x$
2. Transition to the new value with a probability determined by the relative cost of the new value to the old and the temperature.
3. Repeat 1 and 2 while gradually lowering the temperature.

We just need to determine a good cost function and a method of generating new candidate solutions.

The cost function is easy... how about $|Ax-b|$ or $(Ax-b)^2$?

As for how to generate a new candidate, how about perturbing a randomly chosen component by a normal with some small standard deviation?

For the way to choose the acceptance probability as a function of relative cost and temperature, you can probably use the same system as you did for TSP.

There is an issue here cause unlike the TSP this is a continuum problem, so you need to take care to make sure the size of the step to the next trial solution are small enough (it should decrease with time).

This is a silly way to solve this problem... there's no advantage to the temperature noise here since the problem is convex (no local minima).