How do I solve the following multivariable minimization optimization problem?

Question

$$\begin{array}{ll} \text{minimize} & b_1 x_1 + b_2 x_2 + b_3 x_3 + b_4 x _4\\ \text{subject to} & x_1 + x_2 + x_3 + x_4 = 1\\ & \end{array}$$

$$d(1)x(1) +d(2)x(2) + d(3)x(3) + d(4)x(4) \leq Dt$$

$$b(1) > b(2) > b(3) > b(4) $$

$$d(1) < d(2) < d(3) < d(4) $$

• The four variables $x(1)$ to $x(4)$ represent percentages and must add up to $1$
• Is there a minimum for the objective function such that all the constraints are satisified? How to approach such a problem?

Answer 1

Calling

$$ \cases{ f(x) = \sum_k b_k x_k^2\\ r_1(x) = \sum_k x_k^2 - 1\\ r_2(x,s) = \sum_k d_k x_k^2-D+s^2 } $$

we have the lagrangian

$$ L(x,\lambda,\mu,s) = f(x)+\lambda r_1(x)+\mu r_2(x,s) $$

here $s$ is a slack variable to transform the inequality into an equivalent equation.

The stationary points are the solutions for

$$ \nabla L = \cases{ b_j x_j+\lambda x_j + \mu d_j x_j = 0,\ \ j=1,\cdots,4\\ \sum_k x_k^2 - 1=0\\ \sum_k d_k x_k^2-D+s^2=0\\ \mu s = 0 } $$

giving

$$ \left[ \begin{array}{cccccccc} f & x_1^2 & x_2^2 & x_3^2 & x_4^2 & \lambda &\mu & s^2 & \text{condition}\\ b_1 & 1 & 0 & 0 & 0 & -b_1 & 0 & D-d_1 & D\ge d_1\\ b_2 & 0 & 1 & 0 & 0 & -b_2 & 0 & D-d_2 & D\ge d_2\\ b_3 & 0 & 0 & 1 & 0 & -b_3 & 0 & D-d_3 & D \ge d_3\\ b_4 & 0 & 0 & 0 & 1 & -b_4 & 0 & D-d_4 & D\ge d_4\\ \frac{b_2 \left(d_1-D\right)}{d_1-d_2}+\frac{b_1 \left(d_2-D\right)}{d_2-d_1} & \frac{d_2-D}{d_2-d_1} & \frac{d_1-D}{d_1-d_2} & 0 & 0 & \frac{b_1 d_2-b_2 d_1}{d_1-d_2} & \frac{b_2-b_1}{d_1-d_2} & 0 & d_1\le D\le d_2\\ \frac{b_3 \left(d_1-D\right)}{d_1-d_3}+\frac{b_1 \left(d_3-D\right)}{d_3-d_1} & \frac{d_3-D}{d_3-d_1} & 0 & \frac{d_1-D}{d_1-d_3} & 0 & \frac{b_1 d_3-b_3 d_1}{d_1-d_3} & \frac{b_3-b_1}{d_1-d_3} & 0 & d_1\le D\le d_3\\ \frac{b_3 \left(d_2-D\right)}{d_2-d_3}+\frac{b_2 \left(d_3-D\right)}{d_3-d_2} & 0 & \frac{d_3-D}{d_3-d_2} & \frac{d_2-D}{d_2-d_3} & 0 & \frac{b_2 d_3-b_3 d_2}{d_2-d_3} & \frac{b_3-b_2}{d_2-d_3} & 0 & d_2\le D\le d_3\\ \frac{b_4 \left(d_1-D\right)}{d_1-d_4}+\frac{b_1 \left(d_4-D\right)}{d_4-d_1} & \frac{d_4-D}{d_4-d_1} & 0 & 0 & \frac{d_1-D}{d_1-d_4} & \frac{b_1 d_4-b_4 d_1}{d_1-d_4} & \frac{b_4-b_1}{d_1-d_4} & 0 & d_1\le D \le d_4\\ \frac{b_4 \left(d_2-D\right)}{d_2-d_4}+\frac{b_2 \left(d_4-D\right)}{d_4-d_2} & 0 & \frac{d_4-D}{d_4-d_2} & 0 & \frac{d_2-D}{d_2-d_4} & \frac{b_2 d_4-b_4 d_2}{d_2-d_4} & \frac{b_4-b_2}{d_2-d_4} & 0 & d_2\le D \le d_4\\ \frac{b_4 \left(d_3-D\right)}{d_3-d_4}+\frac{b_3 \left(d_4-D\right)}{d_4-d_3} & 0 & 0 & \frac{d_4-D}{d_4-d_3} & \frac{d_3-D}{d_3-d_4} & \frac{b_3 d_4-b_4 d_3}{d_3-d_4} & \frac{b_4-b_3}{d_3-d_4} & 0 &d_3\le D \le d_4\\ \end{array} \right] $$

