Outer-approximation (OA)
Author: Yousef Aloufi (CHEME 6800 Fall 2021)
Introduction
Theory
Example
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 1a: 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)} $