Problem of global minimization of twice continuously differentiable function with Lipschitz second derivatives over a polytope is considered.We suggest a branch and bound method with polytopes as partition elements. Due to the Lipschitz property of the objective function we can construct a quadratic support minorant at each point of the feasible set. Global minimum of of this minorant provides a lower bound of the objective over given partition subset. The main advantage of the suggested method consists in the following. First quadratic minorants usually are nonconvex and we have to solve auxiliary global optimization problem. This problem is reduced to a mixed 0-1 linear programming problem and can be solved by an advanced 0-1 solver. Then we show that the quadratic minorants are getting convex as soon as partition elements are getting smaller in diameter. Hence, at the final steps of the branch and bound method we solve convex auxiliary quadratic problems. Therefore, the method accelerates when we are close to the global minimum of the initial problem.Grant: The investigation was supported by the RFBR grant No. 15-07-08986.
Библиографическая ссылка
Khamisov O.V. Optimization with quadratic support functions in nonconvex smooth optimization // AIP Conference Proceedings. 2016. 1 p. ISBN (print): 9 780 735 . DOI: 10.1063/1.4965331
