SDQP

SDQP: Small-Dimensional Strictly Convex Quadratic Programming in Linear Time

About

1. This solver is super efficient for small-dimensional strictly convex QP with any constraint number, mostly encountered in computational geometry. It enjoys linear complexity about the constraint number.

2. The speed is faster than most numerical solvers in small-dimensional LP (<10) with a large constraints number (>100).

3. This solver computes exact solutions or report infeasibility.

4. This solver generalizes Seidel's algorithm from LP to strictly convex QP.

5. This solver is very elegant thus only a header file with less than 400 lines is all you need.

If our lib helps your research, please cite us

@misc{WANG2022SDQP,
    title={{SDQP: Small-Dimensional Strictly Convex Quadratic Programming in Linear Time}}, 
    author={Wang, Zhepei and Gao, Fei}, 
    year={2022},
    url={https://github.com/ZJU-FAST-Lab/SDQP}
}

Interface

To solve a linear programming:

    min 0.5 x' Q x + c' x,
    s.t. A x <= b,

where x and c are d-dimensional vectors, Q an dxd positive definite matrix, b an m-dimensional vector, A an mxd matrix. It is assumed that d is small (<10) while m can be arbitrary value (1<= m <= 1e+8).

Only one function is all you need:

double sdqp(const Eigen::Matrix<double, d, d> &Q,
            const Eigen::Matrix<double, d, 1> &c,
            const Eigen::Matrix<double, -1, d> &A,
            const Eigen::Matrix<double, -1, 1> &b,
            Eigen::Matrix<double, d, 1> &x)

Input:

    Q: positive definite matrix
    c: linear coefficient vector
    A: constraint matrix
    b: constraint bound vector

Output:

    x: optimal solution if solved
    return: finite value if solved
            infinity if infeasible

Reference

1. Seidel, R., 1991. Small-dimensional linear programming and convex hulls made easy. Discrete & Computational Geometry, 6(3), pp.423-434.

Maintaince and Ack

Thank Zijie Chen for fixing the conversion from QP to minimum norm.

If any bug, please contact Zhepei Wang ([email protected]).