I have 3 time series X1, X2, X3. I want to find the coefficient (c1, c2) that will minimize the distance between them as follow: $$MIN\sum\sqrt{(X1-(c1*X2+c2*X3))^2}$$

The constrains are: $$-1< c1,c2 < 1$$

How can I do it in R?

  • 1
    $\begingroup$ Note that $\sqrt{Y^2}$ is just $|Y|$. But perhaps you meant to put the summation $\Sigma$ inside the square root. One would be the Absolute Norm and the other would be the Euclidean Norm $\endgroup$ – Alex C Jul 16 '17 at 14:25
  • 1
    $\begingroup$ Can you clarify? Do you want to minimize $\sqrt{ \sum_i \left( X_{i,1} - c_1 X_{i,2} - c_2 X_{i,3}\right)^2 }$? Or do you want to minimize $\sum_i \left| X_{i,1} - c_1 X_{i,2} - c_2 X_{i,3}\right| $? In either case, it is an easily solvable, convex optimization problem if your constraints are relaxed to $-1 \leq c_1, c_2 \leq 1$. $\endgroup$ – Matthew Gunn Jul 16 '17 at 18:31
  • $\begingroup$ Yes minimize the absolute values is what I need. Can you direct me to a package in R do solve it? $\endgroup$ – Freewind Jul 17 '17 at 9:11

Define $\|.\|_1$ as the $L_1$ norm. I'll use bold letters to denote vectors and I'm using $\mathbf{y} = \mathbf{x}_1$. Your problem is:

\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $c_1, c_2$)} & \| \mathbf{y} - c_1 \mathbf{x}_2 - c_2 \mathbf{x}_3 \|_1 \\ \mbox{subject to} & -1 \leq c_1 \leq 1\\ & -1 \leq c_2 \leq 1 \end{array} \end{equation}

Or let matrix $X = \begin{bmatrix} \mathbf{x}_2 & \mathbf{x}_3 \end{bmatrix}$ . The problem can be written more succinctly as: \begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{c}$)} & \| X \mathbf{c} - \mathbf{y} \|_1 \\ \mbox{subject to} & \mathbf{c} \preceq \mathbf{1} \\ & -\mathbf{c} \preceq \mathbf{1} \end{array} \end{equation}

Minimizing the $L_1$ norm subject to affine constraints is a convex optimization problem. There are a multitude of approaches to solve this problem, and since it's only in two variables, it's quite trivial to solve. Any general purpose optimization library can probably solve this without issues.

Below is a short list of things you can do. It is not an exhaustive list.

Option 1: Use CVX to solve this problem:

I'm just mentioning this because I know it well. There are ways to call CVX from R but it might be inconvenient. If you were in MATLAB or Python you could do something like:

%% initialize code (currently matlab code)
n = 200;
y = randn(n, 1);  
X = randn(n, 2);

variables c(2);
minimize(norm(y - X * c, 1))
subject to:
-1 <= c
c <= 1

Option 2: Rewrite the problem as a linear program.

By introducing a vector $\mathbf{s} \in \mathbb{R}^n$, the $L_1$ norm minimization problem can be written as a linear program:

\begin{equation} \begin{array}{*2{>{\displaystyle}r}} \mbox{minimize (over $\mathbf{c}, \mathbf{s}$)} & \mathbf{1}'\mathbf{s} \\ \mbox{subject to} & \mathbf{c} \preceq \mathbf{1} \\ & -\mathbf{c} \preceq \mathbf{1} \\ & X\mathbf{c} - \mathbf{y} \preceq \mathbf{s} \\ & -X\mathbf{c} + \mathbf{y} \preceq \mathbf{s} \end{array} \end{equation}

There are numerous solvers in R for linear programs.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.