Global algorithm for a class of multiplicative programs using piecewise linear approximation technique

被引：0
作者：
Zhisong Hou
Sanyang Liu
机构：
[1] Xidian University,School of Computer Science and Technology
[2] Xidian University,School of Mathematics and Statistics
来源：
Numerical Algorithms | 2023年 / 92卷
关键词：
Multiplicative programs; Global optimization; Piecewise linear approximation technique; Branch-and-bound; Accelerating technique;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
This paper presents an efficient algorithm for solving a class of multiplicative programs (MP). For obtaining the global optimal solution of the problem (MP), we first transform the problem (MP) into the equivalent problem (EP) by introducing auxiliary variables. Next, using the new piecewise linear approximation technique, the problem (EP) is systematically converted into a series of linear relaxation programming problems (RP) for obtaining the lower bound of the optimal value for the problem (EP). Then, according to the characteristics of the problem (EP) and the structure of the branch-and-bound framework, some outer space accelerating techniques are constructed to improve the speed of the convergence of the algorithm. Furthermore, by analyzing the computational complexity of the algorithm, we give an estimation for the maximum iterations of the algorithm. Finally, numerical results are reported to demonstrate the effectiveness and robustness of the algorithm.
引用
收藏
页码：1063 / 1082
页数：19
相关论文
共 67 条
  • [11] TreanŢă S(1995)Robust optimization of large-scale systems Oper. Res. 43 264-281
  • [12] Cambini R(2014)Range division and contraction algorithm for a class of global optimization problems Appl. Math. Comput. 242 116-126
  • [13] Sodini C(2005)Decomposition branch-and-bound based algorithm for linear programs with additional multiplicative constraints J. Optim. Theory Appl. 126 41-61
  • [14] Cambini R(1999)Heuristic methods for linear multiplicative programming J. Glob. Optim. 15 433-447
  • [15] Sodini C(1995)Finite algorithm for generalized linear multiplicative programming J. Optim. Theory Appl. 87 441-455
  • [16] Mulvey JM(2000)Outcome-space cutting-plane algorithm for linear multiplicative programming J. Optim. Theory Appl. 104 301-322
  • [17] Vanderbei RJ(1991)Parametric simplex algorithms for solving a special class of nonconvex minimization problems J. Glob. Optim. 1 65-81
  • [18] Zenios SA(1994)Global minimization of a generalized convex multiplicative function J. Glob. Optim. 4 47-62
  • [19] Shen P(1991)A global optimization approach for solving the convex multiplicative programming problem J. Glob. Optim. 1 341-357
  • [20] Yang L(2016)An efficient algorithm for globally solving generalized linear multiplicative programming J. Comput. Appl. Math. 296 840-847
1234567