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

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

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

Subject to

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

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

$$x_{1}\geq 0$$

Failed to parse (Conversion error. Server ("https://wikimedia.org/api/rest_") reported: "Cannot get mml. Server problem."): {\displaystyle 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