
(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 selfpromotion,
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 humanmade systems, such as largescale
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 decisionmaking 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 multidimensional 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 NPhard 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 COMPLEXITY
oCOMPUTATIONAL INTENSITY
oLACK OF EXTANT LITERATURE
oFUNDAMENTAL MATHEMATICAL LIMITATIONS
II. IDEAS FOR SOLUTION
There 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 knowledgebased instead of being experiencebased. 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 EXAMPLES
There 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 NPhard 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
humanmade 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
inglove 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 computationintensive models involving
possible stochastic effects and discrete choices.
V. CONCLUSION
Of course, sections IIV 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 何毓琦院士教年轻人如何做科研 精选
Archiver手机版科学网 ( 京ICP备14006957 )
GMT+8, 20181217 01:18
Powered by ScienceNet.cn
Copyright © 2007 中国科学报社