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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

D. T. Luc, Theory of Vector Optimization, Springer-Verlag, Berlin, Germany, 1989.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

H. X. Phu, On efficient sets in $\mathbbR^2$, Vietnam J. Math., 33 (2005), 463-468.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

H. Tuy, Convex Analysis and Global Optimization, Kluwer Academic Publishers, 1998. doi: 10.1007/978-1-4757-2809-5.  Google Scholar

[21]

Y. Yamamoto, Optimization over the efficient set: Overview, J. Global Optim., 22 (2002), 285-317. doi: 10.1023/A:1013875600711.  Google Scholar

[22]

P. L. Yu, Multiple-Criteria Decision Making, Plenum Press, New York and London, 1985. doi: 10.1007/978-1-4684-8395-6.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[13]

D. T. Luc, Theory of Vector Optimization, Springer-Verlag, Berlin, Germany, 1989.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

H. X. Phu, On efficient sets in $\mathbbR^2$, Vietnam J. Math., 33 (2005), 463-468.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[20]

H. Tuy, Convex Analysis and Global Optimization, Kluwer Academic Publishers, 1998. doi: 10.1007/978-1-4757-2809-5.  Google Scholar

[21]

Y. Yamamoto, Optimization over the efficient set: Overview, J. Global Optim., 22 (2002), 285-317. doi: 10.1023/A:1013875600711.  Google Scholar

[22]

P. L. Yu, Multiple-Criteria Decision Making, Plenum Press, New York and London, 1985. doi: 10.1007/978-1-4684-8395-6.  Google Scholar

[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]

Yasmine Cherfaoui, Mustapha Moulaï. Biobjective optimization over the efficient set of multiobjective integer programming problem. Journal of Industrial & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & 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 & Management Optimization, 2019, 15 (4) : 2009-2021. doi: 10.3934/jimo.2018134
[14]

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
[15]

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
[16]

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
[17]

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
[18]

Jiawei Chen, Guangmin Wang, Xiaoqing Ou, Wenyan Zhang. Continuity of solutions mappings of parametric set optimization problems. Journal of Industrial & Management Optimization, 2020, 16 (1) : 25-36. doi: 10.3934/jimo.2018138
[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]

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

2020 Impact Factor: 1.801

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences