# Tag Info

12

SCIP does not currently support any trigonometric functions as of this post from May 2018. COUENNE appears to handle $\sin$ and $\cos$ expressions. ANTIGONE appears to not support any trigonometric functions as of 2013. BARON states in the manual to not support any trigonometric functions in March 2019. LINDOGLOBAL supports cos, sin, tan, cosh, sinh, ...

11

After further reading it seems that "surrogate models" do exactly this (aka. "meta-models"), a recent discussion of methods is here: https://onlinelibrary.wiley.com/doi/full/10.1111/itor.12292 Also called "Surrogate model-based optimisation" (SMBO) Survey of methods: https://martinzaefferer.de/wp-content/uploads/2016/10/survey-1.pdf

7

Here is an option for MATLAB users which is not mentioned in any other answers. YALMIP's BMIBNB iI a global branch and bound solver https://yalmip.github.io/solver/bmibnb/. It is used in combination with (i.e., calls) a MILP solver (such as CPLEX, GUROBI, SCIP, MOSEK) and a "call back" for evaluation continuous variable local optimization solver (such as ...

6

In YALMIP you can use arbitrary black-box operators to circumvent modelling n = 5; c = randn(3*n,1); A = randn(10*n,3*n); b = rand(10*n,1); % MILP model x = sdpvar(2*n,1); Domain= [0 <= x <= 1]; % Big-M should have some help for i = 1:n x = [x;max([x(i),x(i+n)])]; end optimize([Domain, A*x <= b], c'*x) % Black-box model (sdpfun is renamed to ...

6

An approach that is easy to implement and always worth a shot is a simple neighborhood search, where you start with some candidate solution and iteratively move to a neighbor solution. For your problem, a 2-opt or swap neighborhood could perhaps already find good local optima, as it will pick up on some of the relationships that your function possesses. More ...

6

You might want to google "response surface methodology" and "simulation" together. There is a ton of literature on this, a mixture of how do to response surface modeling (and how to use it to optimize system parameters) and examples of its application.

6

From the presentation given by Vigerske, S. (2015), it is noted that the solvers Couenne by P. Belotti and LindoAPI by Y. Lin and L. Schrage can handle trigonometric expressions. Both are deterministic global optimisation solvers for MINLP. Reference  Vigerske, S. (2015). MINLP - Global Solvers. Available from: http://co-at-work.zib.de/files/...

5

Given that your function is apparently unimodal (single local minimum, which is global), you might try golden section search. The first four function evaluations result in about a 40% reduction in the initial interval. Each additional function thereafter again reduces the remaining interval by about 40%.

5

Octeract Engine (the solver I develop), is a deterministic global MINLP solver that supports all trigonometric functions (including hyperbolic functions).

5

Cross-posting. The math looks good but why starting with $\nabla f(x) = 0$ instead of $\frac{1}{2}\nabla f(x) = 0$? You should have noticed that the factor $2$ was everywhere and could be simplified. For the curious readers who wonder whether there exists a simpler solution to this simple problem: the answer is yes. It suffices to notice that the sum of the ...

4

This is a non-convex global optimisation problem. The state-of-the-art way to solve this is to use a factorable relaxation. A key insight here is that $e^{-\alpha X}$ is convex (since your $\alpha$ is positive). The methodology would be as follows: Introduce a new auxiliary variable $w=e^{-\alpha X}$ You now have $Z=Yw$, and $w=e^{-\alpha X}$ Because both ...

4

Assuming the continuous relaxation is convex you can most likely use conic optimization with the exponential cone. The Mosek modelling cookbook has the details. Unsurprisingly Mosek can solve the mixed integer version of such problems.

4

The default Octeract Engine behaviour is to handle this automatically without reformulating to an MILP.

3

A "random key" genetic algorithm (henceforth RKGA) might get you a pretty good solution within your function call limit (particularly if you cache function values, so that repeated evaluations of the same sequence do not require repeated simulations). The idea behind RKGA is that a "solution" (population member) would in your case be a vector of 500 numbers (...

3

In addition to the references already given in the comments, this paper (DOI link) demonstrates that exact solutions to some non-convex quadratic programs are given by semi-definite programming, and whenever the SDP relaxation is tight we can actually solve the SDP via SOCP! In general the SDP relaxation will of course not be tight, but as shown by ...

3

NP-hardness is an asymptotic result of increasing problem dimensions. It is not a property of one fixed problem instance. So to ask whether your problem class is NP-hard, you would have to explain how the problem would grow with increasing numbers of $X$ variables. As far as solving your specific instance, a number of nonlinear solvers could probably do it, ...

3

The notion of NP-hardness relates to whether one class of problems can be solved by a solver for another class of problems where the translation overhead is negligible. The problem you presented is member of many classes of problems. However NP-hardness is the property of a class of problems. So it is impossible to answer whether this particular instance is ...

3

I might be missing something here (and by "might be" I mean "probably am"), but at least for the case of $x_i \in [0,1]$ you might be able to get solutions via "brute force". I'm assuming that all the parameters ($F,p,b,\beta$) are positive. Suppose we slap a somewhat arbitrary upper bound $M$ on $q_1$, and then do a bisection ...

3

As far as I can see there is no exact convex reformulation for this, unless someone else can think of a nice trick. Constraint 1 can actually be convexified for certain ranges of $q_i$ as these functions are partially convex, e.g. $1/(1+x)^3$ is: The fractions in constraint 3 are also convex past certain hyperplanes. However, you would have to restrict your ...

2

With the exception of special cases, this problem is NP-hard. One interesting case is that minimizing a convex or concave function over a simplex can be solved in polynomial time. In other special cases it is also possible to linearise the problem through reformulations. In the general case however this would be solved by relaxing the objective and using ...

2

You may find a partial answer to your question in the following article (forthcoming in OR) by JP Vielma and J Huchette https://arxiv.org/abs/1708.00050 In that paper, the authors consider the problem of approximating non-linear functions of one or two variables in the objective via the disjunction of multiple hyperplanes. You can then pass the resulting MIP ...

2

I would advise Bayesian Optimization. The benefits imho are that they don’t require a gradient, work for a wide variety of optimization problems and are made for when we are dealing with functions that are hard or slow to evaluate.

1

Considering the first given objective function, the problem is trivial to solve. The decision variables X1 and X2 are positive. Because polynomial with positive coefficients only, the objective function is thus monotonically increasing over the space of feasible solutions. The last constraint over X1 and X2 is inactive because dominated by the previous ones. ...

1

Technically, your statement is correct, but nowadays it depends on who you're talking to. Historically, to $\min f(x) s.t. ...$ means exactly what we see: to find the minimal value. Not some value that's smaller in some arbitrary neighborhood, the minimal value. Ergo, the semantically correct way is to use "solution" for all global solutions, and &...

1

This question is a matter of semantics. If by "solution", you mean the global optimum, then yes, "the" (a) solution to an MINLP is a global optimum (note that some problems have more than one globally optimum solution). If, however, by "solution", you mean a local, but not necessarily, global, optimum, then the solution to an ...

Only top voted, non community-wiki answers of a minimum length are eligible