Description of Testbench optimization problems with YES/NO constraints

Brief description of testbench optimization problems with YES/NO constraints

Two FORTRAN subroutines are provided. One evaluates whether or not constraints are violated at a specified point, and evaluates the objective function. The other routine provides (a) the true solution for each problem (for comparison purposes), (b) 2 standard starting points for each problem, one in the interior and one on the boundary of the feasible region, and (c) a standard search box for methods that search over regions rather than using a starting point per se. The search box is specified so that it contains the true solution.

Twelve problems are included in this testbench. Several are actually families of problems controlled by a continuously variable parameter. These problems can be made easy or hard depending on the choice of the parameter.

Problem descriptions and meaning of the parametrically variable problems can be found inside the sourcecode. The following two tables summarize. Pictures are available through the matlab visualization tool.


Nprob      Description                                                   Params
-------------------------------------------------------------------------------
 1         45 degree constraint boundary.                               Unused
           f(x)=x(1)

 2         User variable slope on constraint boundary on (x(1),x(2))    (0,90)
           Also, uses progressively lower angle on higher dimensions.
           f(x)=x(1)

 3         60 degree constraint boundary on (x(1),x(2))                  [0,1)
           Progressively lower angle on higher dimensions.
           User-variable slope on f(x).

 4         Curved constraint boundary.                                  Unused
           Hard, since the intersection of the wedge of descent
           directions with the set of feasible directions shrinks
           rapidly as one approaches the solution.
           f(x)=x(1)

 5         Constraint boundary has 3 corners in 2D, more in ND          Unused
           f(x)=x(1)

 6         Constraint boundary has 10 corners in 2D, more in ND         Unused
           f(x)=x(1)


 7         Constraints in dimensions higher than 2 are based on         (-45,45)
           l-1 norm rather than l-inf. Also, problem can be rotated.

 8         Solution is not on the constraint boundary.                  Unused

 9         Feasible region can be made very slender.                    (0,4]

10         Feasible region is a wedge and can be made very narrow.      (0,45]

11         Nonconvex constraint boundaries. Multiple local              Unused
           solutions.

12         Nonconvex nonsmooth constraint boundaries. Multiple          Unused
           local solutions.



C                   Nprob        Params(1)
C                   -----        --------
C                     1          not used
C                     2          (0,90). For descent methods, small numbers
C                                          are easier. For DIRECT, small 
C                                               numbers are hard.
C                                          Nprob = 2 is the same as nprob=1 
C                                               if params(1)=45 and n=2
C                     3          [0,1). Easiest is 0.
C                     4          not used
C                     5          not used
C                     6          not used
C                     7          (-45,45) Test of rotational invariance.
C                     8          not used
C                     9          (0,4]    Closer to 0.0 is harder.
C                    10          (0,45]   Closer to 0.0 is harder.
C                    11          not used
C                    12          not used

Fortran sourcecode for the testbench problems. Version 0.8, May 1 1999.

Matlab visualization macros (including precomputed maps of objective and constraints) for the testbench problems. About 660K, unpacks to about 18 meg.

Brief description of Matlab visualization tool.

Return to the YES/NO constraint page.

Return to Richard Carter's page.


Back to CAAM Home Page
webmaster@caam.rice.edu -- 1998-August-25