McCormick envelopes - Revision history

Smu29 at 12:21, 12 December 2021

2021-12-12T12:21:40Z

← Older revision		Revision as of 08:21, 12 December 2021
Line 6:		Line 6:
	== Theory, Methodology and Algorithmic Discussions ==		== Theory, Methodology and Algorithmic Discussions ==
	[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]		[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]
	As McCormick noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function<sup>1</sup>. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.		As McCormick noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function<sup>1</sup>. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function<sup>1</sup>. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.

	Each bilinear term is replaced with a new variable and four sets of constraints are added<sup>1</sup>. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.		Each bilinear term is replaced with a new variable and four sets of constraints are added<sup>1</sup>. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.
Line 133:		Line 133:

	<math>0 \leq y \leq 2</math>		<math>0 \leq y \leq 2</math>



Line 167:		Line 168:

	<math>s.t. \ w \leq 18</math>		<math>s.t. \ w \leq 18</math>



	<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>		<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>
Line 182:		Line 181:

	</math>		</math>



	<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>		<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>
Line 200:		Line 197:

	</math>		</math>



	<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>		<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>
Line 218:		Line 213:

	</math>		</math>



	<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>		<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>

Smu29 at 12:14, 12 December 2021

2021-12-12T12:14:39Z

← Older revision		Revision as of 08:14, 12 December 2021
Line 104:		Line 104:
	</math>		</math>

	<math>u_{i,j} \~~geq~~ x_i^L x_j + x_i x_j^U - {x_i}^L {x_j}^U, \forall i,j \		<math>u_{i,j} \leq x_i^L x_j + x_i x_j^U - {x_i}^L {x_j}^U, \forall i,j \

	</math>		</math>

	<math>u_{i,j} \~~geq~~ x_i^U x_j + x_i x_j^L - {x_i}^U {x_j}^L, \forall i,j \		<math>u_{i,j} \leq x_i^U x_j + x_i x_j^L - {x_i}^U {x_j}^L, \forall i,j \

	</math>		</math>
Line 167:		Line 167:

	<math>s.t. \ w \leq 18</math>		<math>s.t. \ w \leq 18</math>



Line 181:		Line 182:

	</math>		</math>



Line 198:		Line 200:

	</math>		</math>



Line 215:		Line 218:

	</math>		</math>

Smu29 at 14:45, 11 December 2021

2021-12-11T14:45:49Z

← Older revision		Revision as of 10:45, 11 December 2021
Line 45:		Line 45:

	<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>		<math>w\geq x^{U}y+xy^{U}-x^{U}y^{U}</math>


	<math>a=\left ( x^{U}-x\right )</math>		<math>a=\left ( x^{U}-x\right )</math>
Line 51:		Line 52:

	<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>		<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>


	<math>a=\left ( x-x^{L} \right )</math>		<math>a=\left ( x-x^{L} \right )</math>
Line 131:		Line 133:

	<math>0 \leq y \leq 2</math>		<math>0 \leq y \leq 2</math>


	<math>Let\ w = xy		<math>Let\ w = xy
Line 195:		Line 198:

	</math>		</math>


	<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>		<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>
Line 211:		Line 215:

	</math>		</math>


	<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>		<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>
Line 234:		Line 239:
	Another application involves the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality<sup>6</sup>. This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components.		Another application involves the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality<sup>6</sup>. This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components.

	A third application involves the optimized efficiency and reliability of the operation of the electricity grid. Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations<sup>8</sup>. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)<sup>9</sup>.		A third application involves the optimized efficiency and reliability of the operation of the electricity grid. Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations<sup>7</sup>. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)<sup>8</sup>.
	== Conclusion ==		== Conclusion ==
	Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.		Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.
Line 244:		Line 249:
	# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]		# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]
	# P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," ''Computers & Chemical Engineering'', vol. 72, pp. 300-311, 2015.		# P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," ''Computers & Chemical Engineering'', vol. 72, pp. 300-311, 2015.
	#		# J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.
	#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering,'' vol. 29, pp. ''1''914–1933, 2005.		# Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.
	#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''
	#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.
	#Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.
	#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.		#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.
			#

Smu29: /* Applications */

2021-12-11T14:40:17Z

Applications

