Linear Quadratic Problem

In our previous blog post, we discussed using Riccati recursion to solve linear-quadratic (LQ) problems. As an alternative, the KKT system associated with an LQ problem can be solved directly using a sparse linear solver, such as QDLDL. We first write the KKT system $(N = 3)$ as

\[\begin{aligned} \mathcal{A} z &= b \\ \left[ \begin{array}{ccccccccc} R_0 & B_0^\top \\ B_0 & & -I\\ \hline & -I & Q_1 & S_1^\top & A_1^\top \\ & & S_1 & R_1 & B_1^\top \\ & & A_1 & B_1 & & -I \\ \hline & & & & -I & Q_2 & S_2^\top & A_2^\top \\ & & & & & S_2 & R_2 & B_2^\top \\ & & & & & A_2 & B_2 & & -I \\ \hline & & & & & & & -I & P_3 \end{array} \right] \left[ \begin{array}{c} u_0 \\ \lambda_1 \\ \hline x_1 \\ u_1 \\ \lambda_2 \\ \hline x_2 \\ u_2 \\ \lambda_3 \\ \hline x_3 \end{array} \right] &= \left[ \begin{array}{c} -r_0 - S_0 x_0 \\ -A x_0 - c_0 \\ \hline -q_1 \\ -r_1 \\ -c_1 \\ \hline -q_2 \\ -r_2 \\ -c_2 \\ \hline -p_3 \end{array} \right] \end{aligned}.\]

The KKT matrix $\mathcal{A}$ exhibits sparsity, with a significant number of zero elements. For improved computational performance, we use a sparse linear solver to solve the KKT system above. Let us now take a closer look at how sparse matrices are represented.

Sparse matrix

As a tutorial example, we consider the following matrix

\[\begin{bmatrix} 0 & 3 & 0 & 0 & 0 \\ 22 & 0 & 0 & 0 & 17 \\ 7 & 5 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 14 & 0 & 8 \end{bmatrix}.\]

We store the nonzero elements in an array using column-major order.

const double x[] = { 22.0, 7.0, 3.0, 5.0, 14.0, 1.0, 17.0, 8.0 };

Two additional index arrays are used to indicate the positions of the nonzero elements in the original matrix.

row indices: stores the row indices of the nonzero elements.
column pointers: indicates where each column starts in the array x. i[k+1] - i[k] implies the number of the nonzero elements in a column.

const int p[] = { 1, 2, 0, 2, 4, 2, 1, 4 };
const int i[] = { 0, 2, 4, 5, 6, 8};

We pack these variables using a struct.

struct CscMatrix {
    int     m;     // number of rows
    int     n;     // number of columns 
    int    *p;     // column pointers (size n+1)
    int    *i;     // row indices 
    double *x;     // values
    int     nzmax; // maximum number of nonzero entries
};

QDLDL

We now have the data $(Q, R, S, q, r, A, B, c, N)$ required for an LQ problem. Using these dense matrices and vectors, we construct the sparse KKT matrix $\mathcal{A}$ and the corresponding right-hand side vector $b$. Then, we call the functions in QDLDL to solve the sparse linear system. For more information, please refer to the repository.