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.

Decamp

From current discussion result, there's not an easy way to verify the equality between steps of local optimal and global optimal. When using greedy algorithm, you can't always expected it to produce global optimal solutions. So It's better to have an overview about which scenairos are suitable for greedy. When solving probles, thinking about whether it belongs those scenarios. Otherwise, use other solutions as we can't make sure about the result's correctness effectively. – Decamp

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.

Grin

you are talking that we can verify the locally optimal by classifying the problem's catalog. Then the problem becames is there any convient way to check whether problem is convex? :) – Decamp

@Decamp - I was speaking loosely. A given problem can often be solved in many ways, depending on how one chooses to represent it. Once you have a specific representation, then it may or may not be possible to classify it as convex or not. For instance, your sample problem of making change can probably be formulated as a linear programming optimization problem. Then the convexity follows automatically and a greedy algorithm for the problem as a linear programming problem will give a globally optimal solution. Formulated in some other way, such a conclusion may not be possible. – Grin

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

Forsaken

Wow! From the first glance, I think it's already beyond my knowledge. Not a mathmatic expert. If we want to verify the solution by programming, is there a good way? – Decamp

@Decamp Theoretical computer science provides a basis for analyzing and proving many properties of problems (complexity, computability) and algorithms (correctness, complexity, etc). Programming alone just won't get you there. – Leapt

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.

Doughy

Answer 4

You need to design a witness example where your premise that the algorithm is a global one fails. Design it according to the algorithm and the problem.

Your example of the coin change was not a valid one. Coins are designed purposely to have all the combinations possible, but not to add confusion. Your addition of 12c is not warranted and is extra.

With your addition, the problem is not coin change but a different one (even though the subject are coins, you can change the example to what you want). For this, you yourself gave a witness example to show the greedy algorithm for this problem will get stuck in a local maximum.

Abagael

I think the question was the reverse of what you answered -- i.e. "How can one prove that a series of locally optimal decisions will lead to a global optimum?" – Leapt

Your coin argument is a good case in point. Is it possible to prove that the "making change" problem has optimal substructure given the coins that actually exist? – Leapt

@andrewjs yes, mabye adding 12c isn't a good example. But I want to express when using the greeday algorigthm, for each step,you choose the best one. Then you first choose 12c, then for the left 3 cents , you can only select 1c*3. So you are said, we need to check the problem case by case? There's not a general paradigm, right ? – Decamp

@Aaron Novstrup: By not finding a witness after much educated analyzing, it is more probable that the local optimum is the global optimum. However, I am not sure how to prove it for certain – Abagael

@Decamp Han: My point was that by modifying the coins you have changed the problem. Coins are designed in such a way that they are chosen carefully. By arbitrarily choosing a coin you have changed the problem. Take foreign currency with different coin values and the change example will still work. – Abagael

@andrewjs In my example, though I changed the coin value, the coin choice sequence(12c+1+1+1) is what the process choosed by greedy algorithm(always selected the local optimal), isn't it? In my opinion, it's not related to insert new coin values(e.g. you can insert 4c,the greedy works well), but what value of coin you inserted. The 12c brokes some internal property that make greedy algorithm failed in such scenario. – Decamp

@Decamp Han: I believe we both have a valid argument. Perhaps this wikipedia entry could clarify further: en.wikipedia.org/wiki/Change-making_problem#Greedy_method – Abagael