The idea of a greedy algorithm (for optimization) is that you do as best you can locally and you don’t worry about the big picture.
For some problems a greedy algorithm is guaranteed to get you to the global optimum. In other cases, no.
An intuitive example
Suppose you are walking and you want to get to a specific place that is north and west of you. The greedy algorithm in this case is to take a street that is going north and/or west; at each intersection you decide whether to go in a new direction.
If you are in midtown Manhattan, you’re in luck — the greedy algorithm is going to get you there. The streets are on a grid.
If you are in London, the greedy algorithm might not work. You might be drawn into a mews that just ends; you might get on a street that circles around.
A lot of problems of interest are more like London than New York. However, greedy algorithms can still be useful in these cases. Greedy algorithms can be used to find locally good solutions while some other mechanism is used to find reasonable locations for the greedy algorithms to explore.
A real example
In particular, trade optimization and generating random portfolios are not the perfect realm for greedy algorithms. Nonetheless, the Portfolio Probe software uses a few greedy algorithms when performing these tasks. A genetic algorithm is the main driver, and the greedy algorithms refine the solutions.
One of the greedy algorithms is nicknamed “polishing”. Suppose we are optimizing a trade and we have a candidate trade in hand. We can think of looking at each asset in the trade in turn. We want to find the best amount to trade of the asset while not changing the amount traded for the other assets.
The catch is that because of constraints some of the other assets will, in general, need to change. The polishing algorithm tries to move the other assets only a little but still satisfy the constraints.
It turns out that polishing is a quite successful adjunct to the genetic algorithm.
Epilogue
And he was rich, yes, richer than a king,
And admirably schooled in every grace:
In fine — we thought that he was everything
To make us wish that we were in his place.
from Richard Cory by Edwin Arlington Robinson
Manhattan picture by Daquella manera via everystockphoto.com.
London picture by Regent’s College London via everystockphoto.com.
Thanks, Pat, for this insightful post on optimization, personally I seldom use optimization, not because the optimized values are wrong, but I feel insecure by using numbers jumping out of those black boxes lack of economic sense (or I don’t get it). So may I know do you really use it a lot in reality, or you just have its results as a reference? If you don’t mind, a real application example is appreciated. Thank you.
Dear Quant,
I presume you are talking about portfolio optimization rather than the more general case. First off, I don’t manage money, I just supply some tools. An answer to your question is that some fund managers use optimization a lot. There are also fund managers who don’t use optimization at all.
I agree with your implicit position that an optimizer used badly is a dangerous thing. However, overcoming the “lack of economic sense” problem is easy to do. You merely need to restrict the turnover that is allowed. This can be done either through a turnover constraint, or (better but harder) through transaction costs.
Portfolio Probe includes a different form of portfolio optimization which is to minimize the distance to a target ideal portfolio. This might be a more palatable approach for those fund managers who don’t use optimization at all at present.
Does this answer your question?
.The greedy algorithm determines the minimum number of coins to give while . These are the steps a human would take to emulate a greedy algorithm to represent 36 cents using coins. Note that in general the change-making problem requires or to find an optimal solution US and other currencies are special cases where the greedy strategy works. …A greedy algorithm is any that follows the of making the locally optimal choice at each stage with the hope of finding the global optimum..For example applying the greedy strategy to the yields the following algorithm At each stage visit the unvisited city nearest to the current city ……
Pingback: Blog year 2010 in review | Portfolio Probe | Generate random portfolios. Fund management software by Burns Statistics