Chance-constraint method - Revision history

Ths76 at 03:43, 16 December 2021

2021-12-16T03:43:07Z

← Older revision		Revision as of 23:43, 15 December 2021
Line 155:		Line 155:
	Now populate the formula with the values identified in the table earlier:		Now populate the formula with the values identified in the table earlier:

	<math>\quad 7.5x_{1} \leq 600 + -0.84\times60</math>		<math>\quad 7.5x_{1} \leq 600 + (-0.84\times60)</math>

	<math> \quad 5x_{2} \leq 400 + -0.84\times40</math>		<math> \quad 5x_{2} \leq 400 + (-0.84\times40)</math>

	<math> \quad 3x_{1} \geq 300 - -1.28\times30</math>		<math> \quad 3x_{1} \geq 300 - (-1.28\times30)</math>

	<math> \quad 7.5x_{1} + 5x_{2} + 3x_{3} \leq 879 + -2.33\times0.5 </math>		<math> \quad 7.5x_{1} + 5x_{2} + 3x_{3} \leq 879 + (-2.33\times0.5) </math>

	<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6120 + -2.33\times0.5</math>		<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6120 + (-2.33\times0.5)</math>

	These are then solved to identify the new parameters for the constraints:		These are then solved to identify the new parameters for the constraints:

Ths76 at 03:30, 16 December 2021

2021-12-16T03:30:38Z

← Older revision		Revision as of 23:30, 15 December 2021
Line 141:		Line 141:
	\|}		\|}

	~~In order to~~ apply chance-constraint, the parameter in each constraint is replaced with <math>\mu + K\sigma</math> when the constraint is defining an upper limit, and <math> \mu - K\sigma</math> when the constraint is defining a lower limit~~. The equations applied to the constraints in this problem are therefore~~:		To apply chance-constraint, the parameter in each constraint is replaced with <math>\mu + K\sigma</math> when the constraint is defining an upper limit, and <math> \mu - K\sigma</math> when the constraint is defining a lower limit:

	<math>\quad 7.5x_{1} \leq \mu_{1} + K_{\alpha, 1}\sigma_{1}</math>		<math>\quad 7.5x_{1} \leq \mu_{1} + K_{\alpha, 1}\sigma_{1}</math>

Ths76 at 03:22, 16 December 2021

2021-12-16T03:22:48Z

Ths76 at 03:11, 16 December 2021

2021-12-16T03:11:51Z

← Older revision		Revision as of 23:11, 15 December 2021
Line 25:		Line 25:
	While both instances of these constraint definitions linear, the first instance shows the random vector as distinguished from the decision vector and the second instance has the random vector directly associated with the decision vector. Each of these types of the random vector within the constraint mapping have real-world optimization applications - most commonly in engineering and energy management.<ref name=":0" />		While both instances of these constraint definitions linear, the first instance shows the random vector as distinguished from the decision vector and the second instance has the random vector directly associated with the decision vector. Each of these types of the random vector within the constraint mapping have real-world optimization applications - most commonly in engineering and energy management.<ref name=":0" />

	=== General Chance ~~Constrained~~ Optimization Problem ===		=== General Chance-constrained Optimization Problem ===
	When factoring in the random vector to the general optimization problem, it now becomes a chance-constrained optimization problem.<ref name=":5" /> The chance-constrained optimization method was first created by Charnes, Cooper, and Symmonds in 1958-1959 relating to financial planning optimization. Over the years, improvements have been made to the chance-constrained optimization theory and computation processing methods, most notably by András Prékopa.<ref name=":1" />		When factoring in the random vector to the general optimization problem, it now becomes a chance-constrained optimization problem.<ref name=":5" /> The chance-constrained optimization method was first created by Charnes, Cooper, and Symmonds in 1958-1959 relating to financial planning optimization. Over the years, improvements have been made to the chance-constrained optimization theory and computation processing methods, most notably by András Prékopa.<ref name=":1" />

