Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

max : $w = |q^T y|$
subject to
$A y \leq b$
$y \geq 0$

Please describe how one could solve the non-linear programming prob. above by using linear programming methods.

I tried changing $y$ to $y' - y''$ in the constraints and $y' + y''$ for the objective function. However, my Excel solver says that "the cells do not converge". How should I solve this?

Thanks a bunch!

share|improve this question
    
the maximum value of $w$ may be infinite. do you have any information about $A,b,q$? –  Ilya Oct 10 '11 at 13:42
    
no, but there's a hint saying: "Try breaking it into 2 linear programming problems. Then, could you think of combining them into just 1 problem?" –  John Oct 10 '11 at 13:46

2 Answers 2

up vote 2 down vote accepted

To follow the advise given to you, consider two problems: $$ \begin{cases} w^+ &= q^Ty^+\to\max, \\ Qy^+&\leq0, \\ Ay^+&\leq b, \\ y^+&\geq 0. \end{cases} $$ and

$$ \begin{cases} w^- &= q^Ty^-\to\max, \\ Qy^-&\geq0, \\ Ay^-&\leq b, \\ y^-&\geq 0. \end{cases} $$

Then $w = \max\{w^+,w^-\}$. Here matrix $Q = (q\quad0\quad\dots\quad0)^T$. With such decomposition you just consider two possible cases for the absolute value.

share|improve this answer
    
Thanks for your answer! However, is there any way to solve this using just 1 linear programming problem? –  John Oct 10 '11 at 17:05
    
@John: I'm afraid, I don't know such a way. –  Ilya Oct 10 '11 at 17:29

Hint: let $y = y_1 + y_2$ where $q^Ty_1 \le 0$ and $q^Ty_2 \ge 0$.

share|improve this answer

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.