Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Minimizing with constraints and linear function

  1. Jul 19, 2014 #1

    Maylis

    User Avatar
    Gold Member

    Hello,

    I am going over these slides and I am very confused on a couple parts. First of all on the first slide, I don't understand why a linear function has the form ##f(x) = c^Tx##. How is that equal to ##c_{1}x_{1} + c_{2}x_{2} + \dots + c_{n}x_{n}##. Wouldn't this depend on how you define ##c## to begin with? What if you just defined ##c## to have the proper matrix deimension to multiply with ##x##?

    On the second slide, I am particularly troubled by this sentence ''There is no dependence in the ##c_{\perp}## direction. The function value is constant along these lines.''

    I don't understand how the function value is constant. This is probably because I must not know what the function value us. Clearly along any of the given lines, the ##c_{\perp}## is increasing. What do they mean by the function value?

    Also, that leads to not understanding the green box on the second slide,
    ''For ##m##-dimensions, there is a ##(m-1)## dimensional plane, perpendicular to ##c##, and ##c^Tx## has no dependence in those directions''.

    What does this mean?
     

    Attached Files:

    Last edited: Jul 19, 2014
  2. jcsd
  3. Jul 20, 2014 #2

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Here both c,x are both vectors ; c=(c_1 c_2.... c_n) and (x_1 x_2....x_n)

    And the lack of dependence has to see with the fact that the function is identically zero along the

    perpendicular direction, as they prove. Is that your question? By definition/construction if 2 vectors v,w

    are perpendicular, their inner-product v^t w is zero . By linearity, f(0)=0, so, for any b, we have f(b v^t w )=bf(v^t w)=b0=0.

    then, for any b, by linearity, f(x+ bv^t w)=f(x)+ bf(v^t w)=f(x)+0=0.
     
    Last edited: Jul 20, 2014
  4. Jul 20, 2014 #3

    Maylis

    User Avatar
    Gold Member

    What do you mean the function is identically zero along the perpendicular direction? What exactly the is 'function value'?

    I am looking at the figure. Yes, I can see that along any of the individual lines, the vector ##c## is not changing. If you go to any other line parallel, it is in a new position. I don't see the relevance of this. I know I am missing something important, since they are going through a few slides to explain this.
     
  5. Jul 20, 2014 #4

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    The perpendicular direction is a multiple of a perpendicular vector by any constant, i.e., if x is perp. to x^t , then cx is in the perp. direction to x^t , for any choice of c. Then:

    i) x^t x=0 .

    ii) For L linear, L(0)=0, so L(cx^t x)=0.

    iii) For L linear , L(a + b)=L(a)+ (b) , and L(ca)=cL(a).

    Remember cx^t x is the perp. direction ,

    Then L(a+ cx^t x)=L(a) + L(cx^t x)=L(a)+cL(cx^t x)=L(a) +L(0) =L(a).
     
    Last edited: Jul 20, 2014
  6. Jul 20, 2014 #5

    Maylis

    User Avatar
    Gold Member

    I just watched this youtube video on linear programming.

    https://www.youtube.com/watch?v=M4K6HYLHREQ

    It seems like a standard optimization problem, but nowhere do I see all this matrix business that is present in the slides. There are some similarities, but why is what I'm doing have all this matrix stuff?

    Also, WWGD, in your post #4, I just see math and to be honest I don't know what it means or how to apply it to my specific question. Perhaps an explanation with words or graphics will aid me better. But thank you for taking the time to try and help me here.
     
  7. Jul 20, 2014 #6

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    Yes, the matrix layout is a bit over-the-top, and maybe even unnecessary ; it is just a generalization about linear functions with linear constraints, and expressing the problem mathematically, and rigorously .

    The issue/idea is that you graph each of the constraint lines. The result of the intersection of these constraint lines is a geometric figure called a polytope , say, P. Then , to find the optimal value , you only consider what happens at the vertices of the polytope . So you evaluate the function, here 40x+30y , only at each of the vertices of P, and out of all these values, you choose the best/optimal value.

    The matrix layout is IMHO ,just a general mathematical way of describing this, and I think is helpful only if you want to do something beyond this type of problem, but it may be confusing if you don't .
     
  8. Jul 20, 2014 #7

    WWGD

    User Avatar
    Science Advisor
    Gold Member

    One thing I forgot :
    Notice 40x+30y can be written as x^t x , in the form:

    (40 30)^t (x y),

    and the same is the case for the linear constraints.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Minimizing with constraints and linear function
Loading...