# Linear optimization with “max” function (convex) constraint

I am working on a linear optimization problem which has a non-linear constraint. Suppose $x = [x_1 x_2]^T$, the problem is

$$\min_{x} \quad c^T x \\ \mathrm{s.t.} \quad Ax \leq b\\ x \geq 0 \\ \max (x_1, \mathrm{k_1}) + \max(x_2, \mathrm{k_2}) \geq \mathrm{L}$$ where $\mathrm{k_1}$ $\mathrm{k_2}$ and $\mathrm{L}$ are fixed values. As far as I know the "$\max$" function is convex and the sum of convex functions will be convex, so the problem would no longer be assumed as a linear optimization problem.

Thanks in advance for any ideas about solving the problem or converting this problem into a linear optimization problem.

• This is not, in fact, a convex problem. The left-hand side of the inequality is indeed convex as you say, but the entire inequality is non-convex. – Michael Grant May 30 '15 at 17:08
• Yes, for the case that $\mathrm{k_1}+\mathrm{k_2}<\mathrm{L}$, the feasibility region for the last inequality is non-convex! – Mahdi Jun 1 '15 at 11:29

We may assume that $k_1+k_2 < L$, otherwise we simply could drop the constraint $\max(x_1,k_1)+\max(x_2,k_2)\geq L$ and solve the remaining system.

Now let $P=\{x\mid Ax\leq b, x\geq 0\}$. Further we define

\begin{align*} P_1&=P\cap\{x_1 \geq k_1, x_2 \geq k_2\},\\ P_2&=P\cap\{x_1 \geq k_1, x_2 \leq k_2\},\\ P_3&=P\cap\{x_1 \leq k_1, x_2 \geq k_2\},\\ P_4&=P\cap\{x_1 \leq k_1, x_2 \leq k_2\}. \end{align*}

We have $P=P_1\cup P_2\cup P_3\cup P_4$. Furthermore, it holds

if $x\in P_1$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow x_1 + x_2 \geq L$;

if $x\in P_2$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow x_1 + k_2 \geq L$;

if $x\in P_3$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow k_1 + x_2 \geq L$;

if $x\in P_4$, then $\max(x_1,k_1)+\max(x_2,k_2) \geq L \Leftrightarrow$ false (since we assume $k_1+k_2<L$).

Now, let

\begin{align*} P_1'&=P_1\cap\{x_1+x_2\geq L\}\\ P_2'&=P_2\cap\{x_1+k_2\geq L\}\\ P_3'&=P_3\cap\{k_1+x_2\geq L\}\\ P_4'&=\emptyset\quad\mbox{(see above)} \end{align*}

and $P_1'\cup P_2'\cup P_3'$ is the set of feasible solutions of the originating system. Note although $P_1'$, $P_2'$ and $P_3'$ are convex, this set does not need to be convex.

Finally we minimize $c^Tx$ over each $P_i'$ individually. Taking the minimum of these values should be the solution of the originating problem.

Building on William's approach, we can express the problem as a mixed-integer program: \begin{array}{ll} \text{minimize} & c^T x \\ \text{subject to} & A x = b \\ & x \geq 0 \\ & x_1 + x_2 + L z_1 \geq L \\ & x_1 + k_2 + (L-k_2) z_2 \geq L \\ & k_1 + x_2 + (L-k_1) z_3 \geq L \\ & k_1 + k_2 + (L-k_1-k_2) z_4 \geq L \\ & z_1 + z_2 + z_3 + z_4 \leq 3$\\ & z_1,z_2,z_3,z_4 \in \{0,1\} \end{array} The$z_i$variables serve to relax each of the four constraints. By ensuring that at least one of the$z_i$values is zero, we ensure that at least one of the constraints is active at the solution. If you know that$k_1+k_2\geq L$, you don't need the$z_4$constraint, and and you can change the last inequality to$z_1+z_2+z_3\leq 2\$.