The hill detouring method for minimizing hinging hyperplanes functions

This paper studies the problem of minimizing hinging hyperplanes (HH) which is a widely applied nonlinear model. To deal with HH minimization, we transform it into a d.c. (difference of convex functions) programming and a concave minimization on a polyhedron, then some mature techniques are applicable. More importantly, HH is a continuous piecewise linear function and for concave HH, the super-level sets are polyhedra. Inspired by this property, we establish a method which searches on the counter map in order to escape a local optimum. Intuitively, this method bypasses the super-level set and is hence called hill detouring method, following the name of hill climbing. In numerical experiments, the proposed algorithm is compared with CPLEX and a heuristic algorithm showing its effectiveness.