全局求解Minimax线性分式规划的分支定界算法

doi:10.13371/j.cnki.chin.q.j.m.2024.04.005

数学季刊 ›› 2024, Vol. 39 ›› Issue (4): 388-398.doi: 10.13371/j.cnki.chin.q.j.m.2024.04.005

全局求解Minimax线性分式规划的分支定界算法

School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, China

收稿日期:2024-02-27 出版日期:2024-12-30 发布日期:2024-12-30
通讯作者: SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; E-mail:shenpeiping@163.com
作者简介:WANG Hui-man (1999-), female, native of Hebi, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application; SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; LIANG Yu-xin (2000-), female, native of Nanyang, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application.
基金资助:
Supported by the National Natural Science Foundation of China (Grant Nos. 12071133 and 11871196).

Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

School of Mathematics and Statistics, North China University of Water Resources and Electric Power, Zhengzhou 450046, China

Received:2024-02-27 Online:2024-12-30 Published:2024-12-30
Contact: SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; E-mail:shenpeiping@163.com
About author:WANG Hui-man (1999-), female, native of Hebi, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application; SHEN Pei-ping (1964-), female, native of Nanyang, Henan, professor of North China University of Water Resources and Electric Power, Ph.D, engages in optimisation theory and application; LIANG Yu-xin (2000-), female, native of Nanyang, Henan, master student of North China University of Water Resources and Electric Power, engages in optimization theory and application.
Supported by:
Supported by the National Natural Science Foundation of China (Grant Nos. 12071133 and 11871196).

摘要/Abstract

摘要： In this paper, we study the minimax linear fractional programming problem on a non-empty bounded set, called problem (MLFP), and we design a branch and bound algorithm to find a globally optimal solution of (MLFP). Firstly, we convert the problem (MLFP) to a problem (EP2) that is equivalent to it. Secondly, by applying the convex relaxation technique to problem (EP2), a convex quadratic relaxation problem (CQRP) is obtained. Then, the overall framework of the algorithm is given and its convergence is proved, the worst-case iteration number is also estimated. Finally, experimental data are
listed to illustrate the effectiveness of the algorithm.

关键词: Minimax linear fractional programming, Global optimal solution, Branch and bound

Abstract: In this paper, we study the minimax linear fractional programming problem on a non-empty bounded set, called problem (MLFP), and we design a branch and bound algorithm to find a globally optimal solution of (MLFP). Firstly, we convert the problem (MLFP) to a problem (EP2) that is equivalent to it. Secondly, by applying the convex relaxation technique to problem (EP2), a convex quadratic relaxation problem (CQRP) is obtained. Then, the overall framework of the algorithm is given and its convergence is proved, the worst-case iteration number is also estimated. Finally, experimental data are
listed to illustrate the effectiveness of the algorithm.

Key words: Minimax linear fractional programming, Global optimal solution, Branch and bound

中图分类号:

O221.2

王慧满, 申培萍, 梁雨欣. 全局求解Minimax线性分式规划的分支定界算法[J]. 数学季刊, 2024, 39(4): 388-398.

WANG Hui-man, SHEN Pei-ping, LIANG Yu-xin. Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming[J]. Chinese Quarterly Journal of Mathematics, 2024, 39(4): 388-398.

[1]	卿乃侨. 收益率椭球分布不确定下的均值-CVaR优化研究[J]. 数学季刊, 2023, 38(1): 85-96.
[2]	靳正芬, 王朵, 尚有林, 律金曼. 一种求解未知噪音水平的低秩矩阵恢复问题有效算法 [J]. 数学季刊, 2021, 36(4): 356-368.
[3]	李硕, 尚有林, 屈德强. 一个新的无参数填充函数及其在最小二乘法中的应用[J]. 数学季刊, 2021, 36(3): 263-274.
[4]	刘金赞, 屈德强. 求解全局优化问题的一种新的非参数填充函数[J]. 数学季刊, 2021, 36(2): 188-195.
[5]	沈楠, 靳正芬, 王秋雨. 求解低秩列稀疏矩阵恢复问题的嵌套交替方向乘子法[J]. 数学季刊, 2021, 36(1): 90-110.
[6]	屈德强, 吴丹, 尚有林. 求解箱式约束全局优化问题的新的填充函数[J]. 数学季刊, 2020, 35(4): 354-362.
[7]	刘金魁. 一种修正的LS共轭梯度方法及其收敛性[J]. 数学季刊, 2014, 29(1): 142-150.
[8]	赵克全, 陈哲, 杨新民. 强伪不变凸性和强伪不变单调性的等价性[J]. 数学季刊, 2011, 26(4): 608-612.
[9]	孙清滢, 桑兆阳, 田凤婷. 求解无约束非线性规化问题的一个新的重开始三项共轭梯度算法的收敛性[J]. 数学季刊, 2011, 26(1): 69-76.
[10]	杜廷松, 费浦生, 蹇继贵. 解一类运输生产问题修正的松驰型分枝定界算法[J]. 数学季刊, 2010, 25(1): 52-59.
[11]	张和平, 叶留青. 不等式约束最优化问题的可行SQP下降算法及其收敛性[J]. 数学季刊, 2009, 24(3): 469-474.
[12]	朱冬梅, 王治国. 拟单调问题的讨论[J]. 数学季刊, 2006, 21(3): 461-464.
[13]	尚有林, 李晓燕. 无约束全局优化的一个可调参数的填充函数[J]. 数学季刊, 2004, 19(3): 232-239.
[14]	曹丽华, 孙清滢. 结合修正Curry-Altman步长搜索一个新的共轭梯度算法的收敛性[J]. 数学季刊, 2004, 19(2): 198-204.
[15]	孙清滢. 求解无约束非线性规划问题的一个新的重开始共轭梯度算法的收敛性[J]. 数学季刊, 2003, 18(2): 154-162.

全局求解Minimax线性分式规划的分支定界算法

Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

PDF (PC)

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

本文评价