Whenever we think of a real life problem, we always want to get the most optimal result. I said optimal and not the best possible because we don’t have unlimited resources. Given unlimited resources, we would always pick the best one and we don’t have to think about it at all. But unfortunately in real life, this is almost never the case. Let’s say you want to buy a car. Ideally you want the best possible car, but you don’t have unlimited money. So you would buy a car with maximum features while minimizing your cost. This is not so hard to do because you have a limited number of variables. Hence you would just do it manually. What would you do when you have to deal with a lot of variables? How would you do it?
What is constrained optimization?
Consider the earlier example. If you were told that you can buy any car you want, you would pick a car of your choice and get the fully loaded version. You are not restricted by anything here. You are optimizing your choice without any regards to cost or performance. But most people wouldn’t do it, mostly because they cannot. People think about features, cost, performance, fuel efficiency, maintenance, robustness etc when they buy a car. These are all the restrictions they have when they want to buy a car. Now keeping all these things in mind, they make a choice which will optimize their needs. This is called constrained optimization. In mathematical lingo, your needs will morph into the ‘objective function’ and the constraints will morph into ‘constraints’. We will see what these terms mean soon.
Why do we need it and where is it used?
Constrained optimization has become a cornerstone of modern engineering and technology. Let’s say a company wants to manufacture a smartphone. There’s no point in coming up with an amazing smartphone that costs $5000. Nobody will buy it! There is not point in coming up with a smartphone that costs just $100 which doesn’t have any features. Nobody is going to buy this either! This is where constrained optimization comes in. In real life, the objective function is extremely complex and there will be millions of constraints. If this is the case, we cannot sit and manually evaluate each and every case. So we need a technique to solve this. Hence we have constrained optimization algorithms. Constrained optimization is used in almost every field of engineering and technology like artificial intelligence, consumer electronics, computer vision, manufacturing, business analysis, stock markets, economics, control engineering etc.
How do we actually optimize?
In general, an optimization problem consists of maximizing or minimizing an objective function by choosing various values to the variables and evaluating the function. Now doing this for all possible values is quite time consuming. Depending on the type of objective function, different methods are available. The objective function is nothing but a mathematical equation with different variables. Constraints are a set of inequalities (or equalities) that need to be satisfied. Consider the earlier example. Let’s say the cost of the car is given by a+b+c+d, where ‘a’, ‘b’, ‘c’ and ‘d’ are the costs for different features of the car. Now you have to minimize the cost of the car given the following constraints:
3a + 2b > 23
6d – 5c < 12
The most obvious way of solving this problem would be trying out all possible values and seeing which one gives the most optimal result. One thing to note is that we try only those values which obey the constraints. This is very useful because it restricts the number of values that need to be tried out before reaching the solution. The problem with exhaustive search is that it is not very efficient as it consumes a lot of time. Hence various optimized search algorithms are available which look through the solution space and converge faster.
The field of mathematical optimization is vast and there are many different techniques used depending on the problem at hand. Two of the more commonly encountered forms of this problem are: Linear programming and Quadratic programming. If the objective function is linear, then we use linear programming. The above example is a linear programming problem. If the objective function is quadratic, then we use quadratic programming. If the cost of the car was a^2 + 3bc + 5d^2, then we would have to use quadratic programming. Both of them require the constraints to be linear. Linear and quadratic programming are two separate and deep fields of study by themselves, and discussing them here will take up too much space. I will discuss them in my future blog posts.
————————————————————————————————-
Perpetual Enigma 