Price Optimisation with convex and non-convex loss functions
Optimisation is used for a number of day-to-day activities from finding the quickest route to our destination using google maps to ordering food through an online app. In this post, we will go through price optimisation for two main types of loss functions i.e. convex and non-convex. We will also cover the best ways to solve these problems using a python library called scipy. The details of the example data and code used in this blog can be found in this notebook.
Convex Optimisation
A convex optimisation problem is a problem where all of the constraints are convex functions, and the objective is a convex function if minimising, or a concave function if maximising. A convex function can be described as a smooth surface with a single global minimum. Example of a convex function is as below:
F(x,y) = x2 + xy + y2.
1. Data Generation
In order to look at how optimisation works, I am generating a toy data set, which consists of sale’s price, volume and cost. Let’s set the objective of the data set is to find a price that would maximise the total profit.
Sale’s Price (price): This is a random number generated between 1000 and 7000. The data is generated using numpy random function.
Volume: volume is generated as a straight line function of the sale’s price with a declining slope as shown below:
f(volume) = (-price/2)+4000
The relationship between sale’s price and volume is as shown below. As expected we see an increase in volume of products sold as the price decreases.
Cost: The cost variable represent the cost of manufacturing of the product. This takes into account some fixed costs (i.e. 300) and a variable costs which is a function of volume (i.e. 0.25).
f(cost) = 300+volume*0.25Now that we have all the variables that we need, we can use the simple formula below to calculate profit:
f(profit) = (price — cost)*volumeA 3-D plot of the sale’s price, volume and profit is as shown below. We can see that it is a bell shaped curve with a peak profit at a particular volume and cost. A objective for a business may be to maximise profit and in the following section’s I will show how we can achieve this using scipy.
2.Estimate cost and volume from observational data
In the above section we have generated a sample data set. However in the real world we may have access to a small set of observations i.e. price, volume and costs for a product. Additionally we will not know the underlying function which governs the relationship between the dependent and independent variable.
In order to simulate observational data let’s take a cut of the generated data i.e. all points where the price is “<3000”. With this observational data we need to find the relationship between price vs cost and volume vs cost. We can do that by performing a simple linear regression on the observation data set. However for real world problem this may involve building complex non-linear models with a large number of independent variables.
Linear Regression:
- Price vs Volume
We take price as an independent variable ‘X’ and volume as a dependent variable ‘y’. Using the stats model library in python, we can determine a linear regression model to capture the relationship between volume and price.
As seen below from the observational data we are achieving a R-squared of 1 (i.e. 100%), which means the change in volume is perfectly explained by the change in price for the product. However this perfect relationship will rarely be observable in real-life data sets.
Additionally we can see the bias of -3,999.67 and the coefficient of -0.5 for prices approximates the function used to generate the volume data.
2. Volume vs Cost
In a similar manner a linear regression with cost as the dependent variable ‘y’ and volume as the independent variable ‘X’ is performed below. We can see that the bias and co-efficient for the cost model approximates the function used to generate the cost data. Hence we can now use these trained models to determine cost and volume for the convex optimisation.
Optimisation using scipy
We will use the scipy optimise library for the optimisation. The library has a minimise function, which takes in the below parameters, additional details on the scipy minimise function can be found here:
result = optimize.minimize(fun=objective,
x0=initial,
method=’SLSQP’,
constraints=cons,
options={‘maxiter’:100, ‘disp’: True})- fun:The objective function to be minimised. In our case we want to maximise the profit. Hence that would mean minimisation of ‘-profit’, where profit is calculate as: profit = (price — cost)*volume
def cal_profit(price):
volume = mod_vol.predict([1, price])
cost = mod_cost.predict([1, volume])
profit = (price — cost)*volume
return profit###### The main objective function for the minimisation.
def objective(price):
return -cal_profit(price)
2. x0: Initial guess i.e in this case we are setting an initial price of 2,000.
initial = [2000]3. bounds: Bounds are the lower and upper limit intervals to be used in the optimisation. It can be set only for for certain optimisation methods which supports bounded inputs such as L-BFGS-B, TNC, SLSQP, Powell, and trust-constr methods.
#################### bounds ####################
bounds=([1000,10000])4. constraints: Here we are specifying constraints to the optimisation problem. The constraints in this case is the volume of products that can be produced (i.e. setting this to 3,000 units). It is an inequality constraint i.e. the volume has to be less than the specified number of units. Other types of constrains such as equality constraints are also available for use.
# Left-sided inequality from the first constraint
def constraint1(price):
return 3000-mod_vol.predict([1, price])# Construct dictionaries
con1 = {'type':'ineq','fun':constraint1}# Put those dictionaries into a tuple
cons = (con1)
5. methods: There a number of methods available for performing the minimisation operation e.g. (see reference):
- ‘Nelder-Mead’ (see here)
- ‘BFGS’ (see here)
- ‘Newton-CG’ (see here)
- ‘L-BFGS-B’ (see here)
- ‘SLSQP’ (see here)
- ‘trust-constr’(see here)
We will use the SLSQP method for optimisation. Sequential quadratic programming (SQP or SLSQP) is an iterative method for constrained nonlinear optimisation.
Not all of the above methods support the use of both bounds and constraints. Hence we are using SLSQP, which supports the use of both the bounds and constraints for optimisation.
Results of convex optimisation
The optimisation was run for a total of 3 iterations. Based on this the objective function has returned a value of -6.6 mil (i.e. -6,587,215.16). This results in a price of 4,577 and volume of 1,710. We are getting a negative value because we are maximising for profit by minimising for negative profit, which is a convex function.
Optimization terminated successfully. (Exit mode 0)
Current function value: -6587215.163007045
Iterations: 3
Function evaluations: 9
Gradient evaluations: 3The results of the optimisation closely matches to the maximum profit as seen in the generated data set. Hence we know that the optimisation has worked as expected.
Non Convex Optimisation
In most of the machine learning problems we come across loss surfaces which are non-convex in nature. Hence they will have multiple local minimum. Hence while solving for such non-convex problems it may be simpler and less computationally intensive if we “convexify” a problem (make it convex optimisation friendly), then to use non-convex optimisation. I will demonstrate how we can achieve this through the below example.
Non convex data set genration:
Here we have created another product with a slightly different price, volume and profit profile. Let’s say that the company can produce only one of these products and wants to use optimisation to find out which of the products it needs to focus on and what price it needs to sell it at.
Use of Convex minimisation for non-convex data
For the above data if we use the same convex optimisation as above, the solution we get will be a local minimum as seen below. We get a max profit of 6.86 mil for a optimised price of 5, 018 and product type 0.
Basinhopping algorithm
Basin-hopping is an algorithm that combines a global stepping algorithm along with a local minimisation at each step. Hence this can be used to seek the best of all the local minimum options available for the non-convex loss surface. The below code demonstrates the implementation of this algorithm.
As seen above we have use the same method i.e. SLSQP and the same bounds and constraints as the previous example. However, we now get a slightly different result. The maximum profit is 9.8 mil with an optimised price of 5,957 and product type of 1.
Conclusion:
In summary, we have reviewed the use of optimisation libraries in scipy for a simple convex optimisation data-set which has a single global minimum and also reviewed the use of basin-hopping algorithm in cases where the loss surface has multiple local minimum and a global minimum. Hope you find the above post useful and the framework provided to solve optimisation problems in the real world.
