This page is to distill an algebra slog I’ve been doing that is useful for some optimization spaces. Less dimensions is usually better, and we can use equality constraints to express some parameters and combinations of others, and essentially work in a lower dimensional space. Maybe there’s a better way to use this using a more general linear algebra approach but the algebra for this cases was doable enough in a short time.

Say we are working in some linear system, in my case I’ve been doing optimization where the objective function is determined experimentally and not analytically.

In the base case we have continuous real parameters xi, i∈I, with lower and upper bounds for each, Li and Ui. And usually we’ll have some linear constraint.

∑Icixi≤CLi≤xi≤Uii∈I

The simplex constraint

Now let’s introduce the simplex constraint, the sum of parameters equals some total T.

∑Ixi=T∑Icixi≤CLi≤xi≤Uii∈I

Let’s select a parameter to remove from the search space, x1. Using (3), we can express it as a function of the other parameters,

x1=T−∑I∖1xi

Subbing this value into (4) and the i=1 constraint of (5), we get the new space to work in:

∑I∖1(ci−c1)xi≤C−c1TT−U1≤∑I∖1xi≤T−L1Li≤xi≤Uii∈I∖1

The simplex constraint and one additional linear equality constraint

Now let’s introduce a linear equality constraint.

∑Ixi=T∑Iaixi=A∑Icixi≤CLi≤xi≤Uii∈I

Using equations (10) and (11), we can extract parameters x1 and x2 as a function of the other parameters. Not for the following to work, we require that a1≠a2.

x1=a2T−Aa2−a1−∑I∖1,2a2−aia2−a1xix2=A−a1Ta2−a1−∑I∖1,2ai−a1a2−a1xi

Subbing this value into (12) and the i=1,2 constraints of (13), we get the new space to work in:

∑I∖1,2(ci−c1a2−c2a1−(c1−c2)aia2−a1)xi≤C−(c1a2−c2a1)T−(c1−c2)aia2−a1a2T−Aa2−a1−U1≤∑I∖1,2a2−aia2−a1xi≤a2T−Aa2−a1−L1A−a1Ta2−a1−U2≤∑I∖1,2ai−a1a2−a1xi≤A−a1Ta2−a1−L2Li≤xi≤Uii∈I∖1,2

The simplex constraint and two additional linear equality constraints

Let’s have two equality constraints.

∑Ixi=T∑Iaixi=A∑Ibixi=B∑Icixi≤CLi≤xi≤Uii∈I

This can get away from us very quickly. But if we are wise and want to avoid too much algebra, we can carefully select things so that

a1=0a2≠0b1,b2=0b3≠0

Then things fall out nicely from (20), (21), and (22). We can express x1,x2,x3 explicitly in terms of the other parameters.

x1=T−Ab3+(a2−a3)Ba2b3−∑I∖1,2,3(1−aib3+(a2−a3)bia2b3)xix2=Ab3−a3Ba2b3−∑I∖1,2,3aib3−a3bia2b3xix3=Bb3−∑I∖1,2,3bib3xi

Subbing these values into (23) and the i=1,2,3 constraints for (24) we get the new space to work in

∑I∖1,2,3[ci−c1−c2−c1a2ai−a2c3−a3c2−(a2−a3)c1a2b3bi]xi≤C−c1T−c2−c1a2A−a2c3−a3c2−(a2−a3)c1a2b3BT−1a2A−a2−a3a2b3B−U1≤∑I∖1,2,3(1−1a2ai−a2−a3a2b3bi)xi≤T−1a2A−a2−a3a2b3B−L1Ab3−a3B−a2b3U2≤∑I∖1,2,3(aib3−a3bi)xi≤Ab3−a3B−a2b3L2B−b3U3≤∑I∖1,2,3bixi≤B−b3L3Li≤xi≤Uii∈I∖1,2,3