Maximize multiple linear equations under a single constraint

[Darren1618]

Hi, I hope this is going in the proper place, its essentially maximizing a matrix so here goes:

Given the independant variables a, b, c, d, and e, and the system

[ 1 1 0 5 1 | A ]
[ 0 3 0 1 1 | B ]
[ 4 1 1 0 1 | C ]
[ 1 0 3 1 0 | D ]

I want to find the a, b, c, d, and e that will maximize A, B, C, and D simultaneously under the given constraint

a + b + c + d + e = x, x a given arbitrary value (lets say 25)

I have not found a single thing on the internet that explains a method to go about optimizing anything more than one linear equation and thousands of constraints. I figure this may be in the realm of statistical analysis so cry pardon if its in the wrong folder. I am not much of a math genius (hacking away at precalc and differentials at the moment) but this was more a personal idea. Thanks for any help.

Darren

 

[Stephen Tashi]

You haven't defined a specific mathematical problem until you explain what "maximize simultaneously" means. Do you mean that a solution should simply maximize the sum A + B + C + D?

Suppose one proposed solution gives A = 10 , B = 5 , C = 5, D = 5 and another gives A = 1 , B = 22, C = 1, D = 1. Is there any reason to prefer one of the solutions to the other?

 

[Darren1618]

I am not trying to maximize the sum of the unknown quantities A, B, C, and D. To simplify what I am doing, imagine two quantities A and B, which are both dependant upon variables x, y, and z. If x, y, and z are going to affect A and B simultaneously if you increase or decrease them, then what is the linear equation which would give a maximum for both A and B? Granted, my matrix is quite a bit hairier than that, but its the same idea.

Essentially instead of dealing with one linear equation with potentially thousands of constraints, I am dealing with potentially thousands of linear equations with only one constraint. I do intend to add more constraints to this problem but for now one seems plenty. I have also tried visualizing the problem as the opposite of linear regression; I have a bunch of lines and I want the points that fit best within all of those lines. For all I know this may be the method of solving the problem.

Darren

 

[Stephen Tashi]

You didn't clarify your question. You seem to assume that some value of the variables will simultaneously make A and B attain their maximum possible values. It isn't evident to me why this would be true. Suppose A = a , B = b and the constraint is a + b = 1. The bigger you make A, the smaller you must make B.

Linear regression involves minimizing an error function. To describe your idea of "the reverse of linear regression" completely, you need to define what you mean by "fit best". What function are you using to measure "fit"? One guess would be that you are trying to minimize the sum of the squares of the distances from each point to each line. However, that interpretation doesn't agree with your example. In your example, you state that the variables are a,b,c,d,e and you write a matrix that suggests a set of linear equations beginning with 1a + 1b + 0c + 5d + 1e = A and you say that A is one of the things you want to maximize.

 

[Darren1618]

Hmmmm

I'll try to be more specific, the problem is I have shown this to numerous instructors in my math department and nobody seems to know either. You are right about the first line of the matrix, and if we take the second line of the matrix there are values for a, b, c, d, and e which will make the best possible values for A and B at the same time. If we take the third line and include C, there are values for a, b, c, d, and e which will make the best possible values for A, B, and C at the same time. I am not adding the capitals together, nor am I finding the highest possible value for any of the capitals, but rather the highest possible value they all can achieve at the same time.

I speak of linear regression because it is a collection of points that are interpreted to find a line that minimizes error amongst the points for predictions about data that the points don't represent. What I think I want to do is take a collection of lines and find points that fit those lines best. I could be completely off with this theory but its the only idea that comes to mind what with my experience.

