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.


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


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

  • $\begingroup$ 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. $\endgroup$
    – A.Γ.
    Nov 1 '15 at 13:48
  • $\begingroup$ 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. $\endgroup$ Nov 1 '15 at 14:33
  • 1
    $\begingroup$ 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. $\endgroup$ Nov 1 '15 at 19:28
  • $\begingroup$ Thanks Johan, I am editing $\dot{x}$ for $u$. $\endgroup$ Nov 1 '15 at 19:56
  • $\begingroup$ 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}]$. $\endgroup$ Nov 1 '15 at 20:00

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.