Skip to content

User Guides

Jump to bottom
PharosAbad edited this page Apr 26, 2023 · 22 revisions

LightenQP follows closely the the implementation of the C/C++ solver OOQP

Define a QP model

Object

Q = OOQP(V, A, C, q, b, g)

or

Q = OOQP(V, q; A=A, b=b, C=C, g=g)

defines the standard OOQP model:

$$ \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{Cx}\leq\mathbf{g}\in\mathbb{R}^{L} \end{array} $$

Default Values

For the

OOQP(V, q; kwargs...)

the default values are ( $\mathbf{A}=\mathbf{1}^{\prime}, \mathbf{b}=1, \mathbf{C}=-\mathbf{I}, \mathbf{g}=0$ ):

A = ones(1,N), b = [1],  C = -I, g = zeros(N)

Hence, OOQP(V, q) defines the following default model (no short sale in portfolio selection):

$$ \begin{array} [c]{cl} \min & \frac{1}{2}\mathbf{z}^{\prime}\mathbf{Vz}+\mathbf{z}^{\prime}\mathbf{q}\\ s.t. & \mathbf{z}^{\prime}\mathbf{1}=1\\ & \mathbf{z}\geq 0\in\mathbb{R}^{N} \end{array} $$

Portfolio Selection

For portfolio optimization, OOQP(V, q, u) defines

$$ \begin{array} [c]{cl} \min & \frac{1}{2}\mathbf{z}^{\prime}\mathbf{Vz}+\mathbf{z}^{\prime}\mathbf{q}\\ s.t. & \mathbf{z}^{\prime}\mathbf{1}=1\\ & \boldsymbol{d}\leq\mathbf{z}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

While OOQP(V, A, C, q, b, g, d, u) defines the FP(L=-1) model: (OOQP + 'd≤z≤u')

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

Why call it FP(L=-1)? It is the trade-off coefficient $L=-1$ in EfficientFrontier.jl. Note that the $L$ in LightenQP corresponds to the value $J+2N$ in EfficientFrontier.

Solve a QP model

Let Q be an OOQP object , we can solve it by

x, status = solveOOQP(Q; settings=Settings())

the output x and status:

    x::Solution   : structure containing the primal solution 'x', dual variables 'y' and 'z' corresponding to the equality 
                     and inequality multipliers respectively, and slack variables 's'
    status::Int   : > 0 if successful (=iter_count), 0 if infeasibility detected, < 0 if not converged (=-iter_count)

Using mpcQP, we can solve a QP model without first defining an OOQP object.

Solved by mpcQP

mpcQP wraps OOQP(...) + solveOOQP(...), and solves QP in the following forms:

  • x, status = mpcQP(V, q, A, b, C, g; settings) solves the standard OOQP model
  • x, status = mpcQP(V, q, A, b, C, g, d, u; settings) solves the OOQP + 'd≤x≤u' model ( FP(L=-1) model )
  • x, status = mpcQP(V, q, d, u; settings) solves the OOQP + 'd≤x≤u' - 'Ax=b, Cx≤g' model

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

  • x, status = mpcQP(V, q, C, g, d, u, h; settings) solves the OOQP + 'd≤x≤u' + 'h≤Cx' - 'Ax=b' model

$$ \begin{array} [c]{cl} \min & \frac{1}{2}\mathbf{x}^{\prime}\mathbf{Vx}+\mathbf{x}^{\prime} \mathbf{q}\\ s.t. & \mathbf{h}\leq\mathbf{Cx}\leq\mathbf{g}\in\mathbb{R}^{L}\\ & \boldsymbol{d}\leq\mathbf{x}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

  • x, status = mpcQP(V, q, A, b, C, g, d, u, h; settings) solves the OOQP + 'd≤x≤u' + 'h≤Cx' model

$$ \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{h}\leq\mathbf{Cx}\leq\mathbf{g}\in\mathbb{R}^{L}\\ & \boldsymbol{d}\leq\mathbf{x}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

Portfolio Selection

Given OOQP object O,

fPortfolio(O::OOQP, L=0; settings)
fPortfolio(mu, O::OOQP; settings)

