Quadratic programming - Revision history

Fall2024 Wiki Team10: /* Step 3: Determine the Feasible Region */

2024-12-16T03:14:12Z

Step 3: Determine the Feasible Region

← Older revision		Revision as of 23:14, 15 December 2024
Line 409:		Line 409:
	** <math> x_1 = 3 </math>		** <math> x_1 = 3 </math>
	** Substitute <math> x_1 = 3 </math> into the first equation		** Substitute <math> x_1 = 3 </math> into the first equation
	*** <math> 3 + x_2 = 5 </math>		** <math> 3 + x_2 = 5 </math>
	*** <math> x_2 = 2 </math>		** <math> x_2 = 2 </math>
	*** Interesection at (3,2)		** Interesection at (3,2)

	The feasible region is bounded & convex in the intersection points (0,5), (0,8), (5,0), (4,0), (3,2).		The feasible region is bounded & convex in the intersection points (0,5), (0,8), (5,0), (4,0), (3,2).

Fall2024 Wiki Team10: /* Step 3: Determine the Feasible Region */

2024-12-16T03:13:31Z

Step 3: Determine the Feasible Region

← Older revision		Revision as of 23:13, 15 December 2024
Line 408:		Line 408:
	** <math>2x_1 + x_2 - x_1 + x_2 = 8 - 5 </math>		** <math>2x_1 + x_2 - x_1 + x_2 = 8 - 5 </math>
	** <math> x_1 = 3 </math>		** <math> x_1 = 3 </math>
	* Substitute <math> x_1 = 3 </math> into the first equation		** Substitute <math> x_1 = 3 </math> into the first equation
	** <math> 3 + x_2 = 5 </math>		*** <math> 3 + x_2 = 5 </math>
	** <math> x_2 = 2 </math>		*** <math> x_2 = 2 </math>
	** Interesection at (3,2)		*** Interesection at (3,2)

	The feasible region is bounded & convex in the intersection points (0,5), (0,8), (5,0), (4,0), (3,2).		The feasible region is bounded & convex in the intersection points (0,5), (0,8), (5,0), (4,0), (3,2).

Fall2024 Wiki Team10: /* Step 3: Determine the Feasible Region */

2024-12-16T03:12:07Z

Step 3: Determine the Feasible Region

← Older revision		Revision as of 23:12, 15 December 2024
Line 386:		Line 386:
	Change the inequalities to equalities.		Change the inequalities to equalities.
	# <math>x_1 + x_2 = 5</math>		# <math>x_1 + x_2 = 5</math>
	# <math>~~2x_2~~ + x_2 = 8</math>		# <math>2x_1 + x_2 = 8</math>
	# <math>x_1 = 0</math>		# <math>x_1 = 0</math>
	# <math>x_2 = 0</math>		# <math>x_2 = 0</math>

Fall2024 Wiki Team10: /* Step 2.2 Determine if the Constraints are Convex */

2024-12-16T03:11:26Z

Step 2.2 Determine if the Constraints are Convex

← Older revision		Revision as of 23:11, 15 December 2024
Line 377:		Line 377:
	==== Step 2.2 Determine if the Constraints are Convex ====		==== Step 2.2 Determine if the Constraints are Convex ====
	# <math>x_1 + x_2 \leq5</math>		# <math>x_1 + x_2 \leq5</math>
	# <math>~~2x_2~~ + x_2 \leq8</math>		# <math>2x_1 + x_2 \leq8</math>
	# <math>x_1 \geq0</math>		# <math>x_1 \geq0</math>
	# <math>x_2 \geq0</math>		# <math>x_2 \geq0</math>

Fall2024 Wiki Team10: /* Conclusion */

2024-12-16T01:26:14Z

Conclusion

← Older revision		Revision as of 21:26, 15 December 2024
Line 734:		Line 734:

	=Conclusion=		=Conclusion=
	Quadratic programming ~~and its ability to optimize quadratic functions~~ is a vastly useful ~~tool~~ for solving real-world problems which are often depicted as quadratic functions. For this reason, QP ~~has been~~ used ~~to model a variety of problems~~ from signal processing to game theory to economics. As one of the simplest non-linear programming types, QP can be used to ~~both~~ solve quadratic functions with linear bounds, made especially straightforward with a convex objective function~~, and~~ can be used as a ~~step in~~ more complicated optimization problems such as sequential quadratic programming. ~~Though only~~ first theorized in the 1950s, QP application has broadened to ~~many~~ fields including finance, scheduling, and engineering modeling.		Quadratic programming is vastly useful as a method for solving real-world problems which are often depicted as quadratic functions. For this reason, to this day QP is used in many fields from signal processing to game theory to economics. As one of the simplest non-linear programming types, QP is versatile in its use and application. QP can be used to solve quadratic functions with linear bounds, made especially straightforward with a convex objective function. QP can also be used as a stepping stone to simplify more complicated optimization problems such as in the case of sequential quadratic programming. Having first been theorized in the 1950s, QP has a deep history and its study and application has broadened over the years to reach a myriad of fields including finance, scheduling, planning, flow computations, and engineering modeling.

	=References=		=References=

Fall2024 Wiki Team10: /* Plug in Hybrid Electric Vehicle Power Management */

2024-12-12T01:35:29Z

Plug in Hybrid Electric Vehicle Power Management

← Older revision		Revision as of 21:35, 11 December 2024
Line 710:		Line 710:

	==Plug in Hybrid Electric Vehicle Power Management==		==Plug in Hybrid Electric Vehicle Power Management==
	Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands. .<sup>15</sup>		Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands.<sup>15</sup>

Fall2024 Wiki Team10 at 04:02, 11 December 2024

2024-12-11T04:02:21Z

← Older revision		Revision as of 00:02, 11 December 2024
Line 350:		Line 350:

	<math>{\partial f\over\partial x_1}= \frac{1}{2} \times 2x_1 + 2 = x_1 + 2</math>		<math>{\partial f\over\partial x_1}= \frac{1}{2} \times 2x_1 + 2 = x_1 + 2</math>

			<math>{\partial f\over\partial x_2}= \frac{1}{2} \times 2 \times 3x_2 + 6 = 3x_2 + 6</math>

	Solve for the second order partial derivatives.		Solve for the second order partial derivatives.
Line 708:		Line 710:

	==Plug in Hybrid Electric Vehicle Power Management==		==Plug in Hybrid Electric Vehicle Power Management==
	Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands.<sup>15</sup>		Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands. .<sup>15</sup>

Fall2024 Wiki Team10: /* Plug in Hybrid Electric Vehicle Power Management */

2024-12-11T04:01:26Z

Plug in Hybrid Electric Vehicle Power Management

← Older revision		Revision as of 00:01, 11 December 2024
Line 708:		Line 708:

	==Plug in Hybrid Electric Vehicle Power Management==		==Plug in Hybrid Electric Vehicle Power Management==
	Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands. .<sup>15</sup>		Plug-in hybrid electric vehicles (PHEVs) rely on having an optimized power management program to operate efficiently. PHEVs will draw power from batteries until they are depleted before switching to its hybrid combustion-ev power cycle. The goal for PHEVs becomes a quadratic programming problem where the objective is to minimize a quadratic function associated with costs for fuel which will optimize the power cycles and meet performance demands.<sup>15</sup>

Fall2024 Wiki Team10: /* Finance-Portfolio Optimization */

2024-12-11T03:58:43Z

Finance-Portfolio Optimization

← Older revision		Revision as of 23:58, 10 December 2024
Line 695:		Line 695:

	== Finance-Portfolio Optimization ==		== Finance-Portfolio Optimization ==
	In finance, quadratic programming is commonly used when formulating an investment portfolio that balances returns and risk to meet the investor's goal. Nobel Prize recipient Harry Markowitz developed a portfolio model using quadratic programming to maximize returns while minimizing risks, a model that would later become a cornerstone in Modern Portfolio Theory.<sup>10</sup> Markowitz defined risk as a variance of the portfolio’s return, which captures an essence of a portfolio’s symmetric return volatility. Markowitz's method involved estimating stock returns based on historical data, analyzing variances from historical projections and its realized returns to formulate risk. When provided a budget and risk tolerance, the model would now be able to select a combination of stocks that would maximize returns within the defined constraints. Markowitz further constrained the portfolio model to not include short selling of stock making this a convex quadratic programming problem. Complications to Markowitz's model arise when short selling stocks are considered. When a portfolio short sells a stock, the portfolio essentially takes a negative position on the asset, altering the objective function to include negative returns. A short selling stock portfolio would be an example of a non-convex quadratic programming problem. <sup>10,11</sup>		In finance, quadratic programming is commonly used when formulating an investment portfolio that balances returns and risk to meet the investor's goal. Nobel Prize recipient Harry Markowitz developed a portfolio model using quadratic programming to maximize returns while minimizing risks, a model that would later become a cornerstone in Modern Portfolio Theory.<sup>10</sup> Markowitz defined risk as a variance of the portfolio’s return, which captures an essence of a portfolio’s symmetric return volatility. Markowitz's method involved estimating stock returns based on historical data, analyzing variances from historical projections and its realized returns to formulate risk. When provided a budget and risk tolerance, the model would now be able to select a combination of stocks that would maximize returns within the defined constraints. Markowitz further constrained the portfolio model to not include short selling of stock, making this a convex quadratic programming problem. Complications to Markowitz's model arise when short selling stocks are considered. When a portfolio short sells a stock, the portfolio essentially takes a negative position on the asset, altering the objective function to include negative returns. A short selling stock portfolio would be an example of a non-convex quadratic programming problem. <sup>10,11</sup>

	==Quadratic Knapsack Problem (QKP)==		==Quadratic Knapsack Problem (QKP)==

Fall2024 Wiki Team10 at 03:19, 11 December 2024

2024-12-11T03:19:43Z

← Older revision		Revision as of 23:19, 10 December 2024
Line 82:		Line 82:


	~~<code>~~ Compute a feasible starting point <math>x_0</math>;		Compute a feasible starting point <math>x_0</math>;

	Set <math>W_0</math> to be a subset of the active constraints at <math>x_0</math>;		Set <math>W_0</math> to be a subset of the active constraints at <math>x_0</math>;

	for <math>k=0,1,2...</math>		for <math>k=0,1,2...</math>
			: Solve for <math>p_k=\frac{1}{2}x_k^TGx_k+c^Tx_k</math>
	Solve for <math>p_k=\frac{1}{2}x_k^TGx_k+c^Tx_k</math>		: '''if''' <math>p_k=0</math>
			:: Compute Lagrange multipliers <math>\hat{\lambda}_i</math> that satisfy <math>\Sigma_{i\epsilon\hat{W}}a_i\hat{\lambda}_i=g=G\hat{x}+c,</math> with <math>\hat{W}=W_k</math>
	'''if''' <math>p_k=0</math>		:: '''if''' <math>\hat{\lambda}_i\geq0</math> for all <math>i \in W_k \cap \jmath </math>
			::: '''stop''' with solution <math>x^*=x_k; </math>
	Compute Lagrange multipliers <math>\hat{\lambda}_i</math> that satisfy <math>\Sigma_{i\epsilon\hat{W}}a_i\hat{\lambda}_i=g=G\hat{x}+c,</math>		:: '''else'''
			::: <math>j \longleftarrow </math> arg <math>min_{i \in W_k \cap \jmath} \hat{\lambda}_j;</math>
	with <math>\hat{W}=W_k</math>		::: <math>x_{k+1} \longleftarrow x_k; W_{k+1} \longleftarrow W_k \ \{j\}; </math>
			: '''Else''' <math>(p_k \neq 0) </math>
	'''if''' <math>\hat{\lambda}_i\geq0</math> for all <math>i \in W_k \cap \jmath </math>		:: Compute <math>a_k = min (1, min(\frac{b_i-a_i^Tx_k}{a_i^Tp_k})) </math>
			:: <math>x_{k+1} \longleftarrow x_k + a_kp_k; </math>
	'''stop''' with solution <math>x^*=x_k; </math>		:: '''if''' there are blocking constraints:
			::: obtain <math>W_{k+1} </math> by adding one of the blocking constraints to <math>W_k; </math>
	'''else'''		:: '''else'''
			::: <math>W_{k+1}\longleftarrow W_k; </math>
	<math>j \longleftarrow </math> arg <math>min_{i \in W_k \cap \jmath} \hat{\lambda}_j; </math>		'''end (for)'''

	<math>x_{k+1} \longleftarrow x_k; W_{k+1} \longleftarrow W_k \ \{j\}; </math>

	'''Else''' <math>(p_k \neq 0) </math>

	Compute <math>a_k = min (1, min(\frac{b_i-a_i^Tx_k}{a_i^Tp_k})) </math>

	<math>x_{k+1} \longleftarrow x_k + a_kp_k; </math>

	'''if''' there are blocking constraints:

	obtain <math>W_{k+1} </math> by adding one of the blocking constraints to <math>W_k; </math>

	'''else'''

	<math>W_{k+1}\longleftarrow W_k; </math>

	'''end (for)''' ~~</code>~~

	==Interior Point Methods==		==Interior Point Methods==
