Verified methods for computing Pareto sets: General algorithmic analysis

G.-Tóth, B. ; Kreinovich, V.

International Journal of Applied Mathematics and Computer Science, Tome 19 (2009) no. 3, pp. 369-380.

Résumé

In many engineering problems, we face multi-objective optimization, with several objective functions f1, . . . , fn. 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 fj (x') fj (x) for all j and fj(x') > fj(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.

Détail

Keywords: multi-objective optimisation, Pareto set, verified computing
Mots-clés : optymalizacja wielocelowa, zbiór Pareto

Bibliographie

[1] Aberth, O. (2007). Introduction to Precise Numerical Methods, Academic Press, San Diego, CA.

[2] Beeson, M. (1978). Some relations between classical and constructive mathematics, Journal of Symbolic Logic 43(2): 228-246.

[3] Beeson, M. (1985). Foundations of Constructive Mathematics: Metamathematical Studies, Springer, Berlin/Heidelberg/New York, NY.

[4] Bishop, E. and Bridges, D.S. (1985). Constructive Analysis, Springer-Verlag, Berlin/Heidelberg/New York, NY.

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

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

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

[9] Figueira, J., Greco, S. and Ehrgott, M. (Eds.) (2004). Multiple Criteria Decision Analysis: State of the Art Surveys, Kluwer, Dordrecht.

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

[13] Kushner, B.A. (1985). Lectures on Constructive Mathematical Analysis, American Mathematical Society, Providence, RI.

[14] Nachbar, J.H. and Zame, W.R. (1996). Non-computable strategies and discounted repeated games, Economic Theory 8(1): 103-122.

[15] Nickel, S. and Puerto, J. (2005). Location Theory: A Unified Approach, Springer-Verlag, Berlin.

[16] Ruzika, S. and Wiecek, M.M. (2005). Approximation methods in multiobjective programming. Journal of Optimization Theory and Applications 126(3): 473-501.

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