# What is the class of this optimization problem?

I have the following optimization problem: Find $\mathbf{w}$ such that the following error measure is minimised:

• $E_u = \dfrac{1}{N_u}\sum_{i=0}^{N_u-1}\lVert \mathbf{w}^Tx(t_{i+1})-\mathbf{F}(\{\mathbf{w}^Tx(t_j)_{j=0,i}\})\rVert$,
• $t_i \text{ being the i-th timestamp and } \lVert \cdot \rVert \text{ the } L_2 \text{ norm}$
• $\mathbf{F}$ is something of the form $\sum_{j=0}^{i}\alpha_j\mathbf{w}^Tx(t_j)$ with $\sum_{j=0}^i \alpha_j = 1$.

It's important to note the $\alpha$'s are fixed (because they are from a subsystem).

With the constraints that: $\mathbf{w}>\mathbf{0}$ and $\mathbf{w}<\mathbf{L}$. Both $\mathbf{0}$ and $\mathbf{L}$ are vectors in $\mathbb{R}^6$, $\mathbf{L}$ being a vector of positive arbitrary limits I set.

Unfortunately, this doesn't look like the standard least-squares problem, due to that pesky $\mathbf{w}$ term that pops in both places (this is fixed in a certain epoch). Essentially, is like least squares but the target $\mathbf{y}$ is the value of the series at the next timestamp.

Is this another class of problems? Unfortunately, I don't have enough background on this area, but I've read something about Recursive Least Squares and Kalman filters - is this something that could be solved with this?

• Do you have any constraints to your $\mathbf{w}$? – André Sep 5 '18 at 11:35
• Yes!...Thank you for underlying this important point! I've edited the post accordingly. – marianstefi20 Sep 5 '18 at 15:11

After some research on this problem I've realised the model I've developed was incorrect. This is because I introduced the weight vectors in a wrong manner.

Essentially, in my first model(the one this question was based on), the weight vectors were applied on the target vectors and on the input vectors that went into the model. Suppose this is right...because the model converges to the target => on the long term this will behave like a linear transformation: $$F(w\mathbf{x})=wF(\mathbf{x})$$ Introducing this into $$E_u$$ we get that $$w$$ doesn't even matter. Diving more deeper I realized this was a property of space. I was computing an $$L_2$$ norm...by defining an error as the distance of the model vector from the target. No matter how you strech you transform all the points (target and model) in the same manner <=> the relative positions between the points don't change (the errors might be bigger or smaller, but the order relationship between the errors will be preserved).

The solution was to update my model to use instead the weighed euclidean distance. This means: $$E_u = \dfrac{1}{N_u}\sum_{i=0}^{N_u-1}\left\lVert x(t_{i+1}) - F_D(\{x(t_j)_{j=0,i}\})\right\rVert_D$$

I've written $$F_D$$, because at some point, my model does a query using a Ball Tree, which depends on D. I don't know theoretically why this works, but I can say that experimentally, it works (in the sense that the model outputs things which I expect and are reasonable).

As far as I understand the notation, it looks as though it is normal least squares - you are predicting the state, based on the output of $F$ being applied to previous states, constraining the magnitude of the weights. Perhaps you should distinguish your $w^T$ variables; for example using $w^T$ for the sampled weights and ${w^{T}}^{*}$ for your estimates, i.e. the one within the approximation function, $F$.

The fact that you have $\alpha_j$ in your example approximator should linearly scale the weights arbitrarily to counter any (linear) constraints you apply to $w$. Here I am assuming that $\alpha_j$ is a scalar and learnable, so can acts dynamically with $w$.

Did you make a mistake in your subscripts though, going one too far? Should the argument of $F$ not be: $\mathbf{w}^T x(t_j)_{j=0, i}$ (without: $_{+1}$). Otherwise it would seem you actually use the current state to predict the current state, which any good model would exploit for 100% accuracy. I agree the output of $F$ would be e.g. $y(t_j)_{j=i+1}$

• Thank you very much for the detailed response. I've updated the question accordingly and also added a constraint about the alpha's. – marianstefi20 Sep 5 '18 at 16:59