What is invisible?

Art, Design and Technology

Star Wars and Children

When you want to start to learn something new, its very important to start from a good point. Even in optimization the starting point is very important and in many cases will change the solution you will find and also number of iteration you may have. So in many contexts starting point is crucial. Most of us had read many books and had many courses but sometimes we feel that this book is better than that or this professor describing things better than other professors. However, this feelings may vary from person to person and in some cases for some of us some books feels written in another language! O.K. lets not miss the point! 

One of my friends in EPFL is doing some experiments on children to measure level of learning during different periods of childhood and in one of their studies they tried to teach some children who learned music and notes before incorrectly (actually reteach them) and then compare them to children who have no idea about music before and just learned it for the first time. He told me that seems that its more difficult to reteach children who learned the notes inaccurate before and that reminds me the sentence from the Star Wars: "Sometimes you have to unlearn what you have learned!".

Anyways, I reached a very good book about optimization by Prof. Yang which is published in 2010 by Wiley. And as mentioned before it doesn't mean other books are not good, I just can make more connection with this book! 

You can have a look to this book here. I hope you like it!

Continue on Lagrange multipliers

So in the previous post I was talking about Lagrangian Multipliers and I created an exe file to show the objective function with one constraint. You can reach the file here which includes an exe file and a MCR file in case you don't have Matlab installed on your machine (the exe file compiled and runs just on windows machines). You can visualize the function and the constraint with this file and I will show you an example of that.

The example comes from one of my classes (CE 590 - Modeling and Analysis of Civil Engineering Systems) and called OMAGOSH problem.

Here is the problem description: 

"You are an engineer advising the State Department of Natural Resources as it manages Lake Omagosh. The water quality index, x, can be improved, and better fishing would result. Boat launch facilities could also be added (measure in units, y). The benefits of fishing and pleasure boating are 11x+8y-2xy, in million dollars. The costs are x+2y in million dollars. Only 17 million dollars are available. Use the Kuhn-Tucker approach to evaluate this problem. What is the meaning of the value of the Lagrange multiplier for this problem?"

First of all, lets talk abut Kuhn-Tacker conditions. Because we have inequality in our constraint and we would like to solve this problem with Lagrangian approach and since we can solve this problem with Lagrangian method if we have equality, we can change our inequality in our constraint to equality by adding a slack variable to our constraint. 

So, if we have equality constraint we will have something like: g(x,y)=b

but here we have inequality: g(x,y)<= b and in the Omagosh problem: g(x,y)<= 17.

we can change the inequality to equality as mentioned by adding a slack variable: g(x,y)+s=17.

's', here is our slack variable and its worth to mention that 's' is always positive, we can just put 's^2'. 

You can reach the solution I did by hand here and please let me know if you have any question.

  

In this picture you can see the objective function and constraint.

Lagrange Multipliers

If you are familiar with Lagrange multiplier you are lucky! You can make money by doing this concept and applying that since usually Econ people using this concept. You can get idea of it from the wiki page but since Im in Civil Eng. I will try to explain it in my way.

If you had some structural courses you may heard about virtual work. So in a very simple case lets say what will happen to my structure's forces (for example if we are interested to forces) here to my single bar if I just change the displacement one unit. Economist usually using this concept and they call it shadow price and in many cases it meas if I change the limitation or constraint I have over my resources just one unit, what will happen to my cost or benefit!

Something that we need to be careful about is Lagrangian multiplier's sign. The sign of the multipliers can be positive, negative or in some case we may not have any sign (Lambda = 0) (I used Lambda because usually it used for Lagrange multipliers).

Usually you are trying to maximzie or minimize a objective function, I call it here: f(x,y) 

'f' is my objective function and 'x' and 'y' are variables. I show the constraint function here by: g(x,y). The constraint function as its name shows is limited or constrained by something.

Sometimes for example when we want to go shopping we have limited amount of money and then we are constraint by the amount of money we want to spend, or in many problems we are limited by time, especially when we have exams!!  ;)

g(x,y)<b

('b' here is our constraint.)

other situation is when we are limited at the other end, for example you should be 16 at least to get the driver license, or another example is, you want to do business, you bought something for lets say for 5 box, and you want to make at least 10% benefit, so your price should be greater than $5.5, and if you can sell your thing for more than that you are lucky!

g(x,y)>b

it is worth to mention that here I just have two variables but you may have thousands of them. The concept is the same.

You may have one or more than one constraint function and also you may have more than one objective function that called multi-objective function which we will talk about that later on.

You can get information about your function by the sign of the Lambda.

Lambda is how the objective function changes if I change the limitation (constraint) one unit

Lambda = df/db

In general there are two cases:

1) we are maximizing:

     1-1)  g(x,y)<b

               Lambda is positive

      1-2) g(x,y)>b

               Lambda is negative

2) we are minimizing:

      2-1)  g(x,y)<b

               Lambda is negative

      2-2) g(x,y)>b

               Lambda is positive

so for example when we are maximizing and g(x,y)<b, we are trying to reach the max but the constraint limits us and going uphill our slope will be positive.

If you want to visualize the case 1-2, its like the case 1-1, we want to go uphill again but its like we are going backwards, so if you walk backward and look to your front your slope is negative but the truth is you are going backward toward the summit.

Cases, 2-1 and 2-2 are the same, for example for the case 2-1, we want to minimize and if you walk downhill, when you look at your feet, your slope is negative. The backward walk is again is the same for the case 2-2.

Hello world!

This is my first post here and in this blog I will try to post more about modeling and optimization methods. The name of the blog is scary for me at least, I don't know exactly why I chose that name. Many people like to have interesting and sophisticated names and many times especially if you are in graduate school you will be hear such names which will scares you off, 

 

BUT don't worry everything here is about simplification. I am a visual person or at least I consider myself a visual person and I am trying absorb concepts by visualizing and it works many times because almost everything we have are in 3D world (not really!). However sometimes, usually in optimization world things are in more than three dimensions while visualizing again can help us to understand the problem. 

I have a little question for you, what is your impression from picture above?! Yes, you are right, its a ghost, a baby ghost!!

Actually, its just a picture of a cute baby, nothing more!! which turned to black and white and focused by a red circle! Many times we see things like that, even a simple problem, or a very lovely baby! In my opinion sometimes its good to be like that and I think its because of our imagination. Imagination is infinite (that's impressive for me that we can't count it)  and as Einstein said: “Logic will get you from A to Z; imagination will get you everywhere.” 

Anyways, by giving the picture I just tried to show you that sometimes fancy names are scaring us, like the title of this blog with courier font which is very nerdy, while if we just try to see the concept there is nothing scary over there.

Other thing I would like to mention in my first post is mistakes that might happen when I will try to explain something or algorithm. I am in Civil and Environmental Engineering and I will try my best to have perfect posts, meanwhile if you are in OR or CS or anyways see some mistakes and errors, I would be more than happy to correct them and learn more from you, so just leave a comment and we can work on them.