Posdef matrix

Many optimisations need a positive definite covariance or correlation matrix to have a unique solution. An estimated matrix can fail this for three reasons: collinear assets, fewer observations than assets, and floating-point rounding. Such a matrix has zero or negative eigenvalues.

  • A zero eigenvalue means that a combination of the assets has no variance. A linear or quadratic system with the matrix then has no unique solution.
  • A negative eigenvalue comes from rounding in a badly conditioned matrix, usually one with highly collinear assets, or from an estimator that does not guarantee a positive semi-definite result.

The types and functions below replace such a matrix with the nearest positive definite matrix. The result changes the matrix as little as possible, and it has no zero or negative eigenvalue. A constant variable is the one exception. Its variance is zero, so its row and column stay zero, and the result is positive semidefinite.

Posdef takes the algorithm of the repair. NearestCorrelationMatrix.Newton is the default, and it finds the nearest correlation matrix in the Frobenius norm. ClippedNearestCorrelation clips the eigenvalues of the correlation matrix at a floor, and it also repairs a matrix that is positive definite but nearly singular.

PortfolioOptimisers.AbstractPosdefEstimator — Type
abstract type AbstractPosdefEstimator <: AbstractEstimator

Abstract supertype for all positive definite matrix estimator types.

A type that projects a matrix to a positive definite matrix is a subtype of AbstractPosdefEstimator.

Interfaces

To add a positive definite matrix estimator, subtype AbstractPosdefEstimator, keep its parameters in the fields of the struct, and add these methods:

  • posdef!(pdm::AbstractPosdefEstimator, X::MatNum) -> MatNum: Projects X in place to the nearest positive definite matrix.
  • posdef(pdm::AbstractPosdefEstimator, X::MatNum) -> MatNum: Optional. Returns the projection of X in a new matrix. A fallback method copies X and calls posdef!, so add this method only when it avoids the copy.

Arguments

  • pdm: Positive definite matrix estimator.
  • X: Covariance-like or correlation-like matrix assets × assets.

Returns

  • X::MatNum: The projected input matrix X.

Examples

The example below defines a minimal positive definite estimator.

julia> struct MyPosdefEstimator <: PortfolioOptimisers.AbstractPosdefEstimator endjulia> function PortfolioOptimisers.posdef!(pdm::MyPosdefEstimator, X::PortfolioOptimisers.MatNum)           # Implement your in-place PD projection logic here.           println("Projecting to positive definite matrix in-place...")           return X       endjulia> function PortfolioOptimisers.posdef(pdm::MyPosdefEstimator, X::PortfolioOptimisers.MatNum)           X = copy(X)           println("Copy X...")           posdef!(pdm, X)           return X       endjulia> posdef!(MyPosdefEstimator(), [1.0 2.0; 2.0 1.0])Projecting to positive definite matrix in-place...2×2 Matrix{Float64}: 1.0  2.0 2.0  1.0julia> posdef(MyPosdefEstimator(), [1.0 2.0; 2.0 1.0])Copy X...Projecting to positive definite matrix in-place...2×2 Matrix{Float64}: 1.0  2.0 2.0  1.0

Related

source
PortfolioOptimisers.ClippedNearestCorrelation — Type
struct ClippedNearestCorrelation{__T_tau, __T_higham, __T_iter} <: AbstractAlgorithm

Repairs a covariance matrix by a clip of the eigenvalues of its correlation matrix, and keeps its variances. It is an algorithm that Posdef takes, beside the algorithms of NearestCorrelationMatrix.jl.

The algorithm has its own acceptance test. It returns a matrix unchanged when the matrix passes the Cholesky factorisation, its covariance eigenvalues are positive, and its smallest correlation eigenvalue is at least tau / 2. It repairs any other matrix. It clips the correlation eigenvalues at tau, scales the diagonal back to one, and restores the variances. When the result fails the same test, the clip runs once more at 10 * tau.

