Fitting under-determined simultaneous equations with additional constraints

Question

I am trying to find a method to fit an under-determined system of simultaneous equations with an additional constraint. In the example below I am trying to find the coefficients $m_1$, $m_2$, $\dots$, $m_7$, obeying $\dots$

$$\begin{pmatrix} 5 & 7& 4& 0& 6& 0& 0 \\ 5& 7& 0& 9& 0& 8& 0 \\ 5& 0& 4& 9& 0& 0& 3 \end{pmatrix}\begin{pmatrix} m_1 \\ m_2 \\ m_3 \\ m_4 \\ m_5 \\ m_6 \\ m_7 \end{pmatrix} = \begin{pmatrix} 225 \\ 270 \\ 230 \end{pmatrix}$$

$\dots$ and subject to the constraint that the different between the coefficients is a small as possible, i.e. ideally $m_1 = m_2 = \dots = m_7$.

If anyone knows of a method for fitting such a system that would be much appreciated.

Answer 1

What you are calling a constraint should be called an objective function. Therefore, depending on the choice of objective function to be optimized, subject to the constraint that the equations are solved, you are trying to solve an optimization problem.

As for the objective function, the p-norm of m - mean(m) for various possible values of p might make sense.

p = 1 would minimize average absolute deviation.

p = 2 would minimize (square root of) average squared deviation, and is the same as standard deviation of m.

p = infinity ("inf" below) minimizes the largest (among the 7 components) absolute deviation from the mean.

Here are the formulation and solutions under YALMIP under MATLAB; The optimizations are shown in the order 1-norm, 2-norm, inf-norm.

A=[5 7 4 0 6 0 0;5 7 0 9 0 8 0;5 0 4 9 0 0 3];
b=[225 270 230]';
m=sdpvar(7,1);optimize(A*m==b,norm(m-mean(m),1))

Optimal m per 1-norm = 10.2510 8.0723 13.9332 10.2510 10.2510 8.7475 10.2510

m=sdpvar(7,1);optimize(A*m==b,norm(m-mean(m),2))

Optimal m per 2-norm = 10.7633 8.5358 11.8951 10.5422 10.6421 7.6941 11.2411

m=sdpvar(7,1);optimize(A*m==b,norm(m-mean(m),inf))

Optimal m per inf-norm = 12.2209 8.3697 12.2209 9.2611 9.4040 8.3697 12.2209

Another objective function which could be minimized is max(m) - min(m).

m=sdpvar(7,1);optimize(A*m==b,max(m)-min(m))

Optimal m per max - min = 11.2956 7.9380 11.2956 10.4947 11.2956 7.9380 11.2956

In the following table, each of the first 3 rows corresponds to which norm is being minimized (respectively 1, 2, infinity), with the last row minimizing max(m) - min(m). Each of the first 3 columns corresponds to the norm of the deviation from the mean in the respective norms, with the last column being max(m) - min(m). As can be seen, the best 1-norm is obtained when that is what is being optimized. Similarly for the other norms, and for max - min. You can judge which of these solutions is best according to your preferences.

              1-norm    2-norm   inf norm   max(m)-min(m)
    1.0000    7.3645    4.5350    3.6822      5.8609
    2.0000    8.2908    3.6926    2.4936      4.2010
       Inf   11.5534    4.5170    1.9256      3.8511 
  max - min   9.1357    3.8883    2.2839      3.3577