Mathematical Optimization In Layman’s Terms ( Part 1)
As a researcher in Operations and Decision Science, I need to apply different mathematical optimization techniques in my work and as a professional while solving complex real-world problems from predictive to prescriptive insights.
While merging machine learning with OR techniques to do optimization at the prescriptive layer it is always difficult to explain the optimization techniques in layman’s terms.
Starting this series on introducing mathematical optimization in layman’s terms so that it becomes the reference document for me and others whoever needs to explain optimization. In this first part following are the topics I am going to cover:-
Basic Optimization definition
Defining optimization problem
Formulating optimization problems
Types of optimization problem
Finding the optimal point
What is Optimization?
Part of Operation Research, Optimization is the process of choosing the optimal solution from all the feasible solutions. Optimization is something that we do all times in our routine life while making decisions.
In data science, optimization is focused on generating prescriptive insights and recommend the optimal action based on the input from the machine learning model output.
How to define the optimization problem?
The optimization problem will have an objective function which we either try to minimize or maximize. The objective is a function of the decision variables. Decision variables are choices available like the number of products to manufacture.
The objective function is usually maximized or minimized subject to some constraints. Constraints are restrictions like the labor available for product manufacturing, or the minimum number of hours needed to manufacture a product. Similar to objective, constraints are also a function of decision variables. An optimal value is a feasible solution that generates the minimum or maximum objective function value. An optimal solution must satisfy the constraints and give us the largest or smallest value of the objective function, depending upon whether it’s a maximization or minimization problem.
How to formulate optimization problems?
Formulating an optimization problem is usually an iterative process and follow the 4 step approach:-
1: Define the problem — We start with the definition of a business problem and see what we are trying to solve, for example, are we trying to minimize the cost?
2:- Define the decision variable — Next we define the decision variables and to do that we take help from decision-makers and decide which variables are under their control and are likely to influence the solution to the given problem.
3: Formulate the objective function — Next is formulating the objective function as an equation that consists of how decision variables related to the solution in terms of maximizing or minimizing. Decision-makers again help us to decide objective function need to be minimized ( for example cost ) or maximized ( for example profit margin).
4: Defining the constraints:- The last step is is to define all constraints in terms of the number of variables that can be produced, for example, what are the restriction to the solution?
After following these four steps we will get a solution that will help decision-makers to take some actions that will reduce the cost or increase profit margin. As I mentioned it is an iterative process so once we follow the basic four steps we should get the formulation reviewed by decision-makers and see if the formulation makes sense. Based on the feedback we should start adding complications to make the formulation more general and realistic and complication y can come in the form of additional constraints and restrictions. A useful solution is built up through an iterative process; start simple and then move forward by adding interesting and more general types of restrictions to the problem. Formulating a business problem as an optimization problem forces us to think through the business problem in a logical manner
What are the different types of optimization problems?
There are different types of optimization problems:-
LP: Linear programming — Objective function and all of the constraints are linear functions of the decision variables.
ILP: Integer linear programming problems — Objective function and constraints are linear functions of the decision variables, and values for all of the decision variables must be integer-valued.
MILP: Mixed integer linear programming — Objective function and constraints are linear functions of the decision variables, and some of the decision variable values must be integer-valued.
NLP: Nonlinear programming problems — Objective function and constraints are continuous functions of the decision variables, but not all of them are linear functions.
How to find the optimal value?
One method for finding optimal values is to take the derivatives of the objective with respect to the decision variables and then set these derivatives equal to 0. Because the minimum or maximum of a function will occur when the derivative of the function is 0, we can follow the derivative up or down to find a local maximum or minimum. This method is generally called gradient descent for minimization problems, but for maximization problems, it would be gradient ascent.
Gradient Descent
Gradient Descent is a generic optimization algorithm that works in variety of scenarios to find the optimal solutions and uses the first derivative to search for local minima. In simple words, as the name suggests gradient means slope and descent means going down to in this algorithm we find the local minimum of a function using its gradient. More intuitively you can give the example of a mountain where you are on the top and it is foggy & slippery, so to come down you will take optimal steps ( not very small, not very big) in direction of steepest slope to reach the bottom and gradient descent do the same where it measures the local gradient of the error function and goes in direction of descending gradient and once the gradient is zero we reached the minimum.
Newton’s method
Gradient descent uses the first derivative to search for local minima, but Newton’s method extends this idea to incorporate information from the second derivative into the iterative calculations.
The idea is to perform a Taylor expansion of the function that we want to optimize, and then truncate the expansion to keep only the second-order terms. We take the derivative of the second-order Taylor expansion and set it equal to zero. This is essentially looking for the local optimum using a local approximation, so we step toward this local optimum and recalculate the second-order Taylor expansion.
This is very similar to gradient descent; we are following the derivative down (or toward the local optimum), but we choose our step size and direction based on the second derivative. Just like gradient descent, when the derivative approaches 0, the iterates stop changing, and the algorithm has converged.
Hope this part gives you a better understanding of mathematical optimization and some idea to explain this in Layman’s term. In the next part, we will deep dive into learning programming with some simple real-life examples.
