A modified hill detouring algorithm for hinging hyperplanes minimization

摘要

This paper considers the global optimization of hinging hyperplanes (HH), which is a widely applied nonlinear model. HH minimization can be equivalently transformed into difference of convex functions (D.C.) programming, and further, concave optimization over a polyhedron. Motivated by a novel algorithm called Hill Detouring (HD), we present a modified hill detouring (MHD) algorithm. The proposed algorithm escapes local optima efficiently with a new search strategy, and establishes an exact stopping criterion for global optimality based on the theory of γ valid cut. In the numerical experiments, MHD is compared with mixed integer programming (MIP) and HD, which shows its superior performance on the numerical efficiency and the global search capability.