Minimize variation of an equation system

Question

We currently have a mathematical system of equations :

$ \hat{Y}_{N \times 1} = Y_{N \times 1} + a * T_{N \times 1} + b * K_{N \times K} \times M_{K \times 1} $

where

• $a$ and $b$ are constants

• $Y_{N \times 1}$ is a fixed vector of floats (distributed on $N(\mu, \sigma )$)

• $K_{N \times K}$ is a fixed matrix having only one "$1$" per row such as \begin{bmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 1 \end{bmatrix}

• 24 <= $N$ <= 144

• 4 <= $K$ <= 24

• $T_{N \times 1}$ and $M_{K \times 1}$ are the 2 vectors of integers to fit (let say between -20 and +20 for now)

• $\hat{Y}_{N \times 1}$ is a float vector of the result of the linear equation.

I would like to know if there is a way to find one solution to minimize the deviation over $\hat{Y}$ (Standard Deviation or Maximum deviation) ?

I know that with the current state of the problem, it doesn't exist one unique solution. There is missing constrains (N equations, N+K variables). The final optimal solution would be also to minimize the sum of $T_{N \times 1}$ and $M_{N \times 1}$ but it may make the problem even more complicated.

We could try to use Genetic Algorithms but maybe there is a more analytical approach, hence the question :)

Thanks in advance,

Nicolas

Answer 1

I presume T and M are the vectors to be optimally fitted, and they are constrained to be integers.

This can be formulated as an integer-constrained L2 (Euclidean) norm minimization problem (minimize least squares deviations) or as an integer-constrained infinity norm minimization problem (minimize the maximum absolute value of deviation)

I suggest using a package such as CVX (under MATLAN), CVXPY (under Python), or CVXR (under R) to formulate this and call the solver. You will need to have a mixed-integer capable solver installed (for CVX, that would be Gurobi or Mosek).

For the L2 norm formulation, it is more numerically robust and relaible when using one of the above packages to formulate the problem in terms of the norm, rather than the norm squared.

Here is roughly what it would look like for the L2 (Euclidean) norm in CVX:

% It is assumed that a, b, N, K, Yhat, Y are numerically populated as input data
cvx_begin
variable T(N) integer
variable M(N) integer
minimize(norm(Yhat - (Y + a*T + b*K*M),2))
-20 <= T <= 20
-20 <= M <= 20
cvx_end

For infinity norm minimization, just change the 2 to inf, i.e.,

minimize(norm(Yhat - (Y + a*T + b*K*M),inf))

At the conclusion of the program, CVX calls the solver. If CVX reports the problem has been solved, then T and M are available in your MATLAB session, and are populated with their optimal values.

Programs in the other packages are similar, mainly reflecting differences in the syntax of the language they are operating under.