Line 140:		Line 140:
	\| -2.33		\| -2.33
	\|}		\|}


	In order to apply chance-constraint, the parameter in each constraint is replaced with the following formula.		In order to apply chance-constraint, the parameter in each constraint is replaced with the following formula.
Line 177:		Line 176:

	<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6118.84</math>		<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6118.84</math>


	Making the new optimization problem which can now be solved using linear programming		Making the new optimization problem which can now be solved using linear programming

Ths76 at 02:52, 16 December 2021

2021-12-16T02:52:40Z

Show changes

Ths76 at 02:05, 16 December 2021

2021-12-16T02:05:56Z

Show changes

Jlm592: Updates to the Theory/Methodology section

2021-12-15T03:59:12Z

Updates to the Theory/Methodology section

Show changes

Jlm592: Minor LaTex edits

2021-12-14T19:31:54Z

Minor LaTex edits

Jlm592: Reformatting and introduction of new sections to the Theory/Methodology section

2021-12-14T19:29:17Z

Reformatting and introduction of new sections to the Theory/Methodology section

← Older revision		Revision as of 15:29, 14 December 2021
Line 4:		Line 4:

	==Theory/Methodology==		==Theory/Methodology==
	The chance-constrained optimization method was first created by Charnes, Cooper, and Symmonds in 1958-1959 relating to financial planning optimization. Over the years, improvements have been made to the chance-constrained optimization theory and computation processing methods, most notably by András Prékopa.<ref name=":1" />

	=== General ~~Form~~ ===		=== General Optimization Problem ===
	A general form of ~~a chance constraint~~ is shown below:		'''NOTE TO ADD MORE''': want to add a brief introduction of a 'basic' optimization problem, which leads into a discussion of the random vector and then into chance constraints and then the chance constraint optimization problem; see Reference 3

			A general form of an optimization problem is shown below:<ref name=":5">S. Peng, "Chance constrained problem and its applications," Université Paris Saclay; Xi’an Jiaotong University, 2019</ref>

	<math>~~P(h~~(x~~,\xi) \geq 0~~) ~~\geq p~~</math>		<math>min \quad g(x)</math>

	<math>~~where~~ \, x ~~\, is \, a \, decision \, variable~~, \xi \, ~~is \, the \, uncertainty/randomness~~ \, ~~variable~~, h(x,\xi) \~~geq~~ 0 \, ~~maps \, the \, constraints \, as \, a \, finite \, system \, of \, inequalities, and \, p~~ \in ~~[0,1]~~</math>		<math>s.t. \quad h_1(x,\xi) \leq 0, ... \, , h_d(x,\xi) \leq 0, x \in X</math>

	~~This chance constraint formulated above is considered to be a constraint within an optimization problem~~ where ~~this~~ is ~~some~~ objective function ~~- usually denoted by <math>f(~~x)</math> ~~- that is meant to be minimized.~~		<math>where \, g \, is \, the \, objective \, function, h_1 , ... \, , h_d, are inequality \, constraints \, X \, \in \mathbb{R}^m \, is \, a \, deterministic \, set, x \in X \, is \, the \, decision \, vector, \xi \, is \, a \, parameter \, vector, </math>

	~~Compared to a conventional optimization problem,~~ the ~~chance-~~constrained optimization problem ~~differs due to the left-hand side inequality above because it is rarely provided explicitly~~. ~~Therefore~~, ~~there~~ is ~~not~~ a ~~general solution approach for chance-constrained~~ optimization ~~problems~~. ~~The random and decision variables in~~ the ~~above equation~~ can ~~guide~~ the ~~path~~ to ~~solution via~~ a ~~linear programming solution~~, ~~but not always~~.<ref name=":0" />		The above general form of the constrained optimization problem has multiple real world applications. However, in the real world the parameter <math>\xi</math> is often uncertain and introduces a level of randomness to the optimization problem. Sometimes this uncertainty is bypassed by using the expected value of <math>\xi</math> which can cause issues as the optimal solution to the above optimization problem may have a high chance of being infeasible. Therefore, the random vector needs to be accounted for depending on the optimization application.<ref name=":5" />

	==== The Random ~~Variable =~~===		=== The Random Vector ===
	The random ~~variable~~, <math>\xi</math>~~, (sometimes referred to as the random vector)~~, can both be dependent on time or time-independent. The wide ranging possibilities of the random ~~variable~~ play the largest role in the difficult nature of the chance-constrained optimization problem. Though generally speaking, the random ~~variable~~ is considered to have a known distribution.<ref name=":1" /> For example, the chance constraints can take the linear form in the random ~~variable~~. This is illustrated in both of the constraint defining equations below <ref name=":0" />:		The random vector, <math>\xi</math>, can both be dependent on time or time-independent. The wide ranging possibilities of the random vector play the largest role in the difficult nature of the chance-constrained optimization problem. Though generally speaking, the random vector is considered to have a known distribution.<ref name=":1" /> For example, the chance constraints can take the linear form in the random vector. This is illustrated in both of the constraint defining equations below <ref name=":0" />:

	<math>h(x,\xi) = g(x) - A\xi \quad or \quad h(x,\xi) = A(\xi)g(x) - b</math>		<math>h(x,\xi) = g(x) - A\xi \quad or \quad h(x,\xi) = A(\xi)g(x) - b</math>
Line 24:		Line 25:
	<math>where \, A \, is \, a \, deterministic \, matrix, A(\xi) \, is \, a \, stochastic \, matrix, x \, is \, a \, decision \, variable, g \, is \, a \, mapping \, on \, x, and \, b \, is \, a \, vector \, of \, relative \, appropriate \, size</math>		<math>where \, A \, is \, a \, deterministic \, matrix, A(\xi) \, is \, a \, stochastic \, matrix, x \, is \, a \, decision \, variable, g \, is \, a \, mapping \, on \, x, and \, b \, is \, a \, vector \, of \, relative \, appropriate \, size</math>

	While both instances of these constraint definitions linear, the first instance shows the random ~~variable~~ as distinguished from the decision ~~variable~~ and the second instance has the random ~~variable~~ directly associated with the decision ~~variable~~. Each of these types of the random ~~variable~~ within the constraint mapping have real-world applications - most commonly in engineering and energy management.<ref name=":0" />		While both instances of these constraint definitions linear, the first instance shows the random vector as distinguished from the decision vector and the second instance has the random vector directly associated with the decision vector. Each of these types of the random vector within the constraint mapping have real-world applications - most commonly in engineering and energy management.<ref name=":0" />

			=== General Chance Constrained Optimization ===
			The chance-constrained optimization method was first created by Charnes, Cooper, and Symmonds in 1958-1959 relating to financial planning optimization. Over the years, improvements have been made to the chance-constrained optimization theory and computation processing methods, most notably by András Prékopa.<ref name=":1" />

			A general form of a chance constraint is shown below:

			<math>\mathbb{P}(h(x,\xi) \geq 0) \geq p</math>

			<math>h(x,\xi) \geq 0 \, maps \, the \, constraints \, as \, a \, finite \, system \, of \, inequalities, and \, p \in [0,1]</math>

			This chance constraint formulated above is considered to be a constraint within an optimization problem where this is some objective function - usually denoted by <math>f(x)</math> - that is meant to be minimized.

			Compared to a conventional optimization problem, the chance-constrained optimization problem differs due to the left-hand side inequality above because it is rarely provided explicitly. Therefore, there is not a general solution approach for chance-constrained optimization problems. The random and decision vectors in the above equation can guide the path to solution via a linear programming solution, but not always.<ref name=":0" />

	=== Joint vs. Individual Chance Constraints ===		=== Joint vs. Individual Chance Constraints ===
	The chance constraint above can be written more explicitly as:		The chance constraint above can be written more explicitly as:

	<math>P(h_{j} (x,\xi) \geq 0 (j = 1,...,m)) \geq p</math>		<math>\mathbb{P}(h_{j} (x,\xi) \geq 0 (j = 1,...,m)) \geq p</math>

	This is called a joint chance constraint (or sometimes a separate chance constraint,<ref name=":1" />) because the entire probability covers the entirety of the inequality. In simpler terms, the entire constraint is considered as a whole. On the other hand, if each of the constraints in the system need to be considered individually, the chance constraint becomes a single constraint, which is formulated below:		This is called a joint chance constraint (or sometimes a separate chance constraint,<ref name=":1" />) because the entire probability covers the entirety of the inequality. In simpler terms, the entire constraint is considered as a whole. On the other hand, if each of the constraints in the system need to be considered individually, the chance constraint becomes a single constraint, which is formulated below:

	<math>P(h_{j} (x,\xi) \geq 0) \geq p (j = 1,...,m)</math>		<math>\mathbb{P}(h_{j} (x,\xi) \geq 0) \geq p (j = 1,...,m)</math>

	This type of constraint is known as an individual chance constraint (and sometimes as a single chance constraint,<ref name=":1" />).		This type of constraint is known as an individual chance constraint (and sometimes as a single chance constraint,<ref name=":1" />).

Jlm592: Expanded the Theory/Methodology section

2021-12-14T18:35:54Z

Expanded the Theory/Methodology section

← Older revision		Revision as of 14:35, 14 December 2021
Line 18:		Line 18:

	==== The Random Variable ====		==== The Random Variable ====
	The ~~wide ranging possibilities of the~~ random variable (sometimes referred to as the random vector) play the largest role in the difficult nature of the chance-constrained optimization problem. For example, the chance constraints can take the linear form in the random variable. This is illustrated in both of the constraint defining equations below:		The random variable, <math>\xi</math>, (sometimes referred to as the random vector), can both be dependent on time or time-independent. The wide ranging possibilities of the random variable play the largest role in the difficult nature of the chance-constrained optimization problem. Though generally speaking, the random variable is considered to have a known distribution.<ref name=":1" /> For example, the chance constraints can take the linear form in the random variable. This is illustrated in both of the constraint defining equations below <ref name=":0" />:

	<math>h(x,\xi) = g(x) - A\xi \quad or \quad h(x,\xi) = A(\xi)g(x) - b</math>		<math>h(x,\xi) = g(x) - A\xi \quad or \quad h(x,\xi) = A(\xi)g(x) - b</math>
Line 43:		Line 43:
	Caution should be taken when utilizing solely individual chance constraints in an attempt to overly simplify a problem. It can be appealing to attempt to model an entire system as a single inequality, especially if a certain probability level of satisfaction is warranted over a specific amount of time. However, this modeling may fail in robustness when considering the system throughout the entire timeframe. As a brief example, if a system is required to reach a certain probability level over a lengthy timeframe, it may be appealing to model the system using individual chance constraints over multiple shorter time slots. The system is then modeled solely over those separate time slots to ensure the certain probability level is satisfied in piecemeal fashion. While this may result in a more easy-to-solve problem, this individual chance constraint modeling setup may breakdown when expanding over the entire timeframe instead of focusing in on the separate time slots. So in instances such as these, joint chance constraints may cause a lengthier problem and solution, but will result in a more robust answer.<ref>W. Ackooij, R. Henrion, A. Möller, and R. Zorgati, "On probabilistic constraints induced by rectangular sets and multivariate normal distributions," ''Mathematical Methods of Operations Research'', vol. 71(3), pp. 535-549, 2010.</ref>		Caution should be taken when utilizing solely individual chance constraints in an attempt to overly simplify a problem. It can be appealing to attempt to model an entire system as a single inequality, especially if a certain probability level of satisfaction is warranted over a specific amount of time. However, this modeling may fail in robustness when considering the system throughout the entire timeframe. As a brief example, if a system is required to reach a certain probability level over a lengthy timeframe, it may be appealing to model the system using individual chance constraints over multiple shorter time slots. The system is then modeled solely over those separate time slots to ensure the certain probability level is satisfied in piecemeal fashion. While this may result in a more easy-to-solve problem, this individual chance constraint modeling setup may breakdown when expanding over the entire timeframe instead of focusing in on the separate time slots. So in instances such as these, joint chance constraints may cause a lengthier problem and solution, but will result in a more robust answer.<ref>W. Ackooij, R. Henrion, A. Möller, and R. Zorgati, "On probabilistic constraints induced by rectangular sets and multivariate normal distributions," ''Mathematical Methods of Operations Research'', vol. 71(3), pp. 535-549, 2010.</ref>

			'''NOTE TO ADD MORE:''' A brief discussion on the linear vs. nonlinear solution approaches;
	'''NOTE TO ADD MORE''': Perhaps a section on convexity - see Section 2.4 of Reference 1 and Section 4.1 of Reference 2		'''NOTE TO ADD MORE''': Perhaps a section on convexity - see Section 2.4 of Reference 1 and Section 4.1 of Reference 2. Would also have to discuss the "random right-side" topic; Note - this is a bit confusing and not necessarily sure what it adds to this section

	==Numerical Example==		==Numerical Example==

← Older revision		Revision as of 23:22, 15 December 2021
Line 141:		Line 141:
	\|}		\|}

	In order to apply chance-constraint, the parameter in each constraint is replaced with the ~~following formula~~.		In order to apply chance-constraint, the parameter in each constraint is replaced with <math>\mu + K\sigma</math> when the constraint is defining an upper limit, and <math> \mu - K\sigma</math> when the constraint is defining a lower limit. The equations applied to the constraints in this problem are therefore:

	<math>\quad 7.5x_{1} \leq \mu_{1} + K_{\alpha, 1}\sigma_{1}</math>		<math>\quad 7.5x_{1} \leq \mu_{1} + K_{\alpha, 1}\sigma_{1}</math>
Line 153:		Line 153:
	<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq \mu_{5} + K_{\alpha, 5}\sigma_{5}</math>		<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq \mu_{5} + K_{\alpha, 5}\sigma_{5}</math>

	Now populate the formula with the values identified in the table earlier		Now populate the formula with the values identified in the table earlier:

	<math>\quad 7.5x_{1} \leq 600 + -0.84\times60</math>		<math>\quad 7.5x_{1} \leq 600 + -0.84\times60</math>
Line 165:		Line 165:
	<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6120 + -2.33\times0.5</math>		<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6120 + -2.33\times0.5</math>

	These are then solved to identify the new parameters for the constraints		These are then solved to identify the new parameters for the constraints:

	<math>\quad 7.5x_{1} \leq 549.6</math>		<math>\quad 7.5x_{1} \leq 549.6</math>
Line 177:		Line 177:
	<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6118.84</math>		<math> \quad 200x_{1} + 200x_{2} + 200x_{3} \leq 6118.84</math>

	Making the new optimization problem which can now be solved using linear programming		Making the new optimization problem which can now be solved using linear programming:

	<math>max \quad P = 3x_{1} + x_{2} + 5x_{3}</math>		<math>max \quad P = 3x_{1} + x_{2} + 5x_{3}</math>

