Re: Gaussian elimination with guaranteed positive coefficients

I don't thing Gaussian elimination is the right tool for your problem.
It looks like an optimization problem ( or a set of inequalities ) where
your positivity requirements are just further constraints.
If your functions W(a), etc, are linear, this is a classical linear
optimization problem, otherwise it's a nonlinear optimization problem.
Have a look at http://plato.la.asu.edu/guide.html

Marshall wrote:
Hi All,

I'm experimenting with gaussian elimination as a method for solving
percentage-based linear systems. In other words, all of the resulting
coefficients must be positive values and the sum of all coefficients
must be 1.

Is anyone familiar with a gaussian elimination algorithm variant (or a
completely different computational approach to the problem) that will
always search for a positive coefficient solution?

My concern with the generic triangular echelon/back-substitution
implementation is that the algorithm will (I believe) complete on the
first match, which might contain negative coefficients, even if an
all-positive-coefficient solution exists.

I can, of course, handle the "add up to one" portion by using an
equation like "a + b + c = 1".

Eventually, I'll be using numerical iteration in combination with the
linear system solver to locate valid coefficient sets. As a trivial
example, let's say that we want to light our office with three
different light bulbs, and have only one light bulb on at a time. Each
light bulb (a, b and c) has a different wattage and lifespan. Say
further that we want our average power consumption per day to be
between 6 and 7 watts, and we want all of our bulbs to burn out between
200 and 250 days. The application would allow us to specify each light
bulb's attributes, plug in the desired ranges, and then solve for the
length of time as a percentage of the whole day that each light bulb
should be left on. Therefore the equations to solve would be:

6 < W(a) * a + W(b) * b + W(c) * c < 7
200 < L(a) * a + L(b) * b + L(c) * c < 250
a + b + c = 1

Where W(a) and L(a) are respectively the wattage and lifespan of light
bulb a, and so on. Any set of positive coefficient values for a, b and
c would represent a valid solution to the problem. The application
would therefore iterate over the complete range for W and L to create
an map of all value combinations that generate valid coefficients.

If there were more than just two range requirements (say we also want
our lightbulbs to average a certain number of lumens) then we would
calculate the solution map for each combination of two ranges
separately and then analyze the resulting maps for overlap. If there
were less than two range requirements we would choose arbitrary
in-range values for one of the light bulbs to reduce the number of
coefficients and then solve for the other light bulb coefficients.

Does this sound feasible? Can anyone think of a better way to tackle
this type of problem? Does anyone know of an algorithm for solving
systems of linear equations that meets these requirements?


--
Helmut Jarausch

Lehrstuhl fuer Numerische Mathematik
RWTH - Aachen University
D 52056 Aachen, Germany
.

Relevant Pages

  • Re: Gaussian elimination with guaranteed positive coefficients
    ... It seems that linear optimization is exactly ... If your functions W, etc, are linear, this is a classical linear ... coefficients must be positive values and the sum of all coefficients ... different light bulbs, and have only one light bulb on at a time. ...
    (sci.math.num-analysis)
  • Re: Trying to solve 2 homogenous quadratics
    ... Firstly, if F, G, or any linear combination of them, is definite then ... Step 1 - Express F in Determinant Form ... we can assume that one of the non-zero coefficients ...
    (sci.math)
  • Re: Polynomial regression analysis
    ... >>That is just another multiple LINEAR regression model, ... >>> contained zero, say that a linear model was good enough. ... >>will tell you whether each of the polynomial coefficients is ...
    (sci.stat.edu)
  • Re: interaction terms in regression model
    ... effects (simple linear terms) are included then you'll almost surely ... model coefficients can be misleading if not pointless. ... There's yet another point about centering. ... are not statistically significant, ...
    (sci.stat.edu)
  • Re: Volterra series
    ... brute-force employ Volterra series to do it). ... the output of this possibly linear or possibly non-linear ... an FIR filter is a hyperplane! ... of all of the coefficients of any significance, ...
    (comp.dsp)