Linear optimization solves the problem $$\min_{\bf x}\{\|{\bf Ax - b}\|_2^2\}$$
Edit: Some clarification
Doing the derivation of the optimum, first expand the norm: $$\|{\bf Ax - b}\|_2^2 = ({\bf Ax-b})^T({\bf Ax-b}) = {\bf x}^T{\bf A}^T{\bf Ax} - {\bf x}^T{\bf A}^T{\bf b} - {\bf b}^T{\bf Ax} + {\bf b}^T{\bf b}$$ Then when differentiating this expression with respect to $\bf x$ and setting equal to the zero vector, we do get a linear equation system $${\bf A}^T{\bf Ax}= {\bf A}^T{\bf b}$$ So we see that for any $\bf A$, the left hand side is a non negative matrix. If we add $\lambda {\bf I}$, with $\lambda > 0$, corresponding to $\lambda\|{\bf x}\|_2^2$ in the optimization, we would be sure to have a positive definite system.
In algebra many non-linear things can be expressed as ${\bf M}^k$ thanks to representation theory, that group elements can be represented as matrices. Famous examples include rotating on a circle or a sphere (rotation matrices) and cyclic groups. In some sense turning a non-linear concept into a linear one.
So say I instead want to solve the problem. $$\min_{k}\{\|{{\bf A}^k{\bf x - b}}\|_2^2\}$$ or even $$\min_{k}\{\|{{\bf A}^k - {\bf M}}\|_2^2\}$$
What are your favourite methods to attack these kinds of problems?
Own "work"
I suppose one could view it as minimizing a multivariable polynomial equation system, as the ${\bf A}_{ij}$ gets multiplied and summed up in $k$ scalar products for each element. Minimizing such a function should be a multivariate polynomial equation system ( setting each partial differential, which is also a multivariate polynomial = 0 ). However I have no Idea how fruitful it would be to try and search for such a solution or if there are better approaches.