← Older revision		Revision as of 10:40, 11 December 2021
Line 230:		Line 230:
	Bilinear functions occur in numerous engineering and natural science applications where McCormick Envelopes can be utilized.		Bilinear functions occur in numerous engineering and natural science applications where McCormick Envelopes can be utilized.

	For example, an application is the modeling of dynamic biological processes based on experimental data<sup>8</sup>. The challenge for this model is establishing model parameter values that align or calibrate the model response with observed data. These model parameter values can be estimated using optimization techniques, including McCormick Envelopes, to minimize the difference between observed and simulated data.		For example, an application involves the modeling of dynamic biological processes based on experimental data<sup>2</sup>. The challenge for this model is establishing model parameter values that align or calibrate the model response with observed data. These model parameter values can be estimated using optimization techniques, including McCormick Envelopes, to minimize the difference between observed and simulated data.

	Another application is the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality<sup>6</sup>. This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components.		Another application involves the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality<sup>6</sup>. This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components.

	A third application is the optimized efficiency and reliability of the operation of the electricity grid. Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations<sup>8</sup>. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)<sup>9</sup>.		A third application involves the optimized efficiency and reliability of the operation of the electricity grid. Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations<sup>8</sup>. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)<sup>9</sup>.
	== Conclusion ==		== Conclusion ==
	Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.		Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.
Line 244:		Line 244:
	# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]		# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]
	# P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," ''Computers & Chemical Engineering'', vol. 72, pp. 300-311, 2015.		# P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," ''Computers & Chemical Engineering'', vol. 72, pp. 300-311, 2015.
			#
	#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering,'' vol. 29, pp. ''1''914–1933, 2005.		#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering,'' vol. 29, pp. ''1''914–1933, 2005.
	#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''		#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''

Smu29 at 14:13, 11 December 2021

2021-12-11T14:13:24Z

← Older revision		Revision as of 10:13, 11 December 2021
Line 3:		Line 3:
	== Introduction ==		== Introduction ==
	The McCormick Envelope, originally developed by Dr. Garth McCormick, is a type of convex relaxation used for the optimization of bilinear <math>(e.g., x*y, e^xy + y, sin(x+y) - x^2)		The McCormick Envelope, originally developed by Dr. Garth McCormick, is a type of convex relaxation used for the optimization of bilinear <math>(e.g., x*y, e^xy + y, sin(x+y) - x^2)
	</math> non-linear programming (NLP) problems<sup>1</sup>. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem.		</math> non-linear programming (NLP) problems<sup>1</sup>. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution<sup>2</sup>. Different techniques are used to address this challenge depending on the characteristics of the problem.
	== Theory, Methodology and Algorithmic Discussions ==		== Theory, Methodology and Algorithmic Discussions ==
	[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]		[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]
Line 12:		Line 12:
	The LP solution gives a lower (L) bound and any feasible solution to the problem gives an upper (U) bound.		The LP solution gives a lower (L) bound and any feasible solution to the problem gives an upper (U) bound.

	As noted by Scott et al, McCormick envelopes are effective since they are recursive, can be applied to a variety of applications, and are typically stronger than those resulting from convexification or linearization procedures<sup>2</sup>.		As noted by Scott et al, McCormick envelopes are effective since they are recursive, can be applied to a variety of applications, and are typically stronger than those resulting from convexification or linearization procedures<sup>3</sup>.

	The following is a derivation of the McCormick Envelopes for a given bilinear ~~function1~~:		The following is a derivation of the McCormick Envelopes for a given bilinear function<sup>1</sup>:

	<math>Let \ w = xy</math>		<math>Let \ w = xy</math>
Line 118:		Line 118:
	'''Piecewise McCormick Relaxation'''		'''Piecewise McCormick Relaxation'''

	As discussed by Hazaji, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning<sup>3</sup>. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>4</sup>.		As discussed by Hazaji, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning<sup>4</sup>. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>5</sup>.

	== Example: Numerical ==		== Example: Numerical ==
Line 131:		Line 131:

	<math>0 \leq y \leq 2</math>		<math>0 \leq y \leq 2</math>



	<math>Let\ w = xy		<math>Let\ w = xy
Line 180:		Line 178:

	</math>		</math>




Line 199:		Line 195:

	</math>		</math>



	<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>		<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>
Line 217:		Line 211:

	</math>		</math>



	<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>		<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>
Line 248:		Line 240:
	== References ==		== References ==
	# G. P. McCormick, "Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems," ''Mathematical Programming,'' vol. 10, pp. 147-175, 1976.		# G. P. McCormick, "Computability of Global Solutions To Factorable Nonconvex Solutions: Part I: Convex Underestimating Problems," ''Mathematical Programming,'' vol. 10, pp. 147-175, 1976.
			# A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics,'' vol. 13, 2012.
	# J. K. Scott, M. D. Stuber and P. I. Barton, "Generalized McCormick Relaxations," ''Journal of Global Optimization,'' vol. 51, pp. 569-606, 2011.		# J. K. Scott, M. D. Stuber and P. I. Barton, "Generalized McCormick Relaxations," ''Journal of Global Optimization,'' vol. 51, pp. 569-606, 2011.
	# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]		# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]
			# P. Castro, "Tightening piecewise McCormick relaxations for bilinear problems," ''Computers & Chemical Engineering'', vol. 72, pp. 300-311, 2015.
	#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering,'' vol. 29, pp. ''1''914–1933, 2005.		#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering,'' vol. 29, pp. ''1''914–1933, 2005.
	#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''		#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''
	#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.		#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.
	#A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics,'' vol. 13, 2012.
	#Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.		#Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.
	#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.		#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.

Smu29: corrected reference

2021-12-11T13:36:44Z

corrected reference

Smu29: added applications

2021-12-09T12:58:26Z

added applications

← Older revision		Revision as of 08:58, 9 December 2021
Line 131:		Line 131:

	<math>0 \leq y \leq 2</math>		<math>0 \leq y \leq 2</math>



Line 165:		Line 166:

	<math>s.t. \ w \leq 18</math>		<math>s.t. \ w \leq 18</math>


	<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>		<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>
Line 178:		Line 180:

	</math>		</math>



Line 196:		Line 199:

	</math>		</math>



Line 213:		Line 217:

	</math>		</math>



Line 231:		Line 236:

	== Applications ==		== Applications ==
	Bilinear functions occur in numerous engineering and natural science applications where McCormick Envelopes can be utilized~~, including the following :~~		Bilinear functions occur in numerous engineering and natural science applications where McCormick Envelopes can be utilized.

	~~Computer vision <sup>5</sup>~~

	~~Energy conversion networks <sup>6</sup>~~

	~~Cellular networks~~<sup>7</sup>		For example, an application is the modeling of dynamic biological processes based on experimental data<sup>8</sup>. The challenge for this model is establishing model parameter values that align or calibrate the model response with observed data. These model parameter values can be estimated using optimization techniques, including McCormick Envelopes, to minimize the difference between observed and simulated data.

	~~Dynamic biological systems~~<sup>8</sup>		Another application is the optimization of financial objectives and risk management for energy conversion for a large scale operation such as a college campus or a municipality<sup>6</sup>. This operation involves flexibility of energy sources and several facets of uncertainty involved with pricing. This model uses McCormick Envelopes to optimize the bilinear nonconvex components.

	~~Alternate~~ current optimal power flow (ACOPF)<sup>9</sup>		A third application is the optimized efficiency and reliability of the operation of the electricity grid. Optimal power flow (OPF) and unit commitment (UC) are two optimization problems that support the electricity market operations<sup>8</sup>. McCormick Envelopes are used to strengthen the second-order cone (SOC) relaxation of the alternate current optimal power flow (ACOPF)<sup>9</sup>.
	== Conclusion ==		== Conclusion ==
	Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.		Non-convex NLPs are challenging to solve and may require a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. McCormick Envelopes provide a relaxation technique for bilinear non-convex nonlinear programming problems. McCormick Envelopes provide a straightforward technique of replacing each bilinear term with a new variable and adding four constraints. Due to the recursive nature of this technique, it may be applied to a wide variety of engineering and scientific applications involving bilinear terms.
Line 252:		Line 253:
	#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''		#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''
	#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.		#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.
	#F. Ahmed, M. Naeem, W. Ejaz, M. Iqbal and A. Anpalagan, "Renewable Energy Assisted Sustainable and Environment Friendly Energy Cooperation in Cellular Networks," ''Wireless Personal Communications'', vol. 108''',''' pp. 2585–2607, 2019.
	#A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics,'' vol. 13, 2012.		#A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics,'' vol. 13, 2012.
			#Jeremy Lin; Fernando H. Magnago, "Optimal Power Flow," in Electricity Markets: Theories and Applications , IEEE, 2017, pp.147-171, doi: 10.1002/9781119179382.ch6.
	#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.		#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.

