Outer-approximation (OA)

Author: Yousef Aloufi (CHEME 6800 Fall 2021)

Example

Minimize

$$f(x)=y_{1}+y_{2}+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2y_{1}\geq 0$$

$$x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0$$

$$x_{1}+y_{1}-1\geq 0$$

$$x_{2}-y_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3y_{1}$$

$$y_{1}+y_{2}\geq 1$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

$$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

$$f=2+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2\geq 0$$

$$x_{1}-x_{2}\geq 0$$

$$x_{1}\geq 0$$

$$x_{2}-1\geq 0$$

$$x_{1}+x_{2}\geq 3$$

$$0\leq x_{1}\leq 4$$

$$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]}$ :

$$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}$$

$$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 )}$$

$$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}$$

$$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

$$\alpha$$

Subject to

$$\alpha \geq y_{1}+y_{2}+5+4{\big (}x_{1}-2{\big )}+2{\big (}x_{2}-1{\big )}$$

$$-x_{2}\leq 0$$

$$x_{1}-2y_{1}\geq 0$$

$$x_{1}-x_{2}-3{\big (}1-y_{1}{\big )}\geq 0$$

$$x_{1}+y_{1}-1\geq 0$$

$$x_{2}-y_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3y_{1}$$

$$y_{1}+y_{2}\geq 1$$

$$0\leq x_{1}\leq 4$$

$$0\leq x_{2}\leq 4$$

$$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

$$f=1+{\big (}x_{1}{\big )}^{2}+{\big (}x_{2}{\big )}^{2}$$

Subject to

$${\big (}x_{1}-2{\big )}^{2}-x_{2}\leq 0$$

$$x_{1}-2\geq 0$$

$$x_{1}-x_{2}\geq 0$$

$$x_{1}\geq 0$$

$$x_{2}\geq 0$$

$$x_{1}+x_{2}\geq 3$$

$$0\leq x_{1}\leq 4$$

$$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}$