Line 161:		Line 141:

	'''repeat''' until a stopping test for the nonlinear program is satisfied.		'''repeat''' until a stopping test for the nonlinear program is satisfied.
			: '''repeat''' unitl <math>E(x_k, s_k, y_k, z_k; \mu_k) \leq \mu_k</math>
	'''repeat''' unitl <math>E(x_k, s_k, y_k, z_k; \mu_k) \leq \mu_k</math>		: Solve <math>\begin{bmatrix} \bigtriangledown_{xx}^2 L & 0 & -A_E^T(x) & -A_i^T(x) \\ 0 & Z & 0 & S \\ A_E(x) & 0 & 0 & 0 \\ A_i(x) & -I & 0 & 0 \end{bmatrix}</math><math>\begin{bmatrix} p_x \\ p_s \\ p_y \\ p_z \end{bmatrix}</math><math>=-\begin{bmatrix} \bigtriangledown f(x) - A_E^T (x) y - A_i^T(x)z \\ Sz-\mu e \\ c_E(x) \\ c_i(x) - s \end{bmatrix}</math>to obtain the search direction <math>p=(p_x, p_s, p_y, p_z);</math>
			:: Compute <math>\alpha_s^{max}, \alpha_z^{Max}</math> using:
	Solve <math>\begin{bmatrix} \bigtriangledown_{xx}^2 L & 0 & -A_E^T(x) & -A_i^T(x) \\ 0 & Z & 0 & S \\ A_E(x) & 0 & 0 & 0 \\ A_i(x) & -I & 0 & 0 \end{bmatrix}</math><math>\begin{bmatrix} p_x \\ p_s \\ p_y \\ p_z \end{bmatrix}</math><math>=-\begin{bmatrix} \bigtriangledown f(x) - A_E^T (x) y - A_i^T(x)z \\ Sz-\mu e \\ c_E(x) \\ c_i(x) - s \end{bmatrix}</math>to obtain the search direction <math>p=(p_x, p_s, p_y, p_z);</math>		::: <math>\alpha_s^{max} = max \{ \alpha \in (0,1): s + \alpha p_s \geq (1- \tau) s</math>
			::: <math>\alpha_z^{max} = max \{ \alpha \in (0,1): z + \alpha p_s \geq (1- \tau) z</math>
	Compute <math>\alpha_s^{max}, \alpha_z^{Max}</math> using:		:: Compute <math>(x_{k+1}, s_{k+1}, y_{k+1}, z_{k+1})</math> using:
			::: <math>x^+ = x + a_s^{max} p_x, s^+ = s + a_s^{max} p_s , </math>
	<math>\alpha_s^{max} = max \{ \alpha \in (0,1): s + \alpha p_s \geq (1- \tau) s</math>		::: <math>y^+ = x + a_z^{max} p_y, z^+ = z + a_z^{max} p_z , </math>
			:: Set <math>\mu_{k+1} \leftarrow \mu_k </math> and <math>k\leftarrow k + 1; </math>
	<math>\alpha_z^{max} = max \{ \alpha \in (0,1): z + \alpha p_s \geq (1- \tau) z</math>		: '''end'''
			: Choose <math>\mu_k \in (0, \mu_k); </math>
	Compute <math>(x_{k+1}, s_{k+1}, y_{k+1}, z_{k+1})</math> using:

	<math>x^+ = x + a_s^{max} p_x, s^+ = s + a_s^{max} p_s , </math>

	<math>y^+ = x + a_z^{max} p_y, z^+ = z + a_z^{max} p_z , </math>

	Set <math>\mu_{k+1} \leftarrow \mu_k </math> and <math>k\leftarrow k + 1; </math>

	'''end'''

	Choose <math>\mu_k \in (0, \mu_k); </math>

	'''end'''		'''end'''

Line 222:		Line 190:
	* <math>l </math> represents the lower bounds on the decision variables.		* <math>l </math> represents the lower bounds on the decision variables.
	* <math>u </math> represents the upper bounds on the decision variables.		* <math>u </math> represents the upper bounds on the decision variables.


	Compute a feasible starting point <math>x_0; </math>		Compute a feasible starting point <math>x_0; </math>

	'''for''' <math>k = 0, 1, 2,... </math>		'''for''' <math>k = 0, 1, 2,... </math>
			: '''if''' <math>x^k </math> satisfies the KKT conditions for the quadratic programming problem:
	'''if''' <math>x^k </math> satisfies the KKT conditions for the quadratic programming problem:		:: minimize <math>q = \frac{1}{2}x^TGx+x^Tc </math>
			:: subject to <math>l \leq x \leq u </math>
	minimize <math>q = \frac{1}{2}x^TGx+x^Tc </math>		:: '''stop''' with solution <math>x^* = x^k; </math>
			: Set <math>x = x^k </math> and find the Cauchy point <math>x^c; </math>
	subject to <math>l \leq x \leq u </math>		: Find an approximate solution <math>x^+ </math> of:
			:: minimize <math>q = \frac{1}{2}x^TGx + x^Tc </math>
	'''stop''' with solution <math>x^* = x^k; </math>		:: subject to <math>x_i = x_i^c, i \in A(x^c), </math> <math>l_i \leq x_i \leq \mu_i, i \not\in A(x^c) </math>
			:: such that <math>q(x^+) \leq q(x^+) \leq q(x^c) </math> and <math>x^+ </math> is feasible;
	Set <math>x = x^k </math> and find the Cauchy point <math>x^c; </math>		: <math>x^{k+1} \leftarrow x^+; </math>

	Find an approximate solution <math>x^+ </math> of

	minimize <math>q = \frac{1}{2}x^TGx + x^Tc </math>

	subject to <math>x_i = x_i^c, i \in A(x^c), </math>

	<math>l_i \leq x_i \leq \mu_i, i \not\in A(x^c) </math>

	such that <math>q(x^+) \leq q(x^+) \leq q(x^c) </math> and <math>x^+ </math> is feasible;

	<math>x^{k+1} \leftarrow x^+; </math>

	'''end(for)'''		'''end(for)'''