Distributionally robust mixed integer linear programs: Persistency models with applications

In this paper, we review recent advances in the distributional analysis of mixed integer linear programs with random objective coefficients. Suppose that the probability distribution of the objective coefficients is incompletely specified and characterized through partial moment information. Conic programming methods have been recently used to find distributionally robust bounds for the expected optimal value of mixed integer linear programs over the set of all distributions with the given moment information. These methods also provide additional information on the probability that a binary variable attains a value of 1 in the optimal solution for 0–1 integer linear programs. This probability is defined as the persistency of a binary variable. In this paper, we provide an overview of the complexity results for these models, conic programming formulations that are readily implementable with standard solvers and important applications of persistency models. The main message that we hope to convey through this review is that tools of conic programming provide important insights in the probabilistic analysis of discrete optimization problems. These tools lead to distributionally robust bounds with applications in activity networks, vertex packing, discrete choice models, random walks and sequencing problems, and newsvendor problems.     

A strategic decision support system framework for energy-efficient technology investments

Energy systems optimization under uncertainty is increasing in its importance due to on-going global de-regulation of the energy sector and the setting of environmental and efficiency targets which generate new multi-agent risks requiring a model-based stakeholders dialogue and new systemic regulations. This paper develops an integrated framework for decision support systems (DSS) for the optimal planning and operation of a building infrastructure under appearing systemic de-regulations and risks. The DSS relies on a new two-stage, dynamic stochastic optimization model with moving random time horizons bounded by stopping time moments. This allows to model impacts of potential extreme events and structural changes emerging from a stakeholders dialogue, which may occur at any moment of the decision making process. The stopping time moments induce endogenous risk aversion in strategic decisions in a form of dynamic VaR-type systemic risk measures dependent on the system’s structure. The DSS implementation via an algebraic modeling language (AML) provides an environment that enforces the necessary stakeholders dialogue for robust planning and operation of a building infrastructure. Such a framework allows the representation and solution of building infrastructure systems optimization problems, to be implemented at the building level to confront rising systemic economic and environmental global changes.     

Bicriterion shortest hyperpaths in random time-dependent networks

In relevant application areas, such as transportation and telecommunications,there has recently been a growing focus on random time-dependentnetworks (RTDNs), where arc lengths are represented by time-dependentdiscrete random variables. In such networks, an optimal routingpolicy does not necessarily correspond to a path, but ratherto an adaptive strategy. Finding an optimal strategy reducesto a shortest hyperpath problem that can be solved quite efficiently. The bicriterion shortest path problem, i.e. the problem offinding the set of efficient paths, has been extensively studiedfor many years. Recently, extensions to RTDNs have been investigated.However, no attempt has been made to study bicriterion strategies.This is the aim of this paper. Here we model bicriterion strategy problems in terms of bicriterionshortest hyperpaths, and we devise an algorithm for enumeratingthe set of efficient hyperpaths. Since the computational effortrequired for a complete enumeration may be prohibitive, we proposesome heuristic methods to generate a subset of the efficientsolutions. Different criteria are considered, such as expectedor maximum travel time or cost; a computational experience isreported.     

A Linear Risk Model

A special structure optimization model is presented which includes many of the single variable risk problems that are encountered in operational problems. A risk function is assumed which is a piece-wise linear function of some random variable whose distribution is known; one seeks the value of the decision variable which minimizes expected risk. In this paper are presented the necessary and sufficient conditions for this optimization for random variables which are either continuously or discretely distributed. The important special case of a continuous risk function is discussed; multiple risk problems with a joint constraint are analyzed; and the change in policy for a small change in the distribution of the random variable is investigated. Examples illustrate the application of the model.     

MOMENT GENERATING FUNCTIONS OF RANDOM VARIABLES AND ASYMPTOTIC BEHAVIOUR FOR GENERALIZED FELLER OPERATORS