Newton, the default of Posdef, finds the nearest correlation matrix in the Frobenius norm. The clip is a spectral repair with a floor on the eigenvalues, so it is not the nearest matrix, but its smallest eigenvalue is bounded away from zero.

Mathematical definition

The algorithm standardises the covariance $\mathbf{\Sigma}$ into the correlation matrix $\mathbf{C}$, and clips the eigenvalues of $\mathbf{C}$ at $\tau$:

\[\begin{align} \mathbf{C} &= \mathbf{D}^{-1} \mathbf{\Sigma} \mathbf{D}^{-1} = \mathbf{V} \mathrm{Diag}(\boldsymbol{\lambda}) \mathbf{V}^\intercal\,, \\ \mathbf{Y} &= \mathbf{V} \mathrm{Diag}(\max(\boldsymbol{\lambda}, \tau)) \mathbf{V}^\intercal\,, \\ \hat{\mathbf{C}}_{ij} &= \frac{Y_{ij}}{\sqrt{Y_{ii} Y_{jj}}}\,, \\ \hat{\mathbf{\Sigma}}_{ij} &= \hat{\mathbf{C}}_{ij}\, \sigma_i \sigma_j \;\; (i \neq j)\,, \qquad \hat{\mathbf{\Sigma}}_{ii} = \mathbf{\Sigma}_{ii}\,. \end{align}\]

Section 3 of [22] first states the clip and the scaling of the diagonal. It replaces the negative eigenvalues by zero, or by a small positive number $\Delta$ when the result must be positive definite, and it then scales the diagonal back to one. That work replaces only the negative eigenvalues, and this algorithm lifts every eigenvalue below $\tau$. At $\tau = 0.05$ this algorithm reproduces its Equation 3.3, the repair of the matrix of its Equation 2.5. Equations 8 to 13 of [23] state the clip again with a floor of zero, for the correlation matrices of risk management. The standardisation of a covariance, the restored variances, the acceptance test and the retry are this library's.

The algorithm accepts the repair when $\hat{\mathbf{\Sigma}}$ has a Cholesky factor, $\lambda_{\min}(\hat{\mathbf{\Sigma}}) > 0$ and $\lambda_{\min}(\hat{\mathbf{C}}) \geq \tau / 2$. The half floor absorbs the round-off of the scaling, so the algorithm does not repair a matrix a second time. After the retry at $10 \tau$, the algorithm also accepts the repair when the Cholesky factor exists and $\lambda_{\min}(\hat{\mathbf{\Sigma}}) \geq -n\, \varepsilon \max_i |\lambda_i(\hat{\mathbf{\Sigma}})|$.

With higham = true, Higham's alternating projections with Dykstra's correction replace $\mathbf{C}$ before the clip. Each iteration projects onto the positive semidefinite cone with an eigenvalue floor of $5 \varepsilon$, and then onto the matrices of unit diagonal:

\[\begin{align} \mathbf{R}_k &= \mathbf{Y}_{k-1} - \Delta\mathbf{S}_{k-1}\,, \\ \mathbf{X}_k &= \mathbf{V}_k \mathrm{Diag}(\max(\boldsymbol{\lambda}(\mathbf{R}_k), 5 \varepsilon)) \mathbf{V}_k^\intercal\,, \\ \Delta\mathbf{S}_k &= \mathbf{X}_k - \mathbf{R}_k\,, \\ \mathbf{Y}_k &= \mathbf{X}_k \text{ with a unit diagonal}\,. \end{align}\]

The iterations start at $\mathbf{Y}_0 = \mathbf{C}$ and $\Delta\mathbf{S}_0 = \mathbf{0}$. They stop when $\lambda_{\min}(\mathbf{Y}_k) \geq -n\, \varepsilon \max_i |\lambda_i(\mathbf{Y}_k)|$, or after iter iterations. The clip then runs on the last $\mathbf{Y}_k$, so a sequence that has not converged still gives a repaired matrix, and the algorithm never refuses the call for that reason.

