排序最佳化

排序最佳化(ordinal optimization)也稱為序最佳化,是最优化中的一種,是針對在偏序集(poset)上取值函數的最佳化[1][2][3][4]。排序最佳化可以應用在等候网络的理論中。

數學基礎

偏序是指在集合P內的二元关系 "≤",是自反关系反对称关系传递关系。針對集合P內的所有a, bc,會有以下的關係:

  • a ≤ a(自反關係);
  • a ≤ bb ≤ a ,則 a = b(反對稱關係);
  • if a ≤ b and b ≤ c,則 a ≤ c(傳遞關係).

偏序關係也可以說是预序关系。具有偏序關係的集合稱為偏序集(poset)。

針對偏序集P內的兩個相異元素a, b,若a ≤ bb ≤ a,則ab 是可比較的,否則是不可比較的。若偏序集中任兩個元素都是可比較的,此偏序集稱為全序关系或「chain」(也就是依順序排列的自然數)。若任兩個元素都是不可比較的,則稱為反链

以下是一些數學中偏序集的例子:

  • 实数的偏序關係是標準的小於等於關係 ≤ ,也是全序集。
  • 特定集合子集形成的集合(冪集),偏序關係是包含
  • 向量空间子空間的集合,偏序關係也是包含。

計算機科學及統計學中的排序最佳化

在許多領域都有排序最佳化的問題。计算机科学中會研究选择算法,這種算法比排序算法要簡單[5][6]

决策论會研究选择算法,會要識別出「最佳」的子群體,或是識別出「近乎最佳」的子群體[7][8][9][10][11]

應用

自1960年代起,排序最佳化在其理論及應用上都有許多的擴展。其中的antimatroid英语antimatroidmax-plus代數英语max-plus algebra已應用在网络分析等候理論中,特別是在等候網路中。排序最佳化也應用在离散事件仿真[12][13][14]

相關條目

参考文献

  1. ^ 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.
  2. ^ Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  3. ^ 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
  4. ^ Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  5. ^ 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.
  6. ^ 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.
  7. ^ Gibbons, Jean Dickinson; Olkin, Ingram, and Sobel, Milton, Selecting and Ordering of Populations, Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)
  8. ^ 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.)
  9. ^ Santner, Thomas J., and Tamhane, A. C., Design of Experiments: Ranking and Selection, M. Dekker, (1984).
  10. ^ 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.
  11. ^ Friedrich Liese, Klaus-J. Miescke. 2008. Statistical Decision Theory: Estimation, Testing, and Selection. Springer Verlag.
  12. ^ 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. 
  13. ^ 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. 
  14. ^ 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

外部連結