2
$\begingroup$

Let $D = {x ∈ R^3: |2x1 − x2 + 3x3 + 1| + |x2 + 2x3 − 2| + |5x2 − 3x3| ≤ 10}$. Express D as the feasible solution set of a linear system of inequalities (meaning, a system of the form $Ax ≤ b$).

How is the feasible solution set represented? Is this problem just a matter of removing the absolute signs and setting up two linear equations as such: $2x1 + x2 - 3x3 - 1 \le 10$ and $(2x1 + x2 - 3x3 - 1) \le 10$ ? Any help is appreciated.

$\endgroup$
1
$\begingroup$

Your original constraint is $$|2x_1−x_2+3x_3+1|+|x_2+2x_3−2|+|5x_2−3x_3|≤10$$

Now consider the case where $5x_2−3x_3 \geq 0$. If we knew that was always true we could write simply $$|2x_1−x_2+3x_3+1|+|x_2+2x_3−2|+5x_2−3x_3≤10$$ If we knew $5x_2−3x_3 \leq 0$ then we could write simply $$|2x_1−x_2+3x_3+1|+|x_2+2x_3−2|-(5x_2-3x_3)≤10$$

If we have both of these constraints, we capture both possibilities.

We can now extend that reasoning for all the $2^3$ possible combinations of terms being negative and non-negative, e.g.

$$+(2x_1−x_2+3x_3+1)+(x_2+2x_3−2)+(5x_2−3x_3)≤10$$ $$-(2x_1−x_2+3x_3+1)+(x_2+2x_3−2)+(5x_2−3x_3)≤10$$ $$+(2x_1−x_2+3x_3+1)-(x_2+2x_3−2)+(5x_2−3x_3)≤10$$ $$-(2x_1−x_2+3x_3+1)-(x_2+2x_3−2)+(5x_2−3x_3)≤10$$ $$+(2x_1−x_2+3x_3+1)+(x_2+2x_3−2)-(5x_2−3x_3)≤10$$ $$+(2x_1−x_2+3x_3+1)-(x_2+2x_3−2)-(5x_2−3x_3)≤10$$ $$-(2x_1−x_2+3x_3+1)-(x_2+2x_3−2)-(5x_2−3x_3)≤10$$ $$-(2x_1−x_2+3x_3+1)+(x_2+2x_3−2)-(5x_2−3x_3)≤10$$

If thats a bit confusing, consider $$|y_1| + |y_2| \leq 1$$ and draw it out. It makes a diamond centered on the origin, with its tips at 1 - the L1 "ball", in otherwords. There are four linear constraints that define that diamond, and they are $$y_1 + y_2 \leq 1$$ $$-y_1 + y_2 \leq 1$$ $$y_1 - y_2 \leq 1$$ $$-y_1 - y_2 \leq 1$$ Hopefully you see the connection.

$\endgroup$
  • $\begingroup$ Thanks for the detailed response. Do these linear inequalities represent the feasible solution set of D, as opposed to just the solution set? If so, what is the difference? $\endgroup$ – shinobutime Nov 2 '14 at 21:04
  • $\begingroup$ They are the feasible set D, the "solution set" is not so formally defined, but would need some sort of objective function to be defined, and it'd be the set of feasible solutions that have the same optimal objective function value. $\endgroup$ – IainDunning Nov 2 '14 at 21:13

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.