Smu29 at 11:39, 9 December 2021

2021-12-09T11:39:23Z

← Older revision		Revision as of 07:39, 9 December 2021
Line 2:		Line 2:

	== Introduction ==		== Introduction ==
	The McCormick Envelope, originally developed by Dr. Garth McCormick<sup>1</sup>, is a type of convex relaxation used for the optimization of bilinear ~~(e.g., xy, e<sup>xy</sup> + y, sin (x+y) - x<sup>2</sup>)~~ <math>(e.g., xy, e^xy + y, sin(x+y) - x^2)		The McCormick Envelope, originally developed by Dr. Garth McCormick<sup>1</sup>, is a type of convex relaxation used for the optimization of bilinear <math>(e.g., x*y, e^xy + y, sin(x+y) - x^2)
	</math> non-linear programming (NLP) problems.		</math> non-linear programming (NLP) problems. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem.

	Optimization of a non-convex ~~function~~ f(x) is challenging since it may have multiple locally optimal solutions or no solution ~~and it~~ can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem.
	== Theory, Methodology and Algorithmic Discussions ==		== Theory, Methodology and Algorithmic Discussions ==
	[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]		[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]
	As McCormick<sup>1</sup> noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function.		As McCormick<sup>1</sup> noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.

	~~One technique used for a given non-convex function is the identification of a concave envelope and a convex envelope.~~ The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.

	Each bilinear term is replaced with a new variable and four sets of constraints are added. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.		Each bilinear term is replaced with a new variable and four sets of constraints are added. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.
Line 120:		Line 116:
	Good lower and upper bounds focus and minimize the feasible solution space; they reduce the number of iterations to find the optimal solution.		Good lower and upper bounds focus and minimize the feasible solution space; they reduce the number of iterations to find the optimal solution.

	Piecewise McCormick Relaxation		'''Piecewise McCormick Relaxation'''

	As discussed by Hazaji<sup>3</sup>, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>4</sup>.		As discussed by Hazaji<sup>3</sup>, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>4</sup>.
Line 135:		Line 131:

	<math>0 \leq y \leq 2</math>		<math>0 \leq y \leq 2</math>


	<math>Let\ w = xy		<math>Let\ w = xy
Line 181:		Line 178:

	</math>		</math>



Line 198:		Line 196:

	</math>		</math>


	<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>		<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>
Line 208:		Line 207:
	</math>		</math>

	<math>w \leq ~~10y + x0 - 10*0~~		<math>w \leq 10y


Line 214:		Line 213:

	</math>		</math>


	<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>		<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>

Smu29 at 11:22, 9 December 2021

2021-12-09T11:22:09Z

← Older revision		Revision as of 07:22, 9 December 2021
Line 2:		Line 2:

	== Introduction ==		== Introduction ==
	[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope and a convex envelope. ]]
	Optimization of a non-convex function f(x) is challenging since it may have multiple locally optimal solutions or no solution and it can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem. One technique used for a given non-convex function is the identification of a concave envelope and a convex envelope. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.
	~~== McCormick Envelopes: Theory, Methodology and Algorithmic Discussions ==~~
	The McCormick Envelope, originally developed by Dr. Garth McCormick<sup>1</sup>, is a type of convex relaxation used for the optimization of bilinear (e.g., xy, e<sup>xy</sup> + y, sin (x+y) - x<sup>2</sup>) <math>(e.g., xy, e^xy + y, sin(x+y) - x^2)		The McCormick Envelope, originally developed by Dr. Garth McCormick<sup>1</sup>, is a type of convex relaxation used for the optimization of bilinear (e.g., xy, e<sup>xy</sup> + y, sin (x+y) - x<sup>2</sup>) <math>(e.g., xy, e^xy + y, sin(x+y) - x^2)
	</math> non-linear programming (NLP) problems. As McCormick<sup>1</sup> noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function.		</math> non-linear programming (NLP) problems.

			Optimization of a non-convex function f(x) is challenging since it may have multiple locally optimal solutions or no solution and it can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem.
			== Theory, Methodology and Algorithmic Discussions ==
			[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]
			As McCormick<sup>1</sup> noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function.

			One technique used for a given non-convex function is the identification of a concave envelope and a convex envelope. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.

	Each bilinear term is replaced with a new variable and four sets of constraints are added. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.		Each bilinear term is replaced with a new variable and four sets of constraints are added. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.

