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.
 A: 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.
A: 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$.
