Mathematical programming with equilibrium constraints - Revision history

Aa2789: update styling

2021-12-15T21:10:18Z

update styling

← Older revision		Revision as of 17:10, 15 December 2021
Line 128:		Line 128:

	==== NLP Reformulation ====		==== NLP Reformulation ====
	NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach. <ref>S. A. Sadat en L. Fan, “[https://doi.org/10.1109/PESGM.2017.8273875 Mixed integer linear programming formulation for chance constrained mathematical programs with equilibrium constraints]”, in ''2017 IEEE Power Energy Society General Meeting'', 2017, bll 1–5.</ref> The general form of MPECs that can be reformulated is:		NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach<ref>S. A. Sadat en L. Fan, “[https://doi.org/10.1109/PESGM.2017.8273875 Mixed integer linear programming formulation for chance constrained mathematical programs with equilibrium constraints]”, in ''2017 IEEE Power Energy Society General Meeting'', 2017, bll 1–5.</ref>. The general form of MPECs that can be reformulated is:

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

Aa2789: added citation to NLP reformulation

2021-12-15T21:08:19Z

added citation to NLP reformulation

← Older revision		Revision as of 17:08, 15 December 2021
Line 128:		Line 128:

	==== NLP Reformulation ====		==== NLP Reformulation ====
	NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach. The general form of MPECs that can be reformulated is:		NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach. <ref>S. A. Sadat en L. Fan, “[https://doi.org/10.1109/PESGM.2017.8273875 Mixed integer linear programming formulation for chance constrained mathematical programs with equilibrium constraints]”, in ''2017 IEEE Power Energy Society General Meeting'', 2017, bll 1–5.</ref> The general form of MPECs that can be reformulated is:

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

Aa2789: updated citation

2021-12-15T21:00:09Z

updated citation

← Older revision		Revision as of 17:00, 15 December 2021
Line 156:		Line 156:
	# Drop the active constraint (ie. violates the condition above) with the largest magnitude.		# Drop the active constraint (ie. violates the condition above) with the largest magnitude.
	# Add the violated constraints to <math>J </math> making them active.		# Add the violated constraints to <math>J </math> making them active.
	# Return to <u>Step 2</u> <ref ~~name=":3"~~ />.		# Return to <u>Step 2</u> <ref>You, F. Lecture on “Nonlinear Programming”. Archives for SYSEN 6800 Computational Optimization (2021FA), Cornell University, Ithaca, NY (2021).</ref>.

	=== General Approaches ===		=== General Approaches ===

Aa2789: heading rank

2021-12-15T08:10:16Z

heading rank

← Older revision		Revision as of 04:10, 15 December 2021
Line 127:		Line 127:
	<u>Step 2:</u> Set <math>x^{v+1} = x^v + dx^v</math> and check for termination. If check fails, repeat steps 1 and 2 with <math>v = v+1</math><ref name=":2" />.		<u>Step 2:</u> Set <math>x^{v+1} = x^v + dx^v</math> and check for termination. If check fails, repeat steps 1 and 2 with <math>v = v+1</math><ref name=":2" />.

	=== NLP Reformulation ===		==== NLP Reformulation ====
	NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach. The general form of MPECs that can be reformulated is:		NLP Reformulation technique is applicable to MPECs that fall into the same grouping as piecewise SQP. It is possible to generate positive slack variables on optimization function and constraints while setting the constraint equalities to zero. With this reformulation is it now possible to apply other NLP techniques to solving a MPEC such as the Karush- Kuhn-Tucker approach. The general form of MPECs that can be reformulated is:

Line 159:		Line 159:

	=== General Approaches ===		=== General Approaches ===
	Note that the above approaches do not cover all formulations of MPEC problems. Aside from these formulations, one of the main approaches for the solution of optimization problems with constraints is a reformulation of the problem as a standard nonlinear program which allows the solution to use existing non-linear programming algorithms<ref>J. X. Ban, H. X. Liu, M. C. Ferris, en B. Ran, [https://doi.org/10.1016/j.mcm.2005.11.001 “A general MPCC model and its solution algorithm for continuous network design problem”], ''Mathematical and Computer Modelling'', vol 43, no 5, bll 493–505, 2006.</ref>. Some of these algorithms are mentioned here on this wiki including [[Quasi-Newton methods]] and [[Trust-region methods\|trust-region method]]. There have been three advances in the past two decades which have increased the capability of a modeler to solve large scale complementarity problems. First was the implementation of large-scale complementarity solvers which utilize advance methods in linear algebra and nonlinear optimization. Some of these solvers are MILES, PATH and SMOOTH. The second advancement is the start of modeling systems that are able to express complementarity problems as part of their syntax and pass the model to the solver. The third advancement was the interactions in which the first two develop. A modeler is able to generate realistic large-scale models which allow the solvers to be tested on large and more difficult class of models. By solving larger and complex programming problems with additional constraints, this furthers the development of new applied economic models <ref name=":1" />.		Note that the above approaches do not cover all formulations of MPEC problems. Aside from these formulations, one of the main approaches for the solution of optimization problems with constraints is a reformulation of the problem as a standard nonlinear program which allows the solution to use existing non-linear programming algorithms<ref>J. X. Ban, H. X. Liu, M. C. Ferris, en B. Ran, [https://doi.org/10.1016/j.mcm.2005.11.001 “A general MPCC model and its solution algorithm for continuous network design problem”], ''Mathematical and Computer Modelling'', vol 43, no 5, bll 493–505, 2006.</ref>. Some of these algorithms are mentioned here on this wiki including [[Quasi-Newton methods]] and [[Trust-region methods\|trust-region method]]. There have been three advances in the past two decades which have increased the capability of a modeler to solve large scale complementarity problems. First was the implementation of large-scale complementarity solvers which utilize advance methods in linear algebra and nonlinear optimization. Some of these solvers are MILES, PATH and SMOOTH. The second advancement is the start of modeling systems that are able to express complementarity problems as part of their syntax and pass the model to the solver. The third advancement was the interactions in which the first two develop. A modeler is able to generate realistic large-scale models which allow the solvers to be tested on large and more difficult class of models. By solving larger and complex programming problems with additional constraints, this furthers the development of new applied economic models <ref name=":1" />.

	==Numerical example==		==Numerical example==

Aa2789: /* Targeted Approaches */

2021-12-15T05:24:04Z

Targeted Approaches

@@ Line 36: / Line 36: @@
 === Targeted Approaches ===
-Three different types of algorithmic approaches can be used to solve MPEC. These are the penalty interior point approach (PIPA), the implicit programming approach, and the piecewise sequential quadratic programming (SQP) approach <ref name=":2" />.
+Four different types of algorithmic approaches can be used to solve MPEC. Of the 4 techniques, three of these specialized techniques include the penalty interior point approach (PIPA), the implicit programming approach, and the piecewise sequential quadratic programming (SQP) approach <ref name=":2" />. Additionally, some MPEC problems can be reformulated as a relaxed NLP which can then be solved using other NLP techniques. <ref name=":3">Nocedal, Jorge and Wright, Stephen J., [https://doi.org/10.1007/978-0-387-40065-5_12 “Theory of Constrained Optimization”], in ''Numerical Optimization'', New York, NY: Springer New York, 2006, bll 304–354.</ref>
 ==== PIPA ====
@@ Line 126: / Line 126: @@
 <u>Step 2:</u> Set <math>x^{v+1} = x^v + dx^v</math> and check for termination. If check fails, repeat steps 1 and 2 with <math>v = v+1</math><ref name=":2" />.
 === General Approaches ===
-Note that the above approaches do not cover all formulations of MPEC problems. Aside from these formulations, one of the main approaches for the solution of optimization problems with constraints is a reformulation of the problem as a standard nonlinear program which allows the solution to use existing non-linear programming algorithms. There have been three advances in the past two decades which have increased the capability of a modeler to solve large scale complementarity problems. First was the implementation of large-scale complementarity solvers which utilize advance methods in linear algebra and nonlinear optimization. Some of these solvers are MILES, PATH and SMOOTH. The second advancement is the start of modeling systems that are able to express complementarity problems as part of their syntax and pass the model to the solver. The third advancement was the interactions in which the first two develop. A modeler is able to generate realistic large-scale models which allow the solvers to be tested on large and more difficult class of models. By solving larger and complex programming problems with additional constraints, this furthers the development of new applied economic models <ref name=":1" />.
+Note that the above approaches do not cover all formulations of MPEC problems. Aside from these formulations, one of the main approaches for the solution of optimization problems with constraints is a reformulation of the problem as a standard nonlinear program which allows the solution to use existing non-linear programming algorithms<ref>J. X. Ban, H. X. Liu, M. C. Ferris, en B. Ran, [https://doi.org/10.1016/j.mcm.2005.11.001 “A general MPCC model and its solution algorithm for continuous network design problem”], ''Mathematical and Computer Modelling'', vol 43, no 5, bll 493–505, 2006.</ref>. Some of these algorithms are mentioned here on this wiki including [[Quasi-Newton methods]] and [[Trust-region methods|trust-region method]]. There have been three advances in the past two decades which have increased the capability of a modeler to solve large scale complementarity problems. First was the implementation of large-scale complementarity solvers which utilize advance methods in linear algebra and nonlinear optimization. Some of these solvers are MILES, PATH and SMOOTH. The second advancement is the start of modeling systems that are able to express complementarity problems as part of their syntax and pass the model to the solver. The third advancement was the interactions in which the first two develop. A modeler is able to generate realistic large-scale models which allow the solvers to be tested on large and more difficult class of models. By solving larger and complex programming problems with additional constraints, this furthers the development of new applied economic models <ref name=":1" />.
 ==Numerical example==

Mvb48: /* Numerical example */

2021-12-15T01:47:24Z

Numerical example

← Older revision		Revision as of 21:47, 14 December 2021
Line 187:		Line 187:
	KKT point lies at <math>x_1=2,x_2=14,x_3=0</math>		KKT point lies at <math>x_1=2,x_2=14,x_3=0</math>

	The following numerical example was also solved with GAMS using an MPEC solver to verify solution accuracy		The following numerical example was also solved with GAMS using an MPEC solver to verify solution accuracy<ref>[http://www.gamsworld.org/mpec/mpeclib/gauvin.htm ''Gauvin.gms'', http://www.gamsworld.org/mpec/mpeclib/gauvin.htm.]</ref>

	==Applications==		==Applications==

Mvb48: /* Numerical example */

2021-12-15T01:40:00Z

Numerical example

← Older revision		Revision as of 21:40, 14 December 2021
Line 183:		Line 183:
	<math>x_1=2, x_2=14, \mu_1=1,x_3=0</math>		<math>x_1=2, x_2=14, \mu_1=1,x_3=0</math>

	<math>g_2,g_3,g_4,g_5,g_6<0, </math>so <math>\mu_2=\mu_3=\mu_4=\mu_5=\mu_6=0</math>		Point (2,14,0) satisfies <math>g_2,g_3,g_4,g_5,g_6<0, </math>so <math>\mu_2=\mu_3=\mu_4=\mu_5=\mu_6=0</math>

			KKT point lies at <math>x_1=2,x_2=14,x_3=0</math>

			The following numerical example was also solved with GAMS using an MPEC solver to verify solution accuracy

	==Applications==		==Applications==

Mvb48: /* Numerical example */

2021-12-15T01:34:24Z

Numerical example

@@ Line 182: / Line 182: @@
 <math>x_1=2, x_2=14, \mu_1=1,x_3=0</math>
- Variables  objvar,x2,x3,x4,x5;
- Positive Variables x5;
+<math>g_2,g_3,g_4,g_5,g_6<0,  </math>so <math>\mu_2=\mu_3=\mu_4=\mu_5=\mu_6=0</math>
 ==Applications==

Mvb48 at 00:47, 15 December 2021

2021-12-15T00:47:08Z

← Older revision		Revision as of 20:47, 14 December 2021
Line 181:		Line 181:
	<math>\begin{bmatrix} 2x_1 \\\ 2x_2-20 \\0\end{bmatrix}+\mu_1\cdot\begin{bmatrix} -4 \\\ -8 \\-1\end{bmatrix}=\begin{bmatrix} 0 \\\ 0 \\0\end{bmatrix}</math>		<math>\begin{bmatrix} 2x_1 \\\ 2x_2-20 \\0\end{bmatrix}+\mu_1\cdot\begin{bmatrix} -4 \\\ -8 \\-1\end{bmatrix}=\begin{bmatrix} 0 \\\ 0 \\0\end{bmatrix}</math>

			<math>x_1=2, x_2=14, \mu_1=1,x_3=0</math>
	Variables objvar,x2,x3,x4,x5;		Variables objvar,x2,x3,x4,x5;
	Positive Variables x5;		Positive Variables x5;

Tshamshudin: /* Numerical example */ explanation

2021-12-15T00:03:46Z

Numerical example: explanation

← Older revision		Revision as of 20:03, 14 December 2021
Line 130:		Line 130:

	==Numerical example==		==Numerical example==

			The numerical example below contains a feasible region that is not necessarily convex or connected. The example also involves variational inequalities as shown by the two constraints. The methodology utilized below has the initial form as an NLP problem. Realistically, the initial problem would start as an MPEC and transform into an NLP.

	Consider the following MPEC example by Savard and Gauvin <ref>[https://dl.acm.org/doi/10.1016/0167-6377%2894%2990086-8 Savard, G, and Gauvin, J, The Steepest Descent for the Nonlinear Bilevel Programming Problem. Operation Research Letters 15 (1994), 265-272.]</ref>		Consider the following MPEC example by Savard and Gauvin <ref>[https://dl.acm.org/doi/10.1016/0167-6377%2894%2990086-8 Savard, G, and Gauvin, J, The Steepest Descent for the Nonlinear Bilevel Programming Problem. Operation Research Letters 15 (1994), 265-272.]</ref>