Home

Welcome to the StatusSwitchingQP.jl wiki!

Native Model

StatusSwitchingQP.jl solves the following convex quadratic programming problems (called SSQP):

$$ \begin{array} [c]{cl} \min & \frac{1}{2}\mathbf{x}^{\prime}\mathbf{Vx}+\mathbf{x}^{\prime} \mathbf{q}\\ s.t. & \mathbf{Ax}=\mathbf{b}\in\mathbb{R}^{M}\\ & \mathbf{Gx}\leq\mathbf{g}\in\mathbb{R}^{J}\\ & \boldsymbol{d}\leq\mathbf{x}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

with positive semi-definite symmetric matrix $\mathbf{V}\in\mathbb{R}^{N\times N}$. And the following linear programming problems

$$ \begin{array} [c]{cl} \min & \mathbf{c}^{\prime}\mathbf{x}\\ s.t. & \mathbf{Ax}=\mathbf{b}\in\mathbb{R}^{M}\\ & \mathbf{Gx}\leq\mathbf{g}\in\mathbb{R}^{J}\\ & \boldsymbol{d}\leq\mathbf{x}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

Given an optimal solution $\mathbf{x}$, let $\mathsf{D}$ and $\mathsf{U}$ be the subset of all subscripts $\mathsf{N}=\{1,2,\cdots,N\}$ where the components lie on one of their downside and upside bounds, respectively. Then $\mathsf{D}=\{i\in\mathsf{N}:x_{i}=d_{i}\}$ and $\mathsf{U}=\{i\in\mathsf{N}:x_{i}=u_{i}\}$. Let $\mathsf{B}=\mathsf{D}\cup\mathsf{U}$ be the components on the boundary, and $\mathsf{I}=\mathsf{N}\setminus\mathsf{B} =\{i\in\mathsf{N}:d_{i} < x_{i} < u_{i}\}$ be all indices whose component is in the interior of the interval. For convenience, we indicate the component in $\mathsf{D}$, $\mathsf{U}$, and $\mathsf{I}$ by DN, UP and IN, respectively.

Using $N+1$ to $N+J$ to number the inequality constraints. When the inequality constraint is not active, it is represented by the state OE; when it is active, it is represented by the state EO.

Remark: make sure that J > 0 || any(isfinite.(d)) || any(isfinite.(u)). Otherwise, there are no any inequalities or bounds, there are only equality constraints. For QP, there is a known closed-form solution, and for LP, the solution is unbounded.

Examples

A Quick Example

    using StatusSwitchingQP

    c = [-3.0, -2]
    d = [0.0, 0]
    u = [Inf, Inf]
    G = [-1.0 3; 1 -5]
    g = [12.0; 5]
    A = zeros(0, 2)
    b = zeros(0)

    Q = LP(c, A, b; d=d, u=u, G=G, g=g) #define the LP model

    x, S, status = solveLP(Q) #solved by Status Switching method
    display((x, S, status))

    z = SimplexLP(Q) #solved by Simplex method
    display(z)

outputs

([12.0, 8.0], Status[IN, IN, EO, OE], 3)
([5.0, 0.0], Status[IN, DN, OE, EO], 3)

where

    x               : solution,  N x 1 vector
    S               : Vector{Status}, (N+J)x1
    status          : 1 unique; 0 infeasible; 2 infinitely many sol; 3 unbounded; -1 numerical errors; -maxIter, not done

QP Example

    using StatusSwitchingQP

    V = [1/100 1/80 1/100
        1/80 1/16 1/40
        1/100 1/40 1/25]
    E = [109 / 100; 23 / 20; 119 / 100]

    up = [0.7; +Inf; 0.7]     #Inf means no bounded
    P = QP(V; u=up)  #default q=0, Ax=b => 1'x=1, G=[], g =[], d = 0
    display(P)  # V A G q b g d u N M J
    z, S, iter = solveQP(P)
    display((z, S, iter))

    P2 = QP(P, E, 0.25) #set q = -0.25*E
    display(P2)
    z2, S2, iter2 = solveQP(P2)
    display((z2, S2, iter2))

outputs

QP{Float64}([0.01 0.0125 0.01; 0.0125 0.0625 0.025; 0.01 0.025 0.04], [1.0 1.0 1.0], Matrix{Float64}(undef, 0, 3), [0.0, 0.0, 0.0], [1.0], Float64[], [0.0, 0.0, 0.0], [0.7, Inf, 0.7], 3, 1, 0)
([0.7, 0.05238095238095242, 0.24761904761904768], Status[UP, IN, IN], 2)
QP{Float64}([0.01 0.0125 0.01; 0.0125 0.0625 0.025; 0.01 0.025 0.04], [1.0 1.0 1.0], Matrix{Float64}(undef, 0, 3), [-0.2725, -0.2875, -0.2975], [1.0], Float64[], [0.0, 0.0, 0.0], [0.7, Inf, 0.7], 3, 1, 0)
([0.22105263157895372, 0.07894736842105071, 0.7], Status[IN, IN, UP], 6)

where

      status          : > 0 if successful (=iter_count); = 0 if infeasibility detected; < 0 fail (=-1 if numerical error, =-maxIter if not converged)