Abstract
The paper describes new results in the field of multiobjective optimization techniques. The Interactive Decision Maps (IDM) technique is based on approximation of Feasible Criterion Set (FCS) and subsequent visualization of the Pareto frontier of FCS by interactive displaying the bi-criteria slices of FCS. The Estimation Refinement (ER) method is now the main method for approximating convex FCS in the framework of IDM. The properties of the ER method are studied. We prove that the number of facets of the approximation constructed by ER and the number of the support function calculations of an approximated set are asymptotically optimal. These results are important from the point of view of real-life applications of ER.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Bushenkov, V. A., & Lotov, A. V. (1982). Methods for the construction and application of generalized reachable sets. Moscow: Computing Center of the USSR Academy of Sciences (in Russian).
Chernykh, O. L. (1988). Construction of the convex hull of a finite set of points when the computations are approximate. Computational Mathematics and Mathematical Physics, 28(5), 71–77.
Chernykh, O. L. (1995). Approximating the Pareto hull of a convex set by polyhedral sets. Computational Mathematics and Mathematical Physics, 35(8), 1033–1039.
Dietrich, J., Schumann, A. H., & Lotov, A. V. (2006). Workflow oriented participatory decision support for integrated river basin planning. In A. Castelletti & R. Soncini Sessa (Eds.), Topics on system analysis and integrated water resource management (pp. 207–221). Amsterdam: Elsevier.
Efremov, R. V., & Kamenev, G. K. (2002). An a priori estimate for the asymptotic efficiency of a class of algorithms for the polyhedral approximation of convex bodies. Computational Mathematics and Mathematical Physics, 42(1), 20–29.
Efremov, R., Rios Insua, D., & Lotov, A. (2006). A framework for participatory group decision support over the Web based on Pareto frontier visualization, goal identification and arbitration. Rey Juan Carlos University technical reports on statistics and decision sciences.
Gass, S., & Saaty, T. (1955). The computational algorithm for the parametric objective function. Naval Research Logistics Quarterly, 2, 39.
Gruber, P. M. (1993). Asymptotic estimates for best and stepwise approximation of convex bodies I. Forum Mathematicum, 5, 281–297.
Kamenev, G. K. (1992). A class of adaptive algorithms for the approximation of bodies by polyhedra. Computational Mathematics and Mathematical Physics, 32(1), 114–127.
Kamenev, G. K. (1994). Investigation of an algorithm for the approximation of convex bodies. Computational Mathematics and Mathematical Physics, 34(4), 521–528.
Larichev, O. Cognitive validity in design of decision-aiding techniques. Journal of Multi-Criteria Decision Analysis 1(3) (1992).
Lotov, A. V., Bushenkov, V. A., & Kamenev, G. K. (2004a). Interactive decision maps. Approximation and visualization of Pareto frontier. Dordrecht: Kluwer Academic.
Lotov, A., Kistanov, A., & Zaitsev, A. (2004b). Visualization-based data mining tool and its Web application. In Y. Shi, W. Xu, & Z. Chen (Eds.), Lecture notes in artificial intelligence (Vol. 3327(XIII), p. 263). Berlin/Heidelberg: Springer.
McMullen, P., & Shephard, G. C. (1971). Convex polytopes and the upper bound conjecture. Cambridge: Cambridge University Press.
Preparata, F. P., & Shamos, M. I. (1985). Computational geometry: An introduction. New York: Springer.
Schneider, R. (1983). Zur optimalen Approximation konvexer Hyperflächen durch Polyeder. Mathematische Annalen, 256(3), 289–301.
Schneider, R., & Wieacker, J. A. (1981). Approximation of convex bodies by polytopes. Bulletin of the London Mathematical Society, 13, 149–156.
Wierzbicki, A. (1981). A mathematical basis for satisfying decision making. In J. Morse (Ed.), Organizations: Multiple agents with multiple criteria (pp. 465–485). Berlin: Springer.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Efremov, R.V., Kamenev, G.K. Properties of a method for polyhedral approximation of the feasible criterion set in convex multiobjective problems. Ann Oper Res 166, 271–279 (2009). https://doi.org/10.1007/s10479-008-0418-y
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0418-y