Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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!

share|improve this question
    
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
show 1 more comment

4 Answers

up vote 3 down vote accepted

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.

share|improve this answer
    
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
1  
@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
add comment

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.

share|improve this answer
    
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
add comment

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).

share|improve this answer
add comment

Removing this answer

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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