When are locally optimal solutions equal to the global optimal? Thinking of a greedy algorithm

Question

I recently searched for some greedy algorithms. I am confused about locally optimal. As you know, greedy algorithms consist of locally optimal options. But combining locally optimal solutions does not necessarily mean globally optimal, right?

Take the change as an example: using the smallest number of coins to make 15% if we have 10%, 5% and 1%; coins, then you can achieve this with 10%; and one 5%. But if we add 12%; (1 x 12 + 3 x 1 x cent) uses more coins than (1 x 10 x plus 1 x 5 x cent).

Consider some classic greedy algorithms, for example. Huffman, Dijkstra. In my opinion, these algorithms are successful because they have no degenerate cases, which means that the combination of locally optimal steps is always equal to the global optimal one. Do I understand correctly?

If my understanding is correct, is there a general method for validating a greedy algorithm?

I found some discussion of greedy algorithms elsewhere on the site . However, the problem did not go into details.

Answer 1

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

A heuristic search will give you a global optimum with locally optimal solutions if the heuristic function has certain properties. For more information on this, refer to the AI ​​book.

In the general case, if the problem is not convex, I do not know any methods for proving the 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.) For more information see this Wikipedia section: http://en.wikipedia.org/wiki/Matroid#Greedy_algorithms

Answer 3

The greedy algorithm almost never succeeds in finding the optimal solution. In cases where this happens, it depends a lot on the problem itself. As Ted Hopp explained, with convex curves you can find a global optimal option, assuming that you should, of course, find the maximum objective function (on the contrary, concave curves also work if you need to minimize). Otherwise, you will almost certainly be stuck in local optima. This assumes that you already know the objective function.

Another factor I can think of is the neighborhood function. Some areas, if large enough, will cover both global and local maxima so that local maxima can be avoided. However, you cannot make the neighborhoods too large or the search will be slow.

In other words, regardless of whether you find the global optimal or not with greedy algorithms, the problem is specific, although in most cases you will not find the global optimal.

Answer 4

You need to develop an example of a witness in which your premise that the algorithm is global fails. Create it according to the algorithm and problem.

Your example coin change is invalid. Coins are designed specifically for all possible combinations, but not to add confusion. Your addition of 12c is not a guarantee and is optional.

With your addition, the problem is not in changing coins, but in another (even if the subject is coins, you can change the example to whatever you want). To do this, you yourself gave an example of a witness to show that the greedy algorithm for this problem gets stuck at a local maximum.