排序最佳化
外觀
![]() | 此條目需要精通或熟悉數學的編者參與及協助編輯。 (2020年2月20日) |
排序最佳化(ordinal optimization)也稱為序最佳化,是最優化中的一種,是針對在偏序集(poset)上取值函數的最佳化[1][2][3][4]。排序最佳化可以應用在等候網絡的理論中。
數學基礎
[編輯]偏序是指在集合P內的二元關係 "≤",是自反關係、反對稱關係及傳遞關係。針對集合P內的所有a, b及c,會有以下的關係:
- a ≤ a(自反關係);
- 若 a ≤ b 且 b ≤ a ,則 a = b(反對稱關係);
- if a ≤ b and b ≤ c,則 a ≤ c(傳遞關係).
偏序關係也可以說是預序關係。具有偏序關係的集合稱為偏序集(poset)。
針對偏序集P內的兩個相異元素a, b,若a ≤ b或b ≤ a,則a和b 是可比較的,否則是不可比較的。若偏序集中任兩個元素都是可比較的,此偏序集稱為全序關係或「chain」(也就是依順序排列的自然數)。若任兩個元素都是不可比較的,則稱為反鏈。
以下是一些數學中偏序集的例子:
計算機科學及統計學中的排序最佳化
[編輯]在許多領域都有排序最佳化的問題。計算機科學中會研究選擇算法,這種算法比排序算法要簡單[5][6]
決策論會研究選擇算法,會要識別出「最佳」的子群體,或是識別出「近乎最佳」的子群體[7][8][9][10][11]。
應用
[編輯]自1960年代起,排序最佳化在其理論及應用上都有許多的擴展。其中的antimatroid及max-plus代數已應用在網絡分析及等候理論中,特別是在等候網路中。排序最佳化也應用在離散事件仿真上[12][13][14]。
相關條目
[編輯]參考文獻
[編輯]- ^ Brenda L. Dietrich; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
- ^ Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
- ^ Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
- ^ Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
- ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.
- ^ Gibbons, Jean Dickinson; Olkin, Ingram, and Sobel, Milton, Selecting and Ordering of Populations, Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)
- ^ Gupta, Shanti S.; Panchapakesan, S. Multiple decision procedures: Theory and methodology of selecting and ranking populations. Wiley Series in Probability and Mathematical Statistics. New York: John Wiley & Sons. 1979: xxv+573. ISBN 0-471-05177-2. MR 0555416. (Republished as a Classic in Applied Mathematics by SIAM.)
- ^ Santner, Thomas J., and Tamhane, A. C., Design of Experiments: Ranking and Selection, M. Dekker, (1984).
- ^ Robert E. Bechhofer, Thomas J. Santner, David M. Goldsman. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. John Wiley & Sons, 1995.
- ^ Friedrich Liese, Klaus-J. Miescke. 2008. Statistical Decision Theory: Estimation, Testing, and Selection. Springer Verlag.
- ^ Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839.
- ^ Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266.
- ^ Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299.
延伸閱讀
[編輯]- Fujishige, Satoru Submodular functions and optimization. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp. ISBN 0-444-52086-4
- Gondran, Michel; Minoux, Michel Graphs, dioids and semirings. New models and algorithms. Operations Research/Computer Science Interfaces Series, 41. Springer, New York, 2008. xx+383 pp. ISBN 978-0-387-75449-9
- Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
- Murota, Kazuo Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. xxii+389 pp. ISBN 0-89871-540-7
- Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
- Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
- Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
- Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380 pp.
- Cuninghame-Green, Raymond Minimax algebra. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp. ISBN 3-540-09113-0
- Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266.
- Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839.
- Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299.
- Ho, Y.C., Sreenivas, R., Vakili, P.,"Ordinal Optimization of Discrete Event Dynamic Systems", J. of DEDS 2(2), 61-88, (1992).
- Allen, Eric, and Marija D. Ilic. Price-Based Commitment Decisions in the Electricity Market. Advances in industrial control. London: Springer, 1999. ISBN 978-1-85233-069-9