How does BOG work?

BOG is based on a grid-search optimization technique. The process of gem design optimization can be likened to mountain climbing (see figure below). Imagine a world in which one grid direction (i.e. east-west) corresponds to the current pavillion angle, and the other (north-south) corresponds to the current crown angle. The altitude at any point is a measure of how good the gem is with that particular combination of pavillion and crown angles. BOG calculates a merit function to determine this altitude (gem quality). Finding the best gem then becomes a problem of finding the highest peak within the area defined by an acceptable range of pavillion and crown angles - essentially within the edges of the world below.

How do we go about finding the highest peak? Finding the maxima (and minima) of surfaces is a very important problem in all areas of science and engineering, and there are a large number of peak-finding algorithms. BOG uses the simplest and most robust of these, a so-called grid search. Imagine you are a mountaineer dropped down somewhere on the world below with the task of finding the peak. To do a grid search, you would begin by taking a step in one direction, say east. If the terrain goes up, you take another step. If the very first step is downhill, you reverse direction and start looking the other way. Having selected a search direction, you carry on taking steps until the ground stops getting higher.

At this point, things go downhill to both the east and west. The obvious strategy is to begin exploring north-south in the same way. When that is no longer productive, you switch back to searching east-west. And so on. The grid search algorithm within BOG has a few additional bells and whistles. For example, before switching to the other grid direction, it uses the altitude of the last three steps to make a more accurate estimate of the highest point before setting off at right angles. It also continuously adjusts the size of the steps, based on how long it took to exhaust a certain grid direction.

 

Although you would look pretty silly doing this on a real mountaintop, it is clear that this simple strategy inevitably leads to the highest point in the vicinity. There is a problem, however. Look again at the terrain in the figure. The grid-search strategy will lead to a peak, but not necessarily the highest peak. In other words, this algorithm (like most) really finds the local, not absolute maximum. Depending on where you set out (in other words, depending on your choice of initial pavillion and crown angles), you may not find the best gem.

This problem is also well-known, and there are a variety of solutions. BOG again adopts the simplest strategy, so-called Merit Function Mapping. This technique essentially boils down to calculating the Merit Function on a grid of pavillion and crown angles. This helps identify multiple peaks and good starting points for the Optimization algorithm. See the Merit Function Mapper Tutorial for more details.

Back to Main Page.

 

 


Documentation maintained by Tom Herbst. Last modified 10-Aug-2005