Ordinal Optimization

by Ho, Yu-Chi; Zhao, Qian-chuan; Jia, Qing Shan

• ISBN13: 9780387372327
• ISBN10: 0387372326
• Format: Hardcover
• Copyright: 2007-09-07
• Publisher: Springer-Verlag New York Inc

Summary

Our civilization employs increasingly complex human-made systems, such as large-scale electric power grids, air traffic control systems, manufacturing plants and supply chains, the Internet and other communication networks. Performance evaluation of these systems is accomplished by using simulation models rather than experiment with the real systems. However, these systems operate and evolve in time via human-made rules of operation which are difficult to describe and capture by succint mathematical models. And while simulation models are often used for design validation and other purposes, computational constraints and the changing nature of the problem domain make them unsuitable for optimization purposes.If we accept the need for search based methods as a complement to the more established analytical techniques, then quickly narrowing the search for optimum performance (ordinal optimization) is more important than accurately estimating the values of system performance during the process of optimization (cardinal optimization). The purpose of this book is to address the difficulties of ordinal optimization problems " the optimization of complex systems via simulation models or other computation-intensive models involving possible stochastic effects and discrete choices. This book will establish the distinct advantages of the "softer" ordinal approach for search-based type problems, analyze some of its general properties, and show the many orders of magnitude improvement in computational efficiency that is possible. As such, the book is complementary to existing optimization literature. The tools described here do not replace but can be used separately or in conjunction with other methodological tools of optimization.

Author Biography

Yu-Chi Ho (lead author) is the only author whose book in the system/control field has the distinction of being a SCI Citation Classic* as the most referenced book on the subject.  After 37 years, his book is still selling about 500 copies per year without a revision.Applied Optimal Control (with A.E. Bryson Jr.); Hemisphere-Wiley 1975, first published by Xerox College Publishing 1969.*Citation Classic, SCIENCE CITATION INDEX (CURRENT CONTENTS) 2/25/80, Vol. 11, No. 8, as the most cited reference on the subject.Dr. Ho is the founding editor of the international journal, Discrete Event Dynamic Systems.  He is the recipient of various fellowships and awards including the Guggenheim (1970), the IEEE Field Award for Control Engineering and Science (1989), the Chiang Technology Achievement Award (1993), the American Automatic Control Council Bellman Control Heritage Award (1999), the ASME Rufus Oldenburger Award (1999), and the Isaacs Award from the International Society of Dynamic Games (2004).  Dr. Ho is an IEEE Life Fellow and an INFORMS Inaugural Fellow (elected 2002), a Distinguished Member of the IEEE Control Systems Society, a member of the U.S. National Academy of Engineering and a foreign member of the Chinese Academy of Engineering and the Chinese Academy of Sciences.In addition to serving on various governmental and industrial panels, and professional society administrative bodies, Dr. Ho was the President of the IEEE Robotics & Automation Society in 1988. 

Table of Contents

Preface	p. xiii
Acknowledgements	p. xv
Introduction	p. 1
Ordinal Optimization Fundamentals	p. 7
Two basic ideas of Ordinal Optimization (OO)	p. 7
Definitions, terminologies, and concepts for OO	p. 9
A simple demonstration of OO	p. 13
The exponential convergence of order and goal softening	p. 15
Large deviation theory	p. 16
Exponential convergence w.r.t. order	p. 21
Proof of goal softening	p. 26
Blind pick	p. 26
Horse race	p. 28
Universal alignment probabilities	p. 37
Blind pick selection rule	p. 38
Horse race selection rule	p. 39
Deterministic complex optimization problem and Kolmogorov equivalence	p. 48
Example applications	p. 51
Stochastic simulation models	p. 51
Deterministic complex models	p. 53
Preview of remaining chapters	p. 54
Comparison of Selection Rules	p. 57
Classification of selection rules	p. 60
Quantify the efficiency of selection rules	p. 69
Parameter settings in experiments for regression functions	p. 73
Comparison of selection rules	p. 77
Examples of search reduction	p. 80
Example: Picking with an approximate model	p. 80
Example: A buffer resource allocation problem	p. 84
Some properties of good selection rules	p. 88
Conclusion	p. 90
Vector Ordinal Optimization	p. 93
Definitions, terminologies, and concepts for VOO	p. 94
Universal alignment probability	p. 99
Exponential convergence w.r.t. order	p. 104
Examples of search reduction	p. 106
Example: When the observation noise contains normal distribution	p. 106
Example: The buffer allocation problem	p. 108
Constrained Ordinal Optimization	p. 113
Determination of selected set in COO	p. 115
Blind pick with an imperfect feasibility model	p. 115
Impact of the quality of the feasibility model on BPFM	p. 119
Example: Optimization with an imperfect feasibility model	p. 122
Conclusion	p. 124
Memory Limited Strategy Optimization	p. 125
Motivation (the need to find good enough and simple strategies)	p. 126
Good enough simple strategy search based on OO	p. 128
Building crude model	p. 128
Random sampling in the design space of simple strategies	p. 133
Conclusion	p. 135
Additional Extensions of the OO Methodology	p. 137
Extremely large design space	p. 138
Parallel implementation of OO	p. 143
The concept of the standard clock	p. 144
Extension to non-Markov cases using second order approximations	p. 147
Second order approximation	p. 148
Numerical testing	p. 152
Effect of correlated observation noises	p. 154
Optimal Computing Budget Allocation and Nested Partition	p. 159
OCBA	p. 160
NP	p. 164
Performance order vs. performance value	p. 168
Combination with other optimization algorithms	p. 175
Using other algorithms as selection rules in OO	p. 177
GA+OO	p. 177
SA+OO	p. 183
Simulation-based parameter optimization for algorithms	p. 186
Conclusion	p. 188
Real World Application Examples	p. 189
Scheduling problem for apparel manufacturing	p. 190
Motivation	p. 191
Problem formulation	p. 192
Demand models	p. 193
Production facilities	p. 195
Inventory dynamic	p. 196
Summary	p. 197
Application of ordinal optimization	p. 198
Random sampling of designs	p. 199
Crude model	p. 200
Experimental results	p. 202
Experiment 1: 100 SKUs	p. 202
Experiment 2: 100 SKUs with consideration on satisfaction rate	p. 204
Conclusion	p. 206
The turbine blade manufacturing process optimization problem	p. 207
Problem formulation	p. 208
Application of OO	p. 213
Conclusion	p. 219
Performance optimization for a remanufacturing system	p. 220
Problem formulation of constrained optimization	p. 220
Application of COO	p. 224
Feasibility model for the constraint	p. 224
Crude model for the performance	p. 224
Numerical results	p. 225
Application of VOO	p. 227
Conclusion	p. 232
Witsenhausen problem	p. 232
Application of OO to find a good enough control law	p. 234
Crude model	p. 235
Selection of promising subsets	p. 237
Application of OO for simple and good enough control laws	p. 245
Conclusion	p. 251
Fundamentals of Simulation and Performance Evaluation	p. 253
Introduction to simulation	p. 253
Random numbers and variables generation	p. 255
The linear congruential method	p. 255
The method of inverse transform	p. 257
The method of rejection	p. 258
Sampling, the central limit theorem, and confidence intervals	p. 260
Nonparametric analysis and order statistics	p. 262
Additional problems of simulating DEDS	p. 262
The alias method of choosing event types	p. 264
Introduction to Stochastic Processes and Generalized Semi-Markov Processes as Models for Discrete Event Dynamic Systems and Simulations	p. 267
Elements of stochastic sequences and processes	p. 267
Modeling of discrete event simulation using stochastic sequences	p. 271
Universal Alignment Tables for the Selection Rules in Chapter III	p. 279
Exercises	p. 291
True/False questions	p. 291
Multiple-choice questions	p. 293
General questions	p. 297
References	p. 305
Index	p. 315
Table of Contents provided by Ingram. All Rights Reserved.