Black-box optimization of a symmetric function

Question

Is there a way to exploit symmetry in black box optimization? Specifically, I want to find a local minimum of a function $f: \mathbb{R}^{300} \rightarrow \mathbb{R}$ which has the property that any permutation of the inputs gives the same output. Apart from that, $f$ doesn't have any "nice" property that I know of (it's certainly not smooth).

I have tried a number of black-box optimization techniques (Nelder-Mead, COBYLA, Bayesian optimization...) but they take a prohibitively long time and haven't produced satisfying results. The symmetry in the function's inputs makes me think there should be a way to reduce the impact of the "curse of dimensionality".

Any idea is welcome!

Answer 1

Symmetries in optimization problems are considered as a curse rather than a benefit. They multiply the number of optimal points, so that algorithm that explore trees (e.g. branch-and-bound) have exponentially more work to do.

The usual technique is to remove symmetries by limiting the scope of search to a region where each set of symmetric points has only one point. This is done by adding symmetry-breaking constraints. In your case, you can add a lexicographic order, i.e. if your variables are $v_1, v_2, \dots, v_n$, add the inequalities $v_1 \lt v_2 \lt \dots \lt v_n$, or $v_1 \le v_2 \le \dots \le v_n$, depending upon your problem.

Note that this is not a silver bullet: the problem is still complex and the solver has additional constraints to deal with. But it nevertheless accelerates resolution.
(Except when the optimization software itself implements symmetry detection and removal; this is the case in the best mixed integer programming solvers; but this of course cannot happen with black-box optimization).