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 $x_i,\ i\in\mathcal{I}$, with lower and upper bounds for each, $L_i$ and $U_i$. And usually we’ll have some linear constraint.

\begin{align} \sum_\mathcal{I}c_ix_i &\le C \newline L_i \le x_i & \le U_i \qquad i\in\mathcal{I} \end{align}

The simplex constraint

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

\begin{align} \sum_\mathcal{I} x_i &= T\newline \sum_\mathcal{I}c_ix_i &\le C\newline L_i \le x_i &\le U_i \qquad i\in\mathcal{I} \end{align}

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

\begin{align} x_1 &= T - \sum_{\mathcal{I}\setminus 1}x_i \end{align}

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

\begin{align} \sum_{\mathcal{I}\setminus 1}(c_i-c_1)x_i &\le C - c_1T\newline T - U_1 \le \sum_{\mathcal{I}\setminus 1}x_i &\le T - L_1\newline L_i \le x_i &\le U_i \qquad i\in\mathcal{I}\setminus 1 \end{align}

The simplex constraint and one additional linear equality constraint

Now let’s introduce a linear equality constraint.

\begin{align} \sum_\mathcal{I} x_i &= T\newline \sum_\mathcal{I}a_ix_i &= A\newline \sum_\mathcal{I}c_ix_i &\le C\newline L_i \le x_i &\le U_i \qquad i\in\mathcal{I} \end{align}

Using equations (10) and (11), we can extract parameters $x_1$ and $x_2$ as a function of the other parameters. Not for the following to work, we require that $a_1\ne a_2$.

\begin{align} x_1 &= \frac{a_2T - A}{a_2-a_1} - \sum_{\mathcal{I}\setminus 1,2}\frac{a_2-a_i}{a_2-a_1}x_i\newline x_2 &= \frac{A-a_1T}{a_2-a_1} - \sum_{\mathcal{I}\setminus 1,2}\frac{a_i-a_1}{a_2-a_1}x_i\newline \end{align}

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

\begin{align} \sum_{\mathcal{I}\setminus 1,2}\left(c_i-\frac{c_1a_2 - c_2a_1 - (c_1-c_2)a_i}{a_2-a_1}\right)x_i &\le C - \frac{(c_1a_2 - c_2a_1)T - (c_1-c_2)a_i}{a_2-a_1}\newline \frac{a_2T - A}{a_2-a_1}-U_1 \le \sum_{\mathcal{I}\setminus 1,2}\frac{a_2-a_i}{a_2-a_1}x_i &\le \frac{a_2T - A}{a_2-a_1}-L_1\newline \frac{A - a_1T}{a_2-a_1}-U_2 \le \sum_{\mathcal{I}\setminus 1,2}\frac{a_i-a_1}{a_2-a_1}x_i &\le \frac{A - a_1T}{a_2-a_1}-L_2\newline L_i \le x_i &\le U_i \qquad i\in\mathcal{I}\setminus 1,2 \end{align}

The simplex constraint and two additional linear equality constraints

Let’s have two equality constraints.

\begin{align} \sum_\mathcal{I} x_i &= T\newline \sum_\mathcal{I}a_ix_i &= A\newline \sum_\mathcal{I}b_ix_i &= B\newline \sum_\mathcal{I}c_ix_i &\le C\newline L_i \le x_i &\le U_i \qquad i\in\mathcal{I} \end{align}

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

\begin{align} a_1&=0\newline a_2&\ne0\newline b_1,b_2&=0\newline b_3&\ne0 \end{align}

Then things fall out nicely from (20), (21), and (22). We can express $x_1,x_2,x_3$ explicitly in terms of the other parameters.

\begin{align} x_1 &= T - \frac{Ab_3 + (a_2-a_3)B}{a_2b_3} - \sum_{\mathcal{I}\setminus 1,2,3}\left(1-\frac{a_ib_3 + (a_2-a_3)b_i}{a_2b_3}\right)x_i\newline x_2 &= \frac{Ab_3 - a_3B}{a_2b_3} - \sum_{\mathcal{I}\setminus 1,2,3}\frac{a_ib_3 - a_3b_i}{a_2b_3}x_i\newline x_3 &= \frac{B}{b_3} - \sum_{\mathcal{I}\setminus 1,2,3}\frac{b_i}{b_3}x_i\newline \end{align}

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

\begin{align} \sum_{\mathcal{I}\setminus 1,2,3} \left[ c_i - c_1 - \frac{c_2-c_1}{a_2}a_i - \frac{a_2c_3 - a_3c_2 - (a_2-a_3)c_1}{a_2b_3}b_i\right]x_i &\le C - c_1T - \frac{c_2-c_1}{a_2}A - \frac{a_2c_3 - a_3c_2 - (a_2-a_3)c_1}{a_2b_3}B \newline T - \frac{1}{a_2}A - \frac{a_2-a_3}{a_2b_3}B - U_1 \le \sum_{\mathcal{I}\setminus 1,2,3} \left(1 - \frac{1}{a_2}a_i - \frac{a_2-a_3}{a_2b_3}b_i\right)x_i & \le T - \frac{1}{a_2}A - \frac{a_2-a_3}{a_2b_3}B - L_1\newline Ab_3 - a_3B - a_2b_3U_2 \le \sum_{\mathcal{I}\setminus 1,2,3}\left(a_ib_3 - a_3b_i\right)x_i &\le Ab_3 - a_3B - a_2b_3L_2\newline B - b_3U_3 \le \sum_{\mathcal{I}\setminus 1,2,3} b_ix_i &\le B - b_3L_3\newline L_i \le x_i &\le U_i \qquad i\in\mathcal{I}\setminus 1,2,3 \end{align}