2
$\begingroup$

Let's say I have a linear programming problem, i.e.

\begin{array}{rl} \text{maximize} & c^T x \\ \text{subject to} & {\bf A} x \le b \end{array}

without the non-negativity constraint on $x$ (i.e. $x \ge 0$). However, whenever I read about the linear programming, this constraint was always included. Why is that? To me, the statement above is equivalent to:

\begin{array}{rl} \text{maximize} & c^T x \\ \text{subject to} & {\bf A} x \le b \\ \text{and} & x \ge 0 \lor x \le 0 \end{array}

which can be considered as two, separate problems: one for $x \ge 0$ and one for $x \le 0$ (where the solutions can be combined into one). Also, the problem with the constraint $x \le 0$ can be transformed into the first one by introducing $x' = -x$. This means that I could use linear programming algorithms for solving problems without the non-negativity constraints. Is my reasoning correct?

$\endgroup$
3
$\begingroup$

Keep in mind that $\mathbf x$ is a vector here. So it's not true that one of the two options $\mathbf x\ge \mathbf 0$ (every component of $\mathbf x$ is nonnegative) and $\mathbf x \le \mathbf 0$ (every component of $\mathbf x$ is nonpositive) is necessarily true. We could have a mix.

Whenever we have a linear program \begin{align} \max\ & \mathbf c^{\mathsf T} \mathbf x \\ \text{s.t. } & A\mathbf x \le \mathbf b \end{align} we can turn it into a program in nonnegative variables by substituting $\mathbf x = \mathbf x^+ - \mathbf x^-$, where $\mathbf x^+ \ge \mathbf 0$ and $\mathbf x^- \ge 0$. (Any real number can be written as the difference of two nonnegative numbers.) So you can use LP algorithms that assume nonnegativity to solve such a program, but you will have to deal with twice as many variables.

Another option when dealing with a program like this one is to take the dual. The dual will have the form \begin{align} \min\ & \mathbf u^{\mathsf T} \mathbf b \\ \text{s.t. } & \mathbf u^{\mathsf T}A = \mathbf c^{\mathsf T} \\ & \mathbf u \ge \mathbf 0 \end{align} and so you have nonegativity constraints there.

$\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.