Quadratic programming on a small embedded device — can I do the hard work on the PC first

control theorylinear-controlnumerical optimizationoptimal controlquadratic programming

I have the following constrained quadratic program in $x$

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^TQx + x^Tc\\ \text{subject to} & b_{\min} \leq Ax \leq b_{\max}\\ & x_{\min} \leq x \leq x_{\max}\end{array}$$

I know that Model Predictive Control (MPC) is expensive to have onto an embedded system. So I wonder if I can do the hard work in MATLAB/Octave and create the special Lagrangian matrices — if I recall their names correctly.

Then I implement it on the embedded system, i.e., I compute the inverse first on the PC, then I move the inverse matrix into the embedded system. Instead of doing the heavy mathematical work in the embedded system first.

I have created a MATLAB/Octave script here for computing the input signals $u$ for a state space model. Just insert the discrete matrices $A, B, C$ and the horizon $N$ and the reference $r$ and also the maximum input and output, and last the state vector $x$. Then it will return the quadratic programmed input signals.

As I see it, $GAMMA$ and $PHI$ can be computed in the PC, and also $Q$.
But the $c$ matrix need to be updated as long the state vector $x$ is updated, which it will be for every iteration.

But how abut the constraints? What can I do there so the embedded systems only need to use multiply operation, addition operation and subtraction operation?

function [U] = mpc (A, B, C, x, N, r, minU, maxU, minY, maxY)

  ## Find matrix
  PHI = phiMat(A, C, N);
  GAMMA = gammaMat(A, B, C, N);
  W = eye(size(GAMMA,1)); # Weight, you can tune in this if you want.
  Q = GAMMA'*W*GAMMA;
  c = GAMMA'*W*PHI*x - GAMMA'*W*repmat(r, N, 1);

  ## Constraints input 
  LB = repmat(minU, N, 1);
  UB = repmat(maxU, N, 1);

  ## Constraints output
  Ax = GAMMA;
  b = repmat(maxY, N, 1) - PHI*x;

  ## Solve
  U = quadprog(Q, c, Ax, b, [], [], LB, UB);
  if(U(1) <= minY)
    U(1) = minY;
  end

end

function PHI = phiMat(A, C, N)

  ## Create the special Observabillity matrix
  PHI = [];
  for i = 1:N
    PHI = vertcat(PHI, C*A^i);
  end

end

function GAMMA = gammaMat(A, B, C, N)

  ## Create the lower triangular toeplitz matrix
  GAMMA = [];
  for i = 1:N
    GAMMA = horzcat(GAMMA, vertcat(zeros((i-1)*size(C*A*B, 1), size(C*A*B, 2)),cabMat(A, B, C, N-i+1)));
  end

end

function CAB = cabMat(A, B, C, N)

  ## Create the column for the GAMMA matrix
  CAB = [];
  for i = 0:N-1
    CAB = vertcat(CAB, C*A^i*B);
  end

end

Assume that we have our objective function but we change our subject function
$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^TQx + x^Tc\\ \text{subject to} & Ax = b\end{array}$$

Then our solution is:

$$x^0 = -Q^{-1}c$$
$$\lambda = -(AQ^{-1}A^T)^{-1}(b+AQ^{-1}c)$$
$$x = x^0 – Q^{-1}A^T\lambda$$

How can we use this above to solve for this kind of problem:

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^TQx + x^Tc\\ \text{subject to} & b_{\min} \leq Ax \leq b_{\max}\\ & x_{\min} \leq x \leq x_{\max}\end{array}$$

Or can I just change $b$ which is the maximum output value, to the reference value $r$?

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}x^TQx + x^Tc\\ \text{subject to} & Ax = r\end{array}$$

Example if you look how I made the MATLAB code above:

$$\begin{array}{ll} \text{minimize} & \frac{1}{2}u^TQu + u^Tc\\ \text{subject to} & \Gamma u = r – \Phi x_0\end{array}$$

Best Answer

Having a solver for equality constrained QP only will not help you in solving the general inequality constrained problem (unless you develop a QP solver, which can have an equality-constrained QP solver as a required sub-routine). In other words, your problem cannot be reformulated to a problem with only equalities.

Related Question