Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

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

Chinese Quarterly Journal of Mathematics ›› 2024, Vol. 39 ›› Issue (4): 388-398.doi: 10.13371/j.cnki.chin.q.j.m.2024.04.005

Previous Articles Next Articles

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

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

CLC Number:

O221.2

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]	QING Nai-qiao. Worst-Case Optimization on Mean-CVaR Ratio with Returns Distribution Ellipsoidal Uncertainty [J]. Chinese Quarterly Journal of Mathematics, 2023, 38(1): 85-96.
[2]	JIN Zheng-fen, WANG Duo, SHANG You-lin, LV Jin-man. An Efficient Algorithm for Low Rank Matrix Restoration Problem with Unknown Noise Level [J]. Chinese Quarterly Journal of Mathematics, 2021, 36(4): 356-368.
[3]	LI Shuo, SHANG You-lin, QU De-qiang, . A Novel Parameter-Free Filled Function and Its Application in Least Square Method [J]. Chinese Quarterly Journal of Mathematics, 2021, 36(3): 263-274.
[4]	LIU Jin-zan, QU De-qiang. A New Non-Parameter Filled Function for Global Optimization Problems [J]. Chinese Quarterly Journal of Mathematics, 2021, 36(2): 188-195.
[5]	SHEN Nan , JIN Zheng-fen , WANG Qiu-yu. Nested Alternating Direction Method of Multipliers to Low-Rank and Sparse-Column Matrices Recovery [J]. Chinese Quarterly Journal of Mathematics, 2021, 36(1): 90-110.
[6]	QU De-qiang, WU Dan, SHANG You-lin. A New Filled Function for Global Optimization Problems with Box Constraints [J]. Chinese Quarterly Journal of Mathematics, 2020, 35(4): 354-362.
[7]	LIU Jin-kui. A Descent Gradient Method and Its Global Convergence [J]. Chinese Quarterly Journal of Mathematics, 2014, 29(1): 142-150.
[8]	ZHAO Ke-quan, CHEN Zhe, YANG Xin-min. The Equivalence about Strongly Pseudoinvexity and Strongly Invariant Pseudomonotonicity [J]. Chinese Quarterly Journal of Mathematics, 2011, 26(4): 608-612.
[9]	SUN Qing-ying, SANG Zhao-yang, TIAN Feng-ting. Global Convergence of a New Restarting Three Terms Conjugate Gradient Method for Non-linear Optimizations [J]. Chinese Quarterly Journal of Mathematics, 2011, 26(1): 69-76.
[10]	DU Ting-song, FEI Pu-sheng, JIAN Ji-gui. Relaxation-strategy-based Modification Branch-and-Bound Algorithm for Solving a Class of Transportation-production Problems [J]. Chinese Quarterly Journal of Mathematics, 2010, 25(1): 52-59.
[11]	ZHANG He-ping, YE Liu-qing. Feasible SQP Descent Method for Inequality Constrained Optimization Problems and Its Convergence [J]. Chinese Quarterly Journal of Mathematics, 2009, 24(3): 469-474.
[12]	ZHU Dong~mei, WANG Zhi-guo. On the Quasi-monotonic Problem [J]. Chinese Quarterly Journal of Mathematics, 2006, 21(3): 461-464.
[13]	SHANG You-lin, LI Xiao-yan. A Filled Function with Adjustable Parameters for Unconstrained Global Optimization [J]. Chinese Quarterly Journal of Mathematics, 2004, 19(3): 232-239.
[14]	CAO Li-hua, SUN Qing-ying. Global Convergence of a New Conjugate Gradient Methods with a Modification of the Curry-Altman Step-size Rule [J]. Chinese Quarterly Journal of Mathematics, 2004, 19(2): 198-204.
[15]	SUN Qing-ying. Global Convergence of a New Restarting Conjugate Gradient Method for Nonlinear Optimizations [J]. Chinese Quarterly Journal of Mathematics, 2003, 18(2): 154-162.

Branch and Bound Algorithm for Globally Solving Minimax Linear Fractional Programming

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics

Comments