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.
Best Answer
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.