Nonconvex problem: local vs multistart vs global

In [1] a somewhat abstract non-convex problem is given:

\[\begin{align}\min_x & - x_1^2 - x_2^2 - x_3^2 - x_4^2\\ & Ax \le b \end{align}\]

This is a nonconvex objective with some linear constraints. Of course, the easiest way to gain some insight into how to solve this is to perform some quick and dirty tests with a global QP solver designed for these types of models. As the constraints are linear, a solver like Cplex or Gurobi may be a good starting point (pun intended).

If you have access to a local NLP solver, it may not always be easy to find a good starting point. One possible approach is to use a multistart algorithm (some NLP solvers, like Baron and Knitro, have this built-in). This will not guarantee a global solution (and most likely, it doesn't give you one), but at least we can prevent really bad solutions.  

Tiny non-convex quadratic model brings solvers to their knees

Here is a very small geometric problem:

Given \(n\) points in 2d space, find the smallest triangle that contains all these points.

Find the smallest triangle containing all points.

This looks like a simple problem. Somewhat to my surprise, my attempt here does not bear that out.

Octeract

I don't know what or who this is.

This seems to be a parallel deterministic solver for non-convex MINLPs.  Some things I noticed:

• !np.easy : cute (but nonsense of course: some problems just remain difficult).
• "The first massively parallel Deterministic Global Optimization solver for general non-convex MINLPs."
• Symbolic manipulation: like some other global solvers they need the symbolic form of the problem so they can reason about this. I.e. no black-box problems.
• Support for AMPL and Pyomo
•  "Octeract Engine has implementations of algorithms that guarantee convergence to a global optimum in finite time. The correctness of the majority of the calculations are ensured through a combination of interval arithmetic and infinite precision arithmetic."
• It looks like the benchmarks [3] are against itself (so always a winner). 
• "Massively parallel" makes me think about thousands of cores. The benchmarks do not seem to report anything like this (mostly 1,4 and 8 cores).
• I don't see any names on the web site. The About Company section is unusually vague. I received some more links with additional background info [4,5].

Some of the competing solvers are Baron, Couenne, and Antigone.

References

1. https://octeract.com/ 
2. Manual: https://octeract.com/wp-content/uploads/2019/08/user_manual.pdf
3. Benchmarks: https://octeract.com/benchmarks/
4. Presentation: https://www.youtube.com/watch?v=ayZ3iHmQUak
5. PhD thesis: https://spiral.imperial.ac.uk/bitstream/10044/1/45359/1/Kazazakis-N-2017-PhD-Thesis.pdf