imported>Greatzmoney: /* growthexperiments-addlink-summary-summary:3|0|0 */

2025-10-19T17:26:45Z

growthexperiments-addlink-summary-summary:3|0|0

← Previous revision		Revision as of 17:26, 19 October 2025
Line 2:		Line 2:
	{{For\|the context of control theory\|Stochastic control}}		{{For\|the context of control theory\|Stochastic control}}

	In the field of [[mathematical optimization]], '''stochastic programming''' is a framework for [[Mathematical model\|modeling]] [[Optimization (mathematics)\|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 distribution]]s.<ref>{{cite book\|last1=Shapiro\|first1=Alexander\|~~url~~=~~http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|title=Lectures on stochastic programming: Modeling and theory~~\|last2=Dentcheva\|first2=Darinka\|last3=Ruszczyński\|first3=Andrzej\|~~publisher~~=~~Society for Industrial~~ and ~~Applied Mathematics (SIAM)\|year=2009\|isbn=978-0-89871-687-0~~\|series=MPS/SIAM Series on Optimization\|volume=9\|location=Philadelphia, PA\|pages=xvi+436\|mr=~~2562798\|author2~~-~~link=Darinka Dentcheva~~\|~~author3-link~~=~~Andrzej Piotr Ruszczyński~~\|~~agency~~=~~Mathematical Programming Society (MPS)~~\|access-date=2010-09-22\|archive-date=2020-03-24\|archive-url=https://web.archive.org/web/20200324131907/https://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|url-status=dead}}</ref><ref>{{Cite book\|last1=Birge\|first1=John R.\|last2=Louveaux\|first2=François\|date=2011\|title=Introduction to Stochastic Programming\|url=https://doi.org/10.1007/978-1-4614-0237-4\|series=Springer Series in Operations Research and Financial Engineering\|language=en-gb\|doi=10.1007/978-1-4614-0237-4\|isbn=978-1-4614-0236-7\|issn=1431-8598}}</ref> 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.<ref>		In the field of [[mathematical optimization]], '''stochastic programming''' is a framework for [[Mathematical model\|modeling]] [[Optimization (mathematics)\|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 distribution]]s.<ref>{{cite book\|last1=Shapiro\|first1=Alexander\|author2-link=Darinka Dentcheva\|last2=Dentcheva\|first2=Darinka\|author3-link=Andrzej Piotr Ruszczyński\|last3=Ruszczyński\|first3=Andrzej\|title=Lectures on stochastic programming: Modeling and theory\|series=MPS/SIAM Series on Optimization\|volume=9\|publisher=Society for Industrial and Applied Mathematics and the Mathematical Programming Society\|location=Philadelphia, PA\|year=2009\|pages=xvi+436\|isbn=978-0-89871-687-0\|url=http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|mr=2562798\|access-date=2010-09-22\|archive-date=2020-03-24\|archive-url=https://web.archive.org/web/20200324131907/https://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|url-status=dead}}</ref><ref>{{Cite book\|last1=Birge\|first1=John R.\|last2=Louveaux\|first2=François\|date=2011\|title=Introduction to Stochastic Programming\|url=https://doi.org/10.1007/978-1-4614-0237-4\|series=Springer Series in Operations Research and Financial Engineering\|language=en-gb\|doi=10.1007/978-1-4614-0237-4\|isbn=978-1-4614-0236-7\|issn=1431-8598}}</ref> 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.<ref>
	Stein W. Wallace and William T. Ziemba (eds.). ''[https://books.google.com/books?id=KAI0jsuyDPsC&q=%22Applications+of+Stochastic+Programming%22 Applications of Stochastic Programming]''. MPS-SIAM Book Series on Optimization 5, 2005.		Stein W. Wallace and William T. Ziemba (eds.). ''[https://books.google.com/books?id=KAI0jsuyDPsC&q=%22Applications+of+Stochastic+Programming%22 Applications of Stochastic Programming]''. MPS-SIAM Book Series on Optimization 5, 2005.
	</ref><ref>		</ref><ref>
Line 11:		Line 11:

	Several stochastic programming methods have been developed:		Several stochastic programming methods have been developed:
	* Scenario-based methods including ~~Sample Average Approximation~~		* Scenario-based methods including sample average approximation
	* Stochastic integer programming for problems in which some variables must be integers		* Stochastic [[integer programming]] for problems in which some variables must be integers
	* [[Chance constrained programming]] for dealing with constraints that must be satisfied with a given probability		* [[Chance constrained programming]] for dealing with constraints that must be satisfied with a given probability
	* [[Stochastic dynamic programming]]		* [[Stochastic dynamic programming]]
Line 111:		Line 111:
	Suppose <math>\xi</math> contains <math>d</math> independent random components, each of which has three possible realizations (for example, future realizations of each random parameters are classified as low, medium and high), then the total number of scenarios is <math>K=3^d</math>. Such ''exponential growth'' of the number of scenarios makes model development using expert opinion very difficult even for reasonable size <math>d</math>. The situation becomes even worse if some random components of <math>\xi</math> have continuous distributions.		Suppose <math>\xi</math> contains <math>d</math> independent random components, each of which has three possible realizations (for example, future realizations of each random parameters are classified as low, medium and high), then the total number of scenarios is <math>K=3^d</math>. Such ''exponential growth'' of the number of scenarios makes model development using expert opinion very difficult even for reasonable size <math>d</math>. The situation becomes even worse if some random components of <math>\xi</math> have continuous distributions.

	====Monte Carlo sampling and ~~Sample Average Approximation~~ (SAA) ~~Method~~====		====Monte Carlo sampling and sample average approximation (SAA) method====

	A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation. Suppose the total number of scenarios is very large or even infinite. Suppose further that we can generate a sample <math>\xi^1,\xi^2,\dots,\xi^N</math> of <math>N</math> realizations of the random vector <math>\xi</math>. Usually the sample is assumed to be [[independent and identically distributed]] (i.i.d sample). Given a sample, the expectation function <math>q(x)=E[Q(x,\xi)]</math> is approximated by the sample average		A common approach to reduce the scenario set to a manageable size is by using Monte Carlo simulation. Suppose the total number of scenarios is very large or even infinite. Suppose further that we can generate a sample <math>\xi^1,\xi^2,\dots,\xi^N</math> of <math>N</math> realizations of the random vector <math>\xi</math>. Usually the sample is assumed to be [[independent and identically distributed]] (i.i.d sample). Given a sample, the expectation function <math>q(x)=E[Q(x,\xi)]</math> is approximated by the sample average
Line 129:		Line 129:
	</math>		</math>

	This formulation is known as the ''~~Sample Average Approximation~~'' method. The SAA problem is a function of the considered sample and in that sense is random. For a given sample <math>\xi^1,\xi^2,\dots,\xi^N</math> the SAA problem is of the same form as a two-stage stochastic linear programming problem with the scenarios <math>\xi^j</math>., <math>j=1,\dots,N</math>, each taken with the same probability <math>p_j=\frac{1}{N}</math>.		This formulation is known as the ''sample average approximation'' method. The SAA problem is a function of the considered sample and in that sense is random. For a given sample <math>\xi^1,\xi^2,\dots,\xi^N</math> the SAA problem is of the same form as a two-stage stochastic linear programming problem with the scenarios <math>\xi^j</math>., <math>j=1,\dots,N</math>, each taken with the same probability <math>p_j=\frac{1}{N}</math>.


	=== Statistical inference ===		=== Statistical inference ===
Line 194:		Line 195:
	</math></div>		</math></div>

	where <math>\xrightarrow{\mathcal{D}}</math> denotes convergence in ''distribution'' and <math>Y_x</math> has a normal distribution with mean <math>0</math> and variance <math>\sigma^2(x)</math>, written as <math>\mathcal{N}(0,\sigma^2(x))</math>.		where <math>\xrightarrow{\mathcal{D}}</math> denotes convergence in ''distribution'' and <math>Y_x</math> has a [[normal distribution]] with mean <math>0</math> and variance <math>\sigma^2(x)</math>, written as <math>\mathcal{N}(0,\sigma^2(x))</math>.

	In other words, <math>\hat{g}_N(x)</math> has ''asymptotically normal'' distribution, i.e., for large <math>N</math>, <math>\hat{g}_N(x)</math> has approximately normal distribution with mean <math>g(x)</math> and variance <math>\frac{1}{N}\sigma^2(x)</math>. This leads to the following (approximate) <math>100(1-\alpha)</math>% confidence interval for <math>f(x)</math>:		In other words, <math>\hat{g}_N(x)</math> has ''asymptotically normal'' distribution, i.e., for large <math>N</math>, <math>\hat{g}_N(x)</math> has approximately normal distribution with mean <math>g(x)</math> and variance <math>\frac{1}{N}\sigma^2(x)</math>. This leads to the following (approximate) <math>100(1-\alpha)</math>% [[confidence interval]] for <math>f(x)</math>:

	<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"> <math>		<div class="center" style="width: auto; margin-left: auto; margin-right: auto;"> <math>
Line 337:		Line 338:
	* [[András Prékopa]]. Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995.		* [[András Prékopa]]. Stochastic Programming. Kluwer Academic Publishers, Dordrecht, 1995.
	* [[Andrzej Piotr Ruszczyński\|Andrzej Ruszczynski]] and Alexander Shapiro (eds.) (2003) ''Stochastic Programming''. Handbooks in Operations Research and Management Science, Vol. 10, Elsevier.		* [[Andrzej Piotr Ruszczyński\|Andrzej Ruszczynski]] and Alexander Shapiro (eds.) (2003) ''Stochastic Programming''. Handbooks in Operations Research and Management Science, Vol. 10, Elsevier.
	* {{cite book\|last1=Shapiro\|first1=Alexander\|author2-link=Darinka Dentcheva\|last2=Dentcheva\|first2=Darinka\|author3-link=Andrzej Piotr Ruszczyński\|last3=Ruszczyński\|first3=Andrzej\|title=Lectures on stochastic programming: Modeling and theory\|series=MPS/SIAM Series on Optimization\|volume=9\|publisher=Society for Industrial and Applied Mathematics ~~(SIAM)~~\|location=Philadelphia, PA~~\|agency=Mathematical Programming Society (MPS)~~\|year=2009\|pages=xvi+436\|isbn=978-0-89871-687-0\|url=http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|mr=2562798\|access-date=2010-09-22\|archive-date=2020-03-24\|archive-url=https://web.archive.org/web/20200324131907/https://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|url-status=dead}}		* {{cite book\|last1=Shapiro\|first1=Alexander\|author2-link=Darinka Dentcheva\|last2=Dentcheva\|first2=Darinka\|author3-link=Andrzej Piotr Ruszczyński\|last3=Ruszczyński\|first3=Andrzej\|title=Lectures on stochastic programming: Modeling and theory\|series=MPS/SIAM Series on Optimization\|volume=9\|publisher=Society for Industrial and Applied Mathematics and the Mathematical Programming Society\|location=Philadelphia, PA\|year=2009\|pages=xvi+436\|isbn=978-0-89871-687-0\|url=http://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|mr=2562798\|access-date=2010-09-22\|archive-date=2020-03-24\|archive-url=https://web.archive.org/web/20200324131907/https://www2.isye.gatech.edu/people/faculty/Alex_Shapiro/SPbook.pdf\|url-status=dead}}
	* Stein W. Wallace and William T. Ziemba (eds.) (2005) ''Applications of Stochastic Programming''. MPS-SIAM Book Series on Optimization 5		* Stein W. Wallace and William T. Ziemba (eds.) (2005) ''Applications of Stochastic Programming''. MPS-SIAM Book Series on Optimization 5
	* {{cite book \| last1=King\|first1=Alan J.\|last2=Wallace\|first2=Stein W.\| title=Modeling with Stochastic Programming \| series=Springer Series in Operations Research and Financial Engineering\| publisher=Springer\| location=New York\|year=2012\|isbn=978-0-387-87816-4\| url=https://www.springer.com/mathematics/probability/book/978-0-387-87816-4 }}		* {{cite book \| last1=King\|first1=Alan J.\|last2=Wallace\|first2=Stein W.\| title=Modeling with Stochastic Programming \| series=Springer Series in Operations Research and Financial Engineering\| publisher=Springer\| location=New York\|year=2012\|isbn=978-0-387-87816-4\| url=https://www.springer.com/mathematics/probability/book/978-0-387-87816-4 }}

imported>Folkezoft: /* Stochastic linear programming */ General fixes via AutoWikiBrowser

2025-06-27T18:14:44Z

Stochastic linear programming: General fixes via AutoWikiBrowser

← Previous revision		Revision as of 18:14, 27 June 2025
Line 75:		Line 75:
	A stochastic [[linear program]] is a specific instance of the classical two-stage stochastic program. A stochastic LP is built from a collection of multi-period linear programs (LPs), each having the same structure but somewhat different data. The <math>k^{th}</math> two-period LP, representing the <math>k^{th}</math> scenario, may be regarded as having the following form:		A stochastic [[linear program]] is a specific instance of the classical two-stage stochastic program. A stochastic LP is built from a collection of multi-period linear programs (LPs), each having the same structure but somewhat different data. The <math>k^{th}</math> two-period LP, representing the <math>k^{th}</math> scenario, may be regarded as having the following form:

	<math>		<math>
	\begin{array}{lccccccc}		\begin{array}{lccccccc}
	\text{Minimize} & f^T x & + & g^T y & + & h_k^Tz_k & & \\		\text{Minimize} & f^T x & + & g^T y & + & h_k^Tz_k & & \\
	\text{subject to} & Tx & + & Uy & & & = & r \\		\text{subject to} & Tx & + & Uy & & & = & r \\
	& & & V_k y & + & W_kz_k & = & s_k \\		& & & V_k y & + & W_kz_k & = & s_k \\
	& x & , & y & , & z_k & \geq & 0		& x & , & y & , & z_k & \geq & 0

imported>WikiEditor50: Clean up

2025-05-08T10:35:03Z

Clean up

Show changes

Stochastic programming - Revision history

imported>Greatzmoney: /* growthexperiments-addlink-summary-summary:3|0|0 */

imported>Folkezoft: /* Stochastic linear programming */ General fixes via AutoWikiBrowser

imported>WikiEditor50: Clean up