Method and apparatus for preconditioned model predictive control

Patent metadata

Field	Value
Publication number	US-10209685-B2
Application number	US-201514926650-A
Country	US
Kind code	B2
Filing date	Oct 29, 2015
Priority date	Oct 29, 2015
Publication date	Feb 19, 2019
Grant date	Feb 19, 2019

Abstract

A method for a model predictive control (MPC) of a system determines entries of an approximate coefficient matrix only at locations identified in a map of locations as significant. The map of locations identifies each location of an entry in the approximate coefficient matrix as either significant or insignificant. The entries are determined using one or combination of an approximate coefficient function and an exact coefficient function. Next, the method determines a preconditioner using the approximate coefficient matrix and determines a solution vector by solving a matrix equation of the MPC with a coefficient matrix defined by an exact coefficient function at a current time step of a control using an iterative method with the preconditioner. The method generates a control signal for controlling the system using the solution vector.

First claim

We claim:

1. A method for model predictive control (MPC) of a system, comprising:
determining on-line entries of an approximate coefficient matrix only at locations identified in a map of locations as significant, wherein the entries are determined to approximate an exact coefficient matrix of the MPC, and wherein the map of locations identifies each location for an entry in the approximate coefficient matrix as either significant or insignificant;
determining at least a part of a preconditioner matrix on-line using the approximate coefficient matrix, wherein the preconditioner matrix is sparse and different from a block diagonal matrix and different from a block tri-diagonal matrix;
determining a solution vector on-line by solving a matrix equation of the MPC with the exact coefficient matrix using an iterative method with the preconditioner matrix;
generating a control signal on-line to control the system in real time using the solution vector; and
transmitting the generated control signal to the system, wherein steps of the method are performed by at least one processor.

2. The method of claim 1 , further comprising:
determining the map of significant locations off-line and storing the map of locations in a memory operatively connected to the processor, wherein a location mapped as not significant is determined by one or a combination of an analytical derivation and numerical simulation by checking whether annulling an entry of the approximate coefficient matrix at the location in the preconditioner matrix maintains a convergence speed of the iterative method with the preconditioner matrix larger than a predefined first threshold.

3. The method of claim 2 , further comprising:
determining the map of significant locations off-line and storing the map of locations in a memory operatively connected to the processor, wherein the significant locations are determined as locations of the largest by absolute value entries of the approximate coefficient matrix, and wherein the number of the non-zero entries identified as significant by the map of locations is determined by one or a combination of a predefined fraction of the total number of entries of the approximate coefficient matrix and a predefined second threshold bounding below the absolute values of the significant entries of the approximate coefficient matrix.

4. The method of claim 1 , wherein the preconditioner matrix is determined as a block matrix, wherein each block is determined as a sum of a block-diagonal matrix and a low-rank matrix having the rank lower than the rank of the preconditioner matrix, wherein the locations and sizes of the blocks are determined off-line.

5. The method of claim 1 , further comprising:
determining an approximate coefficient function and an exact coefficient function, wherein the approximate coefficient function applied to a vector approximates a result of an application of the exact coefficient function to the vector, wherein the approximate coefficient function applied to a vector returns a product of the approximate coefficient matrix and the vector, and wherein the exact coefficient function applied to the vector returns a product of the exact coefficient matrix and the vector; and
updating the entries of the approximate coefficient matrix on-line using one or a combination of the approximate coefficient function and the exact coefficient function.

6. The method of claim 1 , further comprising:
determining the approximate coefficient matrix using an arithmetic having a precision lower than a precision of an arithmetic for determining the exact coefficient matrix.

7. The method of claim 1 , further comprising:
determining the approximate coefficient matrix using an approximate elimination of at least one block of entries in the exact coefficient matrix.

8. The method of claim 1 , further comprising:
determining the exact coefficient matrix using a model of the system;
approximating the model of the system; and
determining the approximate coefficient matrix using the approximate model of the system.

9. The method of claim 1 , wherein the approximate coefficient matrix is the exact coefficient matrix determined for a different time step of the control.

10. The method of claim 1 , wherein the solving is performed by a controller processor during a main control routine, further comprising:
determining one or a combination of the approximate coefficient matrix, the preconditioner matrix, and the factorization of the preconditioner matrix in parallel with the main control routine using an at least one additional processor.

11. The method of claim 1 , wherein the MPC is a continuation MPC, approximately solving necessary optimality conditions for the MPC by a forward-difference Newton-Krylov preconditioned iterative method.

12. The method of claim 1 , wherein determining the preconditioner matrix comprises: permuting rows and columns of the approximate coefficient matrix to produce the preconditioner matrix, wherein the permutation pattern is determined off-line to order the rows and columns for minimizing memory usage and costs of the factorization of the preconditioner matrix.

13. The method of claim 1 , further comprising:
factorizing the preconditioner matrix on-line, using a factorization method, wherein the factorization comprises one or a combination of:
lower-upper, lower-diagonal-lower transposed, Schur, Cholesky, orthogonal-upper, and anti-triangular factorizations, polar, eigenvalue and singular value decompositions, and block versions thereof.

14. The method of claim 1 , wherein the iterative method comprises one or a combination of:
a preconditioned stationary method, a preconditioned Krylov subspace method, a preconditioned minimal residual method, a preconditioned generalized minimal residual method, a preconditioned gradient method, a preconditioned Chebyshev method, and a preconditioned Nesterov method.

15. The method of claim 1 , wherein determining the preconditioner comprises:
determining the preconditioner matrix as a symmetric positive definite matrix, and wherein the iterative method is a preconditioned minimal residual method.

16. The method of claim 1 , further comprising:
determining a rate of convergence of the iterative method; and
updating the preconditioner, if the rate of convergence is below a threshold.

17. The method of claim 1 , further comprising:
determining the iterative method using a preconditioner function, wherein the preconditioner function applied to a vector approximates a product of an inverse of the preconditioner matrix and the vector.

18. The method of claim 1 , further comprising:
updating at least partially the preconditioner matrix during an execution of the iterative method of the current time step, wherein the iterative method is restarted synchronously with the preconditioner matrix update or is a flexible iterative method, such that the preconditioner matrix is a variable preconditioner matrix.

19. The method of claim 1 , wherein the determining the solution vector comprises:
updating the matrix equation in the iterative method at the current time step of the control without restarting iterations of the iterative method from a previous time step of the control wherein the iterative method is a flexible iterative method, such that the matrix equation is a variable matrix equation.

20. A model predictive controller for controlling a system according to a control signal generated at each time step, comprising:
a memory to store a model of the sys

Assignees

• Mitsubishi Electric Res Laboratories Inc

Inventors

• Kniazev Andrei
• Malyshev Aleksandr

Classifications

• G06F17/16

  Matrix or vector computation {, e.g. matrix-matrix or matrix-vector multiplication, matrix factorization (matrix transposition G06F7/78)} · CPC title

• G05B13/048 Primary

  using a predictor · CPC title

• G06F17/12

  Simultaneous equations {, e.g. systems of linear equations} · CPC title