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

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?

• I think you want $1.414x$ rather than $0.707x$ for the first half of the approximation of $\sqrt{x}.$
– prubin
May 26 at 17:52

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.
• Thanks! This is a demo example to demonstrate the working of the approach. In general, the program is encoded to break into n segments and there are m such components in objective. And hence the unnecessary equations, I think. I followed the template so audience can understand for more general case. I'll use this for the time being. May 27 at 7:26