Minimizing with constraints and linear function

In summary, the slides explain how a linear function can have the form ##f(x) = c^Tx## where c is a constant. However, there is no dependence in the ##c_{\perp}## direction. The function value is constant along any given line parallel to c. Also, the lack of dependence in the ##c_{\perp}## direction has to do with the fact that the function is identically zero along that direction.
  • #1
gfd43tg
Gold Member
950
50
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?
 

Attachments

  • linear functions.pdf
    1.1 MB · Views: 310
Last edited:
Physics news on Phys.org
  • #2
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:
  • #3
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.
 
  • #4
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:
  • #5
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.
 
  • #6
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 .
 
  • #7
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.
 

What is the purpose of minimizing with constraints and linear function?

The purpose of minimizing with constraints and linear function is to find the optimal solution to a problem while taking into account any limitations or constraints that may exist. It allows for the most efficient use of resources and helps to achieve the best possible outcome.

What are constraints in the context of minimizing with constraints and linear function?

Constraints refer to any limitations or restrictions that must be considered when finding the optimal solution to a problem. These can include physical, financial, or other practical limitations that must be taken into account.

How is linear function used in minimizing with constraints?

Linear function is used to represent the relationship between variables in a problem and to create a mathematical model that can be minimized. By using linear equations, it is possible to find an optimal solution that satisfies all of the given constraints.

What are some common techniques for minimizing with constraints and linear function?

Some common techniques for minimizing with constraints and linear function include linear programming, simplex method, and gradient descent. These methods use mathematical algorithms to systematically find the best possible solution to a problem while taking into account all constraints.

What are some real-world applications of minimizing with constraints and linear function?

Minimizing with constraints and linear function has numerous applications in various fields such as economics, engineering, and logistics. Some examples include finding the most cost-effective production plan for a company, optimizing transportation routes, and creating efficient resource allocation strategies.

Similar threads

Replies
2
Views
1K
  • Linear and Abstract Algebra
Replies
9
Views
858
  • Linear and Abstract Algebra
Replies
8
Views
996
Replies
7
Views
580
  • Linear and Abstract Algebra
Replies
5
Views
1K
  • Linear and Abstract Algebra
Replies
1
Views
3K
Replies
3
Views
2K
  • Quantum Physics
Replies
8
Views
2K
  • Calculus and Beyond Homework Help
Replies
21
Views
758
Replies
12
Views
660
Back
Top