When locally optimal solutions equal global optimal? Thinking about greedy algorithm

Question

Recently I've been looking at some greedy algorithm problems. I am confused about locally optimal. As you know, greedy algorithms are composed of locally optimal choices. But combining of locally optimal decisions doesn't necessarily mean globally optimal, right?

Take making change as an example: using the least number of coins to make 15¢, if we have 10¢, 5¢, and 1¢ coins then you can achieve this with one 10¢ and one 5¢. But if we add in a 12¢ coin the greedy algorithm fails as (1×12¢ + 3×1¢) uses more coins than (1×10¢ + 1×5¢).

Consider some classic greedy algorithms, e.g. Huffman, Dijkstra. In my opinion, these algorithms are successful as they have no degenerate cases which means a combination of locally optimal steps always equals global optimal. Do I understand right?

If my understanding is correct, is there a general method for checking if a greedy algorithm is optimal?

I found some discussion of greedy algorithms elsewhere on the site. However, the problem doesn't go into too much detail.

Answer 1

Generally speaking, a locally optimal solution is always a global optimum whenever the problem is convex. This includes linear programming; quadratic programming with a positive definite objective; and non-linear programming with a convex objective function. (However, NLP problems tend to have a non-convex objective function.)

Heuristic search will give you a global optimum with locally optimum decisions if the heuristic function has certain properties. Consult an AI book for details on this.

In general, though, if the problem is not convex, I don't know of any methods for proving global optimality of a locally optimal solution.

Answer 2

There are some theorems that express problems for which greedy algorithms are optimal in terms of matroids (also:greedoids.) See this Wikipedia section for details: http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms

Answer 3

A greedy algorithm almost never succeeds in finding the optimal solution. In the cases that it does, this is highly dependent on the problem itself. As Ted Hopp explained, with convex curves, the global optimal can be found, assuming you are to find the maximum of the objective function of course (conversely, concave curves also work if you are to minimise). Otherwise, you will almost certainly get stuck in the local optima. This assumes that you already know the objective function.

Another factor which I can think of is the neighbourhood function. Certain neighbourhoods, if large enough, will encompass both the global and local maximas, so that you can avoid the local maxima. However, you can't make the neighbourhood too large or search will be slow.

In other words, whether you find a global optimal or not with greedy algorithms is problem specific, although for most cases, you will not find the globally optimal.