Verified methods for computing Pareto sets: General algorithmic analysis

• Autorzy: Boglárka G. Tóth , Vladik Kreinovich
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

multi-objective optimization; Pareto set; verified computing

• Wydawca: University of Zielona Gora Press
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2009
• Tom: 19
• Numer: 3
• Strony: 369-380

Daty

wydano

2009

otrzymano

2008-09-22

poprawiono

2008-12-06

Twórcy

autor

Boglárka G. Tóth

• Department of Differential Equations, Institute of Mathematics, Budapest University of Technology and Economics (BME), Egry József u. 1, 1111 Budapest, Hungary

autor

Vladik Kreinovich

• Department of Computer Science, University of Texas at El Paso, 500 W. University, El Paso, Texas 79968, USA

Bibliografia

• Aberth, O. (2007). Introduction to Precise Numerical Methods, Academic Press, San Diego, CA.
• Beeson, M. (1978). Some relations between classical and constructive mathematics, Journal of Symbolic Logic 43(2): 228-246.
• Beeson, M. (1985). Foundations of Constructive Mathematics: Metamathematical Studies, Springer, Berlin/Heidelberg/New York, NY.
• Bishop, E. and Bridges, D.S. (1985). Constructive Analysis, Springer-Verlag, Berlin/Heidelberg/New York, NY.
• 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.
• 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.
• 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.
• 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.
• Figueira, J., Greco, S. and Ehrgott, M. (Eds.) (2004). Multiple Criteria Decision Analysis: State of the Art Surveys, Kluwer, Dordrecht.
• Kreinovich, V. (1975). Uniqueness implies algorithmic computability, Proceedings of the 4th Student Mathematical Conference, Leningrad, USSR, pp. 19-21, (in Russian).
• Kreinovich, V. (1979). Categories of Space-Time Models, Ph.D. dissertation, Institute of Mathematics, Soviet Academy of Sciences, Siberian Branch, Novosibirsk, (in Russian).
• Kreinovich, V., Lakeyev, A., Rohn, J. and Kahl, P. (1998). Computational Complexity and Feasibility of Data Processing and Interval Computations, Kluwer, Dordrecht.
• Kushner, B.A. (1985). Lectures on Constructive Mathematical Analysis, American Mathematical Society, Providence, RI.
• Nachbar, J.H. and Zame, W.R. (1996). Non-computable strategies and discounted repeated games, Economic Theory 8(1): 103-122.
• Nickel, S. and Puerto, J. (2005). Location Theory: A Unified Approach, Springer-Verlag, Berlin.
• Ruzika, S. and Wiecek, M.M. (2005). Approximation methods in multiopbjective programming. Journal of Optimization Theory and Applications 126(3): 473-501.
• 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.

Identyfikatory

DOI

10.2478/v10006-009-0031-5