solve the following portfolio optimization model: as an illustration, let O be a FP(L=-1) model

  • fPortfolio(O): for FP(L=0), LVEP (Lowest Variance Efficient Portfolio, also called GMVP, Global Minimum Variance Portfolio), by setting $\mathbf{q}=0$ ( $L=0$ in EfficientFrontier)

$$ \begin{array} [c]{cl} \min & \frac{1}{2}\mathbf{z}^{\prime}\mathbf{Vz}\\ s.t. & \mathbf{Az}=\mathbf{b}\in\mathbb{R}^{M}\\ & \mathbf{Cz}\leq\mathbf{g}\in\mathbb{R}^{J}\\ & \boldsymbol{d}\leq\mathbf{z}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

  • fPortfolio(O, -Inf): for FP(L=-Inf), LMFP (Lowest Mean Frontier Portfolio)

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

where $\mu_L$ is the lowest expected return available, which is automatically computed by mpcLP(O)

  • fPortfolio(O, Inf): for FP(L=Inf), HMFP (Highest Mean Frontier Portfolio), or HVEP (Highest Variance Efficient Portfolio), is the highest expected return efficient portfolio

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

where $\mu_H$ is the highest expected return available, which is automatically computed by mpcLP(O; min=false)

  • fPortfolio(mu0, O): for FP(mu=mu0), the frontier (minimum variance) portfolio at $\mu=\mu_0$. By removing $\mathbf{z}^{\prime}\mathbf{q}$ term in the objective function, and adding $\mathbf{q}^{\prime}\mathbf{z}=\mu_0$ to the equality constraints

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

  • fPortfolio(O, L0): for FP(L=L0), the frontier (minimum variance) portfolio at $L=L_0$. By setting $\mathbf{q}\to -L_0\mathbf{q}$ ( $L=L_0$ in EfficientFrontier )

$$ \begin{array} [c]{cl} \min & \frac{1}{2}\mathbf{z}^{\prime}\mathbf{Vz}-L_0\mathbf{z}^{\prime}\mathbf{q}\\ s.t. & \mathbf{Az}=\mathbf{b}\in\mathbb{R}^{M}\\ & \mathbf{Cz}\leq\mathbf{g}\in\mathbb{R}^{J}\\ & \boldsymbol{d}\leq\mathbf{z}\leq\boldsymbol{u}\in\mathbb{R}^{N} \end{array} $$

Hints: L version fPortfolio(O, L0) is better than mu version fPortfolio(mu0, O). Since they are less constrains, L versions present faster speed, better numerical stability and accuracy.

Linear Programming

Solving a LP through solveOOQP, surely is not efficient since it is a QP solver.

x, status = mpcLP(O::OOQP; settings)

It simply set $\mathbf{V}=0$. Hence, using a genuine LP solver will often do a better job.

x, status = mpcLP(O::OOQP; min=false)

to maximize the objective function $f=\mathbf{q}^{\prime}\mathbf{x}$

LP models

x, status = mpcLP(q, A, b, C, g; settings)

solve the following LP model (keyword argument min=false to maximize)

$$ \begin{array} [c]{cl} \min & \mathbf{q}^{\prime}\mathbf{x}\\ s.t. & \mathbf{Ax}=\mathbf{b}\in\mathbb{R}^{M}\\ & \mathbf{Cx}\leq\mathbf{g}\in\mathbb{R}^{L} \end{array} $$

and

x, status = mpcLP(q, A, b, C, g, d, u; settings)

solve the following LP model (keyword argument min=false to maximize)

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

Settings

The fields of struct Settings are (for Float64)

struct Settings{T<:AbstractFloat}
    maxIter::Int64      #777
    scaleStep::T        #0.99   a crude step scaling factor (using Mehrotra's heuristic maybe better)
    tol::T              #2^-26 ≈ 1.5e-8   general (not use in OOQP solver)
    tolMu::T            #2^-52 ≈ 2.2e-16  violation of the complementary condition
    tolR::T             #2^-49 ≈ 1.8e-15  norm(resid) <= tolR * norm(OOQP)
    minPhi::T           #2^23 = 8388608 ≈ 1e7    phi_min_history, not a foolproof test
end
Clone this wiki locally