Global optimization algorithm for solving linear multiplicative programming problems. (3rd June 2022)

• Record Type: Journal Article
• Authors: Shen, Peiping; Wang, Kaimin; Lu, Ting
• Is Part Of: Optimization. Volume 71:Number 6(2022)
• Page Start: 1421
• Page End: 1441
• Publication Date: 2022-06-03
• Subjects: Global optimization -- linear multiplicative programming -- branch and bound -- linear relaxation technique -- computational complexity; 90C30 -- 90C33 -- 90C15; Mathematical optimization -- Periodicals; 519.7
• DOI: 10.1080/02331934.2020.1812603
• Languages: English
• ISSNs: 0233-1934

Abstract

Abstract : In this paper, a class of linear multiplicative problems (LMP) are considered, which cover many applications and are known to be NP-hard. For finding the globally optimal solution to problem (LMP) with a pre-specified ε -tolerance, problem (LMP) is first transformed into an equivalent problem (EP) via introducing the variable transformation. And, a novel linear relaxation technique is presented by exploiting the special structure of problem (EP), for deriving the linear relaxation programming which can be used to acquire the upper bound of the optimal value to problem (EP). A branch and bound algorithm is then located for globally solving problem (LMP). The convergence of the algorithm is established and its computational complexity is estimated. Finally, numerical results are reported to illustrate the feasibility and efficiency of the proposed algorithm.