Derivative-free based optimization subject to a linear constraint

Question

I'm dealing with a NLP-problem that can be formulated as:

$$\min_{\overrightarrow{x}} f(A\cdot\overrightarrow{x})$$, where $\overrightarrow{x}$ is a vector of $n$ design points where every element sits on the interval $[0, 1]$ and $A$ is a fixed binary matrix of shape $(j, n)$. The input of the function $f$ is thus a variable $x$ of size $j$, but the decision variable is the vector of size $n$.

$f(.)$ is a non-linear function of the form $\sum_{i=1}^j a-\left(bx_i\right)^c*d+\left(ex_i\right)^{f}g+h$, where $a, b, c, d, e, f, g, h$ are alle positive and non-integers constants.

The constraint that we are dealing with is linear:

$$\frac{\sum_{i=1}^j d_ix_i}{\sum_{i=1}^jd_i} = \beta$$, where $d_i$ is a constant variable and $\beta$ is a constant on the interval $[0, 1]$.

I'm looking for a derivative-free based optimization algorithm that can optimize the $n$-design points but considering the linear constraint.

Are there any derivative-free based optimization methods that can handle constraints?

Answer 1

Why do you want derivative-free (see below)? A good derivative-based local optimization solver should be more robust and likely faster executing than a derivative-free solver.

If you insist on using a derivative-free optimizer for some reason, you can use LINCOA, which is a highly regarded derivative-free solver for linearly-constrained optimization problems. It was written by the late Michael J.D. Powell. LINCOA builds up a quadratic model of the objective, and solves a series of trust-region subproblems to arrive at the solution to the original problem. It is a local optimizer, meaning, that if the optimization problem (in your case, specifically, the objective function) is not convex, the solution found by the solver might not be a global minimum.

It is not difficult to calculate (first) derivatives of this objective function with hand-coding, Alternatively, derivatives can easily be calculated by automatic differentiation. Optimization systems such as AMPL can handle that automatically for you. The global optimizer BARON computes whatever derivatives are needed. If $0<c,f \le 1$, the optimization problem is convex, and even a local optimization solver should find the global minimum; if the optimization problem is not convex, you may need a global optimization solver to find the global minimum.