• 论文 • 上一篇    下一篇

一类线性乘积规划问题的分支定界缩减方法

高岳林1,2, 井霞3   

  1. 1. 北方民族大学 信息与系统科学研究所, 银川 750021;
    2. 宁夏大学 数学计算机学院, 银川 750021;
    3. 宁夏大学 数学计算机学院, 银川 750021
  • 收稿日期:2012-09-11 出版日期:2013-02-15 发布日期:2013-01-22
  • 基金资助:

    国家自然科学基金项目(11161001)资助.

高岳林, 井霞. 一类线性乘积规划问题的分支定界缩减方法[J]. 计算数学, 2013, 35(1): 89-98.

Gao Yuelin, Jing Xia. A BRANCH-AND-BOUND REDUCED ALGORITHM FOR SOLVING A CLASS OF LINEAR MULTIPLICATIVE PROGRAMMING PROBLEMS[J]. Mathematica Numerica Sinica, 2013, 35(1): 89-98.

A BRANCH-AND-BOUND REDUCED ALGORITHM FOR SOLVING A CLASS OF LINEAR MULTIPLICATIVE PROGRAMMING PROBLEMS

Gao Yuelin1,2, Jing Xia3   

  1. 1. Institute of Information and System Science, Beifang University for Nationalities, Yinchuan 750021, China;
    2. School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, China;
    3. School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, China
  • Received:2012-09-11 Online:2013-02-15 Published:2013-01-22
提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.
A branch-and-bound reduced method is proposed for globally solving a class of linear multiplicative programming problems and the convergence of the algorithm is proved. In this algorithm, the lower bound functions on the multiplications in the constraints and the objective functions are given by using the convex envelopes technique of the two-vector multiplications so as to determine a relaxed convex programming of the original problem. We solve the relaxed convex programming to find the global optimization value's lower bound the feasible solutions of the original problem.In order to improve convergence rate, a rectangular reduction strategy is used. Numerical experiments show that the proposed algorithm is feasible.

MR(2010)主题分类: 

()
[1] Marinas C D, Andreoulakis I P, Floudas C.A. Solving long term financial planning problems viaglobal optimization[J]. Journal of Economic Dynamics and Control, 1997, 21: 1405-1425.

[2] Mulvey J M, Vanderbei R J, Zenios S A. Robust optimization of large-scale system[J]. OperationsResearch, 1995, 43: 264-281.

[3] Donnish M C, Salinities N V. Global optimization algorithms for chip design andcompaction[J].Engineering Optimization, 1995, 25(2): 131-154.

[4] Kuno T. Globally determining a minimun-aera rectangle enclosing the projection of a higherdimensional Set[J]. Operations Research Letters, 1993, 13: 295-303.

[5] Bennett K P and Mangasarian. Bilinear separation of two sets in n-space[J]. ComputationalOptimization and Application, 1994, 2: 207-227.

[6] Kuno T, Yajima Y, and Konno H. An outer approximation method for minimizing the product ofseveral convex functions on a convex set[J]. Journal of Global optimization, 1993, 3(3): 325-335.

[7] Benson H P. Decomposition branch and bound based algorithm for linear programs with additionalmultiplicative constraints[J]. Journal of Optimization Theory and Applications, 2005,126(1): 41-46.

[8] Flippo O E Rinnoy K. A note on Benders decomposion in mixed-integer quadratic programming[J]. Operations Research Letters, 1990, 9: 81-83.

[9] Stabile S, Sodini C. Finite algorithm for generalized linear multiplicative programming[J]. Journalof Optimization Theory and Applications, 1995, 87(2): 441-455.

[10] Benson H P, Boger G M. Outcome-space cutting-plane algorithm for linear multiplicative programming[J]. Journal of Optimization Theory and Applications, 2001, 104(2): 301-322.

[11] 高岳林, 邓光智.凹二次规划问题的一个融合割平面方法的分支定界混合算法[J].工程数学学报, 2008, 25(4): 23-30.

[12] Shen Peiping, Jiao Hongwei. Linearization method for a class of multiplicative programmingwith exponent[J]. Applied Mathematics and Computation, 2006, 183: 328-336.

[13] Gao Yuelin, Wu Guorong, Ma Weiming. A new global optimization approach for convex multiplicativeprogramming[J]. Applied Mathematics and Computation, 2010, 216: 1206-1218.

[14] 黄红选译.全局优化引论[M]. 北京: 清华大学出版社, 2003, 9.

[15] Kuno T. A finite branch and bound algorithm for generalized linear multiplicative programming[J]. Computational Optimization and Application, 2001, 20: 119-135.
[1] 高岳林, 张博. 线性比式和规划问题的输出空间分支定界算法[J]. 计算数学, 2020, 42(2): 207-222.
[2] 高岳林, 魏飞. 一类非负二次整数规划问题的分支定界缩减方法[J]. 计算数学, 2011, 33(3): 233-248.
[3] 高岳林, 李会荣. 非线性约束优化问题的混合粒子群算法[J]. 计算数学, 2010, 32(2): 135-146.
[4] 彭拯,邬冬华,田蔚文,. 约束全局最优化的水平值估计算法[J]. 计算数学, 2007, 29(3): 293-304.
阅读次数
全文


摘要