These notes.

## Quiz questions

Work on Project 3/ ProblemSet 4

## A Geometric view of optimization

Optimization problems generally consist of a set S of potential solutions and an objective function f, F:S → R, where "R" is the set of real numbers --- the goal being to find an element of S that yields the maximum/minimum value of f. Sometimes it's also convenient to add a constraint function C, C:S → {0,1}, and make the goal to find an element of S that yielding the maximum/minimum value of f amongst those elements satisfying the constraint C.
Example: For the LongPath problem on a graph with n vertices, S is the set of all sequences of distinct vertices, f maps a sequence to its length, and C(s) returns 1 if each successive vertex in the sequence is a neighbor of the vertex before it, and false otherwise.
Optimization has a clear geometric interpretation when S is a Euclidean space and f isn't too exotic. For example, if S = R2 and f is a continuous differentiable or piecewise differentiable function, we have a nice picture like this:

Optimization means finding the point in the S-plane at which the f(S) surface has the maximum or minimum value.

There are many algorithms for optimization in this kind of setting. An algorithm that starts with an initial point x in S and trys to move from x in small steps searching for nearby points with better f-values is doing local optimization. The optimization is "local" in the sense of restricting itself to points near the initial point x. One very straightforward kind of optimization is Hill-Climbing. The idea in hill climbing is to move from an initial point in small steps always taking the step that increases f the most. When you've arrived at a point at which any small step decreases f, you're done. This will give you a local maximum (if you're restricted to a bounded region in S) but not necessarily a/the global maximum. Like this:

This is actually the big problem in optimization: finding local optima is easy, but finding the global optimum (or optima) is difficult ... you keep getting stuck in all those local optima. In fact, for NP-Hard problems the difficulty is that you may have exponentially many local optima to get stuck in!

So what have we learned? We have a geometric view of opimization: we're searching for peaks (or valleys) over the space S. We have a concept of local optimization, and we understand the pitfalls of local minima and maxima.

## A Geometric view of optimization: Part II

What about something like the Travelling Salesman Problem (TSP)? How can we picture the space S of possible solutions? How can we do local optimization when there's no obvious way to talk about the distance between solutions? It turns out that people do think about optimization in the exact same way as in the nice Euclidean example above. The only real catch is that distance between solutions stays a bit fuzzy. What is not fuzzy, however, is how to determine what solutions are close to the current solution. Recall that when we talked about TSP we described the operator 2-OPT for generating new solutions from old solutions. Whenever you choose an operator or set of operators, they actually induce a definition of "nearby" solutions: solution x' is one step away from x if one operator application changes x to x'. The minimum number of operator applications to get from x to x' defines the distance between x and x', though this is such a difficult thing to try to compute that it's not really a useful idea. Local optimization usually means searching all solutions that are one operator application away from the current solution and choosing the solution with the best f value. In other words, we apply local optimization in a greedy manner!
Using 2-OPT, which recall is equivalent to taking a sub-path of vertices in the cycle and reversing the sub-path, solution X = a→b→c→d→e→f and solution X' = a→b→d→c→e→f are neighbors (all you do is reverse c→d), but solution X'' = a→c→b→d→f→e is not a neighbor because it is two reversals (i.e. two 2-OPT moves) away.
Seeing it this way, our "greedy + local optimization", i.e. taking a greedy solution and then repeatedly appling 2-OPT operations that improve the cycle until we get to a point that no 2-OPT operation reduces the cycle cost, is really just hill-climbing from the starting point provided by a greedy algorithm to a local optimum. With this picture in mind, we see the problem too: the local optimum we find may not be a global optimum.

What about applying "randomized greedy + local optimization" repeatedly? Well, we're just hoping that one of the starting points generated by the randomized greedy algorithm is close enough to a global minimum that our hill-climbing finds it instead of some sub-optimal local minimum.

Reiteration time: The "local" in local optimization refers to solution points that are reachable in few operator applications, not necessarily solution points that are near in more comfortable ways. For example, consider squares a and b on the chessboard below:

 Me Me Me Me Me Me M M M M M M M a b M M M M M M M M M M M M M M M
Are a and b near? Well that depends. If you are a king or a rook: yes. If you are knight you might say no, since it takes three moves to get from a to b. If you're a bishop you'd certainly say no, since one is unreachable from the other. It all depends what "operators" you have available for moving through the space. In our search for good solutions to NP-Hard optimization problems, we define the operators we use in local optimization, and in so doing we define what "local" really means.

## Other optimization strategies: Overview

Various strategies for optimization differ in how they use the "operators" for local optimization, and how they make big "non-local" jumps to try to avoid getting permantly stuck in a
• local optimum/minimum, or in a
• plateau, which is a very hard to spell region in S-space over which the f-surface is flat, with constant height, or in a
• ridge, which is a curve in S-space over which the f-surface has constant height
since all of these cause problems for approaches like hill-climbing. So here is a non-exhaustive list of techniques, but we'll try to cover these before the semester ends:

• Random Restart Hill Climbing - This is basically just what we suggested last class: repeatedly start with random solutions using local optimization to improve each of them.
• Local Beam Search - This is like doing k hill-climbing optimizations, but doing them simultaneously. For each of k solutions, we generate all neighboring solutions (i.e. reachable in a single operator application) and the k best of that huge pool of solutions become the new k solutions ... and we repeat.
• Simulated Annealing - We have a solution x and loop; at each iteration choose a random move from x (remember move means an operator application). If the move improves x, we always commit to it, otherwise we only commit to it with probability p. This probability actually depends on how much worse the solution we'd be moving to really is, and on how many iterations of this loop we've been through. In particular, the probability of accepting the move decreases with the number of loop iterations and the badness of the move. Thus, early on you tolerate a lot of random exploration, which you hope will land you near a global optimum at some point, while later on you basically work on finding the local optimum in the area you've settled into. This approach is based on mimicing the annealing process in metallurgy.
• Genetic Algorithms - This is another approach that mimics a natural phenomenon. Here the idea is to keep a population of k solutions, initially chosen randomly. At each step (or generation if we decide to roll with the analogy) we create a new population of k solutions by "mating" the most fit members of the population, i.e. those with the best f values. "Mating" here means that new solutions are built by combining two parent solutions. These new solution undergo "mutation" with some small fixed probability, where mutation is suspiciously like applying one of our operators for local optimization. How this mating is done is extremely problem-specific, and will require some explaining later. Genetic algorithms are extremely popular, but many critics feel that the appeal is in the metaphor, not in the utility of the approach. Still, genetic algorithms are easily the most popular of these approaches --- not just in computer science, but in all fields of science and engineering.