1. Introduction and NotationsThe generalized Feller operators which include many famous operators, such ajsBernstein, Szasz-Mirakjan, BaskakoV, Meyer--K5nig and Zeller operators, can be constructed by making use of the probabilistic method. In the paper [1][2], Xu JihuaPr(--lvjdetl a general scheme f(,r its construction, and Zhao Jillghui showed that theFeller type operators are of good approximations f'or unbounded functions.Our purpose is to present representation of moment generating …     

CEV模型下家庭最优投资决策问题

考虑固定收入下具有随机支出风险的家庭最优投资组合决策问题.在假设投资者拥有工资收入的同时将财富投资到一种风险资产和一种无风险资产,其中风险资产的价格服从CEV模型,无风险利率采用Vasicek随机利率模型.当支出过程是随机的且服从跳-扩散风险模型时,运用动态规划的思想建立了使家庭终端财富效用最大化的HJB方程,采用Legendre-对偶变换进行求解,得到最优策略的显示解,并通过敏感性分析进行验证表明,家庭投资需求是弹性方差系数的减函数,解释了家庭流动性财富的增加对最优投资比例呈现边际效用递减趋势.     

随机网络计划在审计中的应用

审计作为市场经济的自我约束机制,在经济发展中有着不可或缺的责任.本文利用随机网络技术进行分析,旨在设计出高效率的审计活动方案.首先,利用PERT技术建立了确定型的审计活动模型,在此基础上给出了时间—资源优化下的最优人员分配方案;其次,利用GERT技术建立了随机型的审计活动模型,引入矩母函数和梅森公式进行GERT解析求解求出所需的工期等指标,同时采用蒙特卡罗模拟求解验证解析求解的准确性,为审计活动的工期控制提供了理论依据.最后对于工作时间确定的GERT模型,结合PERT和GERT两种技术对其进行简化分析,从而得到了时间—资源优化下的最优人员分配方案.     

An interactive fuzzy satisficing method for multiobjective stochastic linear programming problems through an expectation model

For decision making problems involving uncertainty, both stochastic programming as an optimization method based on the theory of probability and fuzzy programming representing the ambiguity by fuzzy concept have been developing in various ways. In this paper, we focus on multiobjective linear programming problems with random variable coefficients in objective functions and/or constraints. For such problems, as a fusion of these two approaches, after incorporating fuzzy goals of the decision maker for the objective functions, we propose an interactive fuzzy satisficing method for the expectation model to derive a satisficing solution for the decision maker. An illustrative numerical example is provided to demonstrate the feasibility of the proposed method.     

Uncertain portfolio optimization problem under a minimax risk measure

Portfolio optimization problem is concerned with choosing an optimal portfolio strategy that can strike a balance between maximizing investment return and minimizing investment risk. In many cases, the return rate of risky asset is neither a random variable nor a fuzzy variable. Then, it can be described as an uncertain variable. But, the existing works on uncertain portfolio optimization problem fail to find an analytic solution of optimal portfolio strategy. In this paper, we define a new uncertain risk measure for the modeling of investment risk. Then, an uncertain portfolio optimization model is formulated. By introducing a new variable, we transform it into an equivalent bi-criteria optimization model. Then, we derive a method for the construction of the set of analytic Pareto optimal solutions. Finally, a numerical simulation is carried out to show the applicability of the proposed model and the convenience of finding the analytic solution.     

离散椭球分布下两阶段WCVaR风险利润优化模型及应用

本文研究随机变量非完全分布下的两阶段风险-利润优化问题。采用最坏情况下条件风险(Worst-case Conditional Value-at-Risk:WCVaR) 度量指标,在离散椭球分布下建立了两阶段WCVaR 约束下利润期望最大优化模型,运用优化对偶方法将复杂的Max-Min 结构化简,理论上证明了简化模型和原模型的同解性,以发电商电能分配组合优化为数值实例,验证了模型和计算方法的有效性。     

Limit of the solutions for the finite horizon problems as the optimal solution to the infinite horizon optimization problems

In this paper, we consider how to construct the optimal solutions for the undiscounted discrete time infinite horizon optimization problems. We present the conditions under which the limit of the solutions for the finite horizon problems is optimal among all attainable paths for the infinite horizon problem under two modified overtaking criteria, as well as the conditions under which it is the unique optimum under the sum-of-utilities criterion. The results are applied to a parametric example of a simple one-sector growth model to examine the impacts of discounting on the optimal path.     

Graph problems arising from parameter identification of discrete dynamical systems

This paper focuses on combinatorial feasibility and optimization problems that arise in the context of parameter identification of discrete dynamical systems. Given a candidate parametric model for a physical system and a set of experimental observations, the objective of parameter identification is to provide estimates of the parameter values for which the model can reproduce the experiments. To this end, we define a finite graph corresponding to the model, to each arc of which a set of parameters is associated. Paths in this graph are regarded as feasible only if the sets of parameters corresponding to the arcs of the path have nonempty intersection. We study feasibility and optimization problems on such feasible paths, focusing on computational complexity. We show that, under certain restrictions on the sets of parameters, some of the problems become tractable, whereas others are NP-hard. In a similar vein, we define and study some graph problems for experimental design, whose goal is to support the scientist in optimally designing new experiments.     

Convex risk functionals: Representation and applications

We introduce the family of law-invariant convex risk functionals, which includes a wide majority of practically used convex risk measures and deviation measures. We obtain a unified representation theorem for this family of functionals. Two related optimization problems are studied. In the first application, we determine worst-case values of a law-invariant convex risk functional when the mean and a higher moment such as the variance of a risk are known. Second, we consider its application in optimal reinsurance design for an insurer. With the help of the representation theorem, we can show the existence and the form of optimal solutions.     

基于可信性理论的均值-熵-偏度投资组合模型及其算法求解

本文考虑到证券市场的投资者往往面临着随机和模糊两种不确定性的情形,在模糊随机环境下把证券的收益率视作三角模糊变量,在可信性理论基础上建立了带融资约束条件的均值-熵-偏度三目标投资组合决策模型,拓展了基于可信性理论的投资组合决策模型的研究内容,同时通过对约束条件处理方法,外部档案维护方法等关键算子的改良,提出了一种新的约束多目标粒子群算法。本文运用该算法对模型进行求解,把得到的最优解与传统的多目标粒子群算法得到的最优解进行对比,结果表明新算法得到的最优解的质量会显著地优于传统的多目标粒子群算法的最优解,从而验证了算法的有效性和准确性。该算法可以在三维空间中得到一个分布性和逼近性较好的Pareto最优曲面,满足投资者对不同目标的差异需求,为投资者提供合理的投资组合决策方案。     

Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing

Simulated Annealing and Genetic Algorithms are important methods to solve discrete optimization problems and are often used to find approximate solutions for diverse NP-complete problems. They depend on randomness to change their current configuration and transition to a new state. In Simulated Annealing, the random choice influences the construction of the new state as well as the acceptance of that new state. In Genetic Algorithms, selection, mutation and crossover depend on random choices. We experimentally investigate the robustness of the two generic search heuristics when using pseudorandom numbers of limited quality. To this end, we conducted experiments with linear congruential generators of various period lengths, a Mersenne Twister with artificially reduced period lengths as well as quasi-random numbers as the source of randomness. Both heuristics were used to solve several instances of the Traveling Salesman Problem in order to compare optimization results. Our experiments show that both Simulated Annealing and the Genetic Algorithm produce inferior solutions when using random numbers with small period lengths or quasi-random numbers of inappropriate dimension. The influence on Simulated Annealing, however, is more severe than on Genetic Algorithms. Interestingly, we found that when using diverse quasi-random sequences, the Genetic Algorithm outperforms its own results using quantum random numbers.     

Sparse Approximation of Data-Driven Polynomial Chaos Expansions: An Induced Sampling Approach

One of the open problems in the field of forward uncertainty quantification(UQ) is the ability to form accurate assessments of uncertainty having only incomplete information about the distribution of random inputs. Another challenge is to efficiently make use of limited training data for UQ predictions of complex engineering problems, particularly with high dimensional random parameters. We address these challenges by combining data-driven polynomial chaos expansions with a recently developed preconditioned sparse approximation approach for UQ problems. The first task in this two-step process is to employ the procedure developed in [1] to construct an "arbitrary" polynomial chaos expansion basis using a finite number of statistical moments of the random inputs. The second step is a novel procedure to effect sparse approximation via l1 minimization in order to quantify the forward uncertainty. To enhance the performance of the preconditioned l1 minimization problem, we sample from the so-called induced distribution, instead of using Monte Carlo (MC) sampling from the original, unknown probability measure. We demonstrate on test problems that induced sampling is a competitive and often better choice compared with sampling from asymptotically optimal measures(such as the equilibrium measure) when we have incomplete information about the distribution. We demonstrate the capacity of the proposed induced sampling algorithm via sparse representation with limited data on test functions, and on a Kirchoff plating bending problem with random Young's modulus.     

带有限反馈下层的二层规划问题的部分合作模型

对下层最优反馈为离散有限多个的二层规划问题的部分合作模型进行探讨. 当下层的合作程度依赖于上层的决策变量时, 给出一个确定合作系数函数的一般方法, 进而得到一个新的部分合作模型. 在适当地假设下, 可保证所给的部分合作模型一定可以找到比悲观解要好的解, 并结合新的部分合作模型对原不适定问题进行分析, 得到了一些有益的结论. 最后以实际算例说明了所给部分合作模型的可行性.     

On the Joint Path Length Distribution in Random Binary Trees

During the 10th Seminar on Analysis of Algorithms , MSRI, Berkeley, June 2004, Knuth posed the problem of analyzing the left and the right path length in a random binary tree. In particular, Knuth asked about properties of the generating function of the joint distribution of the left and the right path lengths. In this paper, we mostly focus on the asymptotic properties of the distribution of the difference between the left and the right path lengths. Among other things, we show that the Laplace transform of the appropriately normalized moment generating function of the path difference satisfies the first Painlevé transcendent . This is a nonlinear differential equation that has appeared in many modern applications, from nonlinear waves to random matrices. Surprisingly, we find out that the difference between path lengths is of the order n ^5/4 where n is the number of nodes in the binary tree. This was also recently observed by Marckert and Janson. We present precise asymptotics of the distribution's tails and moments. We will also discuss the joint distribution of the left and right path lengths. Throughout, we use methods of analytic algorithmics such as generating functions and complex asymptotics, as well as methods of applied mathematics such as the Wentzel, Kramers, Brillouin (WKB) method.     

一类分布鲁棒线性决策随机优化研究

随机优化广泛应用于经济、管理、工程和国防等领域,分布鲁棒优化作为解决分布信息模糊下的随机优化问题近年来成为学术界的研究热点.本文基于φ-散度不确定集和线性决策方式研究一类分布鲁棒随机优化的建模与计算,构建了易于计算实现的分布鲁棒随机优化的上界和下界问题.数值算例验证了模型分析的有效性.     

Decision making under uncertainty: A semi-infinite programming approach

The subject of this paper is the formulation and discussion of a semi-infinite linear vector optimization problem which extends multiple objective linear programming problems to those with an infinite number of objective functions and constraints. Furthermore it generalizes in some way semi-infinite programming. Besides the statement of some immediately derived results which are related to known results in semi-infinite linear programming and vector optimization, the problem mentioned above is interpreted as a decision model, under risk or uncertainty containing continuous random variables. Thus we treat the case of an infinite number of occuring states of nature. These types of problems frequently occur within aspects of decision theory in management science.