Aha! I completely forgot this rather important fact: a, b, c, d, and e are elements of the whole number system, no rationals, radicals, or integars (or complex). This problem came up in a game I created. I wished to develop a way to generate large amount of data about statistics certain creatures in the game would possess. These statistics (a,b,c,d,e) would then affect another set of statistics (A,B,C,D) which would have a direct affect on the game. The full matrix explaining how each independant statistic affects the dependant statistics is 10x7. I wish to pull 2-5 rows of this larger matrix out and make a new 2-5x7 matrix, then calculate the best possible outcome for the dependant statistics assuming I only have say 20 or 25 "points" to add to the independant statistics. If this system could be automated the advantage is the creatures would then have the best possible statistics only in certain fields, making them particularly powerful in some respects and not so much in others. By increasing the amount of rows that will be optimized in the equation, yet keeping the same constraint of 20 or 25, more dependant statistics would be raised, but not as high as the one with only two stats to optimize. (I think I'm really screwing you up because I want to optimize not maximize I suppose) I hope that makes more sense, if not I could always attach scans of my notes, although they don't seem to help anyone else visualize it either except Dave.

Darrem

 

[Stephen Tashi]

Nobody knows because you are not defining a specific problem.

if we take the second line of the matrix there are values for a, b, c, d, and e which will make the best possible values for A and B at the same time.

Are the a,b,c,d and e variables or numerical values?

If they are specific numerical values, It doesn't make any sense to talk about putting a "constraint" on them. They are already constrained to be specific values.

If they are variables, then you still have the problem of saying what you mean by "the best possible values for A and B at the same time". And you didn't respond to my example.

Variables a,b

Matrix:
1 0 | A
0 1 | B

constraint a + b = 1

What are the values of a and b that give "the best possible values for A and B at the same time"?

 

[Darren1618]

The example isn't really applicable since I don't want to deal with rational numbers, but the answer would be a = .5 and b = .5, in the sense I am trying to visualize here. I say this because this is the largest possible answer for both A and B simultaneously. If you lowered either a or b then A or B would then not be the highest possible answer achievable simultaneously. I guess this is still vague, but the best I can expand your idea at the moment is if you expanded your example to

[ 1 0 0 | A ]
[ 0 1 0 | B ]
[ 0 0 1 | C ]

with variables a, b, and c, the answer that I would want (the optimization I am looking for) is a = 1/3, b = 1/3, and c = 1/3.

The problem is this logic is rather difficult to keep up with when the independant variables (a,b,c,d,e are variables) affect the dependant variables A,B,C,D differently as well as similarly. Essentially though there is some way to get the highest possible outcome for all A,B,C,D without lowering one of them in favor of the other. Cry pardon I can't explain it any more than this, I have my main math studies and a family to tend to. I can't see what else I could say about the problem though. Have I cleared up the confusion enough yet? Hope so.

Darren

 

[HallsofIvy]

You have repeatedly used both "a, b, c, d" and "A, B, C, D". If those are different things then it you have not yet shown any relationship between them.

 

[Stephen Tashi]

Darren1618,

You'll have to state precisely what it means for one solution to be better than another before anyone in the math department can help you!

I'll make an attempt. I think the way you are rating solutions is called a "partial order". So you would say outcome (A2,B2,C2) was better or equal to outcome (A1,B1,C1) if (and only if) A2 >= A1 and B2 >= B1 and C2>= C2.

By that definition the result A = 2, B = 1, C = 1/3 is better than the outcome A = 1/3, B = 1/3, C= 1/3. But the outcome A = 500, B = 400, c = 1/4 is not better than A = 1/3, B = 1/3, C = 1/3. Correct?

 

[hotvette]

I'm guessing that the problem is:

| 1 1 0 5 1 |  | a |   | A |
| 0 3 0 1 1 |  | b |   | B |
| 4 1 1 0 1 |  | c | = | C |
| 1 0 3 1 0 |  | d |   | D | 
               | e |

where:

1. a + b + c + d + e = constant
2. a, b, c, d, e are positive integers
3. Goal is find a,b,c,d,e to 'maximize' A, B, C, D

The 3rd item is ambiguous and needs to be stated in mathematical terms (e.g. maximize the minimum of A, B, C, D). If the above is all true, I think this is an exercise in integer programming.

 

[Darren1618]

Stephen, I think your right but it is sort of confusing and I don't want to rant my thoughts on it because I don't know if it would even be right. Hotvette though, if your multiplying that column (vector?) to the matrix (determinate?) then yes that is the idea. I really can't think of any way to say what I want other than A, B, C, and D might not actually reach their potential maximum, because they all must be raised with equal...significance? So the optimum values for A, B, C, and D must be as close to each other as possible given the constraint.

So I suppose this would be a problem of integar programming? I'll have to look this up. Thanks for the help Stephen and Hotvette, I probably won't understand the concept of it but I'm glad to know it exists.

Darren