(253d) New Underestimator and Branching Scheme for the Global Optimization of General Nonconvex Problems
Our contribution is two-fold. First, instead of using convex underestimators, we propose to exploit a new class of underestimators that is edge-concave . The underestimator is constructed by subtracting a positive quadratic expression such that all non-edge-concavities in the original function is overpowered by the added expression. While the edge-concave underestimator is nonlinear, the linear facets of its vertex polyhedral convex envelope  leads to a linear programming (LP)-based relaxation of the original nonconvex problem. We will present some theoretical results on this new class of underestimators and compare the performance of the LP relaxation with relaxations obtained by convex underestimators such as Î±BB and its variants. Second, we propose a novel branching technique based on a univariate projection of the original multi-dimensional space into a single auxiliary space . The idea is based on the fact that when all function values are projected onto a univariate space t defined by summation of the decision variables x, a point-to-set map can be generated and a univariate function exists on this map such that its global minima is the same as that of the original function. This enables us to devise a novel branching scheme only on t rather than on x in a B&B framework We will present separate results showing the efficacy of the proposed relaxation and branching schemes. Furthermore, results will be presented for the cases where we employ the proposed LP relaxation and the t-branching scheme together in a B&B framework for fast convergence to Ïµ-global optimality.
 Hasan, M. M. F. An edge-concave underestimator for the global optimization of twice-differentiable nonconvex problems. Journal of Global Optimization, 1-18, 2018. https://doi.org/10.1007/s10898-018-0646-x.
 Tardella, F.: On the existence of polyhedral convex envelopes. In: Floudas, C.A., Pardalos, P.M. (eds.) Frontiers in Global Optimization, pp. 563â573. Kluwer Academic Publishers, Dordrecht (2003).
 Bajaj, I. and Hasan, M. M. F. UNIPOPT: Univariate projection-based optimization without derivatives, Under Review.