Derivative-free nonlinear optimization of discrete objective function with linear constraints (simplex)

Question

I am trying to optimize a constrained-problem with a discrete, non-linear objective function. Evaluating this function is also fairly expensive. Nevertheless, despite the above two factors, I hope, that it can still be solved efficiently, since the structure of the constrained parameter space should be helpful.

To be more exact: The parameter space will in general be of dimension 4-150. The parameters lie on a n-simplex, i.e.:

\begin{align} \sum_{i=1}^n p_i =1 \\ p_i \geq 0 \; \forall \; i =1,\dotsc,n \end{align}

Now my question is: Which algorithms could work best for solving such types of problems?

So far I have tried variants of the following:

• Constrain the space by $1-\varepsilon \leq \sum_{i=1}^n p_i \leq 1, \varepsilon >0$ and then apply an adaptive barrier method combined with the Nelder-Mead algorithm (R constrOptim function)

• Apply unconstrained optimization in $\mathbb R^n$ by modifying the objective function, so that in the first step it normalizes the parameters appropriately.

• Map the simplex to the unit sphere. Then perform unconstrained optimization using Nelder-Mead,the Subplex algorithm or the Covariance Matrix Adaptation Evolution Strategy (CMAES) algorithm based on the spherical coordinates.

So far spherical coordinates followed by CMAES shows the best results, but it is too slow. What else could I try?

Answer 1

Generally speaking, for derivative-free optimization, there's no one algorithm that works best for all problems, although there are some algorithms that tend to work better than others. The classic recent review reference for derivative-free optimization is by Rios and Sahinidis (see also this related presentation by Sahinidis, and they suggest the MCS algorithm, the LGO algorithm (proprietary implementation), and BOBYQA/NEWUOA (both of which are implemented by NLOPT).

Derivative-free methods tend not to incorporate general constraints. If you're using a method that does not permit your linear constraint, you can either normalize the parameters as you are doing right now, or you can use more of a barrier-type approach and penalize violation of the constraint with a penalty term and increase the penalty parameter over a number of solves.

Answer 2

In addition to Geoff's answer, you can also just eliminate the linear constraint. The "mollification" $1-\varepsilon \le \sum_i p_i \le 1$ really creates more problems than it solves because it leaves you optimizing in an $n$ dimensional domain that is, however, very narrow in one direction. A better option is to just replace $p_n= 1 - \sum_{i=1}^{n-1} p_i$ everywhere and add the constraints $\sum_{i=1}^{n-1} p_i \le 1$ to your list of inequality constraints. This way, you can simply express everything in terms of just $n-1$ variables. In essence, you are now optimizing over the interior of an $n-1$ simplex.