no. 3
Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems
RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1533-1552

This paper presents an image space branch-reduction-bound algorithm for solving a class of multiplicative problems (MP). First of all, by introducing auxiliary variables and taking the logarithm of the objective function, an equivalent problem (EP) of the problem (MP) is obtained. Next, by using a new linear relaxation technique, the parametric linear relaxation programming (PLRP) of the equivalence problem (EP) can be established for acquiring the lower bound of the optimal value to the problem (EP). Based on the characteristics of the objective function of the equivalent problem and the structure of the branch-and-bound algorithm, some region reduction techniques are constructed for improving the convergence speed of the algorithm. Finally, the global convergence of the algorithm is proved and its computational complexity is estimated, and numerical experiments are reported to indicate the higher computational performance of the algorithm.

Reçu le :
Accepté le :
Première publication :
Publié le :
DOI : 10.1051/ro/2022061
Classification : 90C26
Keywords: Multiplicative problem, global optimization, branch-and-bound algorithm, image space region reduction technique, computational complexity 
@article{RO_2022__56_3_1533_0,
     author = {Jiao, Hongwei and Wang, Wenjie and Yin, Jingben and Shang, Youlin},
     title = {Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems},
     journal = {RAIRO. Operations Research},
     pages = {1533--1552},
     year = {2022},
     publisher = {EDP-Sciences},
     volume = {56},
     number = {3},
     doi = {10.1051/ro/2022061},
     mrnumber = {4440014},
     zbl = {1492.90136},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ro/2022061/}
}
TY  - JOUR
AU  - Jiao, Hongwei
AU  - Wang, Wenjie
AU  - Yin, Jingben
AU  - Shang, Youlin
TI  - Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems
JO  - RAIRO. Operations Research
PY  - 2022
SP  - 1533
EP  - 1552
VL  - 56
IS  - 3
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ro/2022061/
DO  - 10.1051/ro/2022061
LA  - en
ID  - RO_2022__56_3_1533_0
ER  - 
%0 Journal Article
%A Jiao, Hongwei
%A Wang, Wenjie
%A Yin, Jingben
%A Shang, Youlin
%T Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems
%J RAIRO. Operations Research
%D 2022
%P 1533-1552
%V 56
%N 3
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ro/2022061/
%R 10.1051/ro/2022061
%G en
%F RO_2022__56_3_1533_0
Jiao, Hongwei; Wang, Wenjie; Yin, Jingben; Shang, Youlin. Image space branch-reduction-bound algorithm for globally minimizing a class of multiplicative problems. RAIRO. Operations Research, Tome 56 (2022) no. 3, pp. 1533-1552. doi: 10.1051/ro/2022061

[1] K. P. Bennett, Global tree optimization: a non-greedy decision tree algorithm. Comput. Sci. Stat. 26 (1994) 156–160.

[2] H. P. Benson and G. M. Boger, Outcome-space cutting-plane algorithm for linear multiplicative programming. J. Optim. Theory App. 104 (2000) 301–322. | MR | Zbl | DOI

[3] A. Cambini and L. Martein, Generalized Convexity and Optimization: Theory and Applications. Lecture Notes in Economics and Mathematical Systems. Springer (2009). | MR | Zbl

[4] R. Cambini and C. Sodini, On the minimization of a class of generalized linear functions on a flow polytope. Optimization 63 (2014) 1449–1464. | MR | Zbl | DOI

[5] Y. Chen and H. Jiao, A nonisolated optimal solution of general linear multiplicative programming problems. Comput. Oper. Res. 36 (2009) 2573–2579. | MR | Zbl | DOI

[6] M. C. Dorneich and N. V. Sahinidis, Global optimization algorithms for chip design and compaction. Eng. Optim. 25 (1995) 131–154. | DOI

[7] Y. L. Gao, C. X. Xu and Y. T. Yang, Outcome-space branch and bound algorithm for solving linear multiplicative programming. In: International Conference on Computational and Information Science. Springer, Berlin, Heidelberg (2005) pp. 675–681.

[8] Y. Gao, C. Xu and Y. Yang, An outcome-space finite algorithm for solving linear multiplicative programming. Appl. Math. Comput. 179 (2006) 494–505. | MR | Zbl

[9] H. Jiao, A branch and bound algorithm for globally solving a class of nonconvex programming problems. Nonlinear Anal. Theory Methods App. 70 (2009) 1113–1123. | MR | Zbl | DOI

[10] H. Jiao and Y. Shang, Image space branch-reduction-bound algorithm for globally solving the sum of affine ratios problem. J. Comput. Math. (2022) in press. | MR | Zbl

[11] H.-W. Jiao and Y.-L. Shang, Two-level linear relaxation method for generalized linear fractional programming. J. Oper. Res. Soc. China (2022). DOI: . | DOI | MR | Zbl

[12] H. Jiao, S. Liu and, Y. Chen, Global optimization algorithm of a generalized linear multiplicative programming. J. Appl. Math. Comput. 40 (2012) 551–568. | MR | Zbl | DOI

[13] H. Jiao, W. Wang, R. Chen, Y. Shang and J. Yin, An efficient outer space algorithm for generalized linear multiplicative programming problem. IEEE Access 8 (2020) 80629–80637. | DOI

