# Linear programming piecewise linear objective

I am fairly new at linear programming/optimization and am currently working on implementing a linear program that is stated like this:

max $\sum_{i=1}^{k}{p(\vec \alpha \cdot \vec c_i)}$

$s.t.$

$|\alpha_j| \le 1$

Where p(x) = 2x if x < 0, x otherwise, and $\vec c$ is a constant

The p(x) function is what's troubling me, since one can only determine x's sign after an assignment of $\vec \alpha$. How can I remove the function p from the objective and express this objective equivalently as a linear combination of the variables?

Thank you!

-
oh, I forgot to index $\vec c$ by i, so the alpha vector in the sum is the same for each term, but each scalar is different. Also, the i subscript on the alpha constraints is unrelated to the index in the sum. Sorry for any confusion. –  AFJ Apr 20 '10 at 1:04
I've corrected the formula for you but I'm still totally puzzled by the $|\alpha_i|\le 0$ condition. What is that really supposed to be? –  fedja Apr 20 '10 at 2:01
wow, original post was full of mistakes, sorry about that. It should be $|\alpha_i| \le 1$. –  AFJ Apr 20 '10 at 2:12
The last question: do you want to maximize the sum or to minimize it? –  fedja Apr 20 '10 at 2:24
Maximize, although I don't think it matters in answering my question, but you're right that it should be have been included. –  AFJ Apr 20 '10 at 2:27

## 4 Answers

Sorry for making you wait 14 hours unnecessarily but you are partially guilty yourself: if you posted a correct and full version of the question from the beginning, you would get the answer in 5 minutes. Keep it in mind when you ask a question on a public forum next time.

Your problem is equivalent to maximizing the linear expression $\sum_i y_i$ under the linear restrictions $\alpha_j\ge -1$, $\alpha_j\le 1$, $y_i\le c_i\cdot\alpha$, $y_i\le 2c_i\cdot\alpha$. It is as simple as that but it is crucial that your $p$ is concave and that you maximize.

-
Thank you very much. That transformation makes intuitive sense to me, I'm going to try it out. Would you mind briefly explaining how you came about that solution (both for my benefit and for others that come across this later)? –  AFJ Apr 20 '10 at 16:22
@AFJ: Note that your function $p$ is actually $p(x)=\operatorname{min}(x,2x)$. By setting $y_i:=p(\alpha\cdot c_i)=\operatorname{min}(\alpha \cdot c_i,2\alpha\cdot c_i)$, your problem becomes: max $\sum y_i$ s.t. $|\alpha_j|\leq 1$ and $y_i=\operatorname{min}(\alpha\cdot c_i,2\alpha\cdot c_i)$. But clearly you will get the same maximum by relaxing $y_i=\cdots$ to $y_i\leq\cdots$. Now use the fact the $y_i\leq \operatorname{min}(a,b)$ iff $y_i\leq a$ and $y_i\leq b$ to get fedja's conclusion. –  user2734 Apr 20 '10 at 21:44

The easiest way to deal with this is to split it into two problems: one obtained by adding the inequality $x \ge 0$ and using the objective function $2x$, and the other by adding the inequality $x \le 0$ and using the objective function $x$. Incidentally, I don't think that you mean the inequality $|\alpha_i| \le 0$. Perhaps you mean to omit the absolute value?

I think that the best way of dealing with this is to solve the dual problem. I'll have to think about the details, but that should get the number of vertices in the polytope down to a manageable level.

-
It seems to me that it can't be split into the maximum of just two problems, since it is a sum over $p(x_i)$ where the $x_i$ can be different, resulting in $p(x_i)$ being $2 x_i$ or $x_i$ depending on the sign of $x_i$, for a total of $2^k$ ways that p can play a role in the objective. An exponentially growing number of separate problems to solve won't be doable, since $k$ can be $25$ or more. Please correct me if I'm wrong. –  AFJ Apr 20 '10 at 2:24

I am wondering if something similar to Fedja's answer works if p(x)=2x for x<5 and p(x)=x for x >= 5. In this case p(x) is discontinuous at 5 where as in the given problem p(x) is continuous at 0. Now you no longer have the case that y=min(2x, x).

-

Removing this answer

-