Reading

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 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: