Quadratic program solver for MPC using variable ordering

• US 10,423,131 B2
• Filed: 07/20/2016
• Issued: 09/24/2019
• Est. Priority Date: 07/31/2015
• Status: Active Grant

• Current Assignee: Garrett Transportation I Inc. (Garrett Motion, Inc.)
• Original Assignee: Garrett Transportation I Inc. (Garrett Motion, Inc.)
• Inventors: Santin, Ondrej
• Primary Examiner(s): Lee, Hsien Ming
• Application Number:
  US15/215,253
• Publication Number:
  US 20170031332A1
• Time in Patent Office: 1,161 Days
• Field of Search: 706 12, 706 14, 706 46, 706 50, 703 2
• CPC Class Codes: G05B 13/048 using a predictor
• CPC Class Codes: G06F 17/16 Matrix or vector computation , e.g. matrix-matrix or matrix-vector multiplication, matrix factorization matrix transposition G06F7/78
• CPC Class Codes: G06F 2207/483 Indexing scheme relating to group G06F7/483
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence

Abstract

A system and approach for storing factors in a quadratic programming solver of an embedded model predictive control platform. The solver may be connected to an optimization model which may be connected to a factorization module. The factorization module may incorporate a memory containing saved factors that may be connected to a factor search mechanism to find a nearest stored factor in the memory. A factor update unit may be connected to the factor search mechanism to obtain the nearest stored factor to perform a factor update. The factorization module may provide variable ordering to reduce a number of factors that need to be stored to permit the factors to be updated at zero floating point operations per unit of time.

Claims

1. A system for quadratic programming comprising:

an embedded platform comprising a model predictive control (MPC) controller connected to a physical subsystem; and

wherein the MPC controller comprises;

a state observer; and

a semi-explicit quadratic programming (QP) solver connected to the state observer; and

wherein the semi-explicit QP solver comprises;

an optimization module;

a factorization module connected to the QP optimization module;

wherein the factorization module comprises;

a memory having a saved factors unit;

a factor search mechanism connected to the saved factors unit; and

a factor update mechanism connected to the factor search mechanism; and

wherein the factorization module provides variable ordering to reduce factors which need to be stored to allow them to be updated at a zero floating-point operations per unit time (FLOPS) cost.

2. The system of claim 1, wherein the physical subsystem comprises:

a physical plant;

one or more sensors situated at the physical plant and connected to the MPC controller; and

one or more actuators attached to the physical plant and connected to the MPC controller.

3. The system of claim 2, wherein the physical plant is an internal combustion engine or after-treatment device.

4. The system of claim 1, wherein the optimization module comprises a Karush-Kuhn-Tucker (KKT) subsystem having a KKT matrix.