PIECEWISE LINEAR RELAXATION METHOD FOR GLOBALLY SOLVING A CLASS OF MULTIPLICATIVE PROBLEMS

摘要

This paper presents an image space branch-and-bound algorithm for globally solving a class of multiplicative problems (MP). In the algorithm, by introducing new variables and the logarithmic trans-formation, we firstly transform the problem (MP) into an equivalent problem (EP1). Next, by using the properties of the logarithmic function, we propose a piecewise linear relaxation method for constructing the linear relaxation problem of the problem (EP1), which can be used to compute the lower bound of the optimal value of the problem (EP1). Furthermore, to improve the convergence speed of the algorithm, some image space region reduction techniques are added into the branch-and-bound algorithm. Finally, the global convergence of the algorithm is proved and the maximum number of iterations of the algorithm is estimated by analyzing its computational complexity, and numerical results show the feasibility and validity of the algorithm.