Smu29: added math formula

2021-12-08T20:41:24Z

added math formula

← Older revision		Revision as of 16:41, 8 December 2021
Line 131:		Line 131:

	<math>0 \leq y \leq 2</math>		<math>0 \leq y \leq 2</math>



	<math>Let\ w = xy		<math>Let\ w = xy
Line 159:		Line 157:

	</math>		</math>



	Substituting these values into the original problem and the McCormick Envelopes, the problem is reformulated:		Substituting these values into the original problem and the McCormick Envelopes, the problem is reformulated:



	<math>min \ Z = w + 6x + y		<math>min \ Z = w + 6x + y
Line 170:		Line 164:

	<math>s.t. \ w \leq 18</math>		<math>s.t. \ w \leq 18</math>



	<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>		<math>w\geq x^{L}y+xy^{L}-x^{L}y^{L}</math>
Line 185:		Line 177:

	</math>		</math>



Line 203:		Line 194:

	</math>		</math>



	<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>		<math>w\leq x^{U}y+xy^{L}-x^{U}y^{L}</math>
Line 221:		Line 210:

	</math>		</math>



	<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>		<math>w\leq xy^{U}+x^{L}y-x^{L}y^{U}</math>
Line 237:		Line 224:
	</math>		</math>

	Using GAMS, the solution is z= -76.2, x=10, y=1.8.		Using GAMS to solve the reformulated problem, the solution is z= -76.2, x=10, y=1.8.

	== Applications ==		== Applications ==
Line 258:		Line 245:
	# J. K. Scott, M. D. Stuber and P. I. Barton, "Generalized McCormick Relaxations," ''Journal of Global Optimization,'' vol. 51, pp. 569-606, 2011.		# J. K. Scott, M. D. Stuber and P. I. Barton, "Generalized McCormick Relaxations," ''Journal of Global Optimization,'' vol. 51, pp. 569-606, 2011.
	# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]		# H. Hijazi, "[https://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=&ved=2ahUKEwjSr7eu8K70AhVYmHIEHUJzCVsQFnoECAIQAQ&url=http%3A%2F%2Fwww.optimization-online.org%2FDB_FILE%2F2015%2F03%2F4841.pdf&usg=AOvVaw1xf9B1f-EPw0mG1LOqRfm9 Perspective Envelopes for Bilinear Functions"]
	#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering, vol. 29, pp.'' ~~1914–1933~~, 2005.		#M. Bergamini, P. Aguirre, and I. Grossman, "Logic-based outer approximation for globally optimal synthesis of process networks," ''Computers and Chemical Engineering,'' vol. 29, pp. ''1''914–1933, 2005.
	#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''		#M. Chandraker and D. Kriegman, "Globally Optimal Bilinear Programming for Computer Vision Applications," presented at the IEEE Computer Society Conference on ''Computer Vision and Pattern Recognition,'' 2008''.''
	#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science, vol. 67,'' pp. 131-138, 2012.		#J. Kantor and P. Mousaw, "A class of bilinear models for the optimization of energy conversion networks," ''Chemical Engineering Science,'' vol. 67'','' pp. 131-138, 2012.
	#F. Ahmed, M. Naeem, W. Ejaz, M. Iqbal and A. Anpalagan, "Renewable Energy Assisted Sustainable and Environment Friendly Energy Cooperation in Cellular Networks," ''Wireless Personal Communications'', vol. 108''',''' pp. 2585–2607, 2019.		#F. Ahmed, M. Naeem, W. Ejaz, M. Iqbal and A. Anpalagan, "Renewable Energy Assisted Sustainable and Environment Friendly Energy Cooperation in Cellular Networks," ''Wireless Personal Communications'', vol. 108''',''' pp. 2585–2607, 2019.
	#A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics, vol. 13,'' 2012.		#A. Miro, C. Pozo, G. Guillen-Gosalbez, J. Egea and L. Jimenez, "Deterministic global optimization algorithm based on outer approximation for the parameter estimation of nonlinear dynamic biological systems," ''BMC Bioinformatics,'' vol. 13, 2012.
	#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.		#B. Michael, A. Castillo, J. Watson and C. Laird, "Strengthened SOCP Relaxations for ACOPF with McCormick Envelopes and Bounds Tightening," ''Computer Aided Chemical Engineering,'' vol. 44'','' pp. 1555-1560, 2018.

