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.


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.

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.

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.


  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.