A global optimization approach utilizing convex relaxation for linear multiplicative programming problems
摘要
Linear multiplicative programming (LMP) has emerged in fields such as engineering practice and management science and belongs to the class of NP-hard problems. This paper presents an efficient global algorithm for solving a class of LMP problems. The new algorithm mainly employs the proposed novel quadratic convex relaxation and the branch-and-bound framework. First, a novel transformation technique is proposed to convert LMP into an equivalent problem with several linear fractional inequality constraints. Leveraging the inherent structure of these constraints, we handle the non-convex objective function by constructing a quadratic convex relaxation problem. Second, the convergence of the proposed algorithm is analyzed, and its worst-case number of iterations is provided. Finally, extensive numerical experiments demonstrate the efficiency and advantages of the algorithm in obtaining global ϵ-optimal solutions for test instances.