Hi, everyone. We'll come back to operations research. So we're still as our modeling and applications course. And today we're going to jumping to our new topic. We will talk about non-linear programming. So, first I will do some very brief introduction. And then we will talk about two examples. In these two examples, you will naturally see the problem is nonlinear. So we really cannot use integer programming or even linear programming to deal with that. So, we will go through these examples to show you indeed non-linear programming may be used in some way, okay. And then, we will talk about two issues about linearization. So linearization means, you are given a problem and that your first attempt to do the formulation is to make it nonlinear. You will see that in many cases your formulation has something to do with the maximum or minimum function. Or something sometimes you have products of decision variables. And in that case, the program is not linear, but actually there are some ways for you to linearize it if some condition holds, okay. So that's something we will talk about in this particular course. Okay, so that see some very brief examples. In many cases we want to price our products. So for example, suppose there is a retailer. The retailer is buying one product at a cost which is c. So you'd pay $5 to get one product, $10 to get another one. And then the retailer needs to decide a unit retail price, which is p. Once I do that, the demand would be given as a function of p. In this way. So we would see that once we increase our price, our demand would go down in a way that is a- bp. So a and b are two parameters. I know the values of a and b. And that somehow means according to my past experience, I know how consumers are sensitive to my price. So I now want to do profit maximization. I want to set a price so that I can maximise my profit. So in this case, my parameters are a, b, and a c, okay? And then once I collect this information, I want to set my decision variable which is p. The only constraint I have in this particular case is probably that, okay? My price cannot be negative. All right, I want to choose $5, $10, $12 as my unit price. I guess I cannot state a negative price that does not make sense. And then find out We may reach our formulation. So we want to maximize this particular function. p- c is our sales margin, okay? When I sell one product I may earn p minus c dollars. For example, if my sin my price will be 12 per unit. But if my cost is $5 per unit, then if I may sell one unit, I'm going to earn $7. If I can sell two units, I'm going to earn 7 times 2. $14 Okay. So this part is my sales margin and then the other part is my demand. So my profit actually is the product of these two terms. Okay? It depends on for each item how much I may earn, and depends on how much I may sell. Okay. So this is my profit function and the only constraint I have is p should be non negative. Okay. So there are several ways to express this particular formulation. Sometimes we want to write it in this way. Or sometimes some people will say okay, this constraint is so simple. I'm going to put it below the maximization operator. So, in either way, you understand they are talking about the same thing. So in this case this is nonlinear, right because p times p. This is p square, and this is obviously not a linear function. So that's why we say this guy is linear program. Let's see another example. So in this example you are given a piece of square paper, and the lens at one side is a, okay. So a maybe 10 centimeters, 12 centimeters, something like that. We now want to cut down four small squares. Here, here, here and here. And once we do that, we want to make them equal size. So this particular dense would be small d. And once I do that I'm going to fold this paper to create a container in this way, okay? So you may see that for this particular square, that case give us the base for this particular container. And then the height of this particular container would be this small d. All right? So this would be how I may get a container by folding my paper. So now the question is. How may we choose D, the lens here, how can we choose D to maximize the total volume of the container. So, again this is a maximization problem. And again this is an optimization problem. And all we need to do is to somehow formulate our problem to describe the quantity that we are interested in. So we all know that the volume of this particular container is the area of the base multiplied by the height. So the base would have this area a- 2d or a- 2d square. And then multiplied by the height. So a- 2d square times d. That would be the volume. We want to choose a small d to maximize this volume. Okay, again, you have square terms, you have product terms. So this is a nonlinear program. Suppose we want to locate a hospital. So in a country, there are several cities, let's say here, here, here, here, here, and here. So there are many different places where we have cities, many people live there. So For these cities, we all know their locations. For example, this one may be at 8 3. This one may be at the 7 1 and so on. So we know where they are. And then we want to locate a hospital somewhere so that we may minimize the average Euclidean distance from the cities to the hospitals. So what does that mean? That say I locate my hospitals here. All right. Then in this case, I'm going to have traveling distance from all these cities to this particular hospital. So I may have several options. For example, maybe I want to choose the hospitals to be here. Well, if I do that, then I may see that the distance would be somewhat different. And in each setting, I would have different average Euclidean distance, right? So our target here is to choose a location to build our facility. And then we want to minimize the average Euclidean distance. So how can we do that? We have n cities. For each city, I know its location. I also know where to build my facility, okay. I'm going to build it at somewhere (x, y). Once I have that then this particular thing would be the Euclidean distance from my hospital to city I. And then I have so many cities, I'm going to add all these distances. I probably don't need to really divide the whole term by n, I don't need to do that. because whether I do this or not, the answer would be the Sam n. Because divided by n is nothing, but we divided the whole thing by a constant. So, in this case, minimizing the average distance and minimizing the total distance is the same. So here you may see again you have square terms, you even now have square root term. So the whole thing here is again nonlinear. So in all these three examples, we may see that we are having a very natural nonlinear program. Because the world by nature in many cases, are just nonlinear, okay? So the trade offs can only be modeled in a nonlinear way. So that's why linear programming integer programs are not useful in these particular cases. In general, a nonlinear program is always formulated in this way. I want to minimize some function, subject to several constraints. And the somehow some of these F or G functions, some of them are nonlinear, right? So this would be a linear program if all these functions are actually linear. This would be a nonlinear program if at least one of them is nonlinear. So here, some people may have different definitions about linear and nonlinear programs. So for linear programs, the definition is clear. All these functions should be linear. Some people would say, okay, nonlinear programs does not include linear programs. So they will say, nonlinear programs are not linear programs. So, typically I follow this definition. I would say a program is either linear or nonlinear. But a nonlinear program is not a linear program. Okay? Some people will say no, no, they don't think that way. They will say nonlinear programs actually contents linear programs, or they will say any program Graham is a non-linear program. Non-linear program is a generalization of linear programs. Or some people would say that. So when you read articles, when you read textbooks, maybe you need to pay attention about their definitions. But anyway, I guess we all agree. Non-linear programs are much more general than linear programs. So that's why in many cases we really need to do non-linear programming. Okay, and that's also a very important part for this whole course. The course about formulating and optimizing nonlinear programs is called nonlinear programming. In general, the formulation would be easy. We don't need to worry too much about linearization. We don't need to worry too much about using integer variables to do this, do that blah, blah, blah. So you probably still recall that in the previous lecture when we are talking about integer programming formulation. There are many weird ways to deal with the constraints because M variables binary whatever. For non linear programs formulating a nonlinear program is typically easy, because actually now you don't have any restriction. But then optimization would be hard. So in this lecture, we don't really talk about how to solve nonlinear programs. We only try to show you in many cases you need nonlinear programming formulation. Okay, but still we will talk about a lot of places a lot of situations that you would be convinced that nonlinear programming would be really useful. Today, let's focus out about formulation. And maybe in the future, let's talk about algorithms.
