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:

 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:
 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:
 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.

Last revised July 13, 2006