1
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ the maximum value of $w$ may be infinite. do you have any information about $A,b,q$? $\endgroup$ – Ilya Oct 10 '11 at 13:42
  • $\begingroup$ 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?" $\endgroup$ – John Oct 10 '11 at 13:46
2
$\begingroup$

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.

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

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

$\endgroup$

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.