Outer-approximation (OA): Difference between revisions

Revision as of 07:45, 26 November 2021

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Introduction

Theory

Example

Minimize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f(x)= y_{1} +y_{2} + \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } Subject to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-2y_{1} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-x_{2}-3 \big(1-y_{1}\big) \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}+y_{1}-1\geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{2}-y_{2}\geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}+x_{2}\geq 3y_{1}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{1}+y_{2}\geq 1} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{1}\leq 4} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{2}\leq 4} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{1},y_{2} \in \big\{0,1\big\} } Solution
Step 1a: Start from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle y_{1}=y_{2}=1} and solve the NLP below:
Minimize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f= 2+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } Subject to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-2 \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-x_{2} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{2}-1 \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}+x_{2} \geq 3} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{1}\leq 4} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{2}\leq 4} Solution: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x_{1}=2, x_{2}=1} , Upper Bound = 7

Step 1b: Solve the MILP master problem with OA for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x^{*} =[2,1] } :
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\big(x\big) =\big( x_{1} \big)^{2} +\big( x_{2} \big)^{2},~~ \bigtriangledown f\big(x\big)=[2x_{1}~~~~2x_{1}]^{T} ~~for~~x^{*} =[2~~~~1]^{T} } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f\big(x^{*}\big)+ \bigtriangledown f\big(x^{*}\big)^{T}\big(x-x^{*}\big)=5+[4~~~~2] \begin{bmatrix}x_{1}-2 \\x_{2}-1 \end{bmatrix}=5+4\big(x_{1}-2\big)+2\big(x_{2}-1\big)}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\big(x\big)=\big(x_{1}-2\big)^{2}-x_{2},~~ \bigtriangledown g\big(x\big)=[2x_{1}-4~~~~-1]^{T}~~for~~x^{*} =[2~~~~1]^{T} }

Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle g\big(x^{*}\big)+ \bigtriangledown g\big(x^{*}\big)^{T}\big(x-x^{*}\big)=-1+[0~~~~-1] \begin{bmatrix}x_{1}-2 \\x_{2}-1 \end{bmatrix}=-x_{2}}

Minimize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha } Subject to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \alpha\geq y_{1}+y_{2}+5+4\big(x_{1}-2\big)+2\big(x_{2}-1\big) } Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle -x_{2}\leq0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-2y_{1} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-x_{2}-3 \big(1-y_{1}\big) \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}+y_{1}-1\geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{2}-y_{2}\geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}+x_{2}\geq 3y_{1}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{1}+y_{2}\geq 1} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{1}\leq 4} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{2}\leq 4} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_{1},y_{2} \in \big\{0,1\big\} }

MILP Solution: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0} , Lower Bound = 6
Lower Bound < Upper Bound, Integer cut: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle y_{1}- y_{2}\leq 0}

Step 2a: Start from Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle y=[1,0]} and solve the NLP below:
Minimize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle f= 1+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } Subject to Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-2 \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}-x_{2} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{2} \geq 0} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_{1}+x_{2} \geq 3} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{1}\leq 4} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0 \leq x_{2}\leq 4} Solution: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x_{1}=2, x_{2}=1} , Upper Bound = 6
Upper Bound = 6 = Lower Bound, Optimum!
Optimal Solution for the MINLP: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\textstyle x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0} , Upper Bound = 6

Conclusion

References

@@ Line 31: / Line 31: @@
 ''Solution: ''<math display=inline>x_{1}=2, x_{2}=1</math>, Upper Bound = 7 <br>
-'''Step 1a:'''  Solve the MILP master problem with OA for <math display=inline> x^{*} =[2,1] </math> : <br>
+'''Step 1b:'''  Solve the MILP master problem with OA for <math display=inline> x^{*} =[2,1] </math> : <br>
 <math display=block>f\big(x\big) =\big( x_{1} \big)^{2} +\big( x_{2} \big)^{2},~~ \bigtriangledown  f\big(x\big)=[2x_{1}~~~~2x_{1}]^{T} ~~for~~x^{*} =[2~~~~1]^{T} </math>
 <math display=block>f\big(x^{*}\big)+ \bigtriangledown  f\big(x^{*}\big)^{T}\big(x-x^{*}\big)=5+[4~~~~2] \begin{bmatrix}x_{1}-2  \\x_{2}-1  \end{bmatrix}=5+4\big(x_{1}-2\big)+2\big(x_{2}-1\big)</math>
@@ Line 53: / Line 53: @@
 ''MILP Solution: ''<math display=inline>x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0</math>, Lower Bound = 6 <br>
-Lower Bound<Upper Bound, Integer Cut:<math display=inline>y_{1}- y_{2}\leq 0</math>
+Lower Bound < Upper Bound, Integer cut: <math display=inline>y_{1}- y_{2}\leq 0</math>
+'''Step 2a:'''  Start from
+<math display=inline>y=[1,0]</math> and solve the NLP below: <br>
+''Minimize'' <math display=block> f= 1+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} </math>
+''Subject to'' <math display=block>\big(x_{1}-2\big)^{2}-x_{2} \leq 0</math>
+<math display=block>x_{1}-2 \geq 0</math>
+<math display=block>x_{1}-x_{2} \geq 0</math>
+<math display=block>x_{1} \geq 0</math>
+<math display=block>x_{2} \geq 0</math>
+<math display=block>x_{1}+x_{2} \geq 3</math>
+<math display=block>0 \leq x_{1}\leq 4</math>
+<math display=block>0 \leq x_{2}\leq 4</math>
+''Solution: ''<math display=inline>x_{1}=2, x_{2}=1</math>, Upper Bound = 6 <br>
+Upper Bound = 6 = Lower Bound, Optimum!<br>
+''Optimal Solution for the MINLP: ''<math display=inline>x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0</math>, Upper Bound = 6 <br>
 ==Conclusion==
 ==References==