Quadratic constrained quadratic programming - Revision history

Fall2024 Wiki Team2: /* Numerical Example */

2024-12-15T07:46:31Z

Numerical Example

← Older revision		Revision as of 03:46, 15 December 2024
Line 303:		Line 303:

	=== Application 2: Production Planning with Diminishing Returns ===		=== Application 2: Production Planning with Diminishing Returns ===
	[https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Production planning is another area where Quadratic Programming (QP) has significant applications]. The objective is to maximize profit while considering increasing production costs as output scales up(Deckro & Hebert,2003). By modeling the cost as a quadratic function of production volume, QP provides a realistic way to determine optimal production levels, ensuring that diminishing returns are properly accounted for.		[https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Production planning is another area where Quadratic Programming (QP) has significant applications]. The objective is to maximize profit while considering increasing production costs as output scales up(Deckro & Hebert,2003). By modeling the cost as a quadratic function of production volume, QP provides a realistic way to determine optimal production levels, ensuring that diminishing returns are properly accounted for.In many industries, the production process is characterized by an initial phase of increasing returns, followed by a phase of diminishing returns as production scales up. This can be due to factors such as limited machinery capacity, workforce inefficiencies, or increased costs associated with sourcing additional raw materials(Hall, Heady et al,1968). Quadratic programming helps model these non-linear cost increases by incorporating quadratic terms that reflect the rising marginal costs. This allows decision-makers to find the production level at which profit is maximized without overextending resources or incurring disproportionately high costs.

	In many industries, the production process is characterized by an initial phase of increasing returns, followed by a phase of diminishing returns as production scales up. This can be due to factors such as limited machinery capacity, workforce inefficiencies, or increased costs associated with sourcing additional raw materials(Hall, Heady et al,1968). Quadratic programming helps model these non-linear cost increases by incorporating quadratic terms that reflect the rising marginal costs. This allows decision-makers to find the production level at which profit is maximized without overextending resources or incurring disproportionately high costs.

	==== Objective: ====		==== Objective: ====
Line 319:		Line 317:

	==== Constraints: ====		==== Constraints: ====
	[[File:Law of Diminishing Returns.png\|thumb\|[https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Returns]]]Quadratic programming also allows for the inclusion of various constraints that are common in production planning, such as resource availability, labor hours, and budget limits as follows:		[[File:Law of Diminishing Returns.png\|thumb\|[https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Returns(Jensen & Bard,2020)]]]Quadratic programming also allows for the inclusion of various constraints that are common in production planning, such as resource availability, labor hours, and budget limits as follows:

	* Resource constraints: The total amount of available resources, such as labor hours, raw materials, or machine capacity:<math>\sum_i r_i \cdot x_i \leq R_{\text {available }}</math>		* Resource constraints: The total amount of available resources, such as labor hours, raw materials, or machine capacity:<math>\sum_i r_i \cdot x_i \leq R_{\text {available }}</math>
Line 354:		Line 352:
	[10] Hossain, S., Hashim Nik Mustapha, N., & Tak Chen, L. (2002). [https://www.emerald.com/insight/content/doi/10.1108/03068290210419852/full/html?casa_token=SGYpSyJnQJAAAAAA:upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5-_pQeSndVNYw ''A quadratic application in farm planning under uncertainty'']. ''International Journal of Social Economics'', ''29''(4), 282-298.		[10] Hossain, S., Hashim Nik Mustapha, N., & Tak Chen, L. (2002). [https://www.emerald.com/insight/content/doi/10.1108/03068290210419852/full/html?casa_token=SGYpSyJnQJAAAAAA:upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5-_pQeSndVNYw ''A quadratic application in farm planning under uncertainty'']. ''International Journal of Social Economics'', ''29''(4), 282-298.

	[11] McCarl, B. A., Moskowitz, H., & Furtan, H. (1977). Quadratic programming applications. ''Omega'', ''5''(1), 43-55.		[11] Jensen, P. A., & Bard, J. F. (2020). ''Nonlinear programming methods. S2 Quadratic programming''. Operations Research Models and Methods.

			[12] McCarl, B. A., Moskowitz, H., & Furtan, H. (1977). Quadratic programming applications. ''Omega'', ''5''(1), 43-55.

	[12] Migo-Sumagang, M. V., Tan, R. R., Tapia, J. F. D., & Aviso, K. B. (2022). ''Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions''. ''Cleaner Engineering and Technology'', ''9'', 100507.		[13] Migo-Sumagang, M. V., Tan, R. R., Tapia, J. F. D., & Aviso, K. B. (2022). ''Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions''. ''Cleaner Engineering and Technology'', ''9'', 100507.

	[13] NAG. (2022). ''Solving quadratically constrained quadratic programming (QCQP) problems''. Retrieved from <nowiki>https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/</nowiki>		[14] NAG. (2022). ''Solving quadratically constrained quadratic programming (QCQP) problems''. Retrieved from <nowiki>https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/</nowiki>

	[14]Pasandideh, S. H. R., Niaki, S. T. A., & Gharaei, A. (2015). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw ''Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming'']. ''Knowledge-Based Systems'', ''84'', 98-107.		[15] Pasandideh, S. H. R., Niaki, S. T. A., & Gharaei, A. (2015). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw ''Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming'']. ''Knowledge-Based Systems'', ''84'', 98-107.

	[15] Pyman, D. H. (2021). ''The risk-return trade-off to diversified agriculture in Malawi: A quadratic programming approach'' (Doctoral dissertation, Stellenbosch: Stellenbosch University).		[16] Pyman, D. H. (2021). ''The risk-return trade-off to diversified agriculture in Malawi: A quadratic programming approach'' (Doctoral dissertation, Stellenbosch: Stellenbosch University).

	[16] Ries, S., & Houtz, R. (1983). ''Triacontanol as a plant growth regulator.''		[17] Ries, S., & Houtz, R. (1983). ''Triacontanol as a plant growth regulator.''

	[17] Wikipedia. (2021). ''Max paraboloid.svg''. Retrieved from <nowiki>https://en.wikipedia.org/wiki/File:Max_paraboloid.svg</nowiki>		[18] Wikipedia. (2021). ''Max paraboloid.svg''. Retrieved from <nowiki>https://en.wikipedia.org/wiki/File:Max_paraboloid.svg</nowiki>

	[18] Zenios, S. A. (Ed.). (1993). ''Financial optimization''. Cambridge university press,doi:https://doi.org/10.1017/CBO9780511522130		[19] Zenios, S. A. (Ed.). (1993). ''Financial optimization''. Cambridge university press,doi:https://doi.org/10.1017/CBO9780511522130

	==Further Reading==		==Further Reading==

Fall2024 Wiki Team2: /* Introduction */

2024-12-15T07:32:41Z

Introduction

← Older revision		Revision as of 03:32, 15 December 2024
Line 4:		Line 4:

	==Introduction==		==Introduction==
	~~<gallery mode="packed-overlay" widths="300" heights="300">~~		'''[[wikipedia:Quadratic_programming\|Quadratic programming (QP)]]''' is one of the oldest topics in the field of optimization that researchers have studied in the twentieth century. The basic QP, where the
	~~File~~:~~Index~~.~~php?title=~~File:Q.png\|[https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]~~<ref>Cited in the External Link</ref>~~		[[File:Q.png\|thumb\|[https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems](NAG,2022)]]
	~~</gallery>'''[[wikipedia:Quadratic_programming\|Quadratic programming~~ (QP)]]~~''' is one of the oldest topics in the field of optimization that researchers have studied in the twentieth century. The basic QP, where the~~ objective function is quadratic and constraints are linear, paved the way for other forms, such as QCQPs, which also have quadratic constraints (McCarl,Moskowitz et al,1977).		objective function is quadratic and constraints are linear, paved the way for other forms, such as QCQPs, which also have quadratic constraints (McCarl,Moskowitz et al,1977).

	A '''[[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically Constrained Quadratic Program (QCQP)]]''' can be defined as an optimization problem where the objective function and the constraints are quadratic. It emerged as [[wikipedia:Mathematical_optimization\|optimisation theory]] grew to address more realistic, [https://zhengy09.github.io/ECE285/lectures/L6.pdf complex problems] of non-linear objectives and constraints. In particular, the issue involves optimizing (or minimizing) a [[wikipedia:Convex_function\|convex quadratic function]] of decision variables with quadratic constraints. This class of problems is well suited to finance (Zenios,1993), engineering, machine learning, and agriculture because it is easier to model the relationship between variables using quadratic functions.		A '''[[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically Constrained Quadratic Program (QCQP)]]''' can be defined as an optimization problem where the objective function and the constraints are quadratic. It emerged as [[wikipedia:Mathematical_optimization\|optimisation theory]] grew to address more realistic, [https://zhengy09.github.io/ECE285/lectures/L6.pdf complex problems] of non-linear objectives and constraints. In particular, the issue involves optimizing (or minimizing) a [[wikipedia:Convex_function\|convex quadratic function]] of decision variables with quadratic constraints. This class of problems is well suited to finance (Zenios,1993), engineering, machine learning, and agriculture because it is easier to model the relationship between variables using quadratic functions.
Line 18:		Line 18:
	In mathematical optimization, a quadratically constrained quadratic program (QCQP) is a problem where both the objective function and the constraints are quadratic functions. A related but simpler case is the quadratic program (QP), where the objective function is a convex quadratic function, and the constraints are linear.		In mathematical optimization, a quadratically constrained quadratic program (QCQP) is a problem where both the objective function and the constraints are quadratic functions. A related but simpler case is the quadratic program (QP), where the objective function is a convex quadratic function, and the constraints are linear.

	=== QP ===		=== QP(Quadratic Programming) ===
	A '''QP''' can be expressed in the standard form:		A '''QP''' can be expressed in the standard form:

Line 28:		Line 28:
	where <math>P\in \mathbf{S}_+^n</math> (the set of symmetric positive semidefinite matrices), <math>G\in \mathbb{R}^{m\times n}</math>, and <math>A\in \mathbb{R}^{p\times n}</math>. In this case, we minimize a convex quadratic function over a polyhedron.		where <math>P\in \mathbf{S}_+^n</math> (the set of symmetric positive semidefinite matrices), <math>G\in \mathbb{R}^{m\times n}</math>, and <math>A\in \mathbb{R}^{p\times n}</math>. In this case, we minimize a convex quadratic function over a polyhedron.

	=== QCQP ===		=== QCQP(Quadratically Constrained Quadratic Program) ===
	When the inequality constraints are also quadratic, the problem becomes a '''QCQP.''' This extends the QP formulation to:		When the inequality constraints are also quadratic, the problem becomes a '''QCQP.''' This extends the QP formulation to:

Line 58:		Line 58:
	It is widely used in areas where global optimization or approximations to non-convex issues are necessary.		It is widely used in areas where global optimization or approximations to non-convex issues are necessary.
	\|}		\|}
	[[File:Semidefinite Programming.jpg\|thumb\|[https://i.ytimg.com/vi/Sm0IUpxBHNs/maxresdefault.jpg Semidefinite Programming]<ref>Cited in the External Link</ref>]]		[[File:Semidefinite Programming.jpg\|thumb\|[https://i.ytimg.com/vi/Sm0IUpxBHNs/maxresdefault.jpg Semidefinite Programming]<ref>Cited in the External Link</ref>(Wikipedia,2021)]]
	Other relaxations, such as '''Second-Order Cone Programming (SOCP)''', are exact for specific problem classes like QCQPs with zero diagonal elements in the data matrices. These relaxations often produce the same objective value as SDP relaxations(Best,Kale,2000). Moreover, it has been shown that for a class of random QCQPs, SDP relaxations are exact with high probability if the number of constraints grows at a controlled polynomial rate relative to the number of variables.		Other relaxations, such as '''Second-Order Cone Programming (SOCP)''', are exact for specific problem classes like QCQPs with zero diagonal elements in the data matrices. These relaxations often produce the same objective value as SDP relaxations(Best,Kale,2000). Moreover, it has been shown that for a class of random QCQPs, SDP relaxations are exact with high probability if the number of constraints grows at a controlled polynomial rate relative to the number of variables.

Line 358:		Line 358:
	[12] Migo-Sumagang, M. V., Tan, R. R., Tapia, J. F. D., & Aviso, K. B. (2022). ''Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions''. ''Cleaner Engineering and Technology'', ''9'', 100507.		[12] Migo-Sumagang, M. V., Tan, R. R., Tapia, J. F. D., & Aviso, K. B. (2022). ''Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions''. ''Cleaner Engineering and Technology'', ''9'', 100507.

	[13] ~~Pasandideh, S~~. ~~H. R., Niaki, S. T. A., & Gharaei, A~~. (~~2015~~). [https://~~www.sciencedirect~~.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw ''Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming~~'']. ''Knowledge~~-~~Based Systems'', ''84'', 98~~-~~107.~~		[13] NAG. (2022). ''Solving quadratically constrained quadratic programming (QCQP) problems''. Retrieved from <nowiki>https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/</nowiki>

	[14] ~~Pyman~~, D. H. (~~2021~~). ''~~The risk-return trade-off to diversified agriculture in Malawi: A~~ quadratic programming ~~approach~~'' ~~(Doctoral dissertation~~, ~~Stellenbosch: Stellenbosch University)~~.		[14]Pasandideh, S. H. R., Niaki, S. T. A., & Gharaei, A. (2015). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw ''Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming'']. ''Knowledge-Based Systems'', ''84'', 98-107.

	[15] ~~Ries~~, S.~~, & Houtz, R~~. (~~1983~~). ''~~Triacontanol as a plant growth regulator.~~''		[15] Pyman, D. H. (2021). ''The risk-return trade-off to diversified agriculture in Malawi: A quadratic programming approach'' (Doctoral dissertation, Stellenbosch: Stellenbosch University).

	[16] Zenios, S. A. (Ed.). (1993). ''Financial optimization''. Cambridge university press,doi:https://doi.org/10.1017/CBO9780511522130		[16] Ries, S., & Houtz, R. (1983). ''Triacontanol as a plant growth regulator.''

			[17] Wikipedia. (2021). ''Max paraboloid.svg''. Retrieved from <nowiki>https://en.wikipedia.org/wiki/File:Max_paraboloid.svg</nowiki>

			[18] Zenios, S. A. (Ed.). (1993). ''Financial optimization''. Cambridge university press,doi:https://doi.org/10.1017/CBO9780511522130

	==Further Reading==		==Further Reading==

Fall2024 Wiki Team2: /* Introduction */

2024-12-15T04:57:44Z

Introduction

← Older revision		Revision as of 00:57, 15 December 2024
Line 4:		Line 4:

	==Introduction==		==Introduction==
	'''[[wikipedia:Quadratic_programming\|Quadratic programming (QP)]]''' is one of the oldest topics in the field of optimization that researchers have studied in the twentieth century. The basic QP, where the objective function is quadratic and constraints are linear, paved the way for other forms, such as QCQPs, which also have quadratic constraints (McCarl,Moskowitz et al,1977).		<gallery mode="packed-overlay" widths="300" heights="300">
			File:Index.php?title=File:Q.png\|[https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]<ref>Cited in the External Link</ref>
			</gallery>'''[[wikipedia:Quadratic_programming\|Quadratic programming (QP)]]''' is one of the oldest topics in the field of optimization that researchers have studied in the twentieth century. The basic QP, where the objective function is quadratic and constraints are linear, paved the way for other forms, such as QCQPs, which also have quadratic constraints (McCarl,Moskowitz et al,1977).

	A '''[[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically Constrained Quadratic Program (QCQP)]]''' can be defined as an optimization problem where the objective function and the constraints are quadratic. It emerged as [[wikipedia:Mathematical_optimization\|optimisation theory]] grew to address more realistic, [https://zhengy09.github.io/ECE285/lectures/L6.pdf complex problems] of non-linear objectives and constraints. In particular, the issue involves optimizing (or minimizing) a [[wikipedia:Convex_function\|convex quadratic function]] of decision variables with quadratic constraints. This class of problems is well suited to finance (Zenios,1993), engineering, machine learning, and agriculture because it is easier to model the relationship between variables using quadratic functions.		A '''[[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically Constrained Quadratic Program (QCQP)]]''' can be defined as an optimization problem where the objective function and the constraints are quadratic. It emerged as [[wikipedia:Mathematical_optimization\|optimisation theory]] grew to address more realistic, [https://zhengy09.github.io/ECE285/lectures/L6.pdf complex problems] of non-linear objectives and constraints. In particular, the issue involves optimizing (or minimizing) a [[wikipedia:Convex_function\|convex quadratic function]] of decision variables with quadratic constraints. This class of problems is well suited to finance (Zenios,1993), engineering, machine learning, and agriculture because it is easier to model the relationship between variables using quadratic functions.

	* The desire to study QCQPs stems from the fact that they can be used to model practical optimization problems that involve stochasticity in risk, resources, production, and decision-making. For example, in agriculture, using QCQPs can be useful in determining the best crop to grow based on the expected profits and the uncertainties of price changes and unfavourable weather conditions (Floudas,1995).		* The desire to study QCQPs stems from the fact that they can be used to model practical optimization problems that involve stochasticity in risk, resources, production, and decision-making. For example, in agriculture, using QCQPs can be useful in determining the best crop to grow based on the expected profits and the uncertainties of price changes and unfavourable weather conditions (Floudas,1995).
	* In finance, the QCQPs are applied in the portfolio's construction to maximize the portfolio's expected returns and the covariance between the assets. It is crucial to comprehend QCQPs and the ways to solve them, such as '''[[wikipedia:Karush–Kuhn–Tucker_conditions\|KKT (Karush-Kuhn Tucker)]]''' conditions and '''[[wikipedia:Software-defined_perimeter\|SDP (Semidefinite Programming)]]''' relaxations, to solve problems that linear models cannot effectively solve (Bao & Sahinidis,2011).~~<gallery mode="packed" widths="300" heights="300" class="center-images" style="display: block; margin: 0 auto;">~~		* In finance, the QCQPs are applied in the portfolio's construction to maximize the portfolio's expected returns and the covariance between the assets. It is crucial to comprehend QCQPs and the ways to solve them, such as '''[[wikipedia:Karush–Kuhn–Tucker_conditions\|KKT (Karush-Kuhn Tucker)]]''' conditions and '''[[wikipedia:Software-defined_perimeter\|SDP (Semidefinite Programming)]]''' relaxations, to solve problems that linear models cannot effectively solve (Bao & Sahinidis,2011).
	File:Q.png\|[https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]<ref>Cited in the External Link</ref>
	~~</gallery>~~
	In general, analyzing QCQPs is important in order to apply knowledge-based decision-making and enhance the performance and stability of optimization methods in different fields (Zenios,1993).		In general, analyzing QCQPs is important in order to apply knowledge-based decision-making and enhance the performance and stability of optimization methods in different fields (Zenios,1993).

Fall2024 Wiki Team2: /* Numerical Example */

2024-12-15T04:54:29Z

Numerical Example

← Older revision		Revision as of 00:54, 15 December 2024
Line 80:		Line 80:
	* Determined the active constraints using complementary slackness		* Determined the active constraints using complementary slackness

	==== Lagrangian Formulation: ====		==== Step 1: Lagrangian Formulation: ====
	The '''Lagrangian formulation''' in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the '''Lagrangian <math>L</math>''' This formulation introduces '''Lagrange multipliers''' <math>\lambda_i</math>for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows (Pasandideh, Niaki et al,2015):		The '''Lagrangian formulation''' in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the '''Lagrangian <math>L</math>''' This formulation introduces '''Lagrange multipliers''' <math>\lambda_i</math>for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows (Pasandideh, Niaki et al,2015):

Line 109:		Line 109:
	</math>		</math>

	==== Stationarity Condition Application: ====		==== Step 2: Stationarity Condition Application: ====

	===== Setting the results to zero =====		===== Setting the results to zero =====
Line 151:		Line 151:
	* Assume <math>\lambda_2 = 0</math> because Constraint 2 is not active at <math>x_1 = 1</math>.		* Assume <math>\lambda_2 = 0</math> because Constraint 2 is not active at <math>x_1 = 1</math>.

	==== Verification ====		==== Step 3: Verification ====

	===== Complementary Slackness Verification =====		===== Complementary Slackness Verification =====
Line 172:		Line 172:
	</math>		</math>

	==== Conclusion ====		==== Step 4: Conclusion ====

	* Optimal Solution: <math>		* Optimal Solution: <math>
Line 226:		Line 226:
	* Value Optimization		* Value Optimization

	==== Stationarity Condition Application: ====		==== Step 1: Stationarity Condition Application: ====

	* Lifted variable introduction:<math> x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \quad X = x x^T = \begin{pmatrix} x_1^2 & x_1 x_2 \\ x_1 x_2 & x_2^2 \end{pmatrix}. </math>		* Lifted variable introduction:<math> x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \quad X = x x^T = \begin{pmatrix} x_1^2 & x_1 x_2 \\ x_1 x_2 & x_2^2 \end{pmatrix}. </math>
Line 235:		Line 235:
	** Constraint 2: <math>-x_1 x_2 + 1 \leq 0 \implies X_{12} \geq 1.</math>		** Constraint 2: <math>-x_1 x_2 + 1 \leq 0 \implies X_{12} \geq 1.</math>

	==== SDP Relaxation: ====		==== Step 2:SDP Relaxation ====
	The original QCQP is non-convex due to the rank-1 condition on <math>X</math>.		The original QCQP is non-convex due to the rank-1 condition on <math>X</math>.

Line 242:		Line 242:
	<math> \begin{aligned} \text{minimize} \quad & \langle I, X \rangle \\ \text{subject to} \quad & \langle I, X \rangle - 2 \leq 0, \\ & X_{12} \geq 1, \\ & X \succeq 0. \end{aligned} </math>		<math> \begin{aligned} \text{minimize} \quad & \langle I, X \rangle \\ \text{subject to} \quad & \langle I, X \rangle - 2 \leq 0, \\ & X_{12} \geq 1, \\ & X \succeq 0. \end{aligned} </math>

	==== Solver: ====		==== Step 3: Choose Solver ====
	Solving the SDP, the feasible solution <math>X^*</math> found that achieves the minimum:		Solving the SDP, the feasible solution <math>X^*</math> found that achieves the minimum:

Line 253:		Line 253:
	* with <math>x^* = (1, 1)</math>.		* with <math>x^* = (1, 1)</math>.

	==== Value Optimization: ====		==== Step 4: Value Optimization ====
	<math> \text{ The orignial QCQP's optimal value is } x^* = (1,1) </math>		<math> \text{ The orignial QCQP's optimal value is } x^* = (1,1) </math>

Fall2024 Wiki Team2: /* 1. 1 Lagrangian Formulation: */

2024-12-15T04:52:17Z

1. 1 Lagrangian Formulation:

← Older revision		Revision as of 00:52, 15 December 2024
Line 80:		Line 80:
	* Determined the active constraints using complementary slackness		* Determined the active constraints using complementary slackness

	==== ~~1. 1~~ Lagrangian Formulation: ====		==== Lagrangian Formulation: ====
	The '''Lagrangian formulation''' in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the '''Lagrangian <math>L</math>''' This formulation introduces '''Lagrange multipliers''' <math>\lambda_i</math>for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows (Pasandideh, Niaki et al,2015):		The '''Lagrangian formulation''' in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the '''Lagrangian <math>L</math>''' This formulation introduces '''Lagrange multipliers''' <math>\lambda_i</math>for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows (Pasandideh, Niaki et al,2015):

Line 109:		Line 109:
	</math>		</math>

	==== ~~1. 2~~ Stationarity Condition Application: ====		==== Stationarity Condition Application: ====

	===== ~~1.2.1~~ Setting the results to zero =====		===== Setting the results to zero =====

	* <math>		* <math>
Line 126:		Line 126:
	</math>		</math>

	===== ~~1.2.2~~ Substituting =====		===== Substituting =====
	<math>x_2 = 0</math> into the constraints		<math>x_2 = 0</math> into the constraints

Line 136:		Line 136:
	</math>		</math>

	===== ~~1.2.3~~ Problem Solving =====		===== Problem Solving =====

	* Substitute <math>x_2 = 0</math> into Equation (1): <math>		* Substitute <math>x_2 = 0</math> into Equation (1): <math>
Line 151:		Line 151:
	* Assume <math>\lambda_2 = 0</math> because Constraint 2 is not active at <math>x_1 = 1</math>.		* Assume <math>\lambda_2 = 0</math> because Constraint 2 is not active at <math>x_1 = 1</math>.

	==== ~~1. 3~~ Verification ====		==== Verification ====

	===== ~~1.3.1~~ Complementary Slackness Verification =====		===== Complementary Slackness Verification =====

	* Constraint 1: <math>		* Constraint 1: <math>
Line 162:		Line 162:
	</math>		</math>

	===== ~~1.3.2~~ Primal Feasibility Verification =====		===== Primal Feasibility Verification =====

	* Constraint 1: <math>		* Constraint 1: <math>
Line 172:		Line 172:
	</math>		</math>

	==== ~~1. 4~~ Conclusion ====		==== Conclusion ====

	* Optimal Solution: <math>		* Optimal Solution: <math>
Line 226:		Line 226:
	* Value Optimization		* Value Optimization

	==== ~~1. 1~~ Stationarity Condition Application: ====		==== Stationarity Condition Application: ====

	* Lifted variable introduction:<math> x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \quad X = x x^T = \begin{pmatrix} x_1^2 & x_1 x_2 \\ x_1 x_2 & x_2^2 \end{pmatrix}. </math>		* Lifted variable introduction:<math> x = \begin{pmatrix} x_1 \\ x_2 \end{pmatrix}, \quad X = x x^T = \begin{pmatrix} x_1^2 & x_1 x_2 \\ x_1 x_2 & x_2^2 \end{pmatrix}. </math>
Line 235:		Line 235:
	** Constraint 2: <math>-x_1 x_2 + 1 \leq 0 \implies X_{12} \geq 1.</math>		** Constraint 2: <math>-x_1 x_2 + 1 \leq 0 \implies X_{12} \geq 1.</math>

	==== ~~1. 2~~ SDP Relaxation: ====		==== SDP Relaxation: ====
	The original QCQP is non-convex due to the rank-1 condition on <math>X</math>.		The original QCQP is non-convex due to the rank-1 condition on <math>X</math>.

Line 242:		Line 242:
	<math> \begin{aligned} \text{minimize} \quad & \langle I, X \rangle \\ \text{subject to} \quad & \langle I, X \rangle - 2 \leq 0, \\ & X_{12} \geq 1, \\ & X \succeq 0. \end{aligned} </math>		<math> \begin{aligned} \text{minimize} \quad & \langle I, X \rangle \\ \text{subject to} \quad & \langle I, X \rangle - 2 \leq 0, \\ & X_{12} \geq 1, \\ & X \succeq 0. \end{aligned} </math>

	==== ~~1. 2~~ Solver: ====		==== Solver: ====
	Solving the SDP, the feasible solution <math>X^*</math> found that achieves the minimum:		Solving the SDP, the feasible solution <math>X^*</math> found that achieves the minimum:

Line 253:		Line 253:
	* with <math>x^* = (1, 1)</math>.		* with <math>x^* = (1, 1)</math>.

	==== ~~1. 3~~ Value Optimization: ====		==== Value Optimization: ====
	<math> \text{ The orignial QCQP's optimal value is } x^* = (1,1) </math>		<math> \text{ The orignial QCQP's optimal value is } x^* = (1,1) </math>

Line 271:		Line 271:
	==Application==		==Application==

	=== Application 1. Agriculture (crop selection problem) ===		=== Application 1: Agriculture (crop selection problem) ===
	[[File:The quadratic yield response of crops to TRIA in the field.png\|thumb\|The [https://www.researchgate.net/figure/The-quadratic-yield-response-of-crops-to-TRIA-in-the-field-Potatoes-were-grown-at-Stan_fig1_284807130 quadratic yield response] of crops to TRIA in the field (Ries& Houtz, 1983)]]		[[File:The quadratic yield response of crops to TRIA in the field.png\|thumb\|The [https://www.researchgate.net/figure/The-quadratic-yield-response-of-crops-to-TRIA-in-the-field-Potatoes-were-grown-at-Stan_fig1_284807130 quadratic yield response] of crops to TRIA in the field (Ries& Houtz, 1983)]]
	In agriculture, quadratic programming plays an essential role in optimizing crop selection and resource allocation. Farmers often face a set of challenging decisions when determining which crops to plant and how to allocate limited resources such as land, water, and labor(McCarl,Moskowitz et el,1977). The decisions become even more complicated when accounting for uncertainties such as fluctuating crop prices, weather conditions, and yield variability. Quadratic programming provides a powerful framework for making these complex decisions more manageable.		In agriculture, quadratic programming plays an essential role in optimizing crop selection and resource allocation. Farmers often face a set of challenging decisions when determining which crops to plant and how to allocate limited resources such as land, water, and labor(McCarl,Moskowitz et el,1977). The decisions become even more complicated when accounting for uncertainties such as fluctuating crop prices, weather conditions, and yield variability. Quadratic programming provides a powerful framework for making these complex decisions more manageable.
Line 289:		Line 289:
	Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions (Pyman, 2021). As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.		Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions (Pyman, 2021). As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.

	===== ~~(1)~~ Risk =====		===== Risk =====
	The risks can stem from fluctuating market prices, varying yields due to unpredictable weather conditions, and pests or diseases.		The risks can stem from fluctuating market prices, varying yields due to unpredictable weather conditions, and pests or diseases.

Line 295:		Line 295:
	* The goal is to maximize the expected returns while minimizing risk by selecting crops with complementary risk profiles.		* The goal is to maximize the expected returns while minimizing risk by selecting crops with complementary risk profiles.

	===== ~~(2)~~ Constraints =====		===== Constraints =====
	A set of constraints is always included that reflect the available resources. For example:		A set of constraints is always included that reflect the available resources. For example:

Line 302:		Line 302:
	* Non-negativity: <math>x_i \geq 0</math> for all crops <math>i_r</math> ensuring that no crop area is negative.		* Non-negativity: <math>x_i \geq 0</math> for all crops <math>i_r</math> ensuring that no crop area is negative.

	=== Application 2. Production Planning with Diminishing Returns ===		=== Application 2: Production Planning with Diminishing Returns ===
	[https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Production planning is another area where Quadratic Programming (QP) has significant applications]. The objective is to maximize profit while considering increasing production costs as output scales up(Deckro & Hebert,2003). By modeling the cost as a quadratic function of production volume, QP provides a realistic way to determine optimal production levels, ensuring that diminishing returns are properly accounted for.		[https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Production planning is another area where Quadratic Programming (QP) has significant applications]. The objective is to maximize profit while considering increasing production costs as output scales up(Deckro & Hebert,2003). By modeling the cost as a quadratic function of production volume, QP provides a realistic way to determine optimal production levels, ensuring that diminishing returns are properly accounted for.

Fall2024 Wiki Team2: /* Further Reading */

2024-12-15T04:46:50Z

Fall2024 Wiki Team2: /* Reference */

2024-12-15T04:35:46Z

Reference

← Older revision		Revision as of 00:35, 15 December 2024
Line 334:		Line 334:
	Looking forward, there are several potential areas for improvement in QCQP algorithms. One direction is the development of more efficient relaxation techniques for solving non-convex QCQPs, especially in large-scale problems where computational efficiency becomes critical. Additionally, there is ongoing research into hybrid methods that combine the strengths of different optimization techniques, such as SDP and machine learning, to improve the robustness and speed of solving QCQPs in dynamic environments. As optimization problems become increasingly complex and data-rich, advancements in QCQP algorithms will continue to play a crucial role in making informed, optimal decisions in diverse applications.		Looking forward, there are several potential areas for improvement in QCQP algorithms. One direction is the development of more efficient relaxation techniques for solving non-convex QCQPs, especially in large-scale problems where computational efficiency becomes critical. Additionally, there is ongoing research into hybrid methods that combine the strengths of different optimization techniques, such as SDP and machine learning, to improve the robustness and speed of solving QCQPs in dynamic environments. As optimization problems become increasingly complex and data-rich, advancements in QCQP algorithms will continue to play a crucial role in making informed, optimal decisions in diverse applications.
	==Reference==		==Reference==
	[1] Agarwal, D., Singh, P., & El Sayed, M. A. (2023). The Karush–Kuhn–Tucker (KKT) optimality conditions for fuzzy-valued fractional optimization problems. Mathematics and Computers in Simulation, 205, 861-877, DOI:[https://www.researchgate.net/publication/365290227_The_Karush-Kuhn-Tucker_KKT_optimality_conditions_for_fuzzy-valued_fractional_optimization_problems 10.1016/j.matcom.2022.10.024]		[1] Agarwal, D., Singh, P., & El Sayed, M. A. (2023). ''The Karush–Kuhn–Tucker (KKT) optimality conditions for fuzzy-valued fractional optimization problems''. Mathematics and Computers in Simulation, 205, 861-877, DOI:[https://www.researchgate.net/publication/365290227_The_Karush-Kuhn-Tucker_KKT_optimality_conditions_for_fuzzy-valued_fractional_optimization_problems 10.1016/j.matcom.2022.10.024]

	[2] Bao, X., Sahinidis, N. V., & Tawarmalani, M. (2011). [https://link.springer.com/article/10.1007/s10107-011-0462-2 Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons] (PDF). ''Mathematical programming'', ''129'', 129-157.		[2] Bao, X., Sahinidis, N. V., & Tawarmalani, M. (2011). [https://link.springer.com/article/10.1007/s10107-011-0462-2 Semidefinite relaxations for quadratically constrained quadratic programming: A review and comparisons] (PDF). ''Mathematical programming'', ''129'', 129-157.

	[3] ~~Bose~~, ~~S., Gayme, D. F., Chandy, K. M., & Low, S. H~~. (~~2015~~). ~~Quadratically constrained~~ quadratic ~~programs on acyclic graphs with application to power flow. IEEE Transactions on Control of Network Systems, 2(3), 278-287,[https://ieeexplore.ieee.org/document/7035094 DOI: 10.1109/TCNS.2015~~.~~2401172]~~		[3] Bauer, L. (1970). A quadratic programming algorithm for deriving efficient farm plans in a risk setting.

	[4] ~~Elloumi~~, S., & ~~Lambert~~, A. (~~2019~~). ~~Global solution of non-convex quadratically~~ constrained quadratic programs~~. ''Optimization methods and software~~'', ~~''34''~~(1), 98-~~114~~,~~doi:~~ https://~~doi~~.org/10.~~1080~~/~~10556788~~.~~2017~~.~~1350675~~		[4] Bose, S., Gayme, D. F., Chandy, K. M., & Low, S. H. (2015). ''Quadratically constrained quadratic programs on acyclic graphs with application to power flow''. IEEE Transactions on Control of Network Systems, 2(3), 278-287,[https://ieeexplore.ieee.org/document/7035094 DOI: 10.1109/TCNS.2015.2401172]

	[5] ~~Freund~~, R. M. (~~2004~~). ~~[https://ocw~~.~~mit.edu/courses/15-084j-nonlinear-programming-spring-2004/a632b565602fd2eb3be574c537eea095_lec23_semidef_opt.pdf Introduction to semidefinite programming~~ (~~SDP~~)~~] (PDF). Massachusetts Institute of Technology~~, 8-11.		[5] Deckro, R. F., & Hebert, J. E. (2003). ''Modeling diminishing returns in project resource planning''. Computers & industrial engineering, ''44''(1), 19-33.

	[6] ~~Ghojogh~~, B., ~~Ghodsi~~, A.~~, Karray, F~~., ~~& Crowley, M.~~ (~~2021~~)~~. KKT conditions~~, ~~first~~-~~order and second-order optimization~~, ~~and distributed optimization~~: ~~tutorial and survey~~. ~~arXiv preprint arXiv:2110~~.~~01858~~.		[6] Elloumi, S., & Lambert, A. (2019). ''Global solution of non-convex quadratically constrained quadratic programs''. ''Optimization methods and software'', ''34''(1), 98-114,doi: https://doi.org/10.1080/10556788.2017.1350675

	[7] ~~McCarl~~, B. A.~~, Moskowitz, H~~.~~, & Furtan, H~~. ~~(1977)~~. ~~Quadratic~~ programming ~~applications~~. ''~~Omega'', ''5~~''(1), 43-55.		[7] Freund, R. M. (2004). [https://ocw.mit.edu/courses/15-084j-nonlinear-programming-spring-2004/a632b565602fd2eb3be574c537eea095_lec23_semidef_opt.pdf ''Introduction to semidefinite programming (SDP)''] (PDF). Massachusetts Institute of Technology, 8-11.

	[8] ~~Zenios~~, S. A. ~~(Ed~~.). (~~1993~~). ~~Financial~~ optimization~~. Cambridge university press~~,~~doi~~:~~https~~:~~//doi~~.~~org/10~~.~~1017/CBO9780511522130~~		[8] Ghojogh, B., Ghodsi, A., Karray, F., & Crowley, M. (2021). ''KKT conditions, first-order and second-order optimization, and distributed optimization: tutorial and survey''. arXiv preprint arXiv:2110.01858.

	[9] ~~Hossain~~, S., ~~Hashim Nik Mustapha~~, N., & ~~Tak Chen~~, L. (~~2002~~). [https://~~www~~.~~emerald~~.com/~~insight/content~~/~~doi~~/10.~~1108/03068290210419852/full~~/~~html~~?casa_token=~~SGYpSyJnQJAAAAAA~~:~~upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5~~-~~_pQeSndVNYw A quadratic application in farm planning under uncertainty~~]. ''~~International~~ Journal of ~~Social~~ Economics'', ''29''(4), ~~282~~-~~298~~.		[9] Hall, H. H., Heady, E. O., & Plessner, Y. (1968). [https://onlinelibrary.wiley.com/doi/abs/10.2307/1238258?casa_token=4sxkbKbwLBwAAAAA:LXWbjj3TzWEtzJUtp0U6CUDI7xkyvfFeUh-YPI5yXB_gw3mWUIIJOvOI8NLHy4ghcqtubgkAZSUTUA ''Quadratic programming solution of competitive equilibrium for US agriculture'']. ''American Journal of Agricultural Economics'', ''50''(3), 536-555.

	[10] ~~Hall~~, ~~H. H~~., ~~Heady~~, ~~E. O~~., & ~~Plessner~~, Y. (~~1968~~). [https://~~onlinelibrary~~.~~wiley~~.com/doi~~/abs~~/10.~~2307~~/~~1238258~~?casa_token=~~4sxkbKbwLBwAAAAA~~:~~LXWbjj3TzWEtzJUtp0U6CUDI7xkyvfFeUh~~-~~YPI5yXB_gw3mWUIIJOvOI8NLHy4ghcqtubgkAZSUTUA Quadratic programming solution of competitive equilibrium for US agriculture~~]. ''~~American~~ Journal of ~~Agricultural~~ Economics'', ''50''(3), ~~536~~-~~555~~.		[10] Hossain, S., Hashim Nik Mustapha, N., & Tak Chen, L. (2002). [https://www.emerald.com/insight/content/doi/10.1108/03068290210419852/full/html?casa_token=SGYpSyJnQJAAAAAA:upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5-_pQeSndVNYw ''A quadratic application in farm planning under uncertainty'']. ''International Journal of Social Economics'', ''29''(4), 282-298.

	[11] ~~Pasandideh~~, S. ~~H. R~~., ~~Niaki~~, ~~S. T. A~~., & ~~Gharaei~~, A. (~~2015~~). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming]. ''~~Knowledge-Based Systems~~'', ''84'', 98-~~107~~.		[11] McCarl, B. A., Moskowitz, H., & Furtan, H. (1977). Quadratic programming applications. ''Omega'', ''5''(1), 43-55.

	[12] ~~Pyman~~, D. H. (~~2021~~). ''~~The risk~~-~~return trade-off to diversified agriculture in Malawi: A~~ quadratic programming ~~approach~~'' ~~(Doctoral dissertation~~, ~~Stellenbosch: Stellenbosch University)~~.		[12] Migo-Sumagang, M. V., Tan, R. R., Tapia, J. F. D., & Aviso, K. B. (2022). ''Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions''. ''Cleaner Engineering and Technology'', ''9'', 100507.

	[13] ~~Deckro~~, R. F., & ~~Hebert~~, ~~J. E~~. (~~2003~~). ~~Modeling diminishing returns in project resource planning~~. ''~~Computers & industrial engineering~~'', ''44''~~(1)~~, 19-33.		[13] Pasandideh, S. H. R., Niaki, S. T. A., & Gharaei, A. (2015). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw ''Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming'']. ''Knowledge-Based Systems'', ''84'', 98-107.

	[14] ~~Bauer~~, L. (~~1970~~). A quadratic programming ~~algorithm for deriving efficient farm plans in a risk setting~~.		[14] Pyman, D. H. (2021). ''The risk-return trade-off to diversified agriculture in Malawi: A quadratic programming approach'' (Doctoral dissertation, Stellenbosch: Stellenbosch University).

	[15] ~~Migo-Sumagang~~, ~~M. V~~., ~~Tan~~, R~~. R., Tapia, J. F. D., & Aviso, K. B~~. (~~2022~~)~~. Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions~~. ''~~Cleaner Engineering and Technology~~''~~, ''9'', 100507.~~		[15] Ries, S., & Houtz, R. (1983). ''Triacontanol as a plant growth regulator.''

	[16] ~~Ries~~, S.~~, & Houtz, R~~. (~~1983~~). ~~Triacontanol as a plant growth regulator~~.		[16] Zenios, S. A. (Ed.). (1993). ''Financial optimization''. Cambridge university press,doi:https://doi.org/10.1017/CBO9780511522130

	==Further Reading==		==Further Reading==

Fall2024 Wiki Team2: /* Application 2. Production Planning with Diminishing Returns */

2024-12-15T04:29:55Z

Application 2. Production Planning with Diminishing Returns

← Older revision		Revision as of 00:29, 15 December 2024
Line 295:		Line 295:
	* The goal is to maximize the expected returns while minimizing risk by selecting crops with complementary risk profiles.		* The goal is to maximize the expected returns while minimizing risk by selecting crops with complementary risk profiles.

	===== (2) ~~Risk~~ =====		===== (2) Constraints =====
	A set of constraints is always included that reflect the available resources. For example:		A set of constraints is always included that reflect the available resources. For example:

Line 301:		Line 301:
	* Water, labor, or other resource limits: These could be modeled as linear constraints based on the crop's resource needs.		* Water, labor, or other resource limits: These could be modeled as linear constraints based on the crop's resource needs.
	* Non-negativity: <math>x_i \geq 0</math> for all crops <math>i_r</math> ensuring that no crop area is negative.		* Non-negativity: <math>x_i \geq 0</math> for all crops <math>i_r</math> ensuring that no crop area is negative.

	~~[[File:Law of Diminishing Returns.png\|thumb\|[https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Returns]]]~~

	=== Application 2. Production Planning with Diminishing Returns ===		=== Application 2. Production Planning with Diminishing Returns ===
Line 308:		Line 306:

	In many industries, the production process is characterized by an initial phase of increasing returns, followed by a phase of diminishing returns as production scales up. This can be due to factors such as limited machinery capacity, workforce inefficiencies, or increased costs associated with sourcing additional raw materials(Hall, Heady et al,1968). Quadratic programming helps model these non-linear cost increases by incorporating quadratic terms that reflect the rising marginal costs. This allows decision-makers to find the production level at which profit is maximized without overextending resources or incurring disproportionately high costs.		In many industries, the production process is characterized by an initial phase of increasing returns, followed by a phase of diminishing returns as production scales up. This can be due to factors such as limited machinery capacity, workforce inefficiencies, or increased costs associated with sourcing additional raw materials(Hall, Heady et al,1968). Quadratic programming helps model these non-linear cost increases by incorporating quadratic terms that reflect the rising marginal costs. This allows decision-makers to find the production level at which profit is maximized without overextending resources or incurring disproportionately high costs.

			==== Objective: ====
			The objective is to maximize profit, which is the difference between revenue and costs. A typical quadratic function for the cost might look like this:

			<math>\text { Maximize } Z=R(x)-C(x)=p \cdot x-\left(c_0+c_1 \cdot x+c_2 \cdot x^2\right)</math>

			* <math>\quad R(x)</math> is the revenue generated from producing x units of output (linear with respect to x ),<math>\quad C(x)</math> is the cost of producing $x$ units (quadratic, reflecting diminishing returns)
			* <math>\quad p</math> is the price per unit,<math>c_0</math> is the fixed cost (e.g., rent, utilities), <math>c_1</math>is the linear cost coefficient (e.g., cost of raw materials),<math>c_2</math>is the quadratic cost coefficient (the increasing marginal costs as output increases)
			* The term <math>c_2 \cdot x^2</math> models the diminishing returns: as production increases, costs rise faster due to factors like equipment inefficiencies, labor shortages, or higher input costs.

	For instance, a manufacturing company may experience economies of scale initially as production increases, leading to lower average costs per unit. However, beyond a certain point, the company might face increased costs due to equipment wear, higher labor requirements, or supply chain constraints. By using a quadratic cost function, QP can identify the optimal production point where the additional cost of producing one more unit starts to outweigh the benefit from additional revenue(Bauer,1970).		For instance, a manufacturing company may experience economies of scale initially as production increases, leading to lower average costs per unit. However, beyond a certain point, the company might face increased costs due to equipment wear, higher labor requirements, or supply chain constraints. By using a quadratic cost function, QP can identify the optimal production point where the additional cost of producing one more unit starts to outweigh the benefit from additional revenue(Bauer,1970).

	Quadratic programming also allows for the inclusion of various constraints that are common in production planning, such as resource availability, labor hours, and budget limits~~. This makes the solution more practical and applicable to real-world scenarios. By integrating these~~ constraints, the ~~model ensures~~ that ~~production plans are feasible and align with the company's operational capabilities(Migo-Sumagang~~, ~~Tan et al,2022)~~.		==== Constraints: ====
			[[File:Law of Diminishing Returns.png\|thumb\|[https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Returns]]]Quadratic programming also allows for the inclusion of various constraints that are common in production planning, such as resource availability, labor hours, and budget limits as follows:

			* Resource constraints: The total amount of available resources, such as labor hours, raw materials, or machine capacity:<math>\sum_i r_i \cdot x_i \leq R_{\text {available }}</math>
			* Budget limits: Total costs must not exceed a certain budget.<math>\sum_i c_i \cdot x_i \leq B_{\max }</math>
			* Production limits: There may be a maximum or minimum limit on the number of units that can be produced, either due to demand or capacity.

	Moreover, QP can be used to simulate different production scenarios, allowing companies to evaluate how changes in costs, resource availability, or market conditions might impact their optimal production strategy. This ability to adapt and reassess production plans in response to changing conditions is crucial for maintaining profitability in dynamic industries. The flexibility of QP enables businesses to stay responsive and make data-driven decisions that optimize both efficiency and profit.		This makes the solution more practical and applicable to real-world scenarios. By integrating these constraints, the model ensures that production plans are feasible and align with the company's operational capabilities(Migo-Sumagang, Tan et al,2022). Moreover, QP can be used to simulate different production scenarios, allowing companies to evaluate how changes in costs, resource availability, or market conditions might impact their optimal production strategy. This ability to adapt and reassess production plans in response to changing conditions is crucial for maintaining profitability in dynamic industries. The flexibility of QP enables businesses to stay responsive and make data-driven decisions that optimize both efficiency and profit.

	==Conclusion==		==Conclusion==
	In conclusion, Quadratically Constrained Quadratic Programs (QCQPs) are a significant class of optimization problems extending quadratic programming by incorporating quadratic constraints (Bao,Sahinidis,2011). These problems are essential for modeling complex real-world scenarios where both the objective function and the constraints are quadratic. QCQPs are widely applicable in areas such as agriculture, finance, production planning, and machine learning, where they help optimize decisions by balancing competing factors such as profitability, risk, and resource constraints.		In conclusion, Quadratically Constrained Quadratic Programs (QCQPs) are a significant class of optimization problems extending quadratic programming by incorporating quadratic constraints (Bao,Sahinidis,2011). These problems are essential for modeling complex real-world scenarios where both the objective function and the constraints are quadratic. QCQPs are widely applicable in areas such as agriculture, finance, production planning, and machine learning, where they help optimize decisions by balancing competing factors such as profitability, risk, and resource constraints.

	The study and solution of QCQPs are critical due to their ability to capture complex relationships and non-linearities, offering a more realistic representation of many practical problems than simpler linear models. Techniques such as ~~'''~~Karush-Kuhn Tucker (KKT) conditions and semidefinite programming (SDP) relaxations~~'''~~ provide effective tools for solving QCQPs(Elloumi & Lambert,2019), offering both exact and approximate solutions depending on the problem’s structure. These methods allow for efficient handling of the challenges posed by quadratic constraints and non-linearities.		The study and solution of QCQPs are critical due to their ability to capture complex relationships and non-linearities, offering a more realistic representation of many practical problems than simpler linear models. Techniques such as Karush-Kuhn Tucker (KKT) conditions and semidefinite programming (SDP) relaxations provide effective tools for solving QCQPs(Elloumi & Lambert,2019), offering both exact and approximate solutions depending on the problem’s structure. These methods allow for efficient handling of the challenges posed by quadratic constraints and non-linearities.

	Looking forward, there are several potential areas for improvement in QCQP algorithms. One direction is the development of more efficient relaxation techniques for solving non-convex QCQPs, especially in large-scale problems where computational efficiency becomes critical. Additionally, there is ongoing research into hybrid methods that combine the strengths of different optimization techniques, such as SDP and machine learning, to improve the robustness and speed of solving QCQPs in dynamic environments. As optimization problems become increasingly complex and data-rich, advancements in QCQP algorithms will continue to play a crucial role in making informed, optimal decisions in diverse applications.		Looking forward, there are several potential areas for improvement in QCQP algorithms. One direction is the development of more efficient relaxation techniques for solving non-convex QCQPs, especially in large-scale problems where computational efficiency becomes critical. Additionally, there is ongoing research into hybrid methods that combine the strengths of different optimization techniques, such as SDP and machine learning, to improve the robustness and speed of solving QCQPs in dynamic environments. As optimization problems become increasingly complex and data-rich, advancements in QCQP algorithms will continue to play a crucial role in making informed, optimal decisions in diverse applications.

Fall2024 Wiki Team2: /* Application 1. Agriculture (crop selection problem) */

2024-12-15T04:22:10Z

Application 1. Agriculture (crop selection problem)

@@ Line 275: / Line 275: @@
 In agriculture, quadratic programming plays an essential role in optimizing crop selection and resource allocation. Farmers often face a set of challenging decisions when determining which crops to plant and how to allocate limited resources such as land, water, and labor(McCarl,Moskowitz et el,1977). The decisions become even more complicated when accounting for uncertainties such as fluctuating crop prices, weather conditions, and yield variability. Quadratic programming provides a powerful framework for making these complex decisions more manageable.
-In a crop selection problem, [https://www.emerald.com/insight/content/doi/10.1108/03068290210419852/full/html?casa_token=SGYpSyJnQJAAAAAA:upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5-_pQeSndVNYw the goal is typically to maximize the expected profit while minimizing risks associated with different crops]. The risks can stem from fluctuating market prices, varying yields due to unpredictable weather conditions, and pests or diseases. Quadratic programming is particularly effective in modeling these kinds of problems because it can take into account both the expected returns and the covariances between different crops. By using a quadratic objective function, farmers can diversify their crop portfolio to reduce risk—much like how financial portfolio optimization works.
+==== Objective ====
-[https://onlinelibrary.wiley.com/doi/abs/10.2307/1238258?casa_token=4sxkbKbwLBwAAAAA%3ALXWbjj3TzWEtzJUtp0U6CUDI7xkyvfFeUh-YPI5yXB_gw3mWUIIJOvOI8NLHy4ghcqtubgkAZSUTUA Quadratic programming can helps to determine the optimal proportion of each crop to plant], balancing the trade-off between profitability and risk(Pyman,2021). The solution will often suggest a diversified planting strategy that minimizes the overall risk of the farm's production. By including the covariance matrix of crop yields or prices, the quadratic model captures the relationships between crops. For instance, if corn and soybeans tend to have negatively correlated yields due to different water requirements, planting both crops can help mitigate the overall risk. This type of analysis allows farmers to make informed decisions that are not solely based on maximizing immediate profits but also on minimizing the potential downside in adverse scenarios (Hossain, Hashim et al,2002). Quadratic programming can also incorporate constraints such as available land, labor availability, crop rotation requirements, and water usage limits, making the solution more practical and aligned with real-world farming conditions.
+For example, mathematically, the objective could look something like: <math>\operatorname{Maximize} Z=\sum_i p_i x_i-\frac{1}{2} \sum_{i, j} \rho_{i j} x_i x_j</math>.
 Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions. As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.
 [[File:Law of Diminishing Returns.png|thumb|[https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Returns]]]

Fall2024 Wiki Team2: /* Application */

2024-12-15T04:00:56Z

Application

← Older revision		Revision as of 00:00, 15 December 2024
Line 272:		Line 272:

	=== Application 1. Agriculture (crop selection problem) ===		=== Application 1. Agriculture (crop selection problem) ===
	In agriculture, quadratic programming plays an essential role in optimizing crop selection and resource allocation. Farmers often face a set of challenging decisions when determining which crops to plant and how to allocate limited resources such as land, water, and labor. The decisions become even more complicated when accounting for uncertainties such as fluctuating crop prices, weather conditions, and yield variability. Quadratic programming provides a powerful framework for making these complex decisions more manageable.		[[File:The quadratic yield response of crops to TRIA in the field.png\|thumb\|The [https://www.researchgate.net/figure/The-quadratic-yield-response-of-crops-to-TRIA-in-the-field-Potatoes-were-grown-at-Stan_fig1_284807130 quadratic yield response] of crops to TRIA in the field (Ries& Houtz, 1983)]]
			In agriculture, quadratic programming plays an essential role in optimizing crop selection and resource allocation. Farmers often face a set of challenging decisions when determining which crops to plant and how to allocate limited resources such as land, water, and labor(McCarl,Moskowitz et el,1977). The decisions become even more complicated when accounting for uncertainties such as fluctuating crop prices, weather conditions, and yield variability. Quadratic programming provides a powerful framework for making these complex decisions more manageable.

	In a crop selection problem, [https://www.emerald.com/insight/content/doi/10.1108/03068290210419852/full/html?casa_token=SGYpSyJnQJAAAAAA:upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5-_pQeSndVNYw the goal is typically to maximize the expected profit while minimizing risks associated with different crops]. The risks can stem from fluctuating market prices, varying yields due to unpredictable weather conditions, and pests or diseases. Quadratic programming is particularly effective in modeling these kinds of problems because it can take into account both the expected returns and the covariances between different crops. By using a quadratic objective function, farmers can diversify their crop portfolio to reduce risk—much like how financial portfolio optimization works.		In a crop selection problem, [https://www.emerald.com/insight/content/doi/10.1108/03068290210419852/full/html?casa_token=SGYpSyJnQJAAAAAA:upunXwWtsTu1SxBTjLDO7olLjRsF7_GooRy26mSifea9qb33QSreKuYaJfTEQy5aHebBCU5alqRnWVsB5aR8_wkATa3pEsGy0U9q_n5-_pQeSndVNYw the goal is typically to maximize the expected profit while minimizing risks associated with different crops]. The risks can stem from fluctuating market prices, varying yields due to unpredictable weather conditions, and pests or diseases. Quadratic programming is particularly effective in modeling these kinds of problems because it can take into account both the expected returns and the covariances between different crops. By using a quadratic objective function, farmers can diversify their crop portfolio to reduce risk—much like how financial portfolio optimization works.

	[https://onlinelibrary.wiley.com/doi/abs/10.2307/1238258?casa_token=4sxkbKbwLBwAAAAA%3ALXWbjj3TzWEtzJUtp0U6CUDI7xkyvfFeUh-YPI5yXB_gw3mWUIIJOvOI8NLHy4ghcqtubgkAZSUTUA Quadratic programming can helps to determine the optimal proportion of each crop to plant], balancing the trade-off between profitability and risk. The solution will often suggest a diversified planting strategy that minimizes the overall risk of the farm's production. By including the covariance matrix of crop yields or prices, the quadratic model captures the relationships between crops. For instance, if corn and soybeans tend to have negatively correlated yields due to different water requirements, planting both crops can help mitigate the overall risk. This type of analysis allows farmers to make informed decisions that are not solely based on maximizing immediate profits but also on minimizing the potential downside in adverse scenarios. Quadratic programming can also incorporate constraints such as available land, labor availability, crop rotation requirements, and water usage limits, making the solution more practical and aligned with real-world farming conditions.		[https://onlinelibrary.wiley.com/doi/abs/10.2307/1238258?casa_token=4sxkbKbwLBwAAAAA%3ALXWbjj3TzWEtzJUtp0U6CUDI7xkyvfFeUh-YPI5yXB_gw3mWUIIJOvOI8NLHy4ghcqtubgkAZSUTUA Quadratic programming can helps to determine the optimal proportion of each crop to plant], balancing the trade-off between profitability and risk(Pyman,2021). The solution will often suggest a diversified planting strategy that minimizes the overall risk of the farm's production. By including the covariance matrix of crop yields or prices, the quadratic model captures the relationships between crops. For instance, if corn and soybeans tend to have negatively correlated yields due to different water requirements, planting both crops can help mitigate the overall risk. This type of analysis allows farmers to make informed decisions that are not solely based on maximizing immediate profits but also on minimizing the potential downside in adverse scenarios (Hossain, Hashim et al,2002). Quadratic programming can also incorporate constraints such as available land, labor availability, crop rotation requirements, and water usage limits, making the solution more practical and aligned with real-world farming conditions.

	Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions. As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.		Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions. As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.
			[[File:Law of Diminishing Returns.png\|thumb\|[https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Returns]]]

	=== Application 2. Production Planning with Diminishing Returns ===		=== Application 2. Production Planning with Diminishing Returns ===
	[https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Production planning is another area where Quadratic Programming (QP) has significant applications]. The objective is to maximize profit while considering increasing production costs as output scales up. By modeling the cost as a quadratic function of production volume, QP provides a realistic way to determine optimal production levels, ensuring that diminishing returns are properly accounted for.		[https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Production planning is another area where Quadratic Programming (QP) has significant applications]. The objective is to maximize profit while considering increasing production costs as output scales up(Deckro & Hebert,2003). By modeling the cost as a quadratic function of production volume, QP provides a realistic way to determine optimal production levels, ensuring that diminishing returns are properly accounted for.

	In many industries, the production process is characterized by an initial phase of increasing returns, followed by a phase of diminishing returns as production scales up. This can be due to factors such as limited machinery capacity, workforce inefficiencies, or increased costs associated with sourcing additional raw materials. Quadratic programming helps model these non-linear cost increases by incorporating quadratic terms that reflect the rising marginal costs. This allows decision-makers to find the production level at which profit is maximized without overextending resources or incurring disproportionately high costs.		In many industries, the production process is characterized by an initial phase of increasing returns, followed by a phase of diminishing returns as production scales up. This can be due to factors such as limited machinery capacity, workforce inefficiencies, or increased costs associated with sourcing additional raw materials(Hall, Heady et al,1968). Quadratic programming helps model these non-linear cost increases by incorporating quadratic terms that reflect the rising marginal costs. This allows decision-makers to find the production level at which profit is maximized without overextending resources or incurring disproportionately high costs.

	For instance, a manufacturing company may experience economies of scale initially as production increases, leading to lower average costs per unit. However, beyond a certain point, the company might face increased costs due to equipment wear, higher labor requirements, or supply chain constraints. By using a quadratic cost function, QP can identify the optimal production point where the additional cost of producing one more unit starts to outweigh the benefit from additional revenue.		For instance, a manufacturing company may experience economies of scale initially as production increases, leading to lower average costs per unit. However, beyond a certain point, the company might face increased costs due to equipment wear, higher labor requirements, or supply chain constraints. By using a quadratic cost function, QP can identify the optimal production point where the additional cost of producing one more unit starts to outweigh the benefit from additional revenue(Bauer,1970).

	Quadratic programming also allows for the inclusion of various constraints that are common in production planning, such as resource availability, labor hours, and budget limits. This makes the solution more practical and applicable to real-world scenarios. By integrating these constraints, the model ensures that production plans are feasible and align with the company's operational capabilities.		Quadratic programming also allows for the inclusion of various constraints that are common in production planning, such as resource availability, labor hours, and budget limits. This makes the solution more practical and applicable to real-world scenarios. By integrating these constraints, the model ensures that production plans are feasible and align with the company's operational capabilities(Migo-Sumagang, Tan et al,2022).

	Moreover, QP can be used to simulate different production scenarios, allowing companies to evaluate how changes in costs, resource availability, or market conditions might impact their optimal production strategy. This ability to adapt and reassess production plans in response to changing conditions is crucial for maintaining profitability in dynamic industries. The flexibility of QP enables businesses to stay responsive and make data-driven decisions that optimize both efficiency and profit.		Moreover, QP can be used to simulate different production scenarios, allowing companies to evaluate how changes in costs, resource availability, or market conditions might impact their optimal production strategy. This ability to adapt and reassess production plans in response to changing conditions is crucial for maintaining profitability in dynamic industries. The flexibility of QP enables businesses to stay responsive and make data-driven decisions that optimize both efficiency and profit.
Line 319:		Line 321:

	[11] Pasandideh, S. H. R., Niaki, S. T. A., & Gharaei, A. (2015). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming]. ''Knowledge-Based Systems'', ''84'', 98-107.		[11] Pasandideh, S. H. R., Niaki, S. T. A., & Gharaei, A. (2015). [https://www.sciencedirect.com/science/article/pii/S0950705115001392?casa_token=Lh5Tecyr5lcAAAAA:3RM90Wt83hMwaBFbTZRjDeXVHPwicHfp4jpFEvmXeeAQxvO1CXdp6uXu7hYulktZwV5q1kmofw Optimization of a multiproduct economic production quantity problem with stochastic constraints using sequential quadratic programming]. ''Knowledge-Based Systems'', ''84'', 98-107.

			[12] Pyman, D. H. (2021). ''The risk-return trade-off to diversified agriculture in Malawi: A quadratic programming approach'' (Doctoral dissertation, Stellenbosch: Stellenbosch University).

			[13] Deckro, R. F., & Hebert, J. E. (2003). Modeling diminishing returns in project resource planning. ''Computers & industrial engineering'', ''44''(1), 19-33.

			[14] Bauer, L. (1970). A quadratic programming algorithm for deriving efficient farm plans in a risk setting.

			[15] Migo-Sumagang, M. V., Tan, R. R., Tapia, J. F. D., & Aviso, K. B. (2022). Fuzzy mixed-integer linear and quadratic programming models for planning negative emissions technologies portfolios with synergistic interactions. ''Cleaner Engineering and Technology'', ''9'', 100507.

			[16] Ries, S., & Houtz, R. (1983). Triacontanol as a plant growth regulator.

	==Further Reading==		==Further Reading==
Line 338:		Line 350:
	* [[wikipedia:Software-defined_perimeter\|Software-defined perimeter]]		* [[wikipedia:Software-defined_perimeter\|Software-defined perimeter]]
	* [[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically constrained quadratic program]]		* [[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically constrained quadratic program]]
			* [https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Rules]
	* [https://link.springer.com/article/10.1007/s10107-020-01589-9 Semidefinite Programming]		* [https://link.springer.com/article/10.1007/s10107-020-01589-9 Semidefinite Programming]
	* [https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]		* [https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]
			* [https://www.researchgate.net/figure/The-quadratic-yield-response-of-crops-to-TRIA-in-the-field-Potatoes-were-grown-at-Stan_fig1_284807130 Quatratic Programming on Agriculture (crop selection problem)]
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+

← Older revision		Revision as of 00:46, 15 December 2024
Line 59:		Line 59:
	\|}		\|}
	[[File:Semidefinite Programming.jpg\|thumb\|[https://i.ytimg.com/vi/Sm0IUpxBHNs/maxresdefault.jpg Semidefinite Programming]<ref>Cited in the External Link</ref>]]		[[File:Semidefinite Programming.jpg\|thumb\|[https://i.ytimg.com/vi/Sm0IUpxBHNs/maxresdefault.jpg Semidefinite Programming]<ref>Cited in the External Link</ref>]]
	Other relaxations, such as '''Second-Order Cone Programming (SOCP)''', are exact for specific problem classes like QCQPs with zero diagonal elements in the data matrices. These relaxations often produce the same objective value as SDP relaxations. Moreover, it has been shown that for a class of random QCQPs, SDP relaxations are exact with high probability if the number of constraints grows at a controlled polynomial rate relative to the number of variables.~~[2]~~		Other relaxations, such as '''Second-Order Cone Programming (SOCP)''', are exact for specific problem classes like QCQPs with zero diagonal elements in the data matrices. These relaxations often produce the same objective value as SDP relaxations(Best,Kale,2000). Moreover, it has been shown that for a class of random QCQPs, SDP relaxations are exact with high probability if the number of constraints grows at a controlled polynomial rate relative to the number of variables.

	For non-convex QCQPs, SDP or SOCP relaxations can still provide exact solutions under specific conditions, such as non-positive off-diagonal elements. Additionally, polynomial-time-checkable sufficient conditions exist for SDP relaxations to exactly solve general QCQPs. Randomized QCQPs often exhibit exact semidefinite relaxations as the number of variables and constraints increases proportionally.		For non-convex QCQPs, SDP or SOCP relaxations can still provide exact solutions under specific conditions, such as non-positive off-diagonal elements. Additionally, polynomial-time-checkable sufficient conditions exist for SDP relaxations to exactly solve general QCQPs. Randomized QCQPs often exhibit exact semidefinite relaxations as the number of variables and constraints increases proportionally (Bertsima,Darnell et al,1999).

	== Numerical Example ==		== Numerical Example ==
Line 81:		Line 81:

	==== 1. 1 Lagrangian Formulation: ====		==== 1. 1 Lagrangian Formulation: ====
	The '''Lagrangian formulation''' in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the '''Lagrangian <math>L</math>''' This formulation introduces '''Lagrange multipliers''' <math>\lambda_i</math>for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows:		The '''Lagrangian formulation''' in optimization is a mathematical framework used to solve constrained optimization problems by incorporating both the objective function and the constraints into a single scalar function, called the '''Lagrangian <math>L</math>''' This formulation introduces '''Lagrange multipliers''' <math>\lambda_i</math>for each constraint, enabling the transformation of a constrained optimization problem into an unconstrained one as follows (Pasandideh, Niaki et al,2015):

	<math>L(x, \lambda, \nu)=f_0(x)+\sum_{i=1}^m \lambda_i f_i(x)+\nu^T(A x-b)</math>		<math>L(x, \lambda, \nu)=f_0(x)+\sum_{i=1}^m \lambda_i f_i(x)+\nu^T(A x-b)</math>
Line 287:		Line 287:
	Quadratic programming is particularly effective in modeling these kinds of problems because it can take into account both the expected returns and the covariances between different crops. By using a quadratic objective function, farmers can diversify their crop portfolio to reduce risk—much like how financial portfolio optimization works.This type of analysis allows farmers to make informed decisions that are not solely based on maximizing immediate profits but also on minimizing the potential downside in adverse scenarios (Hossain, Hashim et al,2002). Quadratic programming can also incorporate constraints such as available land, labor availability, crop rotation requirements, and water usage limits, making the solution more practical and aligned with real-world farming conditions.		Quadratic programming is particularly effective in modeling these kinds of problems because it can take into account both the expected returns and the covariances between different crops. By using a quadratic objective function, farmers can diversify their crop portfolio to reduce risk—much like how financial portfolio optimization works.This type of analysis allows farmers to make informed decisions that are not solely based on maximizing immediate profits but also on minimizing the potential downside in adverse scenarios (Hossain, Hashim et al,2002). Quadratic programming can also incorporate constraints such as available land, labor availability, crop rotation requirements, and water usage limits, making the solution more practical and aligned with real-world farming conditions.

	Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions. As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.		Another advantage of using quadratic programming in crop selection is its ability to adapt to changing conditions (Pyman, 2021). As new information becomes available—such as updated weather forecasts, market trends, or pest outbreak data—the model can be recalibrated to provide an updated optimal planting strategy. This flexibility is crucial in agriculture, where conditions can change rapidly and have a significant impact on outcomes.

	===== (1) Risk =====		===== (1) Risk =====
Line 370:		Line 370:

	* [1] Floudas, C. A., & Visweswaran, V. (1995). [https://link.springer.com/chapter/10.1007/978-1-4615-2025-2_5 Quadratic optimization. ''Handbook of global optimization''] ''(PDF)'', 217-269.		* [1] Floudas, C. A., & Visweswaran, V. (1995). [https://link.springer.com/chapter/10.1007/978-1-4615-2025-2_5 Quadratic optimization. ''Handbook of global optimization''] ''(PDF)'', 217-269.
	* [2] Xu, H. K. (2003). [https://link.springer.com/article/10.1023/A:1023073621589 An iterative approach to quadratic optimization. ''Journal of Optimization Theory and Applications'']''(PDF)'', ''116'', 659-678.		* [2] [https://link.springer.com/article/10.1007/s10462-022-10273-7 Gunjan, A., & Bhattacharyya, S. (2023). A brief review of portfolio optimization techniques](PDF). ''Artificial Intelligence Review'', ''56''(5), 3847-3886,doi: https://doi.org/10.1007/s10462-022-10273-7
			* [3] Xu, H. K. (2003). [https://link.springer.com/article/10.1023/A:1023073621589 An iterative approach to quadratic optimization. ''Journal of Optimization Theory and Applications'']''(PDF)'', ''116'', 659-678.

	In Finance Portfolio Construction:		In Finance Portfolio Construction:

	* [1] [https://~~link~~.~~springer~~.~~com~~/~~article~~/~~10.1007/s10462~~-~~022~~-~~10273-7 Gunjan, A., & Bhattacharyya, S. (2023). A brief review of~~ portfolio optimization ~~techniques~~]~~(PDF)~~. ''~~Artificial Intelligence Review'', ''56~~''(5), ~~3847-3886~~,~~doi:~~ https://~~doi~~.~~org~~/10.~~1007/s10462~~-~~022-10273-7~~		* [1] Best, M. J., & Kale, J. K. (2000). [https://www.researchgate.net/publication/238301843_Quadratic_Programming_for_Large-Scale_Portfolio_Optimization Quadratic programming for large-scale portfolio optimization]. In ''Financial Services Information Systems'' (pp. 531-548). Auerbach Publications.
	* [2] ~~Xu, H. K.~~ (~~2003~~)~~. An iterative approach to quadratic optimization~~. ''~~Journal of Optimization Theory and Applications~~'', ''~~116~~'', ~~659~~-~~678~~.		* [2] Bertsimas, D., Darnell, C., & Soucy, R. (1999). [https://www.mit.edu/~dbertsim/papers/Finance/Portfolio%20construction%20through%20mixed%20integer%20programming.pdf Portfolio construction through mixed-integer programming at Grantham](pdf), Mayo, Van Otterloo and Company. ''Interfaces'', ''29''(1), 49-66.

	==External Links==		==External Links==

	* [[wikipedia:Convex_function\|Convext Quatratic Function]]		* [[wikipedia:Convex_function\|Convext Quatratic Function]]
			* [[wikipedia:Karush–Kuhn–Tucker_conditions\|Karush–Kuhn–Tucker conditions]]
	* [[wikipedia:Lagrangian_mechanics\|Lagrangian mechanics]]		* [[wikipedia:Lagrangian_mechanics\|Lagrangian mechanics]]
	* [~~[wikipedia~~:~~Karush–Kuhn–Tucker_conditions\|Karush–Kuhn–Tucker conditions]]~~		* [https://utw11041.utweb.utexas.edu/ORMM/supplements/methods/nlpmethod/S2_quadratic.pdf Law of Diminishing Rules]
	* [[wikipedia:Software-defined_perimeter\|Software-defined perimeter]]
	* [[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically constrained quadratic program]]		* [[wikipedia:Quadratically_constrained_quadratic_program\|Quadratically constrained quadratic program]]
	* [https://~~utw11041~~.~~utweb~~.~~utexas.edu~~/~~ORMM~~/~~supplements/methods/nlpmethod/S2_quadratic.pdf Law~~ of ~~Diminishing Rules~~]		* [https://www.researchgate.net/figure/The-quadratic-yield-response-of-crops-to-TRIA-in-the-field-Potatoes-were-grown-at-Stan_fig1_284807130 Quatratic Programming on Agriculture (crop selection problem)]
	* [https://link.springer.com/article/10.1007/s10107-020-01589-9 Semidefinite Programming]		* [https://link.springer.com/article/10.1007/s10107-020-01589-9 Semidefinite Programming]
	* [https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]		* [https://nag.com/solving-quadratically-constrained-quadratic-programming-qcqp-problems/ Solving quadratically constrained quadratic programming (QCQP) problems]
	* [~~https~~:~~//www.researchgate.net/figure/The~~-~~quadratic~~-~~yield-response-of-crops-to-TRIA-in-the-field-Potatoes-were-grown-at-Stan_fig1_284807130 Quatratic Programming on Agriculture (crop selection problem)~~]		* [[wikipedia:Software-defined_perimeter\|Software-defined perimeter]]
	{\| class="wikitable"		{\| class="wikitable"
	\|+		\|+