0

I am trying to formulate an optimization problem using scipy minimize function. However, I am having the following problem that I can't work around:

I want X = [x1, x2, x3, x4, x5] that minimizes a cost function F(X). This X vector, however, are percentage values that must add to 1, i.e., np.sum(X) = 1.

The problem is: if I use, for instance, the "SLSQP" method with some initial values (such as X0 = [0.2, 0.2, 0.2, 0.2, 0.2]), it will try to increment each value to find some convergence direction. For example, the algorithm will make X0 -> [0.21, 0.2, 0.2, 0.2, 0.2]. But that cannot happen, because np.sum(X) = 1 is a requirement for me to compute the objective function.

Using constraints does not help either! I could make a constraint with np.sum(X) = 1. However, the minimize algorithm will only check the constraint after computing the objective function.

Anyone have an idea on how to deal with such a problem?

Thanks a lot!

GiulioSanto
  • 70
  • 5
  • 1
    Please provide a [MWE](https://stackoverflow.com/help/minimal-reproducible-example). – joni May 01 '21 at 16:40
  • Use `F(X/sum(X))` as objective. One remaining issue: all `x=0`. Return a large obj for that case. – Erwin Kalvelagen May 01 '21 at 18:23
  • Amazing Erwin, that is it! Can you please post as an answer, so I can accept it? – GiulioSanto May 02 '21 at 16:10
  • Have you come across Augmented Lagrange Multiplier? It can save you the hassle by converting your constrained optimization to unconstrained optimization :D –  Mar 31 '22 at 15:28

2 Answers2

0

The NLP solvers I typically use will not ask for function and gradient evaluations when X is outside its bounds. That means we can protect things like sqrt(x) and log(x) by adding appropriate lower bounds.

Constraints can not be assumed to hold when we evaluate functions and gradients.

If your function assumes sum(X)=1, you could call F(X/sum(X)). The only complication is when X=0. In that case, return a large value for F so that the solver will move away from it.

Erwin Kalvelagen
  • 15,677
  • 2
  • 14
  • 39
-1

The must sum to 1 constraint effectively reduces the number of variables you need to optimize. If you know the value of all but one of your variables the remaining value is implied by the constraint. It must be exactly 1 - sum(other_vars)

Instead of optimizing five variables X = [x1, x2, x3, x4, x5] you can optimize four variables and compute the fifth: X = [x1, x2, x3, x4, 1 - (x1 + x2 + x3 + x4)].

This formulation of the optimization problem avoids imprecisions that might arise if all X are very low.

If the variables are percentages you will want to specify lower and upper bounds of 0 and 1, respectively. Furthermore, you will need to constrain x1+x2+x3+x4 <= 1 to avoid negative x5. (This inequality constraint is much easier for optimizers than the original equality constraint.)

def cost_function(X):
    x1, x2, x3, x4 = X
    x5 = 1.0 - (x1, x2, x3, x4)    
    return F((x1, x2, x3, x4, x5))

x0 = [0.2, 0.2, 0.2, 0.2]  # initial guess: all values equal
minimize(cost_function, x0, 
         bounds=[(0.0, 1.0)]*4, 
         constraints=dict(type='ineq', fun=lambda X: 1.0 - X.sum()))
MB-F
  • 22,770
  • 4
  • 61
  • 116
  • Similar answer to a very different question: https://stackoverflow.com/a/45712241/3005167 – MB-F May 03 '21 at 09:33
  • Thanks a lot for your answer @kazemakase. The problem in doing ```1 - sum(other_vars)``` is that if we have, for instance, x1 = 0.7 and z2 = 0.8, which will result in a negative x5. – GiulioSanto May 03 '21 at 12:29
  • I think this approach has the same (or similar) deficiency the original post was about. Solvers do not obey constraints for all iterations. Although, in this case, the summation to one is always obeyed, now the bounds on x5 are not honored (until at the end of the run when the problem is optimal -- and feasible). So we are just swapping one kind of infeasibity for another. – Erwin Kalvelagen May 03 '21 at 18:25