Local Search in Continuous Spaces (Russell Norvig)
As discussed in Russell Norvig Chapter 04: Searching Complex Environments
Introduction
The section gives a brief introduction to local search for continuous spaces. A continuous action space has an infinite branching factor, and thus can’t be handled by msot of the algorithms covered so far. The literature on this is vast, dating back to the development of calculus by Newton and Leibniz.
RN introduce continuous search with an example problem. Let us say that we want to place three new airports in a country, such that the sum of squared straight line distances from each city on the map to its nearest airport is minimized. The state space is then defined by the locations of the three airports, which can be expressed as \((x_1,y_1),(x_2,y_2),(x_3,y_3)\). This is a six-dimensional space, states are defined by six variables. Moving around in this space corresponds to moving the airports. We can define the objective function easily if we have the set of cities closet to each airport. Let \(C_i\) be the set of cities closest to the airport i in the state x. Then the function is clearly:
\(f(x) = f(x_1,y_1,x_2,y_2,x_3,y_3) = \sum^{3}_{i=1} \sum_{c \in C_i} (x_i - x_c)^2 + (y_i - y_c)^2\)
But this equation does not work globally, if we move to far from state x by moving one of the airports such that the set of closest cities changes, then we need to recompute the sets.
Discretization and Random Sampling
How do we deal with such a continuous state space? One option is to discretize it, dividing up the space into grids of size \(\delta\). Then each state no longer has infinite successors, it has 12 successors that represent moving one of the six variables \(\pm \delta\). Then one of the other local search methods could be applied.
Alternatively we could try random sampling of the successor states to make the branching factor finite, moving in a random direction by a small amount, \(\delta\). This is called empirical gradient search. It does not necessarily converge to a global optimum, it is similar to steepest-ascent hill climbing.
Calculus and Gradiants
Often we don’t need to proceed empirically though, as the objective function can be expressed in such a form that we can use calculus to solve the problem analytically. Many methods use the gradient of the landscape to find a maximum. The gradient of the objective function is a vector \(\nabla f\) that gives the magnitude and direction of the steepest slope. For the airport problem that gives:
\(\nabla f = \left( \frac{\partial f}{\partial x_1}, \frac{\partial f}{\partial y_1}, \frac{\partial f}{\partial x_2}, \frac{\partial f}{\partial y_2}, \frac{\partial f}{\partial x_3}, \frac{\partial f}{\partial y_3} \right)\)
Sometimes you can find a solution by solving \(\nabla f = 0\). In many cases however that can’t be solved in closed form, like the example problem where the answer depends on which cities are closest to each airport. So you can solve it locally, eg:
\(\frac{\partial f}{\partial x_1} = 2 \sum_{c \in C_1} (x_1 - x_c)\)
With that locally correct gradiant, we can then do steepest-ascent hill climbing. The state is updated as follows: \(x \gets x + \alpha \nabla f(x)\). Alpha is a small constant called the step size.
On p. 139 the book presents the Newton-Raphson method for finding roots of functions, used in this context to find a new direction once a hill has been climbed.
Constrained Optimization and Linear Programming
An optimization problem is constrained if solutions must satisfy some hard constraints on the values of the variables. For example the airports must be on land, not water.
The best known category of constrained optimization problems is that of linear programming problems, in which constraints must be linear inequalities forming a convex set and the objective function is also linear. Linear programming is the most widely studied and broadly useful method for optimization. They are polynomial in the number of variables.