A Simple Introduction to Optimization
What is optimization?
Optimization is finding the best solution out of all the possible solutions. The word “optimal” basically means “best possible”. In mathematics, we solve optimization problems by finding the maximum or the minimum of a function. “How can we maximize the profit?” “Which is the fastest route to reach the destination?” “What are the best parameters of my machine learning model?”
There are so many problems that we can solve with optimization. Exciting!
The 4 main ingredients of an optimization problem
Before we learn how to solve an optimization problem, we have to familiarize ourselves with its 4 main components:
- Objective function. The objective function (sometimes called the cost function or loss function) is the mathematical function we wish to minimize or maximize.
- Decision variables. The decision variables are the unknown and controllable parameters of the optimization problem. We solve the optimization problem by finding the best values of the decision variables, giving us the maximum or minimum objective value.
- Feasible region. The feasible region is the solution space, i.e. all possible solutions are within the feasible region. The constraints of the optimization problem define the feasible region.
- Parameters. The parameters are the uncontrollable inputs (data) needed to identify the objective function and the feasible region.
A graphical example
There are many types of optimization problems and more ways to solve them. An optimization problem can be constrained or unconstrained, its variables can be discrete or continuous, and the equations can be linear or non-linear. Let’s start with a simple linear programming example. Linear programming is a technique to solve an optimization problem with linear objective function and linear constraints. (You might have learnt this in high school!)
Suppose that I have 2 assignments due soon; a math assignment and a biology assignment. Each assignment is worth 100 scores. Let’s assume that an hour spent on the math assignment allows me to gain 10 scores, and an hour spent on the biology assignment allows me to gain 5 scores. However, I only have 24 hours left to work on the assignments. How many hours should I spend on each assignment to maximize my total scores?
Now, we have all the parameters we need to formulate our problem. The decision variables are the number of hours spent on the math and biology assignments. Let the hours spent on the math assignment be x1 and the hours spent on the biology assignment be x2. Our objective is to maximize the total scores. Thus, the objective function is to maximize 10x1 + 5x2. Finally, our feasible region (all the possible solutions, also known as the solution space) is constrained by the number of hours I can spend on my assignments and the maximum scores I can achieve for each. Note that the number of hours must be non-negative. Let’s formulate our problem mathematically:
For linear optimization problems with two variables, we can solve them graphically. First, we plot the constraints on a cartesian plane and identify the feasible region. Note that the feasible region should satisfy all the constraints of our problem. The shaded region in the figure below is our feasible region, where all the points within this region are feasible solutions.
Next, we want to find a point within this feasible region that gives us the best objective value (remember, we want the maximum value). The solution always lies on one of the feasible region’s corner points (vertices) in a linear programming problem. It is not difficult to identify all the corner points using a graphing calculator — let’s label them as A(0,0), B(0,20), C(4,20), D(10,14), and E(10,0).
To find the corner point which gives the best objective value, we need to plot the direction that maximizes 10x1 + 5x2. Then, we trace the direction of maximization up to the corner point furthest away from the origin. Let’s visualize it using the figure below. The red arrow shows the direction of maximization. Following the direction of maximization, we notice that corner point D(10, 14) is furthest away from the origin. Thus, it gives us the highest objective value. To verify this, we can calculate the objective value at each corner point, and we will end up with the same solution at D(10, 14):
Based on the graphical method above, we have found the optimal value, z* =170, and the optimal solution is x* = (10, 14). It means that to obtain maximum total scores, I should spend 10 hours on the math assignment and 14 hours on the biology assignment. This will give me a total of 170 scores.
Do we always have a unique optimal solution?
No. Optimization problems can have a unique optimal solution, multiple optimal solutions, and unbounded or infeasible.
- Unique optimal solution. An optimization problem with a unique optimal solution has only one optimal solution. Like the example given above, there is no other solution equally as good.
- Multiple optimal solutions. It is also possible for an optimization problem to have more than one optimal solution. However, using the same example above, what if my objective is only to maximize my math assignment scores? Then, our objective function would instead be max x1. If we solve the problem, we will have more than one solution. It doesn’t matter if I spend 1 hour, 2 hours, or 5 hours on the biology assignment — as long as I spend 10 hours working on the math assignment, I can achieve my objective.
- Unbounded. If a solution is unbounded, it means that the objective value can be made infinitely large (or infinitely small for a minimization problem) without violating any of its constraints. Let us assume a scenario where there is no upper limit to the scores that I can obtain for the biology assignment, and also, there is no limit to the amount of time I can spend. Then, we can remove the constraints 5x2 ≤ 100 and x1 + x2 ≤ 24. In this case, our feasible region will be unbounded, and we can have infinitely many solutions. Furthermore, we can find a better solution for every solution — we can still find a better solution even if we allocate 100,000 hours working on the biology assignment.
- Infeasible. An infeasible solution means that there is no solution that satisfies all the constraints. Using the same example again, suppose that I set a target to score at least 90 scores for each assignment. Then, we would have additional constraints 10x1 ≥ 90 and 5x2 ≥ 90. However, when we plot the constraints, we will realize that there is no feasible region satisfying all the constraints that we have defined. There is no way to score at least 90 scores each, given our time constraints. Thus, we do not have a feasible solution.
- Extra. Well, what if there is no time constraint? Then, we do not need the constraint x1 + x2 ≤ 24. We will have a feasible region by removing this constraint, as shown in the figure below. Congratulations, it is now possible to score at least 90 marks each! So, don’t leave your assignment till the last 24 hours if you want to get perfect scores :)
Recap
This article discussed the 4 main components of an optimization problem — the objective function, decision variables, constraints, and parameters. We also worked on a simple linear programming problem using the graphical method. Finally, we covered scenarios where we obtain a unique optimal solution, multiple optimal solutions, unbounded solutions, and no solution (infeasible). In the upcoming articles, I will demonstrate how to solve optimization problems using Python. Stay tuned!
References
- The University of Edinburgh, MATH11111 Fundamentals of Optimization
- https://web.stanford.edu/group/sisl/k12/optimization/#!index.md
- https://en.wikipedia.org/wiki/Linear_programming
