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

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?

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.
• Oh, good point, thank you! I had my $\epsilon$ quite large (at 0.1), since I knew that the optimum would lie on the boundary. Still, with your suggestion, constrOptim with the Nelder-Mead algorithm performs better than before. Maybe I should try adapting constrOptim so that it can also use other unconstrained optimization algorithms. – air Oct 15 '14 at 18:59
• @WolfgangBangerth: I think you meant to construct $p_{n}$ in such a way so that the sum over the $p_{i}$ equals 1, and I've modified your formula accordingly. – Geoff Oxberry Oct 15 '14 at 19:05