Global Optimization Algorithm for a Class of Mathematical Problems
Author(s):
J. T. Wan, C. Y. Bai, & J. B. Yin
Affiliation(s):
School of Mathematical Sciences, Henan Institute of Science and Technology, Xinxiang, 453003, China, *Email: [email protected]
ABSTRACT: This article presents an effective branch and bound algorithm for globally solving a class of mathematical problems by using linear relaxation approach. By utilizing character of bilinear function, a sequence of linear relaxation programming (RLP) of the initial mathematical problem (P) are derived which are embedded in a branch and bound framework. The proposed algorithm will be convergent to the global optimal solution by means of the subsequent solutions of a sequence of linear programming problems. Numerical computational experiments are given to demonstrate the feasibility of our approach.
Keywords : Branch and bound algorithm; Global optimization; Linear relaxation programming
[1] H.Konno, T.Kuno, Linear multiplicative programming, Math. Program, vol. 56, 1992, pp. 51-64.
[2] H. Konno, H. Watanabe, Bond Portfolio Optimization Problems and Their Applications to Index Tracking, Journal of the Operation Reseach Social of Japan, vol. 39, 1994, pp. 295-306.
[3] I.Quesada and I.E.Grossmann, Alternative bounding approximations for the global optimization of various engineering design problems. In I.E. Grossmann, (ed.), Global Optimization inEngineering Design, Nonconvex Optimization and Its Applications, Kluwer Academic Publishers,Norwell, MA, vol. 9, 1996, pp. 309-331.
[4] C. D. Maranas, I. P. Androulakis, C. A. Floudas, A. J. Berger and J. M. Mulvey, Solving long-term financial planning problems via global optimization, J. Economic Dynamics & Control, vol. 21, 1997, pp. 1405-1425.
[5] J. M. Henderson, and R.E. Quandt, Microeconomic Theory. 2nd edition, McGraw-Hill, New York, 1971.
[6] J. M. Mulvey, R. J. Vanderbei and S. A. Zenios, Robust optimization of large-scale systems, Oper. Res., vol. 43, 1995, pp. 264-281.
[7] T. Matsui, NP-Hardness of Linear Multiplicative Programming and Related Problems, Journal of Global Optimization, vol. 9, 1996, pp. 113-119.
[8] H. Konno, and T. Kuno, Linear Multiplicative Programming, Mathematical Programming, vol. 56, 1992, pp. 51-64.
[9] H. Swarup, Programming with Inde_nite Quadratic Function with Linear Constraints, Cahier du Coutre d’Etudes de Recherche Operationelle, vol. 8, 1966, pp. 223-234.
[10] H.M.Li, K.C.Zhang, A decomposition algorithm for solving large-scale quadratic programming problems, Applied Mathematics and Computation, vol. 173, no. 1,2006, pp. 394-403.
[11] H. Wu, K. Zhang, A new accelerating method for global non-convex quadratic optimization with non-convex quadratic constraints, Applied Mathematics and Computation, vol.197, no. 2, 2008, pp. 810-818.
[12] H.-W. Jiao, S.-Y. Liu, Y.-F. Zhao, Effective algorithm for solving the generalized linear multiplicative problem with generalized polynomial constraints, Applied Mathematical Modelling, vol. 39, 2015, pp. 7568-7582.
[13] S.T.Liu, R.T.Wang, A numerical solution method to interval quadratic programming, Applied Mathematics and Computation, vol. 189, no. 2, 2007, pp. 1274-1281.
[14] P.Shen, M.Gu, A duality-bounds algorithm for non-convex quadratic programs with additional multiplicative constraints, Applied Mathematics and Computation, vol. 198, no. 1, 2008, pp. 1-11.
[15] P. Shen, Y. Duan, Y. Ma, A robust solution approach for nonconvex quadratic programs with additional multiplicative constraints, Applied Mathematics and Computation, vol. 201, no. 1-2, pp. 514-526, 2008.
[16] H.Konno, K.Fukaishi, A Branch and Bound Algorithm for Solving Low Rank Linear Multiplicative and Fractional Programming Problems, Journal of Global Optimization, vol. 8,2000, pp. 283-299.
[17] H. S. Ryoo and N. V.sahinidis, Global Optimization of Multiplicative Programs, Journal of Global Optimization, vol. 26, 2003, pp. 387-418.
[18] C. Xue, H. Jiao,et al., An approximate algorithm for solving generalized linear multiplicative programming, Journal of Henan Normal University (Natural Science), vol. 36, no. 5, 2008, pp. 13-15.
[19] H.Tuy, N.D.Nghia. Reverse Polyblock Approximation for Generalized Multiplicative/Fractional Programming, VN Journal of Mathematics, vol. 31,2003, pp. 391-402.
[20] S. Schaible and C. Sodini, Finite algorithm for generalized linear multiplicative programming, Journal of Optimization Theory and Applications, vol. 87, no. 2, 1995, pp. 441-455.
[21] Y. Gao, C. Xu, Yongjian Yang, An outcome-space finite algorithm for solving linear multiplicative programming, Applied Mathematics and Computation, vol. 179, no. 2, 2006, pp. 494-505.
[22] H.-W. Jiao, Y.-Q. Chen, W.-X. Cheng, A Novel Optimization Method for Nonconvex Quadratically Constrained Quadratic Programs, Abstract and Applied Analysis, Volume 2014, Article ID 698489, 11 pages, doi:10.1155/2014/698489.
[23] R. M. Oliveira, and P. A. V. Ferreira, An Outcome Space Approach for Generalized Convex Multiplicative Programs, Journal of Global Optimization, vol. 47, 2010, pp. 107-118.
[24] A. M. Ashtiani, P. A. V. Ferreira, Global Maximization of a Generalized Concave Multiplicative Problem in the Outcome Space, Anais do CNMAC, vol. 3, 2010, pp. 377-383.
[25] H. Jiao, et al., Global optimization algorithm for sum of generalized polynomial ratios problem, Applied Mathematics Modelling, Vol. 37, no. 1-2, 2013, pp. 187-197.
[26] H. P. Benson and G.M. Boger, Outcome-space cutting-plane algorithm for linear multiplicative programming, Journal of Optimization Theory and Applications, vol. 104, no. 2, 2000, pp. 301-322.
[27] X. J. Liu, T. Umegaki, and Y. Yamamoto, Heuristic methods for linear multiplicative programming, Journal of Global Optimization, vol. 4, no. 15, 1999, pp. 433-447.
[28] H. Jiao, S. Liu, Range division and compression algorithm for quadratically constrained sum of quadratic ratios, Computational and Applied Mathematics, 2015, DOI: 10.1007/s40314-015-0224-5.
[29] N.T.H. Phuong, and H. Tuy, A unified monotonic approach to generalized linear fractional programming, Journal of Global Optimization, vol. 26, 2003, pp. 229-259.
[30] Y. Chen, H. Jiao, A nonisolated optimal solution of general linear multiplicative programming problems, Computers & Operations Research, vol. 36, 2009, pp. 2573-2579.
[31] W. Chun-Feng, L. San-Yang, S. Pei-Ping, Global minimization of a generalized linear multiplicative programming, Appl. Math. Modelling, doi: 10.1016/j.apm.2011.09.002, 2011.
[32] H. Jiao, Y. Chen, A Global Optimization Algorithm for Generalized Quadratic Programming, Journal of Applied Mathematics, Volume 2013, Article ID: 215312, DOI: 10.1155/2013/215312.
[33] T. Kuno, H. Konno, A Parametric Successive Underestimation Method for Convex Multiplicative Programming Problems, J. of Global Optimization, vol. 1, 1991, pp. 267-286.
[34] P. Shen, H. Jiao, Linearization method for a class of multiplicative programming with exponent, Applied Mathematics and Computation, vol. 183, no. 1, 2006, pp. 328-336.
[35] C.-F. Wang, S.-Y. Liu, A new linearization method for generalized linear multiplicative programming, Computers & Operations Research, vol. 38, 2011, pp. 1008-1013.
[36] H. Jiao, Y.R. Guo, P. Shen, Global optimization of generalized linear fractional programming with nonlinear constraints, Applied Mathematics and Computation, vol. 183, no. 2, 2006, pp. 717-728.
[37] H. Jiao, A branch and bound algorithm for globally solving a class of nonconvex programming problems, Nonlinear Analysis: Theory, Methods & Applications, vol. 70, 2009, pp. 1113-1123.
[38] P. Shen, X. Bai, W. Li, A new accelerating method for globally solving a class of nonconvex programming problems, Nonlinear Analysis: Theory, Methods & Applications, vol. 71, no. 7-8, 2009, pp. 2866-2876.
[39] H. P. Benson, Global Maximization of a Generalized Concave Multiplicative Function, Journal of Optimization Theory and Application, vol. 137, 2008, pp. 105-120.
[40] H. Konno, T. Kuno, and Y. Yajima, Global Minimization of a Generalized Convex Multiplicative Function, Journal of Global Optimization, vol. 4, 1994, pp. 47-62.
[41] B. Jaumard, C. Meyer, H. Tuy, Generalized Convex Multiplicative Programming via Quasiconcave Minimization, Journal of Global Optimization, vol. 10, 1997, pp. 229-256.
[42] H. Jiao, S. Liu, N. Lu, A parametric linear relaxation algorithm for globally solving nonconvex quadratic programming, Applied Mathematics and Computation, vol. 250, 2015, pp. 973-985.