I am trying to set up an optimisation problem and solving it numerically. I am still formalizing it and unsure what is the best way to solve it. It seems like a common problem, and im sure people have already worked on this type of probem and i would like to see how others solved it or what you sugestions are.
Now I am two fixed vectors $x$ the input and $y$ the output, both in $\mathbb{R}^{n}$. I am only allowed to used a fixed amount of up to $k$ matrix multiplications from a fixed set of $\{A_{i}\}, i<j,A_{i}\in\mathbb{R}^{n\times n}$ to transform x into y as much as possible, solving some sort of least squares problem to find the optimal sequence of $A_{i}$.
$$ \min_{s.t.: \forall i_{l}\in \{1,...,j-1\}} ||y-A_{i_{1}}...A_{i_{k}}x||$$
Also we can assume that the number of different matrices is somwhat small and their respective dimensions $n$ are moderate.
So i guess that would require some kind of combinatorical optimization procedure, since this is basically a discrete problem, what algorithms are suited to solve this efficiently?.Is there a specific name for this type of problems?
By taking your matrices to be identity matrices that have at most one additional 1 in a distinct position in the first row, the set of all products of distinct matrices you can form is the set of all matrices that have the first row equal to a distinct set of 0's and 1's (beginning with a 1), and the rest of the matrix equal to the identity. So if you could solve your problem then you could solve the subset sum problem, which is NP-complete. Thus your problem is NP-hard and probably no fast solution exists.