1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

System of linear inequalities to find a vector

  1. Jun 27, 2016 #1
    1. The problem statement, all variables and given/known data
    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

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

    3. 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?
     
  2. jcsd
  3. Jun 27, 2016 #2

    andrewkirk

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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.
     
  4. Jun 27, 2016 #3
    How do I then find the vector with the maximum length in the polyhedron?
     
  5. Jun 27, 2016 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    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 .
     
    Last edited: Jun 27, 2016
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: System of linear inequalities to find a vector
Loading...