Verified Methods for Computing Pareto Sets: General Algorithmic Analysis

G.-Tóth, Boglárka; Kreinovich, Vladik

doi:10.2478/v10006-009-0031-5

Abstract

In many engineering problems, we face multi-objective optimization, with several objective functions f₁, …, f_n. 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.

References

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

Verified Methods for Computing Pareto Sets: General Algorithmic Analysis

Abstract

Paradigm

My account