0
$\begingroup$

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!

Improve this question
$\endgroup$
6
  • $\begingroup$ 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. $\endgroup$
    – AFJ
    Commented Apr 20, 2010 at 1:04
  • $\begingroup$ 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? $\endgroup$
    – fedja
    Commented Apr 20, 2010 at 2:01
  • $\begingroup$ wow, original post was full of mistakes, sorry about that. It should be $|\alpha_i| \le 1$. $\endgroup$
    – AFJ
    Commented Apr 20, 2010 at 2:12
  • $\begingroup$ The last question: do you want to maximize the sum or to minimize it? $\endgroup$
    – fedja
    Commented Apr 20, 2010 at 2:24
  • $\begingroup$ Maximize, although I don't think it matters in answering my question, but you're right that it should be have been included. $\endgroup$
    – AFJ
    Commented Apr 20, 2010 at 2:27

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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)? $\endgroup$
    – AFJ
    Commented Apr 20, 2010 at 16:22
  • 1
    $\begingroup$ @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. $\endgroup$
    – user2734
    Commented Apr 20, 2010 at 21:44
0
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – AFJ
    Commented Apr 20, 2010 at 2:24

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .