$\min\{f(x_1),\dots,f(x_n)\}$ with other constraints

Question

I have an optimization problem which goes:

\begin{align*} \text{Minimize:} \\ & \sqrt{x} + \sqrt{y} \tag{NL-objective} \\ \text{Subject to:} \\ &3x + 2y \geq 2 & \tag{C1} \\ &2x + 3y \geq 2 & \tag{C2} \end{align*}

I am attempting to piecewise linearize it. The idea is to approximate the non-linear function with a bunch of linear functions and solve the MILP problem. I break the function in 2 lines each, equidistant in x. For reference, the image is attached below.

As you can see, $\sqrt x$ can be written as $\min\{0.7071 x,0.5858 x+0.4142\}$ in its piecewise linear form, where minimum is over the lines. Similarly we can write a minimum of linear functions for $\sqrt y$. Generally, we write min of linear functions as MILP as given in image below.

$min\{f_i(x); i=1..n\}$" />

So, I get \begin{align*} \text{Minimize:}\\ &d_{1} + d_{2} \tag{Objective-PWL}\\ \text{Subject to:}\\ &3x+2y \geq 2 &\tag{C1} \\ &2x+3y \geq 2 &\tag{C2} \\ &y_{11} = \sqrt 2 x_{11} &\tag{first line, x} \\ &y_{12} = 0.5858 x_{12}+0.4142 &\tag{second line, x} \\ &y_{21} = \sqrt 2 x_{21} &\tag{first line, y} \\ &y_{22} = 0.5858 x_{22}+0.4142 &\tag{second line, y} \\ &0 \leq y_{11}, y_{21} \leq 0.7071 &\tag{1.i} \\ &0.7071 \leq y_{21}, y_{22} \leq 1 &\tag{1.i} \\ &d_{1} \leq y_{11}, y_{12} &\tag{2.i} \\ &d_{2} \leq y_{21}, y_{22} &\tag{2.i} \\ &d_{1} \geq y_{11} - 0.7071(1 - z_{11}) &\tag{3.i} \\ &d_{1} \geq y_{12} - (1 - z_{12}) &\tag{3.i} \\ &d_{2} \geq y_{21} - 0.7071(1 - z_{21}) &\tag{3.i} \\ &d_{2} \geq y_{22} - (1 - z_{22}) &\tag{3.i} \\ &z_{11}+z_{21}=1 &\tag{4.i} \\ &z_{21}+z_{22}=1 &\tag{4.i} \\ \end{align*}

However, there seems to be an issue with this formulation because there is no co-relation between $x, x_{11}, x_{12}$ What I think I have done is basically replaced the $\sqrt x$ and $\sqrt y$ with a bunch of lines, and converted the linear functions as $\min (f_1(x), f_2(x))$ and reformulated the min part as MILP. I do not know how to incorporate other constraints. Can someone help me figure out the correct formulation?

Answer 1

Your model contains a lot more items than are needed. Assume that $M$ is a sufficiently large positive parameter. I'll add two binary variables $z_x$ (used to linearize $\sqrt{x}$) and $z_y$ (used to linearize $\sqrt{y}$), and change your $d_1$ and $d_2$ to $d_x$ and $d_y$ just for clarity, resulting in the following model:

\begin{align*} \text{Minimize:}\\ &d_{x} + d_{y} \\ \text{Subject to:}\\ &3x+2y \ge 2 & \\ &2x+3y \ge 2 & \\ &d_x \ge \sqrt 2 \cdot x - M(1 - z_x)& \\ &d_x \ge 0.5858 x + 0.4142 -M z_x & \\ &d_y \ge \sqrt 2 \cdot y - M(1 - z_y)& \\ &d_y \ge 0.5858 y + 0.4142 -M z_y & \\ &z_x, z_y \in \lbrace 0, 1 \rbrace &\\ \end{align*}

A key here is that you are minimizing the sum of the surrogate ($d$) variables, meaning you don't have to worry about their being too large. You just have to make sure they are not too small.

If you use more than two linear segments in approximating the square root function, you need additional binary variables and an SOS1 constraint for each set of binaries.