Python How to find solution x+y+z=1 using line search

Question

I want to find 3 weights x, y, z by using line search method and Python, where x, y, z are non-negative and their sum is one.

My code as follows :

import numpy as np
import itertools as it

grid_number = 100 ## number of grid
line_grid = np.linspace(0,1,grid_number+1) ## 100+1 grid 0, 0.01, 0.02, ... , 0.99, 1
all_combination_of_line_grid = list(it.product(line_grid,line_grid,line_grid)) ## all combination of 3 weights
solution = [x for x in all_combination_of_line_grid if x[0]+x[1]+x[2] == 1] ## filter weights satisfying x+y+z = 1

The above code works. But I want to have more solution. When I increase grid number, say 1000, my computer stopped. Maybe it related with some memory problem. There are 1000X1000X1000 elements!!
So, I find method such as batch reading large number of elements of list.

Is there any solution? Any help will go to gratitude. Thank you!

Answer 1

Several things can improve the performance of your code by:

1. I noticed when running your code that some combinations does not appear. I think it's because you are testing equality x[0]+x[1]+x[2] == 1 on float elements and it may give False when you expect True.
2. You can avoid the construction of all the combinations (it.product) but just iterate through them with a list comprehension (solution2 in code below).
3. For even better performance, you can just replace x[2]=1-x[0]-x[1] and loop only over the first two values (solution3 in code below).

Here is a working example:

import numpy as np
import itertools as it
import time

grid_number = 100 ## number of grid

t_start = time.time()
line_grid = np.linspace(0,1,grid_number+1) ## 100+1 grid 0, 0.01, 0.02, ... , 0.99, 1
all_combination_of_line_grid = list(it.product(line_grid,line_grid,line_grid)) ## all combination of 3 weights
solution1 = [x for x in all_combination_of_line_grid if x[0]+x[1]+x[2] == 1] ## filter weights satisfying x+y+z = 1
print('Timer 1: ', (time.time()-t_start), 's')

t_start = time.time()
solution2 = [(i/grid_number,j/grid_number,k/grid_number)
             for i in range(grid_number+1) 
             for j in range(grid_number+1) 
             for k in range(grid_number+1) if i+j+k == grid_number] ## filter weights satisfying x+y+z = 1
print('Timer 2: ', (time.time()-t_start), 's')

t_start = time.time()
solution3 = []
for j in range(grid_number+1):
    solution3 += [(i/grid_number,j/grid_number,(grid_number-i-j)/grid_number)
                  for i in range(grid_number+1-j)]
print('Timer 3: ', (time.time()-t_start), 's')

print('Nb of combinations 1:', len(solution1))
print('Nb of combinations 2:', len(solution2))
print('Nb of combinations 3:', len(solution3))

Output:

% python3 script.py
Timer 1:  0.6716141700744629 s
Timer 2:  0.07801079750061035 s
Timer 3:  0.002294778823852539 s
Nb of combinations 1: 5027
Nb of combinations 2: 5151
Nb of combinations 3: 5151

As you can see the last solution is the fastes. Moreover, your code has found only 5027 combinations out of 5151.