Outer space branch and bound algorithm for solving linear multiplicative programming problems
Tóm tắt
In this paper, we consider a linear multiplicative programming problem (LMP) that is known to be NP-hard even with one product term. We first introduce the auxiliary variables to obtain an equivalent problem of problem LMP. An outer space branch and bound algorithm is then designed, which integrates some basic operations such as the linear relaxation technique, branching rule and region reduction technique. The global convergence of the proposed algorithm is established by means of the subsequent solutions of a series of linear programming problems, and its computational complexity is estimated on the basis of the branching rule. Also, we discuss the relationship between the proposed linear relaxation and existing relaxations for LMP. Finally, preliminary numerical results demonstrate the proposed algorithm can efficiently find the globally optimal solutions for test instances.
Tài liệu tham khảo
Tuy, H.: Convex Analysis and Global Optimization, 2nd edn. Kluwer Academic, Dordrecht (2016)
Zhao, Y., Liu, S.: Global optimization algorithm for mixed integer quadratically constrained quadratic program. J. Comput. Appl. Math. 319, 159–169 (2017)
Konno, H., Yajima, Y.: Solving rank two bilinear programs by parametric simplex algorithms. Technical Report IHSS Report 90-17, Institute of Human And Social Sciences, Tokyo Institute of Technology (1990)
Raghavachari, M.: On connections between zero-one integer programming and concave programming under linear constraints. Oper. Res. 17, 680–684 (1969)
Quesada, I., Grossmann, I.E.: Alternative bounding applications for the global optimization of various engineering design problems. Glob. Optim. Eng. Des. Nonconvex Optim. Appl. 9, 309–331 (1996)
Konno, H., Inori, M.: Bond portfolio optimization by bilinear fractional programming. J. Oper. Res. Soc. Jpn. 32, 143–158 (1988)
Konno, H., Wantanabe, H.: Bond portfolio optimization problems and their applications to index tracking. J. Oper. Res. Soc. Jpn. 39(3), 295–306 (1994)
Wang, C., Liu, K.: An improved particle optimization algorithm based on comparative judgement. Nat. Comput. 17, 641–661 (2018)
Maranas, C., Androulakis, I., Flounda, C., Berger, A., Mulvey, J.: Solving long-term financial planning problems via global optimization. J. Econ. Dyn. Control 21, 1405–1425 (1997)
Shen, P., Li, X.: Branch-reduction-bound algorithm for generalized geometric programming. J. Glob. Optim. 56, 1123–1142 (2013)
Shen, P., Yang, L., Liang, Y.: Range division and contraction algorithm for a class of global optimization problems. Appl. Math. Comput. 242, 116–126 (2014)
Pei, Y., Zhu, D.: Local convergence of a trust-region algorithm with line search filter technique for nonlinear constrained optimization. Appl. Math. Comput. 273, 797–808 (2016)
Qu, S., Zhou, Y., Zhang, Y., Wahab, M.I.M., Zhang, G., Ye, Y.: Optimal strategy for a green supply chain considering shipping policy and default risk. Comput. Ind. Eng. 131, 172–186 (2019)
Bennett, K.P.: Global tree optimization: a non-greedy decision tree algorithm. Comput. Sci. Stat. 26, 156–160 (1994)
Dorneich, M., Sahinidis, N.: Global optimization algorithms for chip design and compaction. Eng. Optim. 25(2), 131–154 (1995)
Mulvey, J., Vanderbei, R., Zenios, S.: Robust optimization of large-scale systems. Oper. Res. 43, 264–281 (1995)
Cambini, A., Martein, L.: Generalized Convexity and Optimization: Theory and Applications. Springer, Berlin (2009)
Cambini, R., Sodini, C.: On the minimization of a class of generalized linear functions on a flow polytope. Optimization 63(10), 1449–1464 (2014)
Cambini, R., Sodini, C.: A unifying approach to solve some classes of rank-three multiplicative and fractional programs involving linear functions. Eur. J. Oper. Res. 207(1), 25–29 (2010)
Jiao, H., Liu, S.: An efficient algorithm for quadratic sum-of-ratios fractional programs problem. Numer. Funct. Anal. Optim. 38(11), 1426–1445 (2017)
Jiao, H., Liu, S.: Range division and compression algorithm for quadratically constrained sum of quadratic ratios. Comput. Appl. Math. 36(1), 225–247 (2017)
Schaible, S., Sodini, C.: Finite algorithm for generalized multiplicative programming. J. Optim. Theory Appl. 87(2), 441–455 (1995)
Oliveira, Rúbia M., Ferreira, P.A.V.: An outcome space approach for generalized convex multiplicative programs. J. Glob. Optim. 47(1), 107–118 (2010)
Shen, P., Wang, C.: Linear decomposition approach for a class of nonconvex programming problems. J. Inequal. Appl. 2017(1), 74 (2017)
Shen, P., Huang, B., Wang, L.: Range division and linearization algorithm for a class of linear ratios optimization problems. J. Comput. Appl. Math. 350, 324–342 (2019)
Benson, H., Boger, G.: Outcome-space cutting-plane algorithm for linear multiplicative programming. J. Optim. Theory Appl. 104, 301–332 (2000)
Chen, Y., Jiao, H.: A nonisolated optimal solution of general linear multiplicative programming problems. Comput. Oper. Res. 36, 2573–2579 (2009)
Yang, L., Shen, P., Pei, Y.: A global optimization approach for solving generalized nonlinear multiplicative programming problem. Abstr. Appl. Anal. (2014). https://doi.org/10.1155/2014/641909
Ryoo, H.S., Sahinidis, N.V.: Global optimization of multiplicative programs. J. Glob. Optim. 26, 387–418 (2003)
Wang, C., Liu, S., Shen, P.: Gobal minmization of a generalized linear multipicative programming. Appl. Math. Model. 36, 2446–2451 (2012)
Zhao, Y., Liu, S.: An efficient method for generalized linear multiplicative programming problem with multiplicative constraints. SpringerPlus (2016). https://doi.org/10.1186/s40064-016-2984-9
Zhao, Y., Zhao, T.: Global optimization for generalized linear multiplicative programming using convex relaxation. Math. Probl. Eng. (2018). https://doi.org/10.1155/2018/9146309
Liu, S., Zhao, Y.: An efficient algorithm for globally solving generalized linear multiplicative programming. J. Comput. Appl. Math. 296, 840–847 (2016)
Cambini, R., Sodini, C.: Global optimization of a rank-two nonconvex program. Math. Methods Oper. Res. 71(1), 165–180 (2010)
Jiao, H., Liu, S., Chen, Y.: Global optimization algorithm of a generalized linear multiplicative programmin. J. Appl. Math. Comput. 40, 551–568 (2012)
Gao, Y., Xu, C., Yang, Y.: Outcome-space branch and bound algorithm for solving linear multiplicative programming. Comput. Intell. Secur. 3801, 675–681 (2005)
Zhou, X., Cao, B., Wu, K.: Gobal optimization method for linear multiplicative programming. Acta Math. Appl. Sin. 31(2), 325–334 (2015)
Wang, C., Bai, Y., Shen, P.: A practicable branch-and-bound algorithm for globally solving multiplicative programming. Optimization 66(3), 397–405 (2017)
Shen, P., Huang, B.: Global algorithm for solving linear multiplicative programming problems. Optim. Lett. 14, 693–710 (2020)
Sherali, H.D., Adams, W.P.: A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, p. 790. Springer, Berlin (1998)
Vandenberghe, L., Boyd, S.: Semidefinite programming. SIAM Rev. 38(1), 49–95 (1996)
Anstreicher, K.M.: Semidefinite programming versus the reformulation-linearization technique for nonconvex quadratically constrained quadratic programming. J. Glob. Optim. 43, 471–484 (2009)
Zheng, X., Sun, X., Li, D.: Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations. J. Glob. Optim. 50, 695–712 (2011)
Burer, S.: Optimizing a polyhedral-semidefinite relaxation of completely positive programs. Math. Program. Comput. 2(1), 1–19 (2010)
An, Le Thi Hoai, Tao, Pham Dinh: Solving a class of linearly constrained indefinite quadratic problems by D.C. algorithms. J. Glob. Optim. 11, 253–285 (1997)
Sahinidis, N.V.: BARON: a general purpose global optimization software package. J. Glob. Optim. 8, 201–205 (1996)
Grant, M., Boyd, S.: CVX: Matlab software for disciplined convex programming, version 2.1 (2018). http://cvxr.com/cvx
IBM ILOG CPLEX: IBM ILOG CPLEX 12.3 User’s Manual for CPLEX, 89 (2011)
Goyal, V., Genc-Kaya, L., Ravi, R.: An FPTAS for minimizing the product of two non-negative linear cost functions. Math. Program. 126, 401–405 (2011)
Matsui, T.: NP-hardness of linear multiplicative programming and related problems. J. Glob. Optim. 9(2), 113–119 (1996)