I've previously solve optimization problems with linear and mixed integer linear programming with Simplex Algorithm.

Now I've an objective function $F=f(x_1, x_2, .. x_n)$ to be minimized, but F is not lineare and its value is computed by an external tool for each combination of $x_1, x_2, ... x_n$.
The decision variables ($x_1, x_2, ... x_n$) are subjected to constraints (inequality and equality linear constraints).

All efficient optimization algorithms require the gradient of the objective function but I cannot calculate it.

Is there a way to search for optimum values (either local or absolute) without evaluating F for each combination of the decision variables?

  • 1
    $\begingroup$ You can't calculate the gradient at any point? Unless your function is extremely messy, you approximate the derivative if it does exist by "the limit definition". You can merge this with any general active constraints method. $\endgroup$ – Koto Jun 28 '17 at 14:55
  • $\begingroup$ If you can calculate $f(x_1,\dots,x_n)$ and $f(x_1,\dots,x_i+\delta,\dots, x_n)$, you can get an approximation for $\partial_i f(\textbf{x})$ by letting $\delta\rightarrow 0$. $\endgroup$ – Koto Jun 28 '17 at 15:01

Your problem falls in the field of ''Derivative free optimization''. Check this book of Andrew R. Conn, Katya Scheinberg and Luis N. Vicente for basic material.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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