Mathematical optimization is basically finding out what combination of inputs will give you the “best” possible output?
Traditionally, we represent a system that has inputs and outputs as functions. Mathematical optimization is finding out the inputs to the function that either maximizes or minimizes the value of the function.
The basic thought process
The derivative of a function is another function that tells you the rate of change of the function as you go through its domain. Therefore when the derivative is 0 at a particular point, it means that at that point, the original function is either at a peak or a valley. We call these points critical points. So to find the critical points of a function:
- get its derivative
- set it equal to 0
Once we have the critical points, we need to go through each critical point and determine whether it is a min or a max (or none - e.g. inflection point). There are lots of ways we could do this, each has its own pros and cons:
- we could simply look at the left and right of the critical point. If both these points is above the critical point, then the critical point must be a min. You can use similar logic to determine if its a max.
- again, we could look at the left and right of the critical point, but this time we will look at the concavity at the left and right. If both sides of the critical point concave down, then the critical point must be a max. You can use similar logic to determine if its a min.
- we could look at the concavity right at the critical point. If it’s concave down, it must be a max. You can use similar logic to determine if it’s a min.
Each of the above has it’s own pros and cons. Sometimes because of the function, you can’t find out the concavity of the function right at the critical point, thus it helps to look at neighbors.
This thought process extends naturally for multivariate functions (functions with multiple inputs).
Often, you have restrictions on what the inputs can be. So you still want to find the inputs that maximize or minimize, but the inputs can’t be any value, they have to satisfy some relationship. We call these problems “constrained optimization problems.”
High level plan
- No constraints? Use derivative tests (like we did above).
- Only equality constraints? Use lagrange multipliers.
- Some inequality constraints?
- All constraints linear?
- Objective function linear too? Use linear programming.
- Objective function quadratic? Use quadratic programming?
- All constraints linear?
- Do inputs have to be integers? Use integer programming (can be integer linear programming or integer quadratic programming)
Note: Even if your function is a vector valued function, optimization techniques still exist! Look up vector optimization.
Mathematical optimization is finding out the best values for a particular situation, with a particular goal. You can even restrict the values (e.g. some of them must be ints, they must satisfy another relationship together, etc). There are a lot of different objective functions (the function whose output you are trying to optimize), different constraints, etc, but most of these problems are solved! Just google!