This is Algorithm 3.3 of [24] with the unweighted Frobenius norm. That algorithm projects onto the positive semidefinite cone with a floor of zero, and it states no stop test. Section 4 of that work stops on the relative change of the iterates, Equation 4.1. The floor of $5 \varepsilon$ and the stop test above are this library's changes.

Where:

  • $\mathbf{\Sigma}$: The input covariance matrix.
  • $\mathbf{D} = \mathrm{Diag}(\boldsymbol{\sigma})$: The diagonal matrix of the standard deviations $\sigma_i = \sqrt{\mathbf{\Sigma}_{ii}}$.
  • $\mathbf{C}$: The correlation matrix of $\mathbf{\Sigma}$, or the last iterate of the alternating projections.
  • $\mathbf{V}$, $\boldsymbol{\lambda}$: The eigenvectors and the eigenvalues of $\mathbf{C}$.
  • $\tau$: The floor of the correlation eigenvalues, the field tau.
  • $\mathbf{Y}$: The correlation matrix with the clipped spectrum, before the scaling of its diagonal.
  • $\hat{\mathbf{C}}$: The repaired correlation matrix.
  • $\hat{\mathbf{\Sigma}}$: The repaired covariance matrix.
  • $\lambda_{\min}(\cdot)$: The smallest eigenvalue of a matrix.
  • $n$: The number of rows of $\mathbf{\Sigma}$.
  • $\varepsilon$: Machine epsilon of the element type, twice its unit roundoff $u$.
  • $\mathbf{R}_k$, $\mathbf{X}_k$, $\mathbf{Y}_k$: The corrected input, the positive semidefinite projection and the unit-diagonal projection of iteration $k$.
  • $\mathbf{V}_k$: The eigenvectors of $\mathbf{R}_k$.
  • $\Delta\mathbf{S}_k$: The correction of Dykstra at iteration $k$.

Algorithm

posdef_accepts and posdef_repair! run these steps for this algorithm. posdef! sets the zero variances aside before the repair.

  1. Refuse a matrix with a non-finite entry, a negative variance, or a correlation matrix that is not symmetric to 1e-8 + 1e-5 |C_ji| in each entry.
  2. Standardise the matrix into C with clipped_correlation.
  3. Return the matrix unchanged when clipped_repair_holds accepts it.
  4. When higham is true, replace C with the last iterate of higham_alternating_projections.
  5. Take the eigen decomposition of C once.
  6. For tau and then 10 * tau: clip the eigenvalues, rebuild Y, scale its diagonal to one, scale it back to a covariance, symmetrise it, restore the variances, and return it when clipped_repair_holds accepts it.
  7. Return the last result when its smallest eigenvalue is at least -n * eps * max|λ|, and refuse it with a PosdefRepairError otherwise, as assert_posdef_repair states. When a last result with no Cholesky factor passes this test, the algorithm returns it with no message.

Fields

  • tau: Floor of the correlation eigenvalues, $0 < \tau < 1$. The acceptance test reads tau / 2, and the one retry clips at 10 * tau.
  • higham: When true, Higham's alternating projections run before the clip.
  • iter: Largest number of iterations of the alternating projections. The algorithm reads it only when higham is true.

Constructors

ClippedNearestCorrelation(;    tau::Number = 1e-13,    higham::Bool = false,    iter::Integer = 100,) -> ClippedNearestCorrelation

Keywords correspond to the struct's fields.

Validation

  • 0 < tau < 1.
  • iter > 0.

Examples

julia> ClippedNearestCorrelation()ClippedNearestCorrelation     tau ┼ Float64: 1.0e-13  higham ┼ Bool: false    iter ┴ Int64: 100

The correlation matrix below passes the Cholesky factorisation, and its smallest eigenvalue is about 1e-15. The default Posdef() accepts it unchanged. The clip lifts its smallest eigenvalue to about tau.

