计算数学
       首页 |  期刊介绍 |  编委会 |  投稿指南 |  期刊订阅 |  下载中心 |  留言板 |  联系我们 |  在线办公 | 
计算数学  2013, Vol. 35 Issue (1): 89-98    DOI:
论文 最新目录 | 下期目录 | 过刊浏览 | 高级检索 Previous Articles  |  Next Articles  
一类线性乘积规划问题的分支定界缩减方法
高岳林1,2, 井霞3
1. 北方民族大学 信息与系统科学研究所, 银川 750021;
2. 宁夏大学 数学计算机学院, 银川 750021;
3. 宁夏大学 数学计算机学院, 银川 750021
A BRANCH-AND-BOUND REDUCED ALGORITHM FOR SOLVING A CLASS OF LINEAR MULTIPLICATIVE PROGRAMMING PROBLEMS
Gao Yuelin1,2, Jing Xia3
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
 全文: PDF (434 KB)   HTML (1 KB)   输出: BibTeX | EndNote (RIS)      背景资料
摘要 提出了求解一类线性乘积规划问题的分支定界缩减方法, 并证明了算法的收敛性.在这个方法中, 利用两个变量乘积的凸包络技术, 给出了目标函数与约束函数中乘积的下界, 由此确定原问题的一个松弛凸规划, 从而找到原问题全局最优值的下界和可行解. 为了加快所提算法的收敛速度, 使用了超矩形的缩减策略. 数值结果表明所提出的算法是可行的.
服务
把本文推荐给朋友
加入我的书架
加入引用管理器
E-mail Alert
RSS
作者相关文章
关键词全局最优化   线性乘积规划问题   分支定界   松弛凸规划   超矩形缩减策略     
Abstract: 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.
Key wordsglobal optimization   linear multiplicative programming   branch-and-bound   relaxed convex programming   hyper-rectangle reduced strategy   
收稿日期: 2012-09-11;
基金资助:

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

引用本文:   
. 一类线性乘积规划问题的分支定界缩减方法[J]. 计算数学, 2013, 35(1): 89-98.
. A BRANCH-AND-BOUND REDUCED ALGORITHM FOR SOLVING A CLASS OF LINEAR MULTIPLICATIVE PROGRAMMING PROBLEMS[J]. Mathematica Numerica Sinica, 2013, 35(1): 89-98.
 
[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]. 计算数学, 2011, 33(3): 233-248.
[2] 高岳林, 李会荣. 非线性约束优化问题的混合粒子群算法[J]. 计算数学, 2010, 32(2): 135-146.
[3] 彭拯,邬冬华,田蔚文,. 约束全局最优化的水平值估计算法[J]. 计算数学, 2007, 29(3): 293-304.

Copyright 2008 计算数学 版权所有
中国科学院数学与系统科学研究院 《计算数学》编辑部
北京2719信箱 (100190) Email: gxy@lsec.cc.ac.cn
本系统由北京玛格泰克科技发展有限公司设计开发
技术支持: 010-62662699 E-mail:support@magtech.com.cn
京ICP备05002806号-10