Choosing a Generating Set for OptGSS

A generating set for Rn is a set of vectors that can generate any point in Rn by linear combinations with positive coefficients.
Currently, OPT++ contains three Generating Set Search options for OptGSS. The first two can be used for n-dimensional problems, whereas the third is applicable only for two-dimensional problems.


GenSetStd:

gensetStd.gif
The standard generating set has 2n elements and consists of the columns of the identity matrix and its negative.
{I, -I}
The standard generating set gives rise to the well-known compass-search algorithm, which searches both sides of every Cartesian direction.

GenSetMin:
gensetMin.gif
A generating set for Rn must contain at least n+1 elements. The standard minimal generating set consists of the columns of the identity matrix plus the vector with all entries equal to -1.
{I, -1}
The standard minimal generating set is useful for problems with expensive function evaluations.

GenSetBox2d:
gensetBox.gif
The Box generating set augments the standard generating set with the corners of a n dimensional hypercube (or "box"). In OPT++, the Box generating set has been implemented for n=2, where the corner vectors are
{(1,1), (-1,1), (-1,-1), (1,-1)}.
This generating set can be used instead of the standard set for two dimensional problems with inexpensive function evaluations. The additional directions can significantly improve the algorithm's convergence rate.


References:

  1. T. Kolda, R. Lewis, V. Torczon. Optimization by Direct Search: New Perspectives on Some Classical and Modern Methods. SIAM REVIEW Vol. 45, No.3, pp.385-482.

  2. A. G. Buckley and H. Ma, A Derivative-Free Algorithm for Parallel and Sequential Optimization, Technical Report, Computer Science Department, University of Victoria, BC, Canada, 1994.

Next Section: Optimization Methods | Back to Main Page

Last revised July 13, 2006


Bug Reports    OPT++ Developers    Copyright Information    GNU Lesser General Public License
Documentation, generated by , last revised August 30, 2006.