3
$\begingroup$

I am trying to solve an NLP using the Knitro solver, but I am beginning to think that I will not be able to solve the model because it is too complex. I have heard that "rolling horizons" can be used to help alleviate the challenges of large models, but I am not sure how you would go about using a rolling horizon in Knitro?

I think that my understanding of the rolling horizon method is not the best, but from what I have read it might be as simple as just solving the model for a sub period. Taking all of the results, and then re inputting those as initial values for the next period, and then solving them like that.

Question: How can a rolling horizon approach be implemented if I am using the Knitro solver?

$\endgroup$
6
$\begingroup$

Rolling horizon methods often arise in the world of optimal control, when you want to solve \begin{aligned} (P)\qquad\min_{x,u}&\quad\sum_{t=0}^T c_t(x_t, u_t)\\ \text{s.t.}&\quad x_{t+1} = f_t(x_t, u_t) & \forall t=0, \cdots, T\\ &\quad x_t \in X_t, \; u_t\in U_t &\forall t =0, \cdots, T \end{aligned} with $t$ denoting the time ($T$ being the final time), $x_t$ the state at time $t$, $u_t$ the control, $c_t$ a cost function penalizing $x_t$ and $u_t$, $X_t$ and $U_t$ the admissible sets and $f_t$ a dynamics function.

The rolling horizon method (for a reference, see e.g. Bertsekas, Dimitri P. Dynamic programming and optimal control) is a method to solve approximately problem $(P)$, in an iterative fashion. Starting from an initial position $x_0$, proceed as follow.

  • Fix an horizon $h \in \mathbb{N}$.
  • At time $k$, starting from a position $\tilde x_k$, solve the optimization problem \begin{aligned} (\tilde P_k)\quad\min_{x,u} &\quad \sum_{t=k}^{k+h} c_t(x_t, u_t)\\ \text{s.t.}&\quad x_{t+1} = f_t(x_t, u_t) &\forall t=k, \cdots, k+h \\ & x_t \in X_t, \; u_t\in U_t & \forall t =k, \cdots, k+h \\ & x_k = \tilde x_k \end{aligned}
  • Once problem $(\tilde P_k)$ solved, recover in the solution the next position $\tilde x_{k+1}$ and the control $\tilde u_k$. Reiterate the procedure at time $k+1$, this time starting from position $\tilde x_{k+1}$.

At the end, your approximate solution is given by the states $\tilde x_0, \cdots, \tilde x_k, \cdots, \tilde x_T$ and the controls $\tilde u_0, \cdots, \tilde u_k, \cdots, \tilde u_T$ you gathered during the previous procedure.

To sum up, you have to solve a collection of non-linear problems $(\tilde P_k)$, in an iterative fashion.

  • If the problem $(\tilde P_{k+1})$ is similar as problem $(\tilde P_k)$, you may want to use Knitro so as to warmstart the resolution of $(\tilde P_{k+1})$ with the solution of $(\tilde P_k)$. The ideal would be to instantiate only a single instance of Knitro in memory, and then update this instance inline to reformulate a problem $(\tilde P_k)$ at time $k$. Since the introduction of an incremental API in Knitro 11.0, doing so is not that difficult.
  • Interior points algorithms are not that efficient when warm-started. You may want to tune Knitro to use the SQP algorithm (algorithm=4 in the option).

If you target to solve generic optimal control problems, I recommend you having a look at Casadi, which is a good library to formulate non-linear model predictive control (NMPC) problems and has a wrapper to Knitro.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I think that I follow along with you, but I have a question with regards to the horizon h. If I was interested in T = 10, and we start at k = 0, in this case h could be something like 2? so then we would have 5 sub-problems to solve. Am I understanding that correctly? $\endgroup$ – GrayLiterature Apr 15 at 16:07
  • $\begingroup$ The horizon h is a parameter of the rolling horizon algorithm, with $0 < h < T$. For the classical algorithm, the number of subproblems to solve is equal to T, as you are solving one subproblem per timestep you have. If you only want to split the global problem, then you are right: if h is equal to 2, you will get 5 subproblems. But you no longer deal with the classical rolling horizon algorithm in that case, in my opinion. $\endgroup$ – fpacaud Apr 15 at 19:23

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.