The hands down most important part to our adventures in optimization is the correct and proper set up of the situation we hope to optimize. In previous posts I gave glimpse to how to formally define optimization problems. Now you will see the proper way to set up our problems.
All optimization problems start the same way, with a cost or objective function. This function is what we are trying to minimize. Our function can be our cost of ingredient, our time traveled, or sitting space in a resturant. All of these are possible functions. We will call the function we are trying to minimize (our objective function) f(x). Where x is a vector of variables. So the first part of our problem set up looks like this.So far its a pretty boring optimization problem. We need to add rules or constraints to make our problem more interesting and more meaningful. There are two general types of constraints, equality and inequality. Obviously one type sets our variables equal to something, while the other tells us the relationship of the variable to constants or other variables. However, we like all of our optimization problems to look pretty much the same. This enables us to draw prallels between different problems and hopefully use the same methods of solving. for this reason we have all our inequality and equality constraints in the following form below.Now our problem is starting to get a little more interesting and also conveying more information to anyone else who is looking at our problem. However we are not done yet. We have to determine what type of optimization problem we have. By identifying our problem type, we know how to approach solving the problem. Certain methods and solvers work better with certain problem type (remember our no free lunch talk). But this is saved for the next post, identifying and categorizing our problem.Before we go let’s take our diet problem from yesterday for a spin. Let’s say we live in a small town with one grocery. This grocery is poorly stocked and only has 8 items on it’s shelves at any given time. Each of these items has a cost associated with it and certain nutritional value. Since we are watching what we eat, we decided to count our macros. Our macros our fats, carbohydrates, and protein. Also I am going to tack on another “macro” vitamins. So let’s see what this super market has to offer.Walking down the aisle we see the 5 items. They have apples, steak, gummy vitamins (Vitafusion only), potatoes, orange juice, ice cream, broccoli, and chicken breasts. Before heading home you take note of all the prices and put them in a list below so they are all nice and organized.
Once you get home you open up chrome and check out some of the nutritional facts on the items from the store. You pop open excel and make a spread sheet that lists all the nutritional facts broke down into our four “macros”. The spreadsheet is shown below.
| food | fat | carbs | protein | vitamins |
| apples | 0 | 5 | 1 | 3 |
| steak | 5 | 2 | 10 | 0 |
| gummy vitamins | 0 | 2 | 0 | 10 |
| potatoes | 0 | 8 | 0 | 1 |
| orange juice | 0 | 4 | 0 | 4 |
| ice cream | 10 | 4 | 0 | 0 |
| broccoli | 0 | 5 | 0 | 5 |
| chicken breasts | 1 | 2 | 7 | 2 |
As you can see some foods provide a lot more macros than others. However, upon first inspection I cannot tell which foods are gonna be the best options for our diet. But before we determine the most optimal diet we need to know how much of each macro we need. Conservatively we guess that we need 40 grams of fat, 60 grams of carbs, 50 grams of protein, and 45 grams of vitamins. With this information, we can formulate our problem. First we need to create a few vectors and matrices. The first vector is going to represent the amount of each foodstuff we buy. The next vector is going to come from our cost list above into a cost vector.
One thing we have to realize is that all the above x’s are non-negative as we cannot vomit up food and sell it to the store. Anyway, its starting to look like an optimization problem. We need two more elements, our constraint matrix and constraint vector. These are going to stem from the spreadsheet we made above and our target macros. The constraint matrix (spreadsheet values) is denoted by “A” and the constraint vector (our target vectors) “b”, they are shown below.
We have all the necessary elements for our optimization problem. Going back we remember the goal of our optimization, to minimize the amount of money we spend on food. However, this is subject to the constraint that we have to fit our macros. Formally declaring the problem gives us the following.
There we have it our first optimization problem. This isn’t exactly standard form, but it is close. In the next couple of posts we will go over various methods to get our problems into standard form. But before that we need to classify our optimization problem. When a problem falls into the form above we classify it as a linear programming problem in optimization. This is because both the objective function (our cost minimizing) and our constraints (macro targets) are linear equations. Linear equations are a nice basis for optimization, Next part we will dive deeper into linear equations and the best ways to solve them.-Marcello