(1) Department of Social Engineering, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, 152 Tokyo, Japan;(2) Institute of Human and Social Sciences, Tokyo Institute of Technology, 2-12-1 Oh-Okayama, Meguro-ku, 152 Tokyo, Japan
Abstract:
This paper addresses itself to the algorithm for minimizing the product of two nonnegative convex functions over a convex set. It is shown that the global minimum of this nonconvex problem can be obtained by solving a sequence of convex programming problems. The basic idea of this algorithm is to embed the original problem into a problem in a higher dimensional space and to apply a branch-and-bound algorithm using an underestimating function. Computational results indicate that our algorithm is efficient when the objective function is the product of a linear and a quadratic functions and the constraints are linear. An extension of our algorithm for minimizing the sum of a convex function and a product of two convex functions is also discussed.