# Derivative-free based optimization subject to a linear constraint

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?

• Why do you want derivative-free? It is not difficult to calculate (first) derivatives 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 not, you may need a global optimization solver to do so. Jul 3 at 10:33
• If you do need a derivative-free algorithm, you might try using a penalty method (converting the constraint to an objective term that penalizes deviations).
– prubin
Jul 3 at 15:23
• @prubin yes, that's indeed the most natural thing to do. I now used dynamic programming by alternating the formulation and that seems to work too. Could get computationally heavy when the n-design points get really large but that's not the case (in my case). Jul 4 at 7:31

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, 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.