Optimum Allocation in Multivariate Stratified Random Sampling: A Modified Prékopa’s Approach

Considering the possible correlation between the characteristics (variables) in multivariate stratified random sampling, a modified Prékopa’s approach is suggested for the problem of optimum allocation in multivariate stratified random sampling. An example is solved by applying the proposed methodology.     

On the Hungarian inventory control model

In this paper we recall and further develop an inventory model formulated by the author [Prékopa, A., 1965. Reliability equation for an inventory problem and its asymptotic solutions. In: Prékopa, A. (Ed.), Colloquia Applied Mathematics in Economics. Publ. House of the Hung. Acad. Sci., Budapest, pp. 317–327; Prékopa, A., 1973. Generalizations of the theorems of Smirnov with application to a reliability type inventory problem. Math. Operationsforschung und Stat. 4, 283–297] and Ziermann [Ziermann, M., 1964. Application of Smirnov’s theorems for an inventory control problem. Publications of the Mathematical Institute of the Hungarian Academy of Sciences Ser. B 8, 509–518] that has had wide application in Hungary and elsewhere. The basic assumption made in connection with this model is that the delivery of the ordered amount takes place in an interval, according to some random process, rather than at one time epoch. The problem is to determine that minimum level of safety stock, that ensures continuous production, without disruption, by a prescribed high probability. The model is further developed first by its combination with another inventory control model, the order up to S model and then, by the formulations of a static and a dynamic type stochastic programming models.     

Solution of and bounding in a linearly constrained optimization problem with convex,polyhedral objective function

A dual method is presented to solve a linearly constrained optimization problem with convex, polyhedral objective function, along with a fast bounding technique, for the optimum value. The method can be used to solve problems, obtained from LPs, where some of the constraints are not required to be exactly satisfied but are penalized by piecewise linear functions, which are added to the objective function of the original problem. The method generalizes an earlier solution technique developed by Prékopa (1990). Applications to stochastic programming are also presented.This research was supported by the National Science Foundation, Grant No. DMS-9005159.Corresponding author.     

The discrete moment problem with fractional moments

Discrete moment problems (DMP) with integer moments were first introduced by Prékopa to provide sharp lower and upper bounds for functions of discrete random variables. Prékopa also developed fast and stable dual type linear programming methods for the numerical solutions of the problem. In this paper, we assume that some fractional moments are also available and propose basic theory and a solution method for the bounding problems. Numerical experiments show significant improvement in the tightness of the bounds.     

A modification of the stochastic ruler method for discrete stochastic optimization

We propose a modified stochastic ruler method for finding a global optimal solution to a discrete optimization problem in which the objective function cannot be evaluated analytically but has to be estimated or measured. Our method generates a Markov chain sequence taking values in the feasible set of the underlying discrete optimization problem; it uses the number of visits this sequence makes to the different states to estimate the optimal solution. We show that our method is guaranteed to converge almost surely (a.s.) to the set of global optimal solutions. Then, we show how our method can be used for solving discrete optimization problems where the objective function values are estimated using either transient or steady-state simulation. Finally, we provide some numerical results to check the validity of our method and compare its performance with that of the original stochastic ruler method.     

Pattern definition of the p-efficiency concept

This study revisits the celebrated p-efficiency concept introduced by Prékopa (Z.?Oper. Res. 34:441?C461, 1990) and defines a p-efficient point (pLEP) as a combinatorial pattern. The new definition uses elements from the combinatorial pattern recognition field and is based on the combinatorial pattern framework for stochastic programming problems proposed in Lejeune (Stochastic programming e-print series (SPEPS) 2010-5, 2010). The approach is based on the binarization of the probability distribution, and the generation of a consistent partially defined Boolean function representing the combination (F,p) of the binarized probability distribution F and the enforced probability level p. A combinatorial pattern provides a compact representation of the defining characteristics of a pLEP and opens the door to new methods for the generation of pLEPs. We show that a combinatorial pattern representing a pLEP constitutes a strong and prime pattern and we derive it through the solution of an integer programming problem. Next, we demonstrate that the (finite) collection of pLEPs can be represented as a disjunctive normal form (DNF). We propose a mixed-integer programming formulation allowing for the construction of the DNF that is shown to be prime and irreducible. We illustrate the proposed method on a problem studied by Prékopa (Stochastic programming: handbook in operations research and management science, vol.?10, Elsevier, Amsterdam, 2003).     

Properties and calculation of multivariate risk measures: MVaR and MCVaR