← Older revision		Revision as of 09:36, 11 December 2021
Line 2:		Line 2:

	== Introduction ==		== Introduction ==
	The McCormick Envelope, originally developed by Dr. Garth McCormick~~<sup>1</sup>~~, is a type of convex relaxation used for the optimization of bilinear <math>(e.g., x*y, e^xy + y, sin(x+y) - x^2)		The McCormick Envelope, originally developed by Dr. Garth McCormick, is a type of convex relaxation used for the optimization of bilinear <math>(e.g., x*y, e^xy + y, sin(x+y) - x^2)
	</math> non-linear programming (NLP) problems. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem.		</math> non-linear programming (NLP) problems<sup>1</sup>. Optimization of these non-convex functions f(x) is challenging since they may have multiple locally optimal solutions or no solution. It can take a significant amount of time, computing resources, and effort to determine if the solution is global or the problem has no feasible solution. Different techniques are used to address this challenge depending on the characteristics of the problem.
	== Theory, Methodology and Algorithmic Discussions ==		== Theory, Methodology and Algorithmic Discussions ==
	[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]		[[File:Image of updated estimators and envelopes.png\|thumb\|Figure 1: Relationships between the given function, concave over-estimators, convex under-estimators, a concave envelope, and a convex envelope. ]]
	As McCormick~~<sup>1</sup>~~ noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.		As McCormick noted, McCormick Envelopes are based on the key assumption that convex and concave envelopes can be constructed for the given function<sup>1</sup>. The concave envelope, and respectively the convex envelope, is the concave over-estimator and convex under-estimator for the given function providing the tightest fit to the given function. The envelope surrounds the given function, like an envelope encloses a letter, and limits the feasible solution space the most in comparison to all other concave over-estimators and convex under-estimators. Multiple concave over-estimators and multiple convex under-estimators may exist but there is only one concave envelope and one convex envelope for a given function and domain. Figure 1 depicts the relationship between the given function f(x), multiple concave over-estimators, multiple convex under-estimators, a convex envelope, and a concave envelope.

	Each bilinear term is replaced with a new variable and four sets of constraints are added. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.		Each bilinear term is replaced with a new variable and four sets of constraints are added<sup>1</sup>. The non-linear programming is converted to a relaxed convex linear programming (LP) which can be more easily solved.

	The LP solution gives a lower (L) bound and any feasible solution to the problem gives an upper (U) bound.		The LP solution gives a lower (L) bound and any feasible solution to the problem gives an upper (U) bound.

	As noted by Scott et al~~<sup>2</sup>~~, McCormick envelopes are effective since they are recursive, can be applied to a variety of applications, and are typically stronger than those resulting from convexification or linearization procedures.		As noted by Scott et al, McCormick envelopes are effective since they are recursive, can be applied to a variety of applications, and are typically stronger than those resulting from convexification or linearization procedures<sup>2</sup>.

	The following is a derivation of the McCormick Envelopes for a given bilinear ~~function~~:		The following is a derivation of the McCormick Envelopes for a given bilinear function1:

	<math>Let \ w = xy</math>		<math>Let \ w = xy</math>
Line 118:		Line 118:
	'''Piecewise McCormick Relaxation'''		'''Piecewise McCormick Relaxation'''

	As discussed by Hazaji~~<sup>3</sup>~~, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>4</sup>.		As discussed by Hazaji, global optimization solvers focus initially on optimizing the lower and upper bounds, and when necessary, focus on domain partitioning<sup>3</sup>. By dividing the domain of a given variable into partitions or smaller regions, the solver is able to tailor and further tighten the convex relaxations of each partition. This strategy is known as the Piecewise McCormick relaxation<sup>4</sup>.

	== Example: Numerical ==		== Example: Numerical ==