julia> using LinearAlgebrajulia> X = [1.0 1.0-1e-15; 1.0-1e-15 1.0];julia> isposdef(X)truejulia> posdef(Posdef(), X) == Xtruejulia> Y = posdef(Posdef(; alg = ClippedNearestCorrelation()), X);julia> eigmin(Y) > 5e-14true

Related

References

  • [22] P. J. Rousseeuw and G. Molenberghs. Transformation of non positive semidefinite correlation matrices. Communications in Statistics - Theory and Methods 22, 965–984 (1993). Section 3, and Equations 2.5 and 3.3.
  • [23] R. Rebonato and P. Jäckel. The most general methodology for creating a valid correlation matrix for risk management and option pricing purposes. Journal of Risk 2, 17–27 (2000). Section 3, Equations 8 to 13.
  • [24] N. J. Higham. Computing the nearest correlation matrix—a problem from finance. IMA Journal of Numerical Analysis 22, 329–343 (2002). Section 3.2, Algorithm 3.3, and Section 4, Equation 4.1.
source
PortfolioOptimisers.Posdef — Type
struct Posdef{__T_alg, __T_kwargs} <: AbstractPosdefEstimator

Projects a co-moment matrix to the nearest positive definite matrix.

Posdef holds the algorithm and the keyword arguments that posdef! and posdef use for the projection.

The algorithm alg is one of the algorithms of NearestCorrelationMatrix.jl, with NearestCorrelationMatrix.Newton as the default, or ClippedNearestCorrelation, a clip of the correlation eigenvalues that keeps the variances. Each algorithm decides with posdef_accepts which matrix it leaves unchanged.

Fields

  • alg: The algorithm of the projection to the nearest correlation matrix.
  • kwargs: A named tuple of keyword arguments that posdef! passes to the algorithm.

Constructors

Posdef(;    alg::Any = NearestCorrelationMatrix.Newton,    kwargs::NamedTuple = (;),) -> Posdef

Keywords correspond to the struct's fields.

Validation

  • kwargs is empty when alg is a ClippedNearestCorrelation. That algorithm reads only its own fields, so it ignores every keyword.

Examples

julia> Posdef()Posdef     alg ┼ UnionAll: NearestCorrelationMatrix.Newton  kwargs ┴ @NamedTuple{}: NamedTuple()

Related

References

  • [24] N. J. Higham. Computing the nearest correlation matrix—a problem from finance. IMA Journal of Numerical Analysis 22, 329–343 (2002). Section 1, Equation 1.1.
  • [25] H. Qi and D. Sun. A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM Journal on Matrix Analysis and Applications 28, 360–385 (2006). Section 5, Algorithm 5.1.
source
PortfolioOptimisers.posdef — Function
posdef(pdm::Option{<:AbstractPosdefEstimator}, X::MatNum) -> MatNum

Out-of-place version of posdef!.

Algorithm

  1. Copy X.
  2. Apply posdef! to the copy, and return it. The function never changes the input.

Arguments

  • pdm: Optional positive definite matrix estimator.
  • X: Covariance-like or correlation-like matrix assets × assets.

Returns

  • X::MatNum: A new matrix equal to the nearest positive definite projection of the input.

Examples

julia> using LinearAlgebrajulia> X = [1.0 2.0; 2.0 1.0];julia> Xpd = posdef(Posdef(), X);julia> LinearAlgebra.isposdef(Xpd)true

Related

source
PortfolioOptimisers.posdef! — Function
posdef!(pdm::Option{<:AbstractPosdefEstimator}, X::MatNum) -> MatNum

Projects a matrix in place to the nearest positive definite matrix under the estimator pdm.

When the diagonal of X is not all ones, the function converts X to a correlation matrix, applies the algorithm, and scales the result back to a covariance.

A variance that is exactly zero belongs to a constant variable, and it keeps a zero row and column. The repair runs on the block of positive variances, so the result is positive semidefinite and not positive definite. The function gives no message for the zero rows, because they are the correct answer.

