|
Correlation Gap
In stochastic programming, the correlation gap is the worst-case ratio between the cost when the random variables are correlated to the cost when the random variables are independent. As an example, consider the following optimization problem. A teacher wants to know whether to come to class or not. There are ''n'' potential students. For each student, there is a probability of 1/''n'' that the student will attend the class. If at least one student attends, then the teacher must come and his cost is 1. If no students attend, then the teacher can stay at home and his cost is 0. The goal of the teacher is to minimize his cost. This is a stochastic-programming problem, because the constraints are not known in advance – only their probabilities are known. Now, there are two cases regarding the correlation between the students: * Case #1: the students are uncorrelated: each student decides whether to come to class or not by tossing a coin with probability 1/n, independently o ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Stochastic Programming
In the field of mathematical optimization, stochastic programming is a framework for modeling optimization problems that involve uncertainty. A stochastic program is an optimization problem in which some or all problem parameters are uncertain, but follow known probability distributions. This framework contrasts with deterministic optimization, in which all problem parameters are assumed to be known exactly. The goal of stochastic programming is to find a decision which both optimizes some criteria chosen by the decision maker, and appropriately accounts for the uncertainty of the problem parameters. Because many real-world decisions involve uncertainty, stochastic programming has found applications in a broad range of areas ranging from finance to transportation to energy optimization. Two-stage problems The basic idea of two-stage stochastic programming is that (optimal) decisions should be based on data available at the time the decisions are made and cannot depend on futur ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Correlated
In statistics, correlation or dependence is any statistical relationship, whether causal or not, between two random variables or bivariate data. Although in the broadest sense, "correlation" may indicate any type of association, in statistics it usually refers to the degree to which a pair of variables are ''linearly'' related. Familiar examples of dependent phenomena include the correlation between the height of parents and their offspring, and the correlation between the price of a good and the quantity the consumers are willing to purchase, as it is depicted in the so-called demand curve. Correlations are useful because they can indicate a predictive relationship that can be exploited in practice. For example, an electrical utility may produce less power on a mild day based on the correlation between electricity demand and weather. In this example, there is a causal relationship, because extreme weather causes people to use more electricity for heating or cooling. However ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Independence (probability Theory)
Independence is a fundamental notion in probability theory, as in statistics and the theory of stochastic processes. Two events are independent, statistically independent, or stochastically independent if, informally speaking, the occurrence of one does not affect the probability of occurrence of the other or, equivalently, does not affect the odds. Similarly, two random variables are independent if the realization of one does not affect the probability distribution of the other. When dealing with collections of more than two events, two notions of independence need to be distinguished. The events are called pairwise independent if any two events in the collection are independent of each other, while mutual independence (or collective independence) of events means, informally speaking, that each event is independent of any combination of other events in the collection. A similar notion exists for collections of random variables. Mutual independence implies pairwise independence ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Submodular Set Function
In mathematics, a submodular set function (also known as a submodular function) is a set function whose value, informally, has the property that the difference in the incremental value of the function that a single element makes when added to an input set decreases as the size of the input set increases. Submodular functions have a natural diminishing returns property which makes them suitable for many applications, including approximation algorithms, game theory (as functions modeling user preferences) and electrical networks. Recently, submodular functions have also found immense utility in several real world problems in machine learning and artificial intelligence, including automatic summarization, multi-document summarization, feature selection, active learning, sensor placement, image collection summarization and many other domains. Definition If \Omega is a finite set, a submodular function is a set function f:2^\rightarrow \mathbb, where 2^\Omega denotes the power set of ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bayesian-optimal Pricing
Bayesian-optimal pricing (BO pricing) is a kind of algorithmic pricing in which a seller determines the sell-prices based on probabilistic assumptions on the valuations of the buyers. It is a simple kind of a Bayesian-optimal mechanism, in which the price is determined in advance without collecting actual buyers' bids. Single item and single buyer In the simplest setting, the seller has a single item to sell (with zero cost), and there is a single potential buyer. The highest price that the buyer is willing to pay for the item is called the ''valuation'' of the buyer. The seller would like to set the price exactly at the buyer's valuation. Unfortunately, the seller does not know the buyer's valuation. In the Bayesian model, it is assumed that the buyer's valuation is a random variable drawn from a known probability distribution. Suppose the cumulative distribution function of the buyer is F(v), defined as the probability that the seller's valuation is less than v. Then, if the pri ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Bayesian-optimal Auction
A Bayesian-optimal mechanism (BOM) is a mechanism in which the designer does not know the valuations of the agents for whom the mechanism is designed, but the designer knows that they are random variables and knows the probability distribution of these variables. A typical application is a seller who wants to sell some items to potential buyers. The seller wants to price the items in a way that will maximize their profit. The optimal prices depend on the amount that each buyer is willing to pay for each item. The seller does not know these amounts, but assumes that they are drawn from a certain known probability distribution. The phrase "Bayesian optimal mechanism design" has the following meaning: * Bayesian means that we know the probability distribution from which the agents' valuations are drawn (in contrast to prior-free mechanism design, which do not assume any prior probability distribution). * Optimal means that we want to maximize the expected revenue of the auctioneer, wher ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Robust Optimization
Robust optimization is a field of mathematical optimization theory that deals with optimization problems in which a certain measure of robustness is sought against uncertainty that can be represented as deterministic variability in the value of the parameters of the problem itself and/or its solution. History The origins of robust optimization date back to the establishment of modern decision theory in the 1950s and the use of worst case analysis and Wald's maximin model as a tool for the treatment of severe uncertainty. It became a discipline of its own in the 1970s with parallel developments in several scientific and technological fields. Over the years, it has been applied in statistics, but also in operations research, electrical engineering, control theory, finance, portfolio management logistics, manufacturing engineering, chemical engineering, medicine, and computer science. In engineering problems, these formulations often take the name of "Robust Design Optimization", ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
Info-gap Decision Theory
Info-gap decision theory seeks to optimize robustness to failure under severe uncertainty,Yakov Ben-Haim, ''Information-Gap Theory: Decisions Under Severe Uncertainty,'' Academic Press, London, 2001.Yakov Ben-Haim, ''Info-Gap Theory: Decisions Under Severe Uncertainty,'' 2nd edition, Academic Press, London, 2006. in particular applying sensitivity analysis of the stability radius type to perturbations in the value of a given estimate of the parameter of interest. It has some connections with Wald's maximin model; some authors distinguish them, others consider them instances of the same principle. It has been developed bYakov Ben-Haim and has found many applications and described as a theory for decision-making under "''severe'' uncertainty". It has been criticized as unsuited for this purpose, and alternatives proposed, including such classical approaches as robust optimization. Summary Info-gap is a theory: it assists in decisions under uncertainty. It does this by using model ... [...More Info...] [...Related Items...] OR: [Wikipedia] [Google] [Baidu] |
