MPC Problem - Slow Convergence

Embedded Optimization
1

Hello,

We’re using OSQP to solve 4 different MPC problems on vehicle. Before trying OSQP, these problems are solved by CVXGEN.

OSQP converges quickly in two smallest problem and the largest problem (in terms of number of variables and constraints) but couldn’t converge in a reasonable number of iterations (< 2000). CVXGEN however, find the optimum in less than 25 iterations on average.

I wonder if there is any types of QP problem where interior point method is superior to the first order method? We’ve noticed two differences between that problem and the other three:

  1. it has many more inactive constraints;
  2. the optimum is not unique.

But we don’t know if it is supported by any theory or there could be anything else. Anything that helps us understand the situation is highly appreciated. Thanks! :smiley:

2

It does not really make sense to compare the number of iterations between CVXGEN and OSQP, since one uses an interior point method and the other ADMM. Roughly speaking, an interior point method will use a relatively low number of iterations that are computationally expensive, while ADMM uses a relatively large number of computationally cheap iterations.

That said, it is true that OSQP sometimes performs less well on problems that are multi-stage optimal control problems, particularly when the cost is not strictly convex. There are some things that you could do to improve the speed:

  1. Make sure that the automatic update of the rho parameter enabled.
  2. Experiment a bit with the initial rho value to see if that improves the convergence speed.
  3. Use the same solver between MPC solves and just update the linear constraint and cost terms to reflect your new initial state (i.e. warm start the solver).

This latter point is very important if you want very fast performance in MPC applications, You would normally expect to see a big advantage in average solve time relative to an IP solver since the IP solver is probably doing a cold start at every solve.

3

Thanks Paul. We know that ADMM takes more iterations than interior point method. But we’d like see how well OSQP could do in that specific problem. I’ll check the parameter rho as you suggested. Thanks for your timely response :smiley: