Interior-point method for LP - Revision history

Wc593 at 11:31, 21 December 2020

2020-12-21T11:31:15Z

← Older revision		Revision as of 07:31, 21 December 2020
Line 1:		Line 1:
	Authors: Tomas Lopez Lauterio, Rohit Thakur and Sunil Shenoy (SysEn ~~6800~~ Fall 2020) <br>		Authors: Tomas Lopez Lauterio, Rohit Thakur and Sunil Shenoy (SysEn 5800 Fall 2020) <br>

	== Introduction ==		== Introduction ==

Wc593 at 10:14, 21 December 2020

2020-12-21T10:14:40Z

← Older revision		Revision as of 06:14, 21 December 2020
Line 1:		Line 1:
	Authors: Tomas Lopez Lauterio, Rohit Thakur and Sunil Shenoy (SysEn 6800 Fall 2020) <br>		Authors: Tomas Lopez Lauterio, Rohit Thakur and Sunil Shenoy (SysEn 6800 Fall 2020) <br>


	== Introduction ==		== Introduction ==

Wc593 at 10:13, 21 December 2020

2020-12-21T10:13:51Z

← Older revision		Revision as of 06:13, 21 December 2020
Line 1:		Line 1:
	Authors: Tomas Lopez Lauterio, Rohit Thakur and Sunil Shenoy (SysEn 6800 Fall 2020) <br>		Authors: Tomas Lopez Lauterio, Rohit Thakur and Sunil Shenoy (SysEn 6800 Fall 2020) <br>
	~~Steward: Dr. Fengqi You and Akshay Ajagekar<br>~~


Line 11:		Line 10:
	minimize <math> f\left ( x \right ) </math><br>		minimize <math> f\left ( x \right ) </math><br>
	subject to: <math> A \cdot x = b </math><br>		subject to: <math> A \cdot x = b </math><br>
	where, <math> A \, \~~varepsilon~~ \, R^{p\, \times \, n} </math> is assumed to have a full row rank		where, <math> A \, \in \, R^{p\, \times \, n} </math> is assumed to have a full row rank
	Lagrange function can be laid out as:<br>		Lagrange function can be laid out as:<br>
	<math>L(x, \lambda ) = f(x) + \sum_{i=1}^{p}\lambda _{i}\cdot a_{i}(x)</math> <br>		<math>L(x, \lambda ) = f(x) + \sum_{i=1}^{p}\lambda _{i}\cdot a_{i}(x)</math> <br>

RohitThakur: /* Numerical Example */

2020-12-14T01:59:13Z

Numerical Example

← Older revision		Revision as of 21:59, 13 December 2020
Line 178:		Line 178:
	Optimal points <math>X_{1} = 2 </math> and <math>X_{2} = 2</math>		Optimal points <math>X_{1} = 2 </math> and <math>X_{2} = 2</math>

	The Newton's Method can also be applied to solve linear programming problems as indicated in the "Theory and Algorithm" section above. The solution to linear programming problems as indicated in this section, will be similar to quadratic equation as obtained above and will converge in one iteration.		The Newton's Method can also be applied to solve linear programming problems as indicated in the "Theory and Algorithm" section above. The solution to linear programming problems as indicated in this section "Numerical Example", will be similar to quadratic equation as obtained above and will converge in one iteration.

	== Applications ==		== Applications ==

RohitThakur: /* Numerical Example */

2020-12-14T01:57:59Z

Numerical Example

← Older revision		Revision as of 21:57, 13 December 2020
Line 177:		Line 177:
	Maximum Value of Objective function <math>=12</math> <br>		Maximum Value of Objective function <math>=12</math> <br>
	Optimal points <math>X_{1} = 2 </math> and <math>X_{2} = 2</math>		Optimal points <math>X_{1} = 2 </math> and <math>X_{2} = 2</math>

			The Newton's Method can also be applied to solve linear programming problems as indicated in the "Theory and Algorithm" section above. The solution to linear programming problems as indicated in this section, will be similar to quadratic equation as obtained above and will converge in one iteration.

	== Applications ==		== Applications ==

Tomas: /* Applications */

2020-12-12T22:52:22Z

Applications

