Wolfram Optimization

Hi, my name is Paritosh Mukasi. I'm a clinical developer at Wolfram Research. And I'll be talking about the various optimization functions and how you can solve various optimization problems using Wolfram language. My name is Paritosh Mukasi. I'll be talking about how we solve various optimization functions in Wolfram language. Now, there are several different optimization problems. They end up coming in a wide variety of flavors. You could have it as linear, nonlinear, you could have global, mixed, integer, parametric, symbolic. You could have fitting problems. All of them fall under the umbrella of optimization. And in order to solve these problems, we have several functions. Now, I'm not going to be able to go through these topics individually. Nina, who has a talk coming up after mine, will be able to address some of the topics in specific. But in order to solve these optimization problems, we end up using a whole number of functions. The most obvious ones that you might be thinking about are N minimize or minimize or find minimum. But we also have a whole bunch of other functions that allow you to solve specific problems, specific optimization problems. So the way I'm going to structure this talk is I'm going to give you a whole bunch of, show you a whole bunch of examples and work through those examples to give you an idea of what to look for, how to solve it, what are the gotchas, how do you ask questions about the optimization problem so that you get relevant information out of it? So let's jump into examples right now. So the first example I want to, I want to start with is we want to design a cantilever beam. We want to minimize the weight of this cantilever beam. And the way this beam is set up is it's made out of a bunch of blocks. Each one is of unit length. And since we want to minimize the weight and it's a unit length, we want to find the width and the height associated with each one of these blocks so that its weight is minimized while still being able to meet the parameter specifications for this cantilever beam. So in this case, this diagram shows four, but I'm going to use 16 blocks. Okay? Typical mechanical engineering problem, you specify the stress constraints and you notice that the way we're specifying the stress constraint is almost literally as you would write it down in a textbook. Right? And that's the first thing I wanted to bring to your attention, is that we can write it in such a natural way, but we have a massive pre processing step. The framework that parses everything, makes everything into a canonical form that Allows a very good representation when it actually goes to the solver. Ok, so you specify the stress constraint, then you have to specify the deflection. And because each one of the blocks are connected to each other, the deflection depends on each other. So that's why there's a do loop here and I'll evaluate that. And of course the deflection at the end of it shouldn't go beyond a certain value, which is Y max, which we'll define a little later. And we'll also specify that the width and the height cannot be. Has to be within a certain range. So that kind of blocks the problem in. Okay, and so that's your dimension constraint. And now you specify the parameters, whatever they might be. So you specify the Young's modulus, you specify the force. Force, the maximum stress it can take and the maximum deflection it can take. All right? And then you go ahead and solve the problem. It's literally in steps. It's five to six lines of code to solve a problem like this. And you'll notice that the result comes back really quickly. And the reason for that is because N minimize is doing a lot of work behind the scenes. It's going and it's analyzing the problem at hand, figures out what the objective is, figures out what the constraints are and based off of that it classifies the problem and then sends it off to that specific solver. So in this case the weight. It turns out that this problem is a geometric optimization problem. So it recognizes that and sends it off to a solver that can solve it, that can solve geometric optimization problems efficiently. If I were to on the other hand, just go method Nelder Mead. Let's say you'll see that the timing is now it's going to take a lot more time. It'll come back with the same result. But you'll see that that 0.15 second is it even. Evaluating see takes 10 seconds. There is a big mechanism that is working behind the scenes to make sure that the problem gets properly classified. And the most efficient solution is given to you in the least amount of time. Once you get the solution, of course you can plot it. Cursor and that's your result. Okay, so that's the first takeaway. I want you to. The reason for showing you this example was that I wanted to bring to your attention that there is. It's not just brute force. It chooses a method and just goes off and does its thing. There is a lot of pre processing happening. The constraints and the objectives get canonized they're put in a standard form so that you get the most efficient solution. All right, let's look at a second example. Now, this is called, this example is a fitting example, but it doesn't fall under the category of a minimization. Falls under the category of a fitting example, but not just any fitting example. So let's say. So this particular example is called basis pursuit. And I'll explain to you what that means. So what you have is a signal. So this is a signal. What we want to do is fit, get a representation of this signal through fitting a bunch of basis functions. But the basis functions we have are like a library of maybe 10,000, 100,000, a million different basis functions. And what we want to do is select out of this 10,000 basis functions maybe 10 or 15 of these basis functions that will best allow us to represent the signal. Right? And so you can't just do it using a brute force method. There is a specialized code. It's a greedy algorithm, but it's a specialized code that it goes to when it recognizes that what you're trying to do is basis pursuit. So first what we're going to do is we're going to construct our basis. And there are 30,000 bases. And if you were to plot a couple of them, it looks like this. These are called Gabor basis. And when you want to do this basis pursuit, you can just, if you just say fit the data, here's the basis on the T, it'll just give you a least squares fit kind of a thing. But if you want to do basis pursuit, you have to say that through the fit regularization, you say that I want to do an L1 regularization, which is sort of making the problem into a convex problem. And it's the most more popular name for that is also called as a lasso regression. And you specify a regression parameter associated with it. Within a second or so you get a result. You see that there are 47 elements that it uses in order to get a decent fit. This regularization parameter, if you make it really large, then it'll take less number of elements, but the fit will not be as good. You shrink down the regularization value, it focuses on the error, and you end up using more. So there's always a trade off. But when you look at the list, you see that the error is pretty decent. But the good thing about that is from here you can actually pull out the basis that you actually need in order to do the fitting. So out of the 10,000 or 30,000 basis functions that we had, we can pull out those 47 just by using the non zero positions and just use that to do our fit. This is one example of how you can extract useful information from your optimization problem. Okay, so the next example that I want to show you is. They are part of that library of Geber functions that I created early on. There were like 30,000 of them, which were these. You know, they're all exponential functions that are stretched and dilated or scaled. And from this entire collection, 47 of them are chosen, and those are used for the best fit. That makes sense. Yeah. Okay. All right, so the next one, and I want to focus on this, is because optimization problems, sometimes you can formulate them in the most obvious way, but then when you want to start asking questions, when you want to do queries, when you want to explore the optimization space, how do you do that efficiently? I want to show you a couple of tricks on how to do that, and I've decided to use something more visual to demonstrate that. Example. What I have is a region. And what I want to do is fit a ball, that smallest ball that encompasses this entire region. The formulation of this is very obvious. You want to minimize the radius of a ball such that all the points are inside that ball. And the formulation is right over here. And the result, you get back almost instantaneously. You get a radius, you get your coordinates, you can visualize the ball, and all is good. But now comes the question, well, what if I want to explore this optimization problem a little more? What if I want to, for example, say, what are the points that touch from my coordinates? What are the extreme points? What are the points that actually contribute to the ball that are closest to the ball? Well, one way to do that would be simply pull out all the information, put those numbers back into your constraint, and try and get a result of it. But I personally think that this is going about the wrong way. I want to show you how you can address this query in different ways. So the first way is reformulation. Optimization problem can be reformulated in multiple ways. For this particular case, instead of minimizing the radius and this one, what we can do is we can turn the problem over its head and say that instead of minimizing the radius, I'm going to maximize a certain objective. And in doing so, the constraints become linear. Okay. And the objective ends up becoming quadratic. Why is this a big deal? Because sometimes the previous, in the previous case, this actually is. The constraints are norm constraints, which means that it is a second order cone problem. Meaning that the solver does a lot more work. This formulation ends up being a quadratic optimization problem, which means that when, when push comes to shove and you have to solve the problem, this formulation is actually 20% to 30% faster. Okay, and you get the same results. You can get the radius in the center. But what's more obvious is that this gives you a natural way of doing that same query as to which points are the extreme points, and those are the ones wherein the weights are non trivial. And you get the exact same result. There are four points, right? There is another method that you can use in order to answer questions like this, and that is using. Well, it's not really hidden, but I'd like to call it hidden for the purposes of this talk. And that is using something called as the dual of the problem. Okay, so I can take the original problem, the N minimize problem, in the same formulation, but instead of using n minimize, I'm going to use conic optimization, because conic optimization allows you to do extract out a lot more information. And in this case I'm going to extract out primal, the, the primal values, the R and the C, and I'm going to extract something called as the dual. And what does this do? Well, when you look at it, if you, if I were to, it's a really lengthy thing, but you'll see that, you'll see that are a whole bunch of zeros. But when you look at which ones are non zero, you get those indices. So technically this dual maximizer is embedding a lot of information that you can use to get a lot of relevant information out of it. So you can now visualize the same thing. And those are the points, those are the extreme points. There are two points on the side and there are two at the bottom right there. Now if you're in the field of optimization, then something like the word dual of a problem might seem obvious, but it's most often not. Dual is one of those cryptic things that people, either they tend to avoid or they just ignore it. So let me just explain to you what a dual is. So when you put an optimization problem together, it is generally of this one. You have an objective, you have some constraints. What you generally do, and this is what happens at the solver level, you generally end up making, constructing what is called as a Lagrangian. So you take all your constraints, you apply them with these Lagrange multipliers, you put them together and then you solve that one big problem. The dual part comes in. But then you take some Certain limits on this X. And what you end up with is a new optimization problem that depends only on these Lagrange multipliers. That's why it's called the dual Lagrangian formulation. And this acts. So you end up with a completely new optimization problem. But that optimization problem is complement to the original one. And when you solve this dual problem, you realize that you are getting some really good information. So let me show you what I mean by that. Let's take another geometry example. So this is a problem. I have two convex polygons. They're done intersecting. The optimization problem is I have these two polygons. I want to find the line that divides them together, that this the line that separates these two convex polygons. So I'm going to set this up. So the natural way to look at it is I have two polygons. Find the nearest point, find two points, one that lies on each one of these polygons. And the nearest point, when you join them, the perpendicular line becomes the hyperplane. So you can just put that in conic optimization and you get the result. So you get two points, and there is an epigraph transformation happening. That's not important. But you end up getting two points. But in order to get the separating hyperplane, you can extract that information. You can do it manually, or you can extract it from the dual. The way you do that is you get the dual information and you look at the constraint, the constraint that deals with this one specific, which happens to be the norm constraint. And you notice that the norm constraint has this dual. And the hyperplane needs two pieces of information. It needs a point and it needs a normal. This dual actually provides you with that normal information. And so you can just extract that information from the dual. And there's your answer, right? The tricky part is understanding the dual. And this is what I want to emphasize. But if you master how to represent and read what are the dual is, you have a very powerful tool at your hands. All right, so let's switch gear. I'm running a little out of time, but I'll try to speed it up. The next problem I want to talk about is optimization with uncertainty. So let's say that you have a convex optimization problem, very simple one. You have bounce and you want to minimize it. You get the result. But what if you're not sure whether this one is actually a one? There might be a noise associated with it. Maybe it's 1.1, maybe it's 1.01. You don't know what that is what you know is that there's noise associated with it. So the question is, how do you solve problems wherein the constraints are uncertain, right? So this again does not fit inside the narrative of your typical and minimized problem. One approach would be to account for these uncertainties and generate like a large table of constraints which account for this uncertainty, right? With all various permutations and combinations. For this case, it's a very simple problem. It might not be that bad. You can solve the problem instead of that one one. You now say taking all the uncertainty account, the best possible result you should be able to get that will satisfy this uncertainty will be 0.9. 0.9. But this approach that I just demonstrated is horribly inefficient and will choke your computer for anything but the most trivial problem. The better way to do that is using a function called robust convex optimization. So let me demonstrate that with one example, you have input and the output is uncertain. I want to fit a cubic polynomial to it. My output has some noise alpha which ranges from negative 0.1 to 0.1. I set it up in a robust convex optimization I get the coefficients for that. In this case I'm generating what is called as an envelope that associated with this uncertainty. The black line is the result you would get taking all these uncertainties into account. This is just one simple example. I'm actually over time I was going to give you a sneak peek on something called as multi objective optimization, which is not in the kernel. It's something currently that we are working on and hopefully it will be there in the future releases. But I will leave you with a pretty picture. Thank you.