System of linear inequalities to find a vector

[FightingWizard]

Homework Statement

Let P be the set of (x,y,z)^t in R^3, which satisfies the following inequalities:
-2x+y+z <=4
x-2y+z<=1
2x+2y-z<=5
x>=1
y>=2
z>=3

Homework Equations

I want to find the vector in the set with the maximal length.

The Attempt at a Solution

I have transformed the linear inequalities into matrix form:
(2 -1 -1 -4)
(-1 2 -1 -1)
(-2 -2 1 -5)

I solved it using Gauss elimination and got x = 2, y = 3 and z = 5, which satisfies the linear inequalities.
To find the length of the vector I did : sqr(2^2+3^2+5^2) = sqrt(38), which was my answer.

My instructor says that my solution is not correct. Can anyone help me?

 

[andrewkirk]

For each inequality, if you consider it as an equality instead, it specifies a plane. Hence the problem specifies six planes, which will form the boundary of a (probably irregular) polyhedron that is the set of possible points.

What you have done by solving that system of equations is find the point that is the intersections of the first three planes. There is no reason to expect that that point will be the one whose position vector has maximum length.

 

[FightingWizard]

For each inequality, if you consider it as an equality instead, it specifies a plane. Hence the problem specifies six planes, which will form the boundary of a (probably irregular) polyhedron that is the set of possible points.

What you have done by solving that system of equations is find the point that is the intersections of the first three planes. There is no reason to expect that that point will be the one whose position vector has maximum length.

How do I then find the vector with the maximum length in the polyhedron?

 

[Ray Vickson]

Homework Statement

Let P be the set of (x,y,z)^t in R^3, which satisfies the following inequalities:
-2x+y+z <=4
x-2y+z<=1
2x+2y-z<=5
x>=1
y>=2
z>=3

Homework Equations

I want to find the vector in the set with the maximal length.

The Attempt at a Solution

I have transformed the linear inequalities into matrix form:
(2 -1 -1 -4)
(-1 2 -1 -1)
(-2 -2 1 -5)

I solved it using Gauss elimination and got x = 2, y = 3 and z = 5, which satisfies the linear inequalities.
To find the length of the vector I did : sqr(2^2+3^2+5^2) = sqrt(38), which was my answer.

My instructor says that my solution is not correct. Can anyone help me?

Your inequalities imply that the feasible region in $R^3$ is a convex polyhedron. If you maximize the squared length $x^2+y^2+z^2$ (which will give you the same $(x,y,z)$ solution as the length itself), you see that you have a so-called convex function which is to be maximized over a convex polyhedron. There is a theorem about problems like that (convex maximization): an optimal solution occurs at a so-called "extreme point" of the feasible region, that is, at a corner point. The point you gave is, in fact, one of the corners, but there are several others. In principle, problems like yours can (and very often do) have numerous local optima, so in the worst case you would need to check the objective value (the squared length) at all the corners and then pick the one with the highest value. Intuitively, though, in your case you are trying to find the corner that is farthest from the origin, so that will cut down on a lot of the work. (Note: if you had been seeking a minimum instead of a maximum the problem would not have numerous local minima, and so there would be no need to enumerate lots of cases.)

I do think your answer is right. However, maybe the teacher objects to the method you used, which is quite naive and not at all rigorous (although, to be fair, it can be fixed up if you do a bit more work).

Your problem is a so-called Quadratic Programming Problem; see, eg.,
https://en.wikipedia.org/wiki/Quadratic_programming .