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.  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.  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.  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.  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.  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.  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.  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.  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, 14 (2008), 234.   Google Scholar

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

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

[13]

D. T. Luc, Theory of Vector Optimization,, Springer-Verlag, (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, 452 (1997), 183.  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.  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.  doi: 10.1080/02331939208843779.  Google Scholar

[17]

H. X. Phu, On efficient sets in $\mathbbR^2$,, Vietnam J. Math., 33 (2005), 463.   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, 341 (2015), 31.  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.  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.  doi: 10.1023/A:1013875600711.  Google Scholar

[22]

P. L. Yu, Multiple-Criteria Decision Making,, Plenum Press, (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.  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.  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.  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.  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.  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.  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.  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.  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, 14 (2008), 234.   Google Scholar

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

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

[13]

D. T. Luc, Theory of Vector Optimization,, Springer-Verlag, (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, 452 (1997), 183.  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.  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.  doi: 10.1080/02331939208843779.  Google Scholar

[17]

H. X. Phu, On efficient sets in $\mathbbR^2$,, Vietnam J. Math., 33 (2005), 463.   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, 341 (2015), 31.  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.  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.  doi: 10.1023/A:1013875600711.  Google Scholar

[22]

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

[1]

Ardeshir Ahmadi, Hamed Davari-Ardakani. A multistage stochastic programming framework for cardinality constrained portfolio optimization. Numerical Algebra, Control & Optimization, 2017, 7 (3) : 359-377. doi: 10.3934/naco.2017023
[2]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[3]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024
[4]

Naeem M. H. Alkoumi, Pedro J. Torres. Estimates on the number of limit cycles of a generalized Abel equation. Discrete & Continuous Dynamical Systems - A, 2011, 31 (1) : 25-34. doi: 10.3934/dcds.2011.31.25
[5]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[6]

Guido De Philippis, Antonio De Rosa, Jonas Hirsch. The area blow up set for bounded mean curvature submanifolds with respect to elliptic surface energy functionals. Discrete & Continuous Dynamical Systems - A, 2019, 39 (12) : 7031-7056. doi: 10.3934/dcds.2019243
[7]

Hakan Özadam, Ferruh Özbudak. A note on negacyclic and cyclic codes of length $p^s$ over a finite field of characteristic $p$. Advances in Mathematics of Communications, 2009, 3 (3) : 265-271. doi: 10.3934/amc.2009.3.265
[8]

Rafael Luís, Sandra Mendonça. A note on global stability in the periodic logistic map. Discrete & Continuous Dynamical Systems - B, 2020, 25 (11) : 4211-4220. doi: 10.3934/dcdsb.2020094
[9]

Lakmi Niwanthi Wadippuli, Ivan Gudoshnikov, Oleg Makarenkov. Global asymptotic stability of nonconvex sweeping processes. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1129-1139. doi: 10.3934/dcdsb.2019212
[10]

Alexandr Mikhaylov, Victor Mikhaylov. Dynamic inverse problem for Jacobi matrices. Inverse Problems & Imaging, 2019, 13 (3) : 431-447. doi: 10.3934/ipi.2019021
[11]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[12]

Valery Y. Glizer. Novel Conditions of Euclidean space controllability for singularly perturbed systems with input delay. Numerical Algebra, Control & Optimization, 2020  doi: 10.3934/naco.2020027
[13]

Alina Chertock, Alexander Kurganov, Mária Lukáčová-Medvi${\rm{\check{d}}}$ová, Șeyma Nur Özcan. An asymptotic preserving scheme for kinetic chemotaxis models in two space dimensions. Kinetic & Related Models, 2019, 12 (1) : 195-216. doi: 10.3934/krm.2019009
[14]

Wei Liu, Pavel Krejčí, Guoju Ye. Continuity properties of Prandtl-Ishlinskii operators in the space of regulated functions. Discrete & Continuous Dynamical Systems - B, 2017, 22 (10) : 3783-3795. doi: 10.3934/dcdsb.2017190
[15]

Mats Gyllenberg, Jifa Jiang, Lei Niu, Ping Yan. On the classification of generalized competitive Atkinson-Allen models via the dynamics on the boundary of the carrying simplex. Discrete & Continuous Dynamical Systems - A, 2018, 38 (2) : 615-650. doi: 10.3934/dcds.2018027
[16]

Carlos Gutierrez, Nguyen Van Chau. A remark on an eigenvalue condition for the global injectivity of differentiable maps of $R^2$. Discrete & Continuous Dynamical Systems - A, 2007, 17 (2) : 397-402. doi: 10.3934/dcds.2007.17.397
[17]

Bernold Fiedler, Carlos Rocha, Matthias Wolfrum. Sturm global attractors for $S^1$-equivariant parabolic equations. Networks & Heterogeneous Media, 2012, 7 (4) : 617-659. doi: 10.3934/nhm.2012.7.617
[18]

Hildeberto E. Cabral, Zhihong Xia. Subharmonic solutions in the restricted three-body problem. Discrete & Continuous Dynamical Systems - A, 1995, 1 (4) : 463-474. doi: 10.3934/dcds.1995.1.463
[19]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[20]

Michel Chipot, Mingmin Zhang. On some model problem for the propagation of interacting species in a special environment. Discrete & Continuous Dynamical Systems - A, 2020  doi: 10.3934/dcds.2020401

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences