How to Do Research #3

(For new reader and those who request 好友请求, please read my 公告栏 first)

HOW TO DO RESEARCH 3 – PRACTICE WHAT YOU PREACH I am most gratified by the response to my two blog articles "How to Do Research?" and "More on How to Do Research". In the space of one week a total of 1500+ persons have read the articles. In the spirit of practicing what I preach, but at the risk of self-promotion, let me give you an example on how my recommendation on "finding a good research topic" benefited myself. For convenience I repeated the recommendation here:“GO FIND A REAL WORLD PROBLEM THAT A GROUP OF PEOPLE IS EAGER TO SOLVE, THAT HAPPENS TO INTEREST YOU FOR WHATEVER REASON, AND THAT YOU DON'T KNOW MUCH ABOUT. MAKE A COMMITMENT TO SOLVE IT BUT NOT A COMMITMENT TO USE TOOLS WITH WHICH YOU HAPPEN TO BE FAMILIAR" (But you should really read this rule in the context of the whole article)I.THE REAL WORLD PROBLEM:Civilization have increasingly created complex human-made systems, such as large-scale electric power grids, air and land traffic control systems, manufacturing plants and supply chains, the Internet and other communication networks, etc. Such systems operate and evolve in time via human made rules of operation, and are difficult to describe and capture by succinct mathematical models such as differential equations for physical systems. Collectively, they are known as Discrete Event Dynamic Systems (DEDS). In fact, the only faithful description of such complex systems is by way of an electronic copy, i.e., a simulation model/program that duplicates everything the real system does in real or simulation time. Evaluation of the performance of such system is accomplished by running such simulation models rather than experimenting with the real systems. To give a familiar example, Consider the Beijing Capital International Airport. On the landside, there are passengers, taxis, buses, and private cars. On the airside, there are planes, military, commercial , and private. All these entities arrive stochastically or are subject to stochastic disturbance such as weather or equipment breakdown. They all require and compete for a series of services from facilities at the airport. For example, in the case of a passenger arriving by car, s/he need parking spaces, luggage handling, check in, security inspection, rest room, snack place, and waiting lounges. It is easy to see that such a system can only be modeled accurately via a simulation model. And simulating and experimenting with the behavior of such a system over a period of say 24 hours, will require considerable amount of computer time. Typically, the time required for one particular evaluation of the system performance can take hours or even days of computer time.But this is not the end of the problem difficulty. Other fundamental mathematical limitations further complicates the problem.It is a well known statistical fact that under the best of circumstance the accuracy of an estimate improves very slowly with the number of samples used to calculate the estimate.. For every one order of magnitude increase in accuracy of the estimate, the number of samples must increase by two orders of magnitude. Since each sample run of the simulation model of a complex system may consume considerable time, running the simulation model many times to achieve an accurate estimate of the performance may impose a heavy burden. And if optimization using the system designs parameters is planned, the total amount of computation required quickly becomes infeasible. As a result, simulation model are often used for validation of a design obtained by other means and not for optimization purposes.To make matters worse, while the literature on optimization and decision-making is huge, much of the concrete analytical results are associated with what may be called Real Variable Based methods. The idea of successive approximation to an optimum (say, minimum) by sequential improvements based on local information is often captured by the metaphor of "skiing downhill in a fog". The concepts of gradient (slope), curvature (valley), and trajectories of steepest descent (fall line) all require the notion of derivatives and are based on the existence of a more or less smooth response surface. There exist various first and second order algorithms of feasible directions for the iterative determination of the optimum (minimum) of an arbitrary multi-dimensional response or.performance surface. Considerable numbers of major success stories exist in this genre including the Nobel Prize winning work on linear programming. It is not necessary to repeat or even reference these here.On the other hand, in spite of the tremendous development of the science and art of optimization and computation, there remain many problems that are still beyond our reach. Among them are the class of combinatorial NP-hard problems and the well known "curse of dimensionality" in dynamic programming. Exponential growth is one law that mathematics and computers cannot overcome. Thus summarizing, the problems are:oSYSTEM COMPLEXITYoCOMPUTATIONAL INTENSITYoLACK OF EXTANT LITERATUREoFUNDAMENTAL MATHEMATICAL LIMITATIONSII. IDEAS FOR SOLUTIONThere are two basic ideas in the methodology of Ordinal Optimization (OO, "序优化") :: o"Order" is much more robust against noise than "Value", i.e. "Asking which is better?" is a much easier question than "how much better"oDon't insist on getting the "Best" but be willing to settle for the "Good Enough" – remember the proverb "best is the enemy of good enough"Space limitation prevent me to further elaborate on these simple notions by intuitive explanations. More details can be found below in section III. Essentially we are making a slight compromise in what we are asking in order to gain advances on the solution front. Of course readers may rightly point out that these ideas are hardly new and very simple. Good engineers and designers do this all the time when confronted with difficult and complex problems of performance evaluation and optimization. My own contribution is simply that we have developed a theory to QUANTIFY these two ideas. The practice of these two ideas is now knowledge-based instead of being experience-based. The expertise of a good designer acquired from experience will now be available to everyone who uses the tools discussed in this methodology. Moreover, the user will have numerical measures rather than just gut feelings. III. APPLICATION EXAMPLESThere are now over 250 references on the topics of Ordinal Optimization (OO, "序优化"). See the annotated list at cfins.au.tsinghua.edu.cn. But my favorite example is the one that led to the invention of OO which I discovered one rainy afternoon in 1991, which I still use to demonstrate the two basic ideas, which you can set up yourself on EXCEL in about 15 minutes, and which can also be found on my web site www.hrl.harvard.edu/~ho. By September 2007, a complete book on this topic which I co-authored with my Tsinghua colleagues will be published by Springer.IV. THE METHODOLOGY OF ORDINAL OPTIMIZATION AND IT RELATIONSHIP TO OTHER TOOLS"Optimization" taken in the broadest sense as seeking improvement is an idea as old as the existence of human beings. In fact, it can be argued that it is the "raison d'être" for our civilization. Without the desire to improve, progresses on all fronts will stall. Yet the study of optimization as a discipline and not as individual endeavors on specific problems did not begin until the invention of calculus, which enabled the mathematical modeling of large number of physical phenomena. The theory of maxima/minima and convexity emerged as a result. Yet the numbers of real world problems that can be explicitly solved by mathematics alone remain limited until the development of the computer. Suddenly, many algorithms, which previously thought to be infeasible for the numerical and iterative solution of difficult optimization problems, now become possible. The golden age of optimization took off in the 1950s and is still ongoing. On the other hand, in spite of the tremendous development of the science and art of optimization and computation, there remain many problems that are still beyond our reach. Among them are the class of combinatorial NP-hard problems and the well known "curse of dimensionality" in dynamic programming. Exponential growth is one law that mathematics and computers cannot overcome. Furthermore, computational burden of a problem does not always necessarily arise because of problem size. Complexity of a problem can also impose infeasible computational burdens as the simulation model of human made systems..Furthermore, we submit that the reason many real world optimization problems remain unsolved is partly due to the changing nature of the problem domain, which makes calculus or real variable based method less applicable. For example, a large number of human-made system problems mentioned above involve combinatorics, symbolic or categorical variables rather than real analysis, discrete instead of continuous choices, and synthesizing a configuration rather than proportioning the design parameters. Optimization for such problem seems to call for general search of the performance terrain or response surface as opposed to the "skiing downhill in a fog" metaphor of real variable based performance optimization . Arguments for change can also be made on the technological front. Sequential algorithms were often dictated as a result of the limited memory and centralized control of earlier generations of computers. With the advent of modern massively parallel machines, distributed and parallel procedures can work hand-in-glove with Search Based method of performance evaluation. The purpose of OO is to address the difficulties of optimization problems described above – the optimization of complex systems via simulation models or other computation-intensive models involving possible stochastic effects and discrete choices.V. CONCLUSIONOf course, sections I-IV represent hindsight. When I started out on that rainy afternoon in 1991 or published the first paper in 1992, I certainly did not have this vision. But I knew enough at the time that the ideas of OO addressed most of the difficulties of the real world problems and had success on some computational issues previously thought to be infeasible. I also had three decades of experience with and confidence in my own recommended rule of research that I applied for funding, encouraged graduate students and postdocs, and dedicated my own efforts for 15 years on the subject.. It is what researchers called a first generation research topic (or what I denote as the second level of research problem discussed in my first blog on the subject of "how to do research".

Note added 5/11/2106: There is a nice Chinese summary of this and related article at http://blog.sciencenet.cn/home.php?mod=space&uid=535297&do=blog&id=636074 何毓琦院士教年轻人如何做科研 精选