When the repaired matrix is positive semidefinite to round-off, the function returns it with no message, singular or not. When it is not, the function raises a PosdefRepairError, as assert_posdef_repair states. So no consumer reads a matrix with a negative variance in some direction.

Mathematical definition

Solves the nearest correlation matrix problem:

\[\begin{align} \hat{\mathbf{C}} &= \underset{\mathbf{Y} \succeq 0,\; Y_{ii} = 1}{\arg\min} \lVert \mathbf{C} - \mathbf{Y} \rVert_F\,. \end{align}\]

Where:

  • $\hat{\mathbf{C}}$: The nearest positive semidefinite correlation matrix.
  • $\mathbf{C}$: The input correlation matrix.
  • $\mathbf{Y}$: A feasible correlation matrix, which is positive semidefinite and has a unit diagonal.
  • $\lVert \cdot \rVert_F$: The Frobenius norm.

The function first standardises a covariance matrix to $\mathbf{C} = \mathrm{diag}(\mathbf{\Sigma})^{-1/2} \mathbf{\Sigma}\, \mathrm{diag}(\mathbf{\Sigma})^{-1/2}$. Then it projects $\mathbf{C}$ and scales the result back.

A zero variance has no correlation, so it cannot be standardised. The projection keeps the diagonal, and a positive semidefinite matrix with a zero diagonal entry has a zero row and column, as zero_variance_rows! states. The projection above then runs on the block of positive variances alone.

Algorithm

  1. Check that X is square.
  2. Return X unchanged when posdef_accepts accepts it under pdm.alg. For an algorithm of NearestCorrelationMatrix.jl the test is isposdef, and ClippedNearestCorrelation has its own test and its own refusals.
  3. Set the zero-variance rows and columns of X to zero with zero_variance_block!. When there is such a row, repair the block of positive variances with a recursive call, write the block back, and return X. The recursive call refuses only a repaired block that is not positive semidefinite to round-off. A matrix with a zero variance never passes the test of step 2, so this step is always reached for it.
  4. Repair X with posdef_repair! under pdm.alg and the keyword arguments pdm.kwargs, and return X.

Arguments

  • pdm: Optional positive definite matrix estimator.

    • ::Posdef: Projects X to the nearest positive definite matrix under pdm.alg. A matrix that posdef_accepts accepts stays unchanged.
    • ::Nothing: Returns X unchanged.
  • X: Covariance-like or correlation-like matrix assets × assets.

Validation

Returns

  • X::MatNum: The input matrix X, modified in place.

Examples

julia> using LinearAlgebrajulia> est = Posdef();julia> X = [1.0 0.9; 0.9 1.0];julia> X[1, 2] = 2.0;  # Not PDjulia> posdef!(est, X)2×2 Matrix{Float64}: 1.0  1.0 1.0  1.0julia> LinearAlgebra.isposdef(X)true

The second variable below is constant. Its row and column stay zero, and the other two variables are repaired as above.

julia> X = [1.0 0.0 2.0; 0.0 0.0 0.0; 2.0 0.0 1.0];julia> posdef!(Posdef(), X)3×3 Matrix{Float64}: 1.0  0.0  1.0 0.0  0.0  0.0 1.0  0.0  1.0

Related

source

References

[22]
P. J. Rousseeuw and G. Molenberghs. Transformation of non positive semidefinite correlation matrices. Communications in Statistics - Theory and Methods 22, 965–984 (1993).
[23]
R. Rebonato and P. Jäckel. The most general methodology for creating a valid correlation matrix for risk management and option pricing purposes. Journal of Risk 2, 17–27 (2000).
[24]
N. J. Higham. Computing the nearest correlation matrix—a problem from finance. IMA Journal of Numerical Analysis 22, 329–343 (2002).
[25]
H. Qi and D. Sun. A quadratically convergent Newton method for computing the nearest correlation matrix. SIAM Journal on Matrix Analysis and Applications 28, 360–385 (2006).