American Institute of Mathematical Sciences

Advanced
  • Previous 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
  • JIMO Home
  • This Issue
  • Next Article
    A priority-based genetic algorithm for a flexible job shop scheduling problem
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

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 and 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-419. 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-111. 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-105. doi: 10.1007/BF02192023.

[4]

H. P. Benson, Global maximization of a generalized concave multiplicative function, J. Optim. Theory Appl., 137 (2008), 105-120. 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-54. 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-631. 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-97. 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-256. 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, Computation and Optimization in Information Systems and Management Sciences (eds. L. T. H. An, P. Bouvry and P. D. Tao), Communications in Computer and Information Science, 14 (2008), 234-243.

[10]

N. T. B. Kim and L. D. Muu, On the projection of the efficient set and potential applications, Optim. 51 (2002), 401-421. 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-115.

[12]

H. Konno, T. Kuno and Y. Yajima, Global Minimization of a Generalized Convex Multiplicative Function, J. Global Optim, 4 (1994), 47-62. doi: 10.1007/BF01096534.

[13]

D. T. Luc, Theory of Vector Optimization, Springer-Verlag, Berlin, Germany, 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, R. Horst, E. Sachs and R. Tichatschke), Lecture Notes in Economics and Mathematical Systems, 452 (1997), 183-195. 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-1001. 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-62. doi: 10.1080/02331939208843779.

[17]

H. X. Phu, On efficient sets in $\mathbb{R}^2$, Vietnam J. Math., 33 (2005), 463-468.

[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, Advances in Intelligent Systems and Computing, 341 (2015), 31-47. 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-336. 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-317. doi: 10.1023/A:1013875600711.

[22]

P. L. Yu, Multiple-Criteria Decision Making, Plenum Press, New York and London, 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-419. 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-111. 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-105. doi: 10.1007/BF02192023.

[4]

H. P. Benson, Global maximization of a generalized concave multiplicative function, J. Optim. Theory Appl., 137 (2008), 105-120. 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-54. 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-631. 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-97. 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-256. 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, Computation and Optimization in Information Systems and Management Sciences (eds. L. T. H. An, P. Bouvry and P. D. Tao), Communications in Computer and Information Science, 14 (2008), 234-243.

[10]

N. T. B. Kim and L. D. Muu, On the projection of the efficient set and potential applications, Optim. 51 (2002), 401-421. 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-115.

[12]

H. Konno, T. Kuno and Y. Yajima, Global Minimization of a Generalized Convex Multiplicative Function, J. Global Optim, 4 (1994), 47-62. doi: 10.1007/BF01096534.

[13]

D. T. Luc, Theory of Vector Optimization, Springer-Verlag, Berlin, Germany, 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, R. Horst, E. Sachs and R. Tichatschke), Lecture Notes in Economics and Mathematical Systems, 452 (1997), 183-195. 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-1001. 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-62. doi: 10.1080/02331939208843779.

[17]

H. X. Phu, On efficient sets in $\mathbb{R}^2$, Vietnam J. Math., 33 (2005), 463-468.

[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, Advances in Intelligent Systems and Computing, 341 (2015), 31-47. 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-336. 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-317. doi: 10.1023/A:1013875600711.

[22]

P. L. Yu, Multiple-Criteria Decision Making, Plenum Press, New York and London, 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 and Management Optimization, 2008, 4 (4) : 647-660. doi: 10.3934/jimo.2008.4.647
[2]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 117-131. doi: 10.3934/jimo.2019102
[3]

Wen-ling Zhao, Dao-jin Song. A global error bound via the SQP method for constrained optimization problem. Journal of Industrial and Management Optimization, 2007, 3 (4) : 775-781. doi: 10.3934/jimo.2007.3.775
[4]

Rentsen Enkhbat, Evgeniya A. Finkelstein, Anton S. Anikin, Alexandr Yu. Gornov. Global optimization reduction of generalized Malfatti's problem. Numerical Algebra, Control and Optimization, 2017, 7 (2) : 211-221. doi: 10.3934/naco.2017015
[5]

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 and Management Optimization, 2013, 9 (1) : 243-253. doi: 10.3934/jimo.2013.9.243
[6]

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 and Management Optimization, 2011, 7 (4) : 789-809. doi: 10.3934/jimo.2011.7.789
[7]

Alireza Ghaffari Hadigheh, Tamás Terlaky. Generalized support set invariancy sensitivity analysis in linear optimization. Journal of Industrial and Management Optimization, 2006, 2 (1) : 1-18. doi: 10.3934/jimo.2006.2.1
[8]

Behrouz Kheirfam, Kamal mirnia. Comments on ''Generalized support set invariancy sensitivity analysis in linear optimization''. Journal of Industrial and Management Optimization, 2008, 4 (3) : 611-616. doi: 10.3934/jimo.2008.4.611
[9]

Zhifeng Dai, Fenghua Wen. A generalized approach to sparse and stable portfolio optimization problem. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1651-1666. doi: 10.3934/jimo.2018025
[10]

Chaabane Djamal, Pirlot Marc. A method for optimizing over the integer efficient set. Journal of Industrial and Management Optimization, 2010, 6 (4) : 811-823. doi: 10.3934/jimo.2010.6.811
[11]

Jing Zhou, Cheng Lu, Ye Tian, Xiaoying Tang. A SOCP relaxation based branch-and-bound method for generalized trust-region subproblem. Journal of Industrial and Management Optimization, 2021, 17 (1) : 151-168. doi: 10.3934/jimo.2019104
[12]

Ye Tian, Qingwei Jin, Zhibin Deng. Quadratic optimization over a polyhedral cone. Journal of Industrial and Management Optimization, 2016, 12 (1) : 269-283. doi: 10.3934/jimo.2016.12.269
[13]

Yong Wang, Wanquan Liu, Guanglu Zhou. An efficient algorithm for non-convex sparse optimization. Journal of Industrial and Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[14]

Zongming Guo, Xuefei Bai. On the global branch of positive radial solutions of an elliptic problem with singular nonlinearity. Communications on Pure and Applied Analysis, 2008, 7 (5) : 1091-1107. doi: 10.3934/cpaa.2008.7.1091
[15]

Guolin Yu. Global proper efficiency and vector optimization with cone-arcwise connected set-valued maps. Numerical Algebra, Control and Optimization, 2016, 6 (1) : 35-44. doi: 10.3934/naco.2016.6.35
[16]

Rentsen Enkhbat, M. V. Barkova, A. S. Strekalovsky. Solving Malfatti's high dimensional problem by global optimization. Numerical Algebra, Control and Optimization, 2016, 6 (2) : 153-160. doi: 10.3934/naco.2016005
[17]

He Huang, Zhen He. A global optimization method for multiple response optimization problems. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022016
[18]

Mohamed Aly Tawhid. Nonsmooth generalized complementarity as unconstrained optimization. Journal of Industrial and Management Optimization, 2010, 6 (2) : 411-423. doi: 10.3934/jimo.2010.6.411
[19]

Jiawei Chen, Guangmin Wang, Xiaoqing Ou, Wenyan Zhang. Continuity of solutions mappings of parametric set optimization problems. Journal of Industrial and Management Optimization, 2020, 16 (1) : 25-36. doi: 10.3934/jimo.2018138
[20]

Yu Zhang, Tao Chen. Minimax problems for set-valued mappings with set optimization. Numerical Algebra, Control and Optimization, 2014, 4 (4) : 327-340. doi: 10.3934/naco.2014.4.327

2021 Impact Factor: 1.411

Tools

Metrics

  • PDF downloads (160)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2022 American Institute of Mathematical Sciences | Privacy Policy