← Older revision		Revision as of 18:52, 12 December 2020
Line 179:		Line 179:

	== Applications ==		== Applications ==
	Primal-Dual interior-point (PDIP) methods are commonly used in optimal power flow (OPF), in this case what is being looked is to maximize user utility and minimize operational cost satisfying operational and physical constraints. The solution to the OPF needs to be available to grid operators in few minutes or seconds due to changes and fluctuations in loads during power generation. Newton-based primal-dual interior point can achieve fast convergence in this OPF optimization problem.<ref> A. Minot, Y. M. Lu and N. Li, "A parallel primal-dual interior-point method for DC optimal power flow," 2016 Power Systems Computation Conference (PSCC), Genoa, 2016, pp. 1-7, doi: 10.1109/PSCC.2016.7540826. </ref>		Primal-Dual interior-point (PDIP) methods are commonly used in optimal power flow (OPF), in this case what is being looked is to maximize user utility and minimize operational cost satisfying operational and physical constraints. The solution to the OPF needs to be available to grid operators in few minutes or seconds due to changes and fluctuations in loads during power generation. Newton-based primal-dual interior point can achieve fast convergence in this OPF optimization problem. <ref> A. Minot, Y. M. Lu and N. Li, "A parallel primal-dual interior-point method for DC optimal power flow," 2016 Power Systems Computation Conference (PSCC), Genoa, 2016, pp. 1-7, doi: 10.1109/PSCC.2016.7540826. </ref>

	Another application of the PDIP is for the minimization of losses and cost in the generation and transmission in hydroelectric power systems. <ref> L. M. Ramos Carvalho and A. R. Leite Oliveira, "Primal-Dual Interior Point Method Applied to the Short Term Hydroelectric Scheduling Including a Perturbing Parameter," in IEEE Latin America Transactions, vol. 7, no. 5, pp. 533-538, Sept. 2009, doi: 10.1109/TLA.2009.5361190. </ref>		Another application of the PDIP is for the minimization of losses and cost in the generation and transmission in hydroelectric power systems. <ref> L. M. Ramos Carvalho and A. R. Leite Oliveira, "Primal-Dual Interior Point Method Applied to the Short Term Hydroelectric Scheduling Including a Perturbing Parameter," in IEEE Latin America Transactions, vol. 7, no. 5, pp. 533-538, Sept. 2009, doi: 10.1109/TLA.2009.5361190. </ref>

Tomas: /* Applications */

2020-12-12T22:48:50Z

Applications

← Older revision		Revision as of 18:48, 12 December 2020
Line 179:		Line 179:

	== Applications ==		== Applications ==
	Primal-Dual interior-point (PDIP) methods are commonly used in optimal power flow (OPF), in this case what is being looked is to maximize user utility and minimize operational cost satisfying operational and physical constraints. The solution to the OPF needs to be available to grid operators in few minutes or seconds due changes fluctuations in loads or power generation. Newton-based primal-dual interior point can achieve fast convergence in this OPF optimization problem.<ref> A. Minot, Y. M. Lu and N. Li, "A parallel primal-dual interior-point method for DC optimal power flow," 2016 Power Systems Computation Conference (PSCC), Genoa, 2016, pp. 1-7, doi: 10.1109/PSCC.2016.7540826. </ref>		Primal-Dual interior-point (PDIP) methods are commonly used in optimal power flow (OPF), in this case what is being looked is to maximize user utility and minimize operational cost satisfying operational and physical constraints. The solution to the OPF needs to be available to grid operators in few minutes or seconds due to changes and fluctuations in loads during power generation. Newton-based primal-dual interior point can achieve fast convergence in this OPF optimization problem.<ref> A. Minot, Y. M. Lu and N. Li, "A parallel primal-dual interior-point method for DC optimal power flow," 2016 Power Systems Computation Conference (PSCC), Genoa, 2016, pp. 1-7, doi: 10.1109/PSCC.2016.7540826. </ref>

	Another application of the PDIP is for the minimization of losses and cost in the generation and transmission in hydroelectric power systems. <ref> L. M. Ramos Carvalho and A. R. Leite Oliveira, "Primal-Dual Interior Point Method Applied to the Short Term Hydroelectric Scheduling Including a Perturbing Parameter," in IEEE Latin America Transactions, vol. 7, no. 5, pp. 533-538, Sept. 2009, doi: 10.1109/TLA.2009.5361190. </ref>		Another application of the PDIP is for the minimization of losses and cost in the generation and transmission in hydroelectric power systems. <ref> L. M. Ramos Carvalho and A. R. Leite Oliveira, "Primal-Dual Interior Point Method Applied to the Short Term Hydroelectric Scheduling Including a Perturbing Parameter," in IEEE Latin America Transactions, vol. 7, no. 5, pp. 533-538, Sept. 2009, doi: 10.1109/TLA.2009.5361190. </ref>

	PDIP are commonly used in imaging processing. One ~~application~~ is for image deblurring, in this case the constrained deblurring problem is formulated as primal-dual. The constrained primal-dual is solved using a semi-smooth Newton’s method. <ref> D. Krishnan, P. Lin and A. M. Yip, "A Primal-Dual Active-Set Method for Non-Negativity Constrained Total Variation Deblurring Problems," in IEEE Transactions on Image Processing, vol. 16, no. 11, pp. 2766-2777, Nov. 2007, doi: 10.1109/TIP.2007.908079. </ref>		PDIP are commonly used in imaging processing. One these applications is for image deblurring, in this case the constrained deblurring problem is formulated as primal-dual. The constrained primal-dual is solved using a semi-smooth Newton’s method. <ref> D. Krishnan, P. Lin and A. M. Yip, "A Primal-Dual Active-Set Method for Non-Negativity Constrained Total Variation Deblurring Problems," in IEEE Transactions on Image Processing, vol. 16, no. 11, pp. 2766-2777, Nov. 2007, doi: 10.1109/TIP.2007.908079. </ref>

	PDIP can be utilized to obtain a general formula for a shape derivative of the potential energy, describing the energy release rate for curvilinear cracks. Problems on cracks and their evolution have important application in engineering and mechanical sciences. <ref> V. A. Kovtunenko, Primal–dual methods of shape sensitivity analysis for curvilinear cracks with nonpenetration, IMA Journal of Applied Mathematics, Volume 71, Issue 5, October 2006, Pages 635–657 </ref>



			PDIP can be utilized to obtain a general formula for a shape derivative of the potential energy describing the energy release rate for curvilinear cracks. Problems on cracks and their evolution have important application in engineering and mechanical sciences. <ref> V. A. Kovtunenko, Primal–dual methods of shape sensitivity analysis for curvilinear cracks with nonpenetration, IMA Journal of Applied Mathematics, Volume 71, Issue 5, October 2006, Pages 635–657 </ref>

	== Conclusion ==		== Conclusion ==