NOTE

We used $x_k^2$ to assure the positiveness. When $s=0$ indicates that $r_2(x,s)$ is actuating. The table of results should be interpreted according to the given condition at the last column.

Attached a python script to check the found stationary points. Note that the python solver only catches one solution. Changing the values for D0 we can observe the diverse solutions.

from scipy.optimize import linprog

b1 = 9
b2 = 8
b3 = 7
b4 = 6
d1 = 2
d2 = 4
d3 = 6 
d4 = 8
D0 = 5
res = \
[[b1, 1, 0, 0, 0, -b1, 0, D0 - d1], 
 [b2, 0, 1, 0, 0, -b2, 0, D0 - d2], 
 [b3, 0, 0, 1, 0, -b3, 0, D0 - d3], 
 [b4, 0, 0, 0, 1, -b4, 0, D0 - d4], 
 [(b2*(-D0 + d1))/(d1 - d2) + (b1*(-D0 + d2))/(-d1 + d2), (-D0 + d2)/(-d1 + d2), (-D0 + d1)/(d1 - d2), 0, 0, (-b2*d1 + b1*d2)/(d1 - d2), (-b1 + b2)/(d1 - d2), 0], 
 [(b3*(-D0 + d1))/(d1 - d3) + (b1*(-D0 + d3))/(-d1 + d3), (-D0 + d3)/(-d1 + d3), 0, (-D0 + d1)/(d1 - d3), 0, (-b3*d1 + b1*d3)/(d1 - d3), (-b1 + b3)/(d1 - d3), 0], 
 [(b3*(-D0 + d2))/(d2 - d3) + (b2*(-D0 + d3))/(-d2 + d3), 0, (-D0 + d3)/(-d2 + d3), (-D0 + d2)/(d2 - d3), 0, (-b3*d2 + b2*d3)/(d2 - d3), (-b2 + b3)/(d2 - d3), 0], 
 [(b4*(-D0 + d1))/(d1 - d4) + (b1*(-D0 + d4))/(-d1 + d4), (-D0 + d4)/(-d1 + d4), 0, 0, (-D0 + d1)/(d1 - d4), (-b4*d1 + b1*d4)/(d1 - d4), (-b1 + b4)/(d1 - d4), 0], 
 [(b4*(-D0 + d2))/(d2 - d4) + (b2*(-D0 + d4))/(-d2 + d4), 0, (-D0 + d4)/(-d2 + d4), 0, (-D0 + d2)/(d2 - d4), (-b4*d2 + b2*d4)/(d2 - d4), (-b2 + b4)/(d2 - d4), 0], 
 [(b4*(-D0 + d3))/(d3 - d4) + (b3*(-D0 + d4))/(-d3 + d4), 0, 0, (-D0 + d4)/(-d3 + d4), (-D0 + d3)/(d3 - d4), (-b4*d3 + b3*d4)/(d3 - d4), (-b3 + b4)/(d3 - d4), 0]
]

print("------stationary points------")

for i in range(10):
    resi = res[i]
    OK = True
    for j in range(5):
        if resi[j] < 0:
            OK = False
    if resi[7] < 0:
        OK = False
    if OK: 
        print(resi[0],[resi[1],resi[2],resi[3],resi[4]])
    
print(30*'-')
print("------------result------------")
obj      = [b1, b2, b3, b4]
lhs_eq   = [[1, 1, 1, 1]]
rhs_eq   = [1]
lhs_ineq = [[d1, d2, d3, d4]]
rhs_ineq = [D0]
bnd      = [(0,float("inf")),(0,float("inf")),(0,float("inf")),(0,float("inf"))]
opt      = linprog(c=obj, A_ub=lhs_ineq, b_ub=rhs_ineq, A_eq=lhs_eq, b_eq=rhs_eq, bounds=bnd, method="revised simplex")
print(opt.fun, opt.x)