Summary of András Prékopa's Scientific Results
András Prékopa published his first paper while he was an undergraduate student at the University of Debrecen, Hungary. The paper solved a probability problem, a generalization of the Banach matchbox problem, where random amounts from randomly chosen finite capacity containers are taken subsequently to meet demands until the first exhaustion occurs. The question is what are the expected, still available amounts in the remaining containers? The Banach problem is a special case, where there are two containers and each time a unit amount is taken from the randomly chosen container.
Stochastic set functions and related topics
During the years when he was working for the Ph.D., he worked on the Poisson processes, their generalizations, random set functions and stochastic integrals. He is among those who first developed the theory of random measures and random set functions in the nineteen fifties: the Swedish mathematician H. Cramér, the Polish mathematicians E. Marczewski, C. Ryll-Nardzewski and the Hungarian mathematician A. Prékopa. Prékopa's results go the farthest. He defined the notion of a random (stochastic) set function of independent increments in a general, abstract space. One of the main results was the extension of a completely additive random set function, defined on a ring or algebra, to a σ-ring or a -algebra. The obtained extension theorems are stochastic counterparts of Carathéodory's measure extension theorems. Also, he introduced the notion of a characteristic functional, proved Radon-Nikodym type theorems, defined stochastic Lebesgue integrals with random measures and deterministic, measurable integrands. One of the highlights of his theory is the proof of a product space theorem in which he proved that given an underlying random point distribution (r.p.d.) of Poisson type in an abstract space X, with non-atomic parameter measure, where the random points give rise independently to further random variables with values from another abstract space Y, then the r.p.d. in the product space X × Y is also of Poisson type. The parameter measure of the resulting r.p.d. is given by an integral formula. The paper, where the above result was published contains another noteworthy theorem: If the parameter measure of an r.p.d. with independent increments is non-atomic, then it is of Poisson type. The paper, at the same time, initiated the theory of marked Poisson processes. When Prékopa obtained the above-mentioned results it was not allowed for Hungarian scientists to publish abroad. So, his papers appeared in local journals but were written in English, so they are available for the international readership.
Copies of those old papers as well as some of the newer ones can be retrieved by the use of his homepage: rutcor.rutgers.edu/~prekopa/.
At the beginning of the nineteen sixties he worked out a novel inventory control model that became widely used in Hungary and elsewhere. In Hungary it resulted in savings of billions (in terms of dollars). The problem was to determine the initial safety stock levels of basic materials and semi-final products in industrial plants, to ensure continuous production on a given safety level. The model was formulated jointly with his former colleague M. Ziermann. They identified order statistics as the methodology to solve the problems. Prékopa went further. He generalized Smirnov's theorems, using deep mathematical tools from the theory of measures in function spaces that allowed him for the derivation of fairly general and practically useful formulas to determine the safety stock levels. The above results are beautiful examples of problem solutions, where deep mathematics and important practical applications are combined. In a further paper with P. Kelle he formulated and solved optimization type variants of the safety stock problems, where the solutions are no longer given by algorithms, rather than by formulas. Recently, he published even more general problem solutions that appeared in EJOR, and wrote a further paper with N. Noyan, in the Journal of Production Economics. The last two papers are based to a large extent on classical results of Kolmogorov, Doob and Donsker on the distribution of funcionals defined on the trajectories of Gaussian stochastic processes.
Stochastic programming and logconcavity
In the nineteen sixties Prékopa's intersest turned to stochastic programming. In his first paper on the subject he proved, under some conditions, that the probability distribution of the optimum value of a random linear programming problem is normal. The result allows for confidence interval construction to the optimum value in those LP's. In another paper, he proved that if randomness is in the technology matrix, the sizes of which grow unlimited, then, under some mild conditions, the difference between the random optimum value and the deterministic optimum value of the LP, written up with the expectations, goes to zero with probability one or in probability, depending on the assumptions. The results received applications also in game theory and population dynamics.
As regards the decision models of stochastic programming, Charnes and Cooper were the first who formulated one of the three basic model types and called it chance constrained programming. However, they imposed probability constraint individually on each stochastic constraint, neglected the stochastic dependence among the random variables involved, thus, their formulation was incomplete. The general formulation, taking into account stochastic dependence, was given by Prékopa and by that earned himself the place as one of the initiator of stochastic programming. One of his main results in the area concern convexity theory of probabilistic constrained stochastic programming problems. His results, however, are of more general significance. He introduced the concept of logarithmic concave measures and proved fundamental theorems. One of them states that if a probability measure is generated by a logconcave probability density (point) function, then the measure is logconcave. An other one states that if we integrate a multivariate logconcave function with respect to some of the variables in their entire space, then the resulting function of the other variables is logconcave. While logconvexity is a relatively simple mathematical theory, logconcavity is deep and is widely applicable. These breakthrough results supplied proof for the convexity of a wide class of probabilistic constrained stochastic programming problems. They also became celebrated and widely applied results in physics, statistics, economics, convex geometry, mathematical analysis and a variety of other fields. The inequality that expresses the result in the first theorem is sometimes misquoted as Prékopa-Leindler inequality. After Prékopa published his theorem, Leindler became interested in one of his auxiliary theorems and gave various generalizations to it but not to the theorem itself. Logconcavity theory helped the convexity theory of stochastic programming in many ways. It also initiated the formulation of the notion and the development of the theory of r-concave probability measures. Even though those are nice mathematical constructions, most of the known and practically important probability distributions are logconcave and very few known probability distributions are r-concave for some r but not logconcave.
Prékopa's results very much impressed Abraham Charnes. In the 1970s Charnes was the secretary of foreign affairs of the National Academy of Engineering of Mexico and in 1977 he proposed Prékopa a foreign corresponding member of that Academy. In his letter to Prékopa, dated February 23, 1977 he wrote: 'To set the honor in perspective, I am also nominating Professor L. Kantorovich, the Russian Nobel Prize winner, as a member.'
Prékopa gave the first algorithm and presented many others for the solution of the probabilistic constrained stochastic programming problem. He also formulated and solved many practical problems of that type for water resources, power systems, economics, network reliability problems, etc. Noteworthy is his model that he formulated for the five year plan of the electrical energy sector of the Hungarian economy, together with Deák, Ganczer and Patyi. When working with the expectations of the random variables, that appeared in the model, the resulting LP produced an optimum value that was not significantly smaller (cost function was to be minimized) than the optimum value of the probabilistic constrained problem, using 95% reliability level. However, the deterministic optimal solution produced only 10% reliability when plugged in into the constraining function in the probabilistic constraint. Thus, without any significant increase in the cost, a highly reliable solution was obtained instead of an unreliable one. The optimal solution, however, was significantly different. The above example shows the power of the stochastic programming in important real life problems.
The solutions of the probabilistic constrained stochastic programming problems with continuous probability distributions are computationally intensive and involve multivariate numerical integration when calculating function and gradient values of the probability in the probabilistic constraint. Somewhat easier is the solution if the random variables in the problem are discrete which case comes frequently up in practice. In order to solve such problems in an efficient way Prékopa introduced the concept of a p-level efficient, or briefly p-efficient point. He gave three algorithmic solutions to this problem, one himself alone, one with Vizvári and Badics and one with Dentcheva and Ruszczyński. The use of p-efficient points became widespread in the literature, since their introduction in 1990 and generated a variety of papers in the field. One of Prékopa's recent papers, where both the discrete and the continuous models are discussed, presents a relationship among probabilistic constrained stochastic programming, disjunctive and multiobjective programming, together with new duality theorems and a new way of solution of the presented problems, where at any iteration we obtain lower and upper bounds for the optimum value such that their differences go to zero monotonically.
Bounding probabilities and expectations, discrete moment problems
In the middle of the nineteen eighties he initiated the development of novel techniques to obtain sharp probability bounds for the probability of the union and other Boolean functions of random events. These results lead him to the discovery that the sharp probability bounds on the probabilities of various Boolean functions of events, that use a few terms from the inclusion-exclusion formula, are optimum values of LP's, that are moment problems with known discrete supports of the random variables involved. Even though problems of that type have already mentioned in books about moment problems, Prékopa was the first who explored the structure of those problems, by the use of linear programming theory, both in the univariate and multivariate cases. In the univariate case he fully described the structure of the dual feasible bases for three special objective functions. The results allowed for the derivation of formulas for the solution of small scale problems as well as the formulation of efficient dual type algorithms, for large problems. Also, he presented a variety of closed form bounds, together with E. Boros. It should be mentioned that any dual feasible basis produces a bound that is sharp if the basis is also primal feasible. Linear programming turned out to be the efficient tool to obtain the best bounds. The three special objective functions made it possible to derive bounds for the probability of the union and the probability that at least r or exactly r out of n events occur. The multivariate case is more complex, multivariate Lagrange interpolation is involved but a variety of dual feasible bases have been discovered, with optimum values, i.e., bounds, obtained in the forms of formulas and algorithms. Some of the multivariate results have been obtained jointly with G. Mádi-Nagy. If we use the binomial moments of the number of events that occur, then the corresponding LP is termed aggregated. If we use individually the joint probabilities of the events, then the LP is termed disaggregated. The disaggregated problem is extremely large but provides us with closer bounds than the aggregated problems. Based on the disaggregated problem Prékopa gave further bounds for the probability of the union and other functions of the events, with J. Bukszár and L. Gao, as coauthors. Most recently he published a paper, together with X. Hou, where the Monge property is revisited, from the point of view of LP theory and bounds for probability distribution functions have been established. In a few recent papers, published jointly with E. Subasi and M. Subasi the bounds are created under further constraints: the shape of the probability distribution is prescribed. Finally, Prékopa also showed how to use the univariate and multivariate bounds for the approximate solution of the probabilistic constrained stochastic programming problem. Successful practical applications of the above-mentioned bounds have been carried out by Prékopa and his coathors for telecommunication and transpoertation network reliability, bounding the probability distribution of the critical path in PERT, solution of the satisfiability problem, etc. Note that stochastic method (probability bounds) have been applied for the solution of the deterministic satisfiability problem The numerical results show that the above-described bounds are very powerful and easy to apply.
Results in economics and finance
Here too, the paper on the five year plan of the electrical energy sector of the Hungarian economy should be mentioned. Recently, with G. Mádi-Nagy, Prékopa published a paper on a class of multiattribute utility functions that have analytic forms, their total order derivatives alternate in sign and couple single attribute utility functions that have similar properties. If the values of the attributes are random, bounds on the expected utility, based on moment information, are also given. In one paper, with T. Szántai, a new and probably highly accurate method is presented for the valuation of the Bermudan and American options. Dynamic programming models are formulated for the put and call options, with dividends and the solutions are presented in recursion formulas that, in turn, are numerically evaluated using sophisticated integration technique for the multivariate normal p.d.f. The paper appeared in the journal of Quantitative Finance; more computational results can be found in a Rutcor Research report by the same authors. In another paper, presented in the INFORMS meeting in Pittsburgh, 2006, Prékopa gave bounds for the values of financial derivatives based on discrete and continuous moment problems that are not special cases of the moment problems discussed above. In addition to the results in finance, the paper contains other important results: further develops the LP and semi-infinite LP solution technique for the solution of the moment problems. In a recent paper, presented at the EURO meeting in Prague, 2007, a novel conditional mean-conditional variance optimal portfolio selection model is formulated and solved, complementing the VaR and CVaR methodology with the use of the conditional variance. Finally, he just published a paper on Multivariate Value at Risk and related topics that was presented as a plenary talk at the APMOD 2008 meeting in Bratislava. The paper opens up a wide avenue for modern and from the point of view of practical application very important financial research.
Water, power, telecommunication engineering and other applied results
Even though the results mentioned in this section are termed 'applied', they are also of theoretical interest because either a new model and/or some new theoretical development is presented in each of them. In connection with water resources, Prékopa created novel stochastic programming type reservoir system design models that have been shown to be convex programs and solved algorithmically. In connection with power systems the results are partly of stochastic network design, partly of transportation network reliability type. He also worked out a deterministic optimal daily scheduling model for electricity production in an interconnected system with thermal power plants, where the unit commitment problem is handled simultaneously with the network constraints. This lead to a large scale nonconvex, nonlinear, mixed (0 − 1) variable optimization problem that was solved almost instantly for the Hungarian power system. Even today it is a noteworthy and applicable methodology. A 200 page paper about the results, originally written in the Hungarian language, is now available in English. He also published papers on telecommunication network design and reliability. The other applications include the fields of chemistry, dietetics, medicine and those mentioned in other sections of this report
History of science
Prékopa also has important papers in connection with history of science. He discovered the origins of nonlinear optimization theory and published papers about it. He wrote papers about the life and works of J. Farkas, the eminent Hungarian mathematician and physicist of the 19-20th centuries, who developed the theory of linear inequalities and published fundamental papers on the mechanical equilibrium. The last mentioned results initiated nonlinear optimization. He commemorated the life and works of Farkas on November 5, 2006 at the INFORMS annual meeting in Pittsburgh, PA, when the Farkas prize was first awarded. Recently, in a volume devoted to the memory of the world famous Hungarian mathematician János Bolyai, he gave an account of the discovery of non-Euclidean geometry in the first half of the 19th century that changed the course of the development of mathematics and also had an impact on the history of human culture. In further papers he discussed the relationship between mathematics and cultural history.
Among the books mentioned in his list of publications we call the attention to his introductory book on Linear Programming that appeared only in Hungarian and his book on Stochastic Programming that appeared in English. The first one was published in 1968 (Prékopa gave his first course on the subject at the University of Budapest in 1958). The book presents linear programming in a mathematically exact, elegant and didactical way and it is still used in Hungary for graduate level courses (it is being extended and translated into English). In the early nineteen seventies an Oxford professor used the book for his courses, by the aid of a Hungarian-English dictionary. The Stochastic Programming book is a high level very informative book that can be used to teach the subject but it is also an excellent source of knowledge in doing research and/or application.