2
$\begingroup$

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?

$\endgroup$
3
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 3, 2023 at 10:33
  • $\begingroup$ 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). $\endgroup$
    – prubin
    Commented Jul 3, 2023 at 15:23
  • $\begingroup$ @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). $\endgroup$ Commented Jul 4, 2023 at 7:31

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.