I am interested in solving the constrained LQR problem with discrete finite time when the target $x$ value is given, but the final $u$ could be anything s.t. constraints.
$$\text{minimize }J = \sum_{k=0}^N x'(k)Qx(k) + u'(k)Ru(k) \\ x(k+1) = x(k) + u(k) \\ Q > 0, \text{symmetric} \\ R > 0, \text{diagonal} \\ x_{min} \le x \le x_{max} \\ u_{min} \le u \le u_{max} $$ where $x(0)$ is given and the terminal state $x(N)$ is also given. Usually $x(N) = 0$, but can be another value.
Here
$x$ is an $n$-dimensional vector. Say, $n=1000$, and occasionally can be up to $n=3000...5000$, so the solution complexity should not be $O(n^3)$.
in "real life", $x$ in a vector of integers. Rounding real values of a solution to integers is OK.
the terminal state does not have to be a "steady state" as in a traditional MPC context: once $x(N)$ is reached, the goal is fulfilled.
the number of steps is also fixed, typically $N=100$.
(I've read some articles and tutorials on MPC and played with it in MATLAB a bit, so please don't blame me too much if I am wrong.)
Questions:
1) Could MPC help solve this problem? (To my understanding, if the number of steps to reach the target state is fixed, MPC is of no use...)
2) What if the process is allowed to run for an arbitrary number of steps and terminates as soon as $x(k)$ reaches $x(N)$ or some vicinity of $x(N)$?
3) Could you advise some other methods to solve this problem? Maybe dynamic programming? isn't its complexity $O(n^3)$?
I disagree A.G. statement that MPC is not useful here. The constraints cause the controller to be piecewise linear (and thus hard to find a closed form, specially for the problem sizes you are looking for).
1) Yes, you can use MPC in this case. In addition, using a terminal constraint ($x(N) = x_{terminal}$) gives you stability (but not robustness) guarantees as long as the problem has a solution.
2) I wan't able to comprehend what you want in this case
3) If you system is exactly what you are showing (box constraints and very simple dynamics) I believe we can devise a very fast solution for high order systems. However, I still believe it would be $O(n^3)$.