Minimizing a univariate function that receives a vector?

I'm trying to minimise a function of the form

$$f(s)=\frac{1}{T}\sum^T_{t=1}(x_t-s_t)^2+\sum^T_{t=2}(s_t-s_{t-1})^2$$, where the vector $$x$$ is fixed, and $$T$$ is of the order of $$10^2$$.

I've tried Minimize[f[s], {s}], but Mathematica assumes s is just a number and not a vector.

How do I minimize this?

• Might consider using Indexed[] to formulate your objective function. – J. M.'s discontentment Oct 20 '18 at 12:58

This is more of a mathematics question rather than a Mathematica question, but I will answer with a bit of a Mathematica flavor.

Your function to be minimized can be written as:

$$v = \frac{1}{t} (x-s) \cdot (x-s) + s \cdot M \cdot s$$

where:

$$A = \left( \begin{array}{cccc} 1 & -1 \\ & 1 & -1 \\ & & \ddots & \ddots \\ & & & 1 & -1 \end{array} \right)$$

and

$$M = A^T \cdot A$$

The vector derivative with respect to $$s$$ is:

$$- \frac{2}{t} (x-s) + 2 M \cdot s$$

Setting this to $$0$$ yields:

$$(I + t M) \cdot s == x$$

where $$I$$ is the identity matrix. Hence, the minimum occurs at:

$$s = (I + t M)^{-1} \cdot x$$

Here is a function that computes the minimum for $$x$$:

A[dim_] := SparseArray[{Band[{1,1}]->1, Band[{1,2}]->-1}, {dim-1, dim}]
M[dim_] := Transpose[A[dim]] . A[dim]

mins[x_] := With[{dim = Length[x]},
LinearSolve[IdentityMatrix[dim, SparseArray] + dim M[dim], x]
]


Example:

SeedRandom[1]
x = RandomReal[1, 5]
s = mins[x]

1/5 (x - s) . (x - s) + s . M[5] . s


{0.817389, 0.11142, 0.789526, 0.187803, 0.241361}

{0.506737, 0.444606, 0.449113, 0.385537, 0.361507}

0.0838865

Let's check this using ArgMin:

s = Array[t, 5];
ArgMin[1/5 (x - s) . (x - s) + s . M[5] . s, s]


{0.506737, 0.444606, 0.449113, 0.385537, 0.361507}

Larger example:

SeedRandom[2]
x = RandomReal[1, 100];
s = mins[x]; //AbsoluteTiming

1/100 (x - s) . (x - s) + s . M[100] . s


{0.000458, Null}

0.0693302

• As an addendum to Carl's fabulous answer: the matrix $\mathbf M$ is a specially-structured tridiagonal matrix with known eigenstructure, which should allow for closed-form solutions for the components of the solution vector. – J. M.'s discontentment Oct 20 '18 at 16:48
• Carl, thanks for your answer. I do think my question was more on the Mathematica than mathematics side, while your answer was more on the mathematics side. – An old man in the sea. Oct 20 '18 at 17:25

For future reference ( I used J.M. helpful comment).

HPo[lambda_, x_] :=
1/T *Sum[(data[[i]] - Indexed[x, i])^2, {i, 1, T}] +
lambda/T*
Sum[((Indexed[x, i + 1] - Indexed[x, i]) - (Indexed[x, i] -
Indexed[x, i - 1]))^2, {i, 2, T - 1}];
hpdata = ArgMin[HPo[16, x], Table[Indexed[x, i], {i, 1, T}]];

• I know this is very inefficient, but it works for my purpose. – An old man in the sea. Oct 21 '18 at 23:37
• You don't need the Table[] in ArgMin[]; ArgMin[HPo[16, x], x] should already work. – J. M.'s discontentment Oct 22 '18 at 5:05
• @J.M.iscomputer-less I tried it, and It doesn't... – An old man in the sea. Oct 22 '18 at 8:03