Assessment of a non-adaptive deterministic global optimization algorithm for problems with low-dimensional non-convex subspaces

The optimum and at least one optimizing point for convex nonlinear programs can be approximated well by the solution to a linear program (a fact long used in branch and bound algorithms). In more general problems, we can identify subspaces of ‘non-convex variables’ such that, if these variables have sufficiently small ranges, the optimum and at least one optimizing point can be approximated well by the solution of a single linear program. If these subspaces are low-dimensional, this suggests subdividing the variables in the subspace a priori, then producing and solving a fixed, known number of linear programs to obtain an approximation to the solution. The total amount of computation is much more predictable than that required to complete a branch and bound algorithm, and the scheme is ‘embarrassingly parallel’, with little need for either communication or load balancing. We compare such a non-adaptive scheme experimentally to our GlobSol branch and bound implementation, on those problems from the COCONUT project Lib1 test set with non-convex subspaces of dimension four or less, and we discuss potential alterations to both the non-adaptive scheme and our branch and bound process that might change the scope of applicability.