[14] H. Jiao, Y. Shang and R. Chen, A potential practical algorithm for minimizing the sum of affine fractional functions. Optimization (2022). DOI: . | DOI | MR | Zbl

[15] H. Jiao, J. Ma and Y. Shang, Image space branch-and-bound algorithm for globally solving minimax linear fractional programming problem. Pac. J. Optim. 18 (2022) 195–212. | MR | Zbl

[16] H. Jiao, Y. Shang and W. Wang, Solving generalized polynomial problem by using new affine relaxed technique. Int. J. Comput. Math. 99 (2022) 309–331. | MR | Zbl | DOI

[17] H. W. Jiao, W. J. Wang and P. P. Shen, Piecewise linear relaxation method for globally solving a class of multiplicative problems. Pac. J. Optim. (2022) in press. | MR | Zbl

[18] A. Khajavirad and N. V. Sahinidis, A hybrid LP/NLP paradigm for global optimization relaxations. Math. Prog. Comput. 10 (2018) 383–421. | MR | Zbl | DOI

[19] H. Konno, H. Shirakawa and H. Yamazaki, A mean-absolute deviation-skewness portfolio optimization model. Ann. Oper. Res. 45 (1993) 205–220. | MR | Zbl | DOI

[20] T. Kuno, A finite branch-and-bound algorithm for linear multiplicative programming. Comput. Optim. App. 20 (2001) 119–135. | MR | Zbl | DOI

[21] T. Kuno, Y. Yajima and H. Konno, An outer approximation method for minimizing the product of several convex functions on a convex set. J. Global Optim. 3 (1993) 325–335. | MR | Zbl | DOI

[22] S. Liu and Y. Zhao, An efficient algorithm for globally solving generalized linear multiplicative programming. J. Comput. Appl. Math. 296 (2016) 840–847. | MR | Zbl | DOI

[23] X. Liu, T. Umegaki and Y. Yamamoto, Heuristic methods for linear multiplicative programming. J. Global Optim. 15 (1999) 433–447. | MR | Zbl | DOI

[24] 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. Econ. Dyn. Control 21 (1997) 1405–1425. | MR | Zbl | DOI

[25] T. Matsui, NP-hardness of linear multiplicative programming and related problem. J. Global Optim. 9 (1996) 113–119. | MR | Zbl | DOI

[26] J. M. Mulvey, R. J. Vanderbei and S. A. Zenios, Robust optimization of large-scale systems. Oper. Res. 43 (1995) 264–281. | MR | Zbl | DOI

[27] H. S. Ryoo and N. V. Sahinidis, Global optimization of multiplicative programs. J. Global Optim. 26 (2003) 387–418. | MR | Zbl | DOI

[28] P. Shen and B. Huang, Global algorithm for solving linear multiplicative programming problems. Optim. Lett. 14 (2020) 693–710. | MR | Zbl | DOI

[29] P. Shen, X. Bai and W. Li, A new accelerating method for globally solving a class of nonconvex programming problems. Nonlinear Anal. Theory Methods App. 71 (2009) 2866–2876. | MR | Zbl | DOI

[30] P. Shen, K. Wang and T. Lu, Outer space branch and bound algorithm for solving linear multiplicative programming problems. J. Optim. 78 (2020) 453–482. | MR | Zbl

[31] P. Shen, K. Wang and T. Lu, Global optimization algorithm for solving linear multiplicative programming problems. Optimization (2020). DOI: . | DOI | MR | Zbl

[32] N. V. Thoai, A global optimization approach for solving the convex multiplicative programming problems. J. Global Optim. 1 (1991) 341–357. | MR | Zbl | DOI

[33] C. F. Wang and S. Y. Liu, A new linearization method for generalized linear multiplicative programming. Comput. Oper. Res. 38 (2011) 1008–1013. | MR | Zbl | DOI

[34] C. F. Wang, S. Y. Liu and P. P. Shen, Global minimization of a generalized linear multiplicative programming. Appl. Math. Modell. 36 (2012) 2446–2451. | MR | Zbl | DOI

[35] C. F. Wang, Y. Q. Bai and P. P. Shen, A practicable branch-and-bound algorithm for globally solving multiplicative programming. Optimization 66 (2017) 397–405. | MR | Zbl | DOI

[36] L. P. Yang, P. P. Shen and Y. G. Pei, A global optimization approach for solving generalized nonlinear multiplicative programming problem, In: Abstract Applied Analysis. Hindawi (2014). DOI: . | DOI | MR | Zbl

[37] Y. F. Zhao and S. Y. Liu, An efficient method for generalized linear multiplicative programming problem with multiplicative constraints. SpringerPlus 5 (2016) 1–14.

[38] Y. F. Zhao and T. Zhao, Global optimization for generalized linear multiplicative programming using convex relaxation. Math. Prob. Eng. (2018). DOI: . | DOI | MR | Zbl

[39] B. Zhang, Y. Gao, X. Liu and X. Huang, Output-space branch-and-bound reduction algorithm for a class of linear multiplicative programs. Mathematics 8 (2020) 315. | DOI

[40] B. Zhang, Y. Gao and X. Liu, An efficient polynomial time algorithm for a class of generalized linear multiplicative programs with positive exponents. Math. Prob. Eng. 2021 (2021). DOI: . | DOI | MR | Zbl

Cité par Sources :