<p>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 <i>ϵ</i>-optimal solutions for test instances.</p>

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

A global optimization approach utilizing convex relaxation for linear multiplicative programming problems

  • Bo Zhang,
  • Suxia Ma,
  • Kai Cao

摘要

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.