Using scipy.optimize.fmin_slsqp

Question

I am trying to use the scipy.optimize package to find the maximum of my cost function.

In this particular case: I have a list of prices that change throughout the day. To make it easier, let's assume that the day has 8 hours, and the price per hour is as follows:

price_list = np.array([1,2,6,8,8,5,2,1]) 

In this simplified case, I want to select the 4 highest prices from this price_list. And for various reasons, I do not want to just sort and select the best four prices, but use some optimization algorithm. I have a few limitations, so I decided to use the least square algorithm from scipy, scipy.optimize.fmin_slsqp.

First I create a schedule for the selected hours:

 schedule_list = np.zeros( len(price_list), dtype=float) 

Next I need to define my inverse function profit_function. For all the selected hours, I want to summarize my profit. Although I want to optimize my schedule, price_list is fixed, so I need to put it in * args:

 def price_func( schedule_list, *price_list ): return -1.*np.sum( np.dot( schedule_list, price_list ) ) 

As soon as I understand how everything works in principle, I will move something. Until then, I just avoid using more * args arguments and define my limit using a hard coded number of hours to run. And I want my selected clock to be exactly 4, so I use the equality constraint:

 def eqcon(x, *price_list): return sum( schedule_list ) - 4 

Also, I want to limit my schedule values ​​to 0 or 1. I am not sure how to implement this right now, so I just use bounds keywords.

Unlimited optimization with borders works great. I just pass my schedule list as a first guess.

 scipy.optimize.fmin_slsqp( price_func, schedule_list, args=price_list, bounds=[[0,1]]*len(schedule_list) ) 

and the output is as good as it can be:

 Optimization terminated successfully. (Exit mode 0) Current function value: -33.0 Iterations: 2 Function evaluations: 20 Gradient evaluations: 2 Out[8]: array([ 1., 1., 1., 1., 1., 1., 1., 1.]) 

Without any additional restrictions, this is the best solution!

Using limited optimization with the following command:

 scipy.optimize.fmin_slsqp( price_func, schedule_list, args=price_list, bounds=[[0,1]]*len(schedule_list), eqcons=[eqcon, ] ) 

gives me an error:

 Singular matrix C in LSQ subproblem (Exit mode 6) Current function value: -0.0 Iterations: 1 Function evaluations: 10 Gradient evaluations: 1 Out[9]: array([ 0., 0., 0., 0., 0., 0., 0., 0.]) 

From gnuplot, I know that this is often due to insensitive questions or poor initial values. I tried almost optimal starting values, but that doesn't help. Anyone have an idea or even a solution for me?

In the next step, I have already formulated the limitations of inequality. Do I understand correctly that in the copied minimizing shell it is assumed that the inequalities are greater than 0, and in fmin_slsqp it is vice versa. Are decisions limited by negative constraint functions?

Answer 1

You have a simple linear program, right?

 min: - prices . x constrain: x >= 0, sum x = 4 

therefore, the second derived matrix aka Hessian is 0.
slsqp tries to invert this - impossible. I agree, the error message might be better.
(The same thing will happen with other quadratic methods, in any package: they will converge much faster on smooth functions, but fail on rough rocks.)

See also why-cant-i-rig-scipys-constrained-optimization-for-integer-programming -
but LP must do the job (max. 4), Integer programming is more complicated.

Answer 2

The SLSQP algorithm is a gradient-based optimizer, meaning it expects the derivatives of the lens and constraints to be continuous. In my opinion, it seems that you are trying to solve the problem of integer programming (continuous values ​​in the schedule list are unacceptable). You need an algorithm that selects the appropriate values ​​(0 or 1) for independent variables, rather than trying to find a minimum of a continuous value space. Unfortunately, I'm not sure if there is anything like that in scipy.