# Constrained LQR with a fixed terminal state. Can MPC be applied to this problem?

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)$?

• What do you mean by "solving" - analytically or numerically? MPC is a numerical heuristic method mostly for hard to model highly non-linear processes. Here the problem is LQR, the simplest possible. Is it your ultimate problem or it is just a model for something else? For LQR on the finite horizon you can also try the discrete-time Pontryagin maximum principle, or get another type of necessary condition via KKT, for example, but then you will need a large-scale optimization anyway, like interior-point methods.
– A.Γ.
Nov 1 '15 at 13:48
• Numerically would suffice, analytically would be great (= faster). It is the ultimate problem. Is there any good literature/tutorial on discrete-time Pontryagin principle? Is an "another type of necessary condition via Karush–Kuhn–Tucker followed by a large-scale optimization" computationally feasible for this problem? The problem needs to be solved for the user's $x(0)$ and $Q$, $R$ are also different, so the calculations should not be very slow. Nov 1 '15 at 14:33
• What do you mean with $\dot{x}$ when you have a discrete-time model?What do you mean with "MPC is of no use", adding a terminal state constraint $x(N) = x_s$ is the most basic trick in MPC to guarantee stability. Nov 1 '15 at 19:28
• Thanks Johan, I am editing $\dot{x}$ for $u$. Nov 1 '15 at 19:56
• As for the "MPC is of no use" statement. In a continuous time model, doesn't MPC require a terminal state control constraint $u(N) = u_s$? And an analog of that in a discrete time case as well? In this problem, $u(N)$ or its analog can be any in $[u_{min}, u_{max}]$. Nov 1 '15 at 20:00

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.
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)$.