1. Not finding help here? Sign up for a free 30min 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!

Feasible Directions & FONC

  1. Mar 19, 2017 #1

    Nugso

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data

    [tex] \text{Minimize } f(x) [/tex]
    [tex] \text{Subject to } \Omega [/tex]

    where [tex] f:R^2 → R \text{ is given by } f(x) = -3x_1 \text{ where } x = [2,0]^\top \text{ and } \Omega = \{x: x_1 + 2x_2^2 \leq 2\}[/tex]

    [tex] \text{Does the point } x^* = [2,0]^\top \text{satisfy F.O.N.C?} [/tex]


    2. Relevant equations

    [tex] d^T\nabla{f(x^*)} \geq 0 [/tex]

    has to be satisfied for FONC.

    3. The attempt at a solution

    I know FONC, but what I'm having trouble understanding is determining feasible directions. For example, in this case, the point is on the boundary.

    [tex] x + ad = [2,0]^\top + a [d_1, d_2]^\top[/tex]

    Now, applying the constraint, I have

    [tex] 2ad_1 + 2(ad_2)^2 \leq 0[/tex]

    From there, it seems like d_2 is an arbitrary choice, while d_1 has to be chosen accordingly. But, also, since the point is on the corner of the boundary, doesn't that mean that d_2 has to be in some specific direction as well?
     
  2. jcsd
  3. Mar 19, 2017 #2

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    What does the term "FONC" mean? I get the "FO" = "first-order" part, but what is NC?
     
  4. Mar 19, 2017 #3

    Nugso

    User Avatar
    Gold Member

    Hi Ray. It's First Order Necessary Condition.
     
  5. Mar 19, 2017 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    I suggest you draw some feasible directions ##\vec{d} = [d_1,d_2]##. Remember that a point of the form ##\vec{x} = [2,0] + t \vec{d}## only need to satisfy the constraint for small, positive ##t##. In particular, if ##d_1=0## then also you need ##d_2 = 0##. Also, of course, you cannot have ##d_1 > 0##; why not?
     
  6. Mar 19, 2017 #5

    Nugso

    User Avatar
    Gold Member

    When I imagine (draw), a coordinate system, with x and y, with our point on the corner of the boundary, I'm inclined to say both ##d_1## and ##d_2## needs to be nonnegative, because otherwise ##d## wouldn't be a feasible direction.

    However, as I've said, if I apply ##d## to the constraint inequality, I only get ##d_1 \geq0##

    For example, if I had the same constraints, but this time our point was only on the boundary (not necessarily corner), I could see why it'd be only ##d_1 \geq0##. But I'm having trouble understanding this.
     
  7. Mar 19, 2017 #6

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    By definition, ##\vec{d} = [d_1,d_2]## is a feasible direction at ##\vec{x}_0## if ##\vec{x} = \vec{x}_0 + t \vec{d}## is feasible for all small enough ##t > 0## (note the sign!). So, for ##\vec{x}_0 = [2,0]##, is ##\vec{d} = [1,0]## feasible? Is ##\vec{d} = [1,1]## feasible? Is ##\vec{d} = [1, -0.01]## feasible? Is ##\vec{d} = [-1,10]## feasible? What about ##\vec{d} = [-1, -1/2]?##
     
  8. Mar 19, 2017 #7

    Nugso

    User Avatar
    Gold Member

    Okay, so, if I were to use the definition, I'd say only ## d = [-1, 10] ## and ## d = [-1, -1/2 ] ## are feasible. However, when I'm trying to picture it, I get the following:

    yu4UwPH.png

    with the blue curve and line [2,-2] the set red lines inside of the set, I think the feasible directions have to be inside the set because we're right at the corner. So by that logic

    ## d = [1,0] ## and ## d = [1,1] ##are also feasible. I think either I'm drawing something incorrect, or I just simply can't interpret it.
     
  9. Mar 19, 2017 #8

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    If you go any positive distance at all along ##\vec{d} = [1,0]## you go into the infeasible region (the unshaded region in your drawing)! Same for ##\vec{d} = [1,1]##.
     
  10. Mar 19, 2017 #9

    Nugso

    User Avatar
    Gold Member

    Ohh! I think I got it now! Thanks!
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted