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.

  • $\begingroup$ 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. $\endgroup$ – Michael Grant May 30 '15 at 17:08
  • $\begingroup$ Yes, for the case that $\mathrm{k_1}+\mathrm{k_2}<\mathrm{L}$, the feasibility region for the last inequality is non-convex! $\endgroup$ – 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.