There are two ways to approach this:
- From the method that you developed in your post. Randomly generate
x1 and x2 and make sure vt < v1*x1 + v2*x2 , then go ahead and solve for x3 . - Formulate this in a linear program . A linear program basically solves a system of equations that obey inequality or equality constraints. In other words:
In this way, we can translate your problem into a linear programming problem. The maximize statement is what is known as the objective function — the overall goal of what you are trying to accomplish. In linear programming problems, we try to minimize or maximize this goal. To do this, we must satisfy the inequalities observed in the condition . Usually this program is presented in canonical form , so the restrictions on each variable should be positive.
The maximization condition can be arbitrary, since you do not care about the goal. You just need some solution. This whole paradigm can be achieved by linprog in MATLAB. What you should do is how linprog pointed linprog . In fact, the goal is minimized , not maximized. The conditions, however, are the same, except that all variables are positive. We will have to code this in ourselves.
In terms of an arbitrary goal, we can simply do x1 + x2 + x3 . Thus, c = [1 1 1] . Our limitation is: v1*x1 + v2*x2 + v3*x3 = vt . We also need to make sure x positive. To encode this, we can select a small constant so that all x values are greater than this value. linprog does not support strict inequalities right now (i.e. x > 0 ), so we have to get around this by doing this trick. In addition, to ensure that the values are positive, linprog assumes that Ax <= b . Therefore, the general trick that is used is to negate the inequality x >= 0 , and therefore this is equivalent to -x <= 0 . To ensure that the values are non-zero, we would really do: -x <= -eps , where eps is a small constant. However, when I did the experiments, doing it this way, two of the variables end up with the same solution. So, I would recommend that we make good decisions, random every time, let us draw b from a uniform random distribution, as you said. This will give us a starting point every time we want to solve this problem.
Therefore, our inequalities:
-x1 <= -rand1 -x2 <= -rand2 -x3 <= -rand3
rand1, rand2, rand3 - three randomly generated numbers that are between 0 and 1 . In matrix form, these are:
[-1 0 0][x1] [-rand1] [0 -1 0][x2] <= [-rand2] [0 0 -1][x3] [-rand3]
Finally, our equality constraint from the previous one:
[v1 v2 v3][x1] [vt] [x2] = [x3]
Now, to use linprog , you would do this:
X = linprog(c, A, b, Aeq, beq);
c is an array of coefficients defined for the purpose. In this case, it will be defined as [1 1 1] , A , and b is the matrix and column vector defined for inequality restrictions, and Aeq and beq is the matrix and column vector defined for equality constraints, Thus, x gives after linprog converges (i.e., x1, x2, x3 ). So you would do this:
A = -eye(3,3); b = -rand(3,1); Aeq = [v1 v2 v3]; beq = vt; c = [1 1 1]; X = linprog(c, A, b, Aeq, beq);
As an example, suppose v1 = 0.33, v2 = 0.5, v3 = 0.2 and vt = 2.5 . Therefore:
rng(123); %// Set seed for reproducibility v1 = 0.33; v2 = 0.5; v3 = 0.2; vt = 2.5; A = -eye(3,3); b = -rand(3,1); Aeq = [v1 v2 v3]; beq = vt; c = [1 1 1]; X = linprog(c, A, b, Aeq, beq);
I get:
X = 0.6964 4.4495 0.2268
To make sure this is vt , we would do:
s = Aeq*X s = 2.5000
The above is just v1*x1 + v2*x2 + v3*x3 . This is calculated as a point product to simplify the work, since x is a column vector, and v1, v2, v3 already installed in Aeq and are a row vector.
That way, any way is good, but at least with linprog , you don’t need to continue the loop until you get the condition to be satisfied!
A little caution
One small caveat that I forgot to mention in the above approach is that you need to make sure that vt >= v1*rand1 + v2*rand2 + v3*rand3 provides convergence. Since you said that v1,v2,v3 limited between 0 and 1 , the worst case is that v1,v2,v3 are equal to 1. So we really need to make sure that vt > rand1 + rand2 + rand3 . If this is not the case, just take each value rand1, rand2, rand3 and divide by (rand1 + rand2 + rand3) / vt . Thus, this ensures that the summation is equal to vt , assuming that all weights are equal to 1, and this will allow the linear program to converge properly.
If you do not, then the solution will not converge due to the inequality conditions placed in for b , and you will not get the correct answer. Just food for thought! So do it for b before running linprog
if sum(-b) > vt b = b ./ (sum(-b) / vt); end
Good luck