Outer-approximation (OA)

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Example

Example 1

Minimize $ {\displaystyle f(x)= y_{1} +y_{2} + \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } $ Subject to $ {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} $ $ {\displaystyle x_{1}-2y_{1} \geq 0} $ $ {\displaystyle x_{1}-x_{2}-3 \big(1-y_{1}\big) \geq 0} $ $ {\displaystyle x_{1}+y_{1}-1\geq 0} $ $ {\displaystyle x_{2}-y_{2}\geq 0} $ $ {\displaystyle x_{1}+x_{2}\geq 3y_{1}} $ $ {\displaystyle y_{1}+y_{2}\geq 1} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 0 \leq x_{2}\leq 4} $ $ {\displaystyle y_{1},y_{2} \in \big\{0,1\big\} } $ Solution
Step 1a: Start from $ {\textstyle y_{1}=y_{2}=1} $ and solve the NLP below:
Minimize $ {\displaystyle f= 2+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } $ Subject to $ {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} $ $ {\displaystyle x_{1}-2 \geq 0} $ $ {\displaystyle x_{1}-x_{2} \geq 0} $ $ {\displaystyle x_{1} \geq 0} $ $ {\displaystyle x_{2}-1 \geq 0} $ $ {\displaystyle x_{1}+x_{2} \geq 3} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 0 \leq x_{2}\leq 4} $ Solution: $ {\textstyle x_{1}=2, x_{2}=1} $, Upper Bound = 7

Step 1b: Solve the MILP master problem with OA for $ {\textstyle x^{*} =[2,1] } $ :
$ {\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} } $ $ {\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)} $
$ {\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} } $

$ {\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 $ {\displaystyle \alpha } $ Subject to $ {\displaystyle \alpha\geq y_{1}+y_{2}+5+4\big(x_{1}-2\big)+2\big(x_{2}-1\big) } $ $ {\displaystyle -x_{2}\leq0} $ $ {\displaystyle x_{1}-2y_{1} \geq 0} $ $ {\displaystyle x_{1}-x_{2}-3 \big(1-y_{1}\big) \geq 0} $ $ {\displaystyle x_{1}+y_{1}-1\geq 0} $ $ {\displaystyle x_{2}-y_{2}\geq 0} $ $ {\displaystyle x_{1}+x_{2}\geq 3y_{1}} $ $ {\displaystyle y_{1}+y_{2}\geq 1} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 0 \leq x_{2}\leq 4} $ $ {\displaystyle y_{1},y_{2} \in \big\{0,1\big\} } $

MILP Solution: $ {\textstyle x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0} $, Lower Bound = 6
Lower Bound < Upper Bound, Integer cut: $ {\textstyle y_{1}- y_{2}\leq 0} $

Step 2a: Start from $ {\textstyle y=[1,0]} $ and solve the NLP below:
Minimize $ {\displaystyle f= 1+ \big(x_{1}\big)^{2} +\big(x_{2}\big)^{2} } $ Subject to $ {\displaystyle \big(x_{1}-2\big)^{2}-x_{2} \leq 0} $ $ {\displaystyle x_{1}-2 \geq 0} $ $ {\displaystyle x_{1}-x_{2} \geq 0} $ $ {\displaystyle x_{1} \geq 0} $ $ {\displaystyle x_{2} \geq 0} $ $ {\displaystyle x_{1}+x_{2} \geq 3} $ $ {\displaystyle 0 \leq x_{1}\leq 4} $ $ {\displaystyle 0 \leq x_{2}\leq 4} $ Solution: $ {\textstyle x_{1}=2, x_{2}=1} $, Upper Bound = 6
Upper Bound = 6 = Lower Bound, Optimum!
Optimal Solution for the MINLP: $ {\textstyle x_{1}=2, x_{2}=1,y_{1}=1, y_{2}=0} $