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.

Subscribe to the Portfolio Probe blog by Email