An Accelerating Algorithm for Linear Multiplicative Programming Problem

Abstract

By reformulating the linear multiplicative programming problem (LMP) as an equivalent nonconvex programming problem (EP), we present a new accelerating outcome space branch-and-bound algorithm for globally solving the problem (LMP). Firstly, a linear relaxed programming problem is constructed, which can be used to compute the lower bound of the global optimal value of the problem (EP). Then, by subsequently subdividing the initial outcome space rectangle, and by solving a series of linear relaxed programming problems, the global optimal solution of the problem (LMP) can be obtained. It's worth mentioning that a new region reducing method and a new linear relaxed programming with a higher degree of tightness are also constructed to improve the computational efficiency in the presented algorithm. The global convergence of the presented algorithm is established, and its computational complexity is estimated. Finally, the numerical tests indicate that the presented algorithm has the higher computational efficiency than the known algorithms.

Keywords

• Linear multiplicative programming
• region reducing method
• improving compactness technique
• linear relaxed programming
• branch-and-bound algorithm