Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set

Previous Article
A priority-based genetic algorithm for a flexible job shop scheduling problem
JIMO Home
This Issue
Next Article
System capacity optimization design and optimal threshold $N^{*}$ for a $GEO/G/1$ discrete-time queue with single server vacation and under the control of Min($N, V$)-policy

October 2016, 12(4): 1417-1433. doi: 10.3934/jimo.2016.12.1417

Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set

Tran Ngoc Thang ^1, and Nguyen Thi Bach Kim ^1,

1.	School of Applied Mathematics and Informatics, Hanoi University of Science and Technology, No. 1 Dai Co Viet, Hai Ba Trung, Hanoi, Vietnam, Vietnam

Received December 2014 Revised June 2015 Published January 2016

Abstract
Related Papers

In this paper, an algorithm of the branch and bound type in outcome space is proposed for solving a global optimization problem that includes, as a special case, generalized multiplicative problems. As an application, we solve the problem of optimizing over the efficient set of a bicriteria concave maximization problem. Preliminary computational experiments show that this algorithm works well for problems where the dimensions of the decision space can be fairly large.

Keywords: Global optimization, outcome space, branch and bound., optimization over the efficient set, generalized multiplicative problem.

Mathematics Subject Classification: Primary: 90C29; Secondary: 90C2.

Citation: Tran Ngoc Thang, Nguyen Thi Bach Kim. Outcome space algorithm for generalized multiplicative problems and optimization over the efficient set. Journal of Industrial & Management Optimization, 2016, 12 (4) : 1417-1433. doi: 10.3934/jimo.2016.12.1417

References:

[1]	A. M. Ashtiani and P. A. V. Ferreira, On the Solution of Generalized Multiplicative Extremum Problems,, J. Optim. Theory Appl., 149 (2011), 411. doi: 10.1007/s10957-010-9782-2.
[2]	H. P. Benson, A Bisection-Extreme Point Search Algorithm for Optimizing over the Efficient Set in the Linear Dependence Case，, J. Global Optim., 3 (1993), 95. doi: 10.1007/BF01100242.
[3]	H. P. Benson and D. Lee, Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem,, J. Optim. Theory Appl., 88 (1996), 77. doi: 10.1007/BF02192023.
[4]	H. P. Benson, Global maximization of a generalized concave multiplicative function,, J. Optim. Theory Appl., 137 (2008), 105. doi: 10.1007/s10957-007-9323-9.
[5]	J. Fulop and L. D. Muu, Branch-and-bound variant of an outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem,, J. Optim. Theory Appl., 105 (2000), 37. doi: 10.1023/A:1004657827134.
[6]	R. Horst and N. V. Thoai, Utility Function Programs and Optimization over the Efficient Set in Multiple-Objective Decision Making,, J. Optim. Theory Appl., 92 (1997), 605. doi: 10.1023/A:1022659523991.
[7]	H. Isermann and R. E. Steuer, Computational Experience Concerning Payoff Tables and Minimum Criterion Values over the Efficient Set,, Eur. J. Oper. Res., 33 (1988), 91. doi: 10.1016/0377-2217(88)90257-3.
[8]	B. Jaumard, C. Meyer and H. Tuy, Generalized convex multiplicative programming via quasiconcave minimization,, J. Global Optim., 10 (1997), 229. doi: 10.1023/A:1008203116882.
[9]	N. T. B. Kim, L. T. H. An and T. M. Thanh, Outcome-Space Polyblock Approximation Algorithm for Optimizing over Efficient Sets,, in Modelling, 14 (2008), 234.
[10]	N. T. B. Kim and L. D. Muu, On the projection of the efficient set and potential applications,, Optim. 51 (2002), 51 (2002), 401. doi: 10.1080/02331930290019486.
[11]	N. T. B. Kim and T. N. Thang, Optimization over the Efficient Set of a Bicriteria Convex Programming Problem,, Pacific J. Optim., 9 (2013), 103.
[12]	H. Konno, T. Kuno and Y. Yajima, Global Minimization of a Generalized Convex Multiplicative Function,, J. Global Optim, 4 (1994), 47. doi: 10.1007/BF01096534.
[13]	D. T. Luc, Theory of Vector Optimization,, Springer-Verlag, (1989).
[14]	L. T. Luc and L. D. Muu, Global optimization approach to optimizing over the efficient set,, in Recent Advances in Optimization* (eds. P. Gritzmann, 452* (1997), 183. doi: 10.1007/978-3-642-59073-3_13.
[15]	D. T. Luc, T. Q. Phong and M. Volle, Scalarizing Functions for Generating the Weakly Efficient Solution Set in Convex Multiobjective Problems,, SIAM J. Optim., 15 (2005), 987. doi: 10.1137/040603097.
[16]	L. D. Muu and B. T. Tam, Minimizing the sum of a convex function and the product of two affine functions over a convex set,, Optim., 24 (1992), 57. doi: 10.1080/02331939208843779.
[17]	H. X. Phu, On efficient sets in $\mathbbR^2$,, Vietnam J. Math., 33 (2005), 463.
[18]	T. N. Thang, Outcome-based branch and bound algorithm for optimization over the efficient set and its application,, in Some Current Advanced Researches on Information and Computer Science in Vietnam, 341 (2015), 31. doi: 10.1007/978-3-319-14633-1_3.
[19]	N. V. Thoai, Conical algorithm in global optimization for optimizing over efficient sets,, J. Global Optim., 18 (2000), 321. doi: 10.1023/A:1026544116333.
[20]	H. Tuy, Convex Analysis and Global Optimization,, Kluwer Academic Publishers, (1998). doi: 10.1007/978-1-4757-2809-5.
[21]	Y. Yamamoto, Optimization over the efficient set: Overview,, J. Global Optim., 22 (2002), 285. doi: 10.1023/A:1013875600711.
[22]	P. L. Yu, Multiple-Criteria Decision Making,, Plenum Press, (1985). doi: 10.1007/978-1-4684-8395-6.

show all references

References:

[1]	A. M. Ashtiani and P. A. V. Ferreira, On the Solution of Generalized Multiplicative Extremum Problems,, J. Optim. Theory Appl., 149 (2011), 411. doi: 10.1007/s10957-010-9782-2.
[2]	H. P. Benson, A Bisection-Extreme Point Search Algorithm for Optimizing over the Efficient Set in the Linear Dependence Case，, J. Global Optim., 3 (1993), 95. doi: 10.1007/BF01100242.
[3]	H. P. Benson and D. Lee, Outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem,, J. Optim. Theory Appl., 88 (1996), 77. doi: 10.1007/BF02192023.
[4]	H. P. Benson, Global maximization of a generalized concave multiplicative function,, J. Optim. Theory Appl., 137 (2008), 105. doi: 10.1007/s10957-007-9323-9.
[5]	J. Fulop and L. D. Muu, Branch-and-bound variant of an outcome-based algorithm for optimizing over the efficient set of a bicriteria linear programming problem,, J. Optim. Theory Appl., 105 (2000), 37. doi: 10.1023/A:1004657827134.
[6]	R. Horst and N. V. Thoai, Utility Function Programs and Optimization over the Efficient Set in Multiple-Objective Decision Making,, J. Optim. Theory Appl., 92 (1997), 605. doi: 10.1023/A:1022659523991.
[7]	H. Isermann and R. E. Steuer, Computational Experience Concerning Payoff Tables and Minimum Criterion Values over the Efficient Set,, Eur. J. Oper. Res., 33 (1988), 91. doi: 10.1016/0377-2217(88)90257-3.
[8]	B. Jaumard, C. Meyer and H. Tuy, Generalized convex multiplicative programming via quasiconcave minimization,, J. Global Optim., 10 (1997), 229. doi: 10.1023/A:1008203116882.
[9]	N. T. B. Kim, L. T. H. An and T. M. Thanh, Outcome-Space Polyblock Approximation Algorithm for Optimizing over Efficient Sets,, in Modelling, 14 (2008), 234.
[10]	N. T. B. Kim and L. D. Muu, On the projection of the efficient set and potential applications,, Optim. 51 (2002), 51 (2002), 401. doi: 10.1080/02331930290019486.
[11]	N. T. B. Kim and T. N. Thang, Optimization over the Efficient Set of a Bicriteria Convex Programming Problem,, Pacific J. Optim., 9 (2013), 103.
[12]	H. Konno, T. Kuno and Y. Yajima, Global Minimization of a Generalized Convex Multiplicative Function,, J. Global Optim, 4 (1994), 47. doi: 10.1007/BF01096534.
[13]	D. T. Luc, Theory of Vector Optimization,, Springer-Verlag, (1989).
[14]	L. T. Luc and L. D. Muu, Global optimization approach to optimizing over the efficient set,, in Recent Advances in Optimization* (eds. P. Gritzmann, 452* (1997), 183. doi: 10.1007/978-3-642-59073-3_13.
[15]	D. T. Luc, T. Q. Phong and M. Volle, Scalarizing Functions for Generating the Weakly Efficient Solution Set in Convex Multiobjective Problems,, SIAM J. Optim., 15 (2005), 987. doi: 10.1137/040603097.
[16]	L. D. Muu and B. T. Tam, Minimizing the sum of a convex function and the product of two affine functions over a convex set,, Optim., 24 (1992), 57. doi: 10.1080/02331939208843779.
[17]	H. X. Phu, On efficient sets in $\mathbbR^2$,, Vietnam J. Math., 33 (2005), 463.
[18]	T. N. Thang, Outcome-based branch and bound algorithm for optimization over the efficient set and its application,, in Some Current Advanced Researches on Information and Computer Science in Vietnam, 341 (2015), 31. doi: 10.1007/978-3-319-14633-1_3.
[19]	N. V. Thoai, Conical algorithm in global optimization for optimizing over efficient sets,, J. Global Optim., 18 (2000), 321. doi: 10.1023/A:1026544116333.
[20]	H. Tuy, Convex Analysis and Global Optimization,, Kluwer Academic Publishers, (1998). doi: 10.1007/978-1-4757-2809-5.
[21]	Y. Yamamoto, Optimization over the efficient set: Overview,, J. Global Optim., 22 (2002), 285. doi: 10.1023/A:1013875600711.
[22]	P. L. Yu, Multiple-Criteria Decision Making,, Plenum Press, (1985). doi: 10.1007/978-1-4684-8395-6.

[1]	Nguyen Van Thoai. Decomposition branch and bound algorithm for optimization problems over efficient sets. Journal of Industrial & Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647
[2]	Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial & Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775
[3]	Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control & Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015
[4]	Nguyen Thi Bach Kim, Nguyen Canh Nam, Le Quang Thuy. An outcome space algorithm for minimizing the product of two convex functions over a convex set. Journal of Industrial & Management Optimization, 2013, 9 (1) : 243-253. doi: 10.3934/jimo.2013.9.243
[5]	Henri Bonnel, Ngoc Sang Pham. Nonsmooth optimization over the (weakly or properly) Pareto set of a linear-quadratic multi-objective control problem: Explicit optimality conditions. Journal of Industrial & Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789
[6]	Alireza Ghaffari Hadigheh, Tamás Terlaky. Generalized support set invariancy sensitivity analysis in linear optimization. Journal of Industrial & Management Optimization, 2006, 2 (1) : 1-18. doi: 10.3934/jimo.2006.2.1
[7]	Behrouz Kheirfam, Kamal mirnia. Comments on ''Generalized support set invariancy sensitivity analysis in linear optimization''. Journal of Industrial & Management Optimization, 2008, 4 (3) : 611-616. doi: 10.3934/jimo.2008.4.611
[8]	Zhifeng Dai, Fenghua Wen. A generalized approach to sparse and stable portfolio optimization problem. Journal of Industrial & Management Optimization, 2018, 14 (4) : 1651-1666. doi: 10.3934/jimo.2018025
[9]	Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial & Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
[10]	Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial & Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269
[11]	Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-13. doi: 10.3934/jimo.2018134
[12]	Rentsen Enkhbat, M. V. Barkova, A. S. Strekalovsky. Solving Malfatti's high dimensional problem by global optimization. Numerical Algebra, Control & Optimization, 2016, 6 (2) : 153-160. doi: 10.3934/naco.2016005
[13]	Guolin Yu. Global proper efficiency and vector optimization with cone-arcwise connected set-valued maps. Numerical Algebra, Control & Optimization, 2016, 6 (1) : 35-44. doi: 10.3934/naco.2016.6.35
[14]	Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial & Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411
[15]	Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure & Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091
[16]	Jiawei Chen, Guangmin Wang, Xiaoqing Ou, Wenyan Zhang. Continuity of solutions mappings of parametric set optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (5) : 1-12. doi: 10.3934/jimo.2018138
[17]	Jian Lu, Lixin Shen, Chen Xu, Yuesheng Xu. Multiplicative noise removal with a sparsity-aware optimization model. Inverse Problems & Imaging, 2017, 11 (6) : 949-974. doi: 10.3934/ipi.2017044
[18]	Pooja Louhan, S. K. Suneja. On fractional vector optimization over cones with support functions. Journal of Industrial & Management Optimization, 2017, 13 (2) : 549-572. doi: 10.3934/jimo.2016031
[19]	Yu Zhang, Tao Chen. Minimax problems for set-valued mappings with set optimization. Numerical Algebra, Control & Optimization, 2014, 4 (4) : 327-340. doi: 10.3934/naco.2014.4.327
[20]	Z.G. Feng, K.L. Teo, Y. Zhao. Branch and bound method for sensor scheduling in discrete time. Journal of Industrial & Management Optimization, 2005, 1 (4) : 499-512. doi: 10.3934/jimo.2005.1.499

2017 Impact Factor: 0.994

American Institute of Mathematical Sciences