Branch and Bound Algorithm Using Cutting Angle Method for Global Minimization of Increasing Positively Homogeneous Functions

We consider the problem of globally minimizing an abstract convex function called increasing positively homogeneous (IPH) function over a compact convex subset of an

n

 −dimensional Euclidean space, for short, IPH optimization problem.

A method for solving IPH optimization problems called cutting angle algorithm was proposed by Rubinov and others in 1999. The principle of cutting angle algorithm is a generalization of the cutting plane method for convex programming problems, where the convex objective function is iteratively approximated by the maximum of a family of affine functions defined by its subgradients. In this article, we propose a method for solving IPH optimization problems which is a combination of the cutting angle algorithm with a branch and bound scheme successfully used in global optimization. The lower bounding procedure in the present algorithm is performed by solving ordinary convex (or even linear) programs. From preliminary computational results we hope that the proposed algorithm could work well for some problems with specific structures.