Deterministic Global optimization relies on convex relaxation of the non-convex problems. Certain nonlinearities are duly converted into linear forms underestimators to be solved by efficient MILP solvers (e.g. signomial functions/ bilinear terms).
Most nonlinearityies are approximated to linear functions by piece-wise linearizations. However, I am wondering if this linearizations guarantees that the approximations are understimators of the original nonconvex problem (i.e. for all x in Domf, f(x) >= u(x) where u is the understimator)
because otherwise the understimator may miss the global optimum during the branch and bound process.
Can the solver still converge even if the relaxation is not an understimator?
Dear Yves,
For answering your question i suggest you to see links and attached file on topic.
A Review of Deterministic Optimization Methods in ... - Hindawi
https://www.hindawi.com › journals › mpe
Global Optimization of Nonlinear Blend-Scheduling Problems ...
https://www.sciencedirect.com › science › article › pii
BB underestimators of general non-linear functions over sub ...
https://link.springer.com › article
arXiv:1707.02514v4 [math.OC] 1 Feb 2019
https://arxiv.org › pdf
The Reformulation-based αGO Algorithm for Solving ...
https://pdfs.semanticscholar.org › ...
Best regards
Yves,
The wording you use ("relaxation") actually implies that they are indeed lower bounds. If they are not, then they need to have their names changed. :-)
That's right. More precisely, if an inequality is of "=" type, we use concave over-estimators (or you can just multiply the inequality by -1).
McCormick's original paper (from 1972) explains this very well. So does this paper:
Ryoo, H. S., & Sahinidis, N. V. (1996). A branch-and-reduce approach to global optimization. Journal of global optimization, 8(2), 107-138.
- Badges
- Science topic