Verified methods for computing Pareto sets: General algorithmic analysis

Boglárka G. Tóth; Vladik Kreinovich

International Journal of Applied Mathematics and Computer Science (2009)

  • Volume: 19, Issue: 3, page 369-380
  • ISSN: 1641-876X

Abstract

top
In many engineering problems, we face multi-objective optimization, with several objective functions f₁,...,fₙ. We want to provide the user with the Pareto set-a set of all possible solutions x which cannot be improved in all categories (i.e., for which f j ( x ' ) ≥ f j ( x ) for all j and f j ( x ) > f j ( x ) for some j is impossible). The user should be able to select an appropriate trade-off between, say, cost and durability. We extend the general results about (verified) algorithmic computability of maxima locations to show that Pareto sets can also be computed.

How to cite

top

Boglárka G. Tóth, and Vladik Kreinovich. "Verified methods for computing Pareto sets: General algorithmic analysis." International Journal of Applied Mathematics and Computer Science 19.3 (2009): 369-380. <http://eudml.org/doc/207942>.

@article{BoglárkaG2009,
abstract = {In many engineering problems, we face multi-objective optimization, with several objective functions f₁,...,fₙ. We want to provide the user with the Pareto set-a set of all possible solutions x which cannot be improved in all categories (i.e., for which $f_j(x^\{\prime \}) ≥ f_j(x)$ for all j and $f_j(x ) > f_j(x)$ for some j is impossible). The user should be able to select an appropriate trade-off between, say, cost and durability. We extend the general results about (verified) algorithmic computability of maxima locations to show that Pareto sets can also be computed.},
author = {Boglárka G. Tóth, Vladik Kreinovich},
journal = {International Journal of Applied Mathematics and Computer Science},
keywords = {multi-objective optimization; Pareto set; verified computing},
language = {eng},
number = {3},
pages = {369-380},
title = {Verified methods for computing Pareto sets: General algorithmic analysis},
url = {http://eudml.org/doc/207942},
volume = {19},
year = {2009},
}

TY - JOUR
AU - Boglárka G. Tóth
AU - Vladik Kreinovich
TI - Verified methods for computing Pareto sets: General algorithmic analysis
JO - International Journal of Applied Mathematics and Computer Science
PY - 2009
VL - 19
IS - 3
SP - 369
EP - 380
AB - In many engineering problems, we face multi-objective optimization, with several objective functions f₁,...,fₙ. We want to provide the user with the Pareto set-a set of all possible solutions x which cannot be improved in all categories (i.e., for which $f_j(x^{\prime }) ≥ f_j(x)$ for all j and $f_j(x ) > f_j(x)$ for some j is impossible). The user should be able to select an appropriate trade-off between, say, cost and durability. We extend the general results about (verified) algorithmic computability of maxima locations to show that Pareto sets can also be computed.
LA - eng
KW - multi-objective optimization; Pareto set; verified computing
UR - http://eudml.org/doc/207942
ER -

References

top
  1. Aberth, O. (2007). Introduction to Precise Numerical Methods, Academic Press, San Diego, CA. Zbl1127.65001
  2. Beeson, M. (1978). Some relations between classical and constructive mathematics, Journal of Symbolic Logic 43(2): 228-246. Zbl0393.03041
  3. Beeson, M. (1985). Foundations of Constructive Mathematics: Metamathematical Studies, Springer, Berlin/Heidelberg/New York, NY. Zbl0565.03028
  4. Bishop, E. and Bridges, D.S. (1985). Constructive Analysis, Springer-Verlag, Berlin/Heidelberg/New York, NY. Zbl0656.03042
  5. Fernández, J. and Tóth, B. (2006). Obtaining the efficient set of biobjective competitive facility location and design problems, Proceedings of the 21th European Conference on Operations Research EURO XXI, Reykjavík, Iceland, pp. T-28. 
  6. Fernández, J. and Tóth, B. (2007). Obtaining an outer approximation of the efficient set of nonlinear biobjective problems, Journal of Global Optimization 38(2): 315-331. Zbl1172.90482
  7. Fernández, J. and Tóth, B. (2009). Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods, Computational Optimization and Applications 42(3):393-419. Zbl1211.90208
  8. Fernández, J., Tóth, B., Plastria, F. and Pelegrín, B. (2006). Reconciling franchisor and franchisee: A planar multiobjective competitive location and design model, in A. Seeger (Ed.) Recent Advances in Optimization, Lecture Notes in Economics and Mathematical Systems, Vol. 563, Berlin/Heidelberg/New York, NY, pp. 375-398. Zbl1101.90059
  9. Figueira, J., Greco, S. and Ehrgott, M. (Eds.) (2004). Multiple Criteria Decision Analysis: State of the Art Surveys, Kluwer, Dordrecht. Zbl1060.90002
  10. Kreinovich, V. (1975). Uniqueness implies algorithmic computability, Proceedings of the 4th Student Mathematical Conference, Leningrad, USSR, pp. 19-21, (in Russian). 
  11. Kreinovich, V. (1979). Categories of Space-Time Models, Ph.D. dissertation, Institute of Mathematics, Soviet Academy of Sciences, Siberian Branch, Novosibirsk, (in Russian). 
  12. Kreinovich, V., Lakeyev, A., Rohn, J. and Kahl, P. (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations, Kluwer, Dordrecht. Zbl0945.68077
  13. Kushner, B.A. (1985). Lectures on Constructive Mathematical Analysis, American Mathematical Society, Providence, RI. Zbl0547.03040
  14. Nachbar, J.H. and Zame, W.R. (1996). Non-computable strategies and discounted repeated games, Economic Theory 8(1): 103-122. Zbl0852.90146
  15. Nickel, S. and Puerto, J. (2005). Location Theory: A Unified Approach, Springer-Verlag, Berlin. Zbl1229.90001
  16. Ruzika, S. and Wiecek, M.M. (2005). Approximation methods in multiopbjective programming. Journal of Optimization Theory and Applications 126(3): 473-501. Zbl1093.90057
  17. Tóth, B. and Fernández, J. (2006). Obtaining the efficient set of nonlinear biobjective optimization problems via interval branch-and-bound methods, Proceedings of the 12th GAMM-IMACS International Symposium on Scientific Computing, Computer Arithmetic, and Validated Numerics SCAN'06, Duisburg, Germany. Zbl1211.90208

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.