Minimizing with constraints and linear function

[gfd43tg]

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?

 

[WWGD]

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.

 

[gfd43tg]

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.

 

[WWGD]

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).

 

[gfd43tg]

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.

 

[WWGD]

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 .

 

[WWGD]

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.