A recent paper by Prékopa (Ann. Oper. Res. 193(1):49–69, 2012) presented results in connection with Multivariate Value-at-Risk (MVaR) that has been known for some time under the name of p-quantile or p-Level Efficient Point (pLEP) and introduced a new multivariate risk measure, called Multivariate Conditional Value-at-Risk (MCVaR). The purpose of this paper is to further develop the theory and methodology of MVaR and MCVaR. This includes new methods to numerically calculate MCVaR, for both continuous and discrete distributions. Numerical examples with recent financial market data are presented.     

Testing successive regression approximations by large-scale two-stage problems

A heuristic procedure, called successive regression approximations (SRA) has been developed for solving stochastic programming problems. They range from equation solving to probabilistic constrained and two-stage models through a combined model of Prékopa. We show here, that due to enhancements in the computer program, SRA can be used to solve large-scale two-stage problems with 100 first stage decision variables and a 120 dimensional normally distributed random right hand side vector in the second stage problem. A FORTRAN source program and computational results for 124 problems are presented at .     

Mesh optimization for singular axisymmetric harmonic maps from the disc into the sphere

We describe in a mathematical setting the singular energy minimizing axisymmetric harmonic maps from the unit disc into the unit sphere; then, we use this as a test case to compute optimal meshes in presence of sharp boundary layers. For the well-posedness of the continuous minimizing problem, we introduce a lower semicontinuous extension of the energy with respect to weak convergence in BV, and we prove that the extended minimization problem has a unique singular solution. We then show how a moving finite element method, in which the mesh is an unknown of the discrete minimization problem obtained by finite element discretization, mimics this geometric point of view. Finally, we present numerical computations with boundary layers of zero thickness, and we give numerical evidence of the convergence of the method. This last aspect is proved in another paper. This work was supported by the Centre de Mathématiques et de Leurs Applications, Ecole Normale Supérieure de Cachan, 61 av. du Président Wilson, 94235 Cachan Cedex, France     

Johri's general dual,the Lagrangian dual,and the surrogate dual

Duality formulations can be derived from a nonlinear primal optimization problem in several ways. One abstract theoretical concept presented by Johri is the framework of general dual problems. They provide the tightest of specific bounds on the primal optimum generated by dual subproblems which relax the primal problem with respect to the objective function or to the feasible set or even to both. The well-known Lagrangian dual and surrogate dual are shown to be special cases. Dominating functions and including sets which are the two relaxation devices of Johri's general dual turn out to be the most general formulations of augmented Lagrangian functions and augmented surrogate regions.     

Combinatorial results on the fitting problems of the multivariate gamma distribution introduced by Prékopa and Szántai

Generalizations of the results of an earlier paper of the second author, related to the problem of fitting a multivarite gamma distribution to empirical data, are discussed in the paper. The multivariate gamma distribution under consideration is the one that was introduced in the paper of Prékopa and Szántai (in Water Resources Research, 14:19?C24, 1978), some earlier results on the fitting problem were given in the paper of Szántai (in Alkalmazott Matematikai Lapok 10:35?C60, 1984). In the present paper it is proved that the necessary conditions given earlier are not sufficient and some further new, mostly computational results are provided, too. Using the more efficient computation tools we are able now to give the sufficient conditions for dimensions 5 and 6 as well. For higher dimensions we have only necessary conditions and the invention of a suitable necessary and sufficient condition remains an open problem when n is greater than 6. The miscellaneousness of the necessary and sufficient conditions obtained in our new project for n=6 indicates that finding necessary and sufficient conditions in general should be a very hard problem.     

The bilevel linear/linear fractional programming problem

Bilevel programming involves two optimization problems where the constraint region of the first level problem is implicitly determined by another optimization problem. In this paper we consider the bilevel linear/linear fractional programming problem in which the objective function of the first level is linear, the objective function of the second level is linear fractional and the feasible region is a polyhedron. For this problem we prove that an optimal solution can be found which is an extreme point of the polyhedron. Moreover, taking into account the relationship between feasible solutions to the problem and bases of the technological coefficient submatrix associated to variables of the second level, an enumerative algorithm is proposed that finds a global optimum to the problem.     

A canonical dual approach for solving linearly constrained quadratic programs

This paper provides a canonical dual approach for minimizing a general quadratic function over a set of linear constraints. We first perturb the feasible domain by a quadratic constraint, and then solve a “restricted” canonical dual program of the perturbed problem at each iteration to generate a sequence of feasible solutions of the original problem. The generated sequence is proven to be convergent to a Karush-Kuhn-Tucker point with a strictly decreasing objective value. Some numerical results are provided to illustrate the proposed approach.     

A Riemannian interpolation inequality à la Borell, Brascamp and Lieb

A concavity estimate is derived for interpolations between L ¹(M) mass densities on a Riemannian manifold. The inequality sheds new light on the theorems of Prékopa, Leindler, Borell, Brascamp and Lieb that it generalizes from Euclidean space. Due to the curvature of the manifold, the new Riemannian versions of these theorems incorporate a volume distortion factor which can, however, be controlled via lower bounds on Ricci curvature. The method uses optimal mappings from mass transportation theory. Along the way, several new properties are established for optimal mass transport and interpolating maps on a Riemannian manifold. Oblatum 1-XII-2000 & 3-V-2001?Published online: 13 August 2001     

On the safety stock problem for random delivery processes

Inventory models are considered in which the delivery of an order occurs not on one occasion but at random moments of a period in random parts. We give two extensions of the reliability type inventory model of A. Prékopa. In this model a known constant demand rate is assumed and a simple approximate formula is given for the initial stock of the order period which serves as safety stock and ensures a continuous supply during the whole order period on a prescribed probability level. This formula is widely used in practice for safety stock planning in the case when deliveries in random parts occur.We formulate a generalized version of the random delivery process and derive the exact solution of the safety stock which can be applied also for the previous model. In the second model a random demand rate is considered together with a random delivery process. An exact solution method and a simple approximate formula for the safety stock will be discussed. We have experiences in the application of these models both in a steel works and a textile factory in Hungary.     

离散变量的分级优化方法及其应用

在工程优化设计中,绝大多数实际问题的设计变量往往限定取离散值,为了求得问题的真正最优解,就必须采用离散变量的优化方法进行求解.本文根据离散变量数学规划的特性,提出了一种分级优化搜索算法.这种方法的基本思想是在约束集合内,寻求一可行的离散初始点,然后在该点的邻域内,进行分级寻优搜索,以求得一个改进的新离散点,随之,以该点作为初始点,重复执行分级寻优搜索过程,直至求得问题的最优解.通过对工程实例的计算,证明本文所提出的新方法具有快速、简便的特点,能有效地应用各种工程优化设计问题.     

Heat Equation and Convolution Inequalities

It is known that many classical inequalities linked to convolutions can be obtained by looking at the monotonicity in time of convolutions of powers of solutions to the heat equation, provided that both the exponents and the coefficients of diffusions are suitably chosen and related. This idea can be applied to give an alternative proof of the sharp form of the classical Young’s inequality and its converse, to Brascamp–Lieb type inequalities, Babenko’s inequality and Prékopa–Leindler inequality as well as the Shannon’s entropy power inequality. This note aims in presenting new proofs of these results, in the spirit of the original arguments introduced by Stam [35] to prove the entropy power inequality.     

非线性整数规划的一个新的无参数填充函数算法

离散填充函数是一种用于求解多极值优化问题最优解的一种行之有效的方法.已被证明对于求解大规模离散优化问题是有效的.本文基于改进的离散填充函数定义,构造了一个新的无参数填充函数,并在理论上给出了证明,提出了一个新的填充函数算法.该填充函数无需调节参数,而且只需极小化一次目标函数.数值结果表明,该算法是高效的、可行的.     

基于时间满意度的应急物资储备库选址问题

基于应急物资配送过程中时间因素的重要性,将时间满意度引人应急物资储备库选址问题中.针对时间满意度为线性分段函数,建立了以时间满意度最小的需求点的时间满意度尽量大以及系统总费用最小为目标的双目标混合整数规划模型,对目标函数的最小最大值问题进行转化,在此基础上构造新的优化模型,并设计了相应的启发式算法求解.最后通过算例说明算法的可行性和有效性.     

Entropic perturbation method for solving a system of linear inequalities

The problem of finding an $\text{x∈}\text{R}{}^{\mathrm{n}}$ such that Ax⩽b and x⩾0 arises in numerous contexts. We propose a new optimization method for solving this feasibility problem. After converting Ax⩽b into a system of equations by introducing a slack variable for each of the linear inequalities, the method imposes an entropy function over both the original and the slack variables as the objective function. The resulting entropy optimization problem is convex and has an unconstrained convex dual. If the system is consistent and has an interior solution, then a closed-form formula converts the dual optimal solution to the primal optimal solution, which is a feasible solution for the original system of linear inequalities. An algorithm based on the Newton method is proposed for solving the unconstrained dual problem. The proposed algorithm enjoys the global convergence property with a quadratic rate of local convergence. However, if the system is inconsistent, the unconstrained dual is shown to be unbounded. Moreover, the same algorithm can detect possible inconsistency of the system. Our numerical examples reveal the insensitivity of the number of iterations to both the size of the problem and the distance between the initial solution and the feasible region. The performance of the proposed algorithm is compared to that of the surrogate constraint algorithm recently developed by Yang and Murty. Our comparison indicates that the proposed method is particularly suitable when the number of constraints is larger than that of the variables and the initial solution is not close to the feasible region.