← Older revision		Revision as of 15:31, 14 December 2021
Line 10:		Line 10:
	A general form of an optimization problem is shown below:<ref name=":5">S. Peng, "Chance constrained problem and its applications," Université Paris Saclay; Xi’an Jiaotong University, 2019</ref>		A general form of an optimization problem is shown below:<ref name=":5">S. Peng, "Chance constrained problem and its applications," Université Paris Saclay; Xi’an Jiaotong University, 2019</ref>

	<math>min \quad g(x)</math>		<math>min \quad f(x)</math>

	<math>s.t. \quad h_1(x,\xi) \leq 0, ... \, , h_d(x,\xi) \leq 0, x \in X</math>		<math>s.t. \quad h_1(x,\xi) \leq 0, ... \, , h_d(x,\xi) \leq 0, x \in X</math>

	<math>where \, g \, is \, the \, objective \, function, h_1 , ... \, , h_d, are inequality \, constraints \, X \, \in \mathbb{R}^m \, is \, a \, deterministic \, set, x \in X \, is \, the \, decision \, vector, \xi \, is \, a \, parameter \, vector, </math>		<math>where \, f \, is \, the \, objective \, function, h_1 , ... \, , h_d, are \, inequality \, constraints \, X \, \in \mathbb{R}^m \, is \, a \, deterministic \, set, x \in X \, is \, the \, decision \, vector, \xi \, is \, a \, parameter \, vector </math>

	The above general form of the constrained optimization problem has multiple real world applications. However, in the real world the parameter <math>\xi</math> is often uncertain and introduces a level of randomness to the optimization problem. Sometimes this uncertainty is bypassed by using the expected value of <math>\xi</math> which can cause issues as the optimal solution to the above optimization problem may have a high chance of being infeasible. Therefore, the random vector needs to be accounted for depending on the optimization application.<ref name=":5" />		The above general form of the constrained optimization problem has multiple real world applications. However, in the real world the parameter <math>\xi</math> is often uncertain and introduces a level of randomness to the optimization problem. Sometimes this uncertainty is bypassed by using the expected value of <math>\xi</math> which can cause issues as the optimal solution to the above optimization problem may have a high chance of being infeasible. Therefore, the random vector needs to be accounted for depending on the optimization application.<ref name=":5" />
Line 23:		Line 23:
	<math>h(x,\xi) = g(x) - A\xi \quad or \quad h(x,\xi) = A(\xi)g(x) - b</math>		<math>h(x,\xi) = g(x) - A\xi \quad or \quad h(x,\xi) = A(\xi)g(x) - b</math>

	<math>where \, A \, is \, a \, deterministic \, matrix, A(\xi) \, is \, a \, stochastic \, matrix~~, x \, is \, a \, decision \, variable~~, g \, is \, a \, mapping \, on \, x, and \, b \, is \, a \, vector \, of \, relative \, appropriate \, size</math>		<math>where \, A \, is \, a \, deterministic \, matrix, A(\xi) \, is \, a \, stochastic \, matrix, g \, is \, a \, mapping \, on \, x, and \, b \, is \, a \, vector \, of \, relative \, appropriate \, size</math>

	While both instances of these constraint definitions linear, the first instance shows the random vector as distinguished from the decision vector and the second instance has the random vector directly associated with the decision vector. Each of these types of the random vector within the constraint mapping have real-world applications - most commonly in engineering and energy management.<ref name=":0" />		While both instances of these constraint definitions linear, the first instance shows the random vector as distinguished from the decision vector and the second instance has the random vector directly associated with the decision vector. Each of these types of the random vector within the constraint mapping have real-world applications - most commonly in engineering and energy management.<ref name=":0" />
Line 34:		Line 34:
	<math>\mathbb{P}(h(x,\xi) \geq 0) \geq p</math>		<math>\mathbb{P}(h(x,\xi) \geq 0) \geq p</math>

	<math>h(x,\xi) \geq 0 \, maps \, the \, constraints \, as \, a \, finite \, system \, of \, inequalities, and \, p \in [0,1]</math>		<math>where \, h(x,\xi) \geq 0 \, maps \, the \, constraints \, as \, a \, finite \, system \, of \, inequalities, and \, p \in [0,1]</math>

	This chance constraint formulated above is considered to be a constraint within an optimization problem where this is some objective function - usually denoted by <math>f(x)</math> - that is meant to be minimized.		This chance constraint formulated above is considered to be a constraint within an optimization problem where this is some objective function - usually denoted by <math>f(x)</math> - that is meant to be minimized.