RohitThakur: /* Numerical Example */

2020-12-07T18:14:29Z

Numerical Example

← Older revision		Revision as of 14:14, 7 December 2020
Line 152:		Line 152:
	\|+ Objective & Barrier Function w.r.t <math>X_{1}</math>, <math>X_{2}</math> and <math>\mu</math>		\|+ Objective & Barrier Function w.r.t <math>X_{1}</math>, <math>X_{2}</math> and <math>\mu</math>
	\|-		\|-
	! <math>\mu</math> !! <math>X_{1}</math> !! <math>X_{2}</math> !! <math>P(X, \mu)</math> !! f(x)		! <math>\mu</math> !! <math>X_{1}</math> !! <math>X_{2}</math> !! <math>P(X, \mu)</math> !! <math>f(x)</math>
	\|-		\|-
	\| 0 \|\| 2 \|\| 2 \|\| 12 \|\| 12		\| 0 \|\| 2 \|\| 2 \|\| 12 \|\| 12

RohitThakur: /* Numerical Example */

2020-12-07T18:12:22Z

Numerical Example

← Older revision		Revision as of 14:12, 7 December 2020
Line 111:		Line 111:

	such that<br>		such that<br>
	<math> X_{1} + X_{2} \leq 4 </math><br>		<math> X_{1} + X_{2} \leq 4, </math><br>
	<math> X_{1} \geq 0 </math><br>		<math> X_{1} \geq 0, </math><br>
	<math> X_{2} \geq 0 </math><br>		<math> X_{2} \geq 0, </math><br>

	Barrier form of the above primal problem is as written below:		Barrier form of the above primal problem is as written below:

RohitThakur: /* Numerical Example */

2020-12-07T18:11:17Z

Numerical Example

← Older revision		Revision as of 14:11, 7 December 2020
Line 150:		Line 150:

	{\| class="wikitable"		{\| class="wikitable"
	\|+ Objective ~~and~~ Barrier Function w.r.t X<~~sub~~>1</~~sub~~>, X<~~sub~~>2</~~sub~~> and μ		\|+ Objective & Barrier Function w.r.t <math>X_{1}</math>, <math>X_{2}</math> and <math>\mu</math>
	\|-		\|-
	! μ !! X<~~sub~~>1</~~sub~~> !! X<~~sub~~>2</~~sub~~> !! P(X, μ) !! f(x)		! <math>\mu</math> !! <math>X_{1}</math> !! <math>X_{2}</math> !! <math>P(X, \mu)</math> !! f(x)
	\|-		\|-
	\| 0 \|\| 2 \|\| 2 \|\| 12 \|\| 12		\| 0 \|\| 2 \|\| 2 \|\| 12 \|\| 12
	\|-		\|-
	\| 0.01 \|\| 1.998 \|\| 1.998 \|\| 11.947 \|\| 11.990		\| 0.01 \|\| 1.998 \|\| 1.998 \|\| 11.947 \|\| 11.990
	\|-		\|-
	\| 0.1 \|\| 1.984 \|\| 1.984 \|\| 11.697 \|\| 11.902		\| 0.1 \|\| 1.984 \|\| 1.984 \|\| 11.697 \|\| 11.902
	\|-		\|-
	\| 1 \|\| 1.859 \|\| 1.859 \|\| 11.128 \|\| 11.152		\| 1 \|\| 1.859 \|\| 1.859 \|\| 11.128 \|\| 11.152
	\|-		\|-
	\| 10\|\| 1.486 \|\| 1.486 \|\| 17.114 \|\| 8.916		\| 10 \|\| 1.486 \|\| 1.486 \|\| 17.114 \|\| 8.916
	\|-		\|-
	\| 100\|\| 1.351 \|\| 1.351 \|\| 94.357 \|\| 8.105		\| 100 \|\| 1.351 \|\| 1.351 \|\| 94.357 \|\| 8.105
	\|-		\|-
	\| 1000\|\| 1.335 \|\| 1.335\|\| 871.052 \|\| 8.011		\| 1000 \|\| 1.335 \|\| 1.335 \|\| 871.052 \|\| 8.011
	\|}		\|}