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 <: AbstractEstimatorAbstract 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: ProjectsXin place to the nearest positive definite matrix.posdef(pdm::AbstractPosdefEstimator, X::MatNum) -> MatNum: Optional. Returns the projection ofXin a new matrix. A fallback method copiesXand callsposdef!, so add this method only when it avoids the copy.
Arguments
pdm: Positive definite matrix estimator.X: Covariance-like or correlation-like matrixassets × assets.
Returns
X::MatNum: The projected input matrixX.
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.0Related
PortfolioOptimisers.ClippedNearestCorrelation — Type
struct ClippedNearestCorrelation{__T_tau, __T_higham, __T_iter} <: AbstractAlgorithmRepairs 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.
- 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. - Standardise the matrix into
Cwithclipped_correlation. - Return the matrix unchanged when
clipped_repair_holdsaccepts it. - When
highamistrue, replaceCwith the last iterate ofhigham_alternating_projections. - Take the eigen decomposition of
Conce. - For
tauand then10 * tau: clip the eigenvalues, rebuildY, scale its diagonal to one, scale it back to a covariance, symmetrise it, restore the variances, and return it whenclipped_repair_holdsaccepts it. - Return the last result when its smallest eigenvalue is at least
-n * eps * max|λ|, and refuse it with aPosdefRepairErrorotherwise, asassert_posdef_repairstates. 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 readstau / 2, and the one retry clips at10 * tau.
higham: Whentrue, Higham's alternating projections run before the clip.
iter: Largest number of iterations of the alternating projections. The algorithm reads it only whenhighamistrue.
Constructors
ClippedNearestCorrelation(; tau::Number = 1e-13, higham::Bool = false, iter::Integer = 100,) -> ClippedNearestCorrelationKeywords 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: 100The 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-14trueRelated
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.
PortfolioOptimisers.Posdef — Type
struct Posdef{__T_alg, __T_kwargs} <: AbstractPosdefEstimatorProjects 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 thatposdef!passes to the algorithm.
Constructors
Posdef(; alg::Any = NearestCorrelationMatrix.Newton, kwargs::NamedTuple = (;),) -> PosdefKeywords correspond to the struct's fields.
Validation
kwargsis empty whenalgis aClippedNearestCorrelation. 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.
PortfolioOptimisers.posdef — Function
posdef(pdm::Option{<:AbstractPosdefEstimator}, X::MatNum) -> MatNumOut-of-place version of posdef!.
Algorithm
- Copy
X. - 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 matrixassets × 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)trueRelated
PortfolioOptimisers.posdef! — Function
posdef!(pdm::Option{<:AbstractPosdefEstimator}, X::MatNum) -> MatNumProjects 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
- Check that
Xis square. - Return
Xunchanged whenposdef_acceptsaccepts it underpdm.alg. For an algorithm ofNearestCorrelationMatrix.jlthe test isisposdef, andClippedNearestCorrelationhas its own test and its own refusals. - Set the zero-variance rows and columns of
Xto zero withzero_variance_block!. When there is such a row, repair the block of positive variances with a recursive call, write the block back, and returnX. 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. - Repair
Xwithposdef_repair!underpdm.algand the keyword argumentspdm.kwargs, and returnX.
Arguments
pdm: Optional positive definite matrix estimator.::Posdef: ProjectsXto the nearest positive definite matrix underpdm.alg. A matrix thatposdef_acceptsaccepts stays unchanged.::Nothing: ReturnsXunchanged.
X: Covariance-like or correlation-like matrixassets × assets.
Validation
assert_matrix_issquarechecksXbefore any other step.ClippedNearestCorrelationrefuses a non-finite entry, a negative variance and a matrix that is not symmetric, asposdef_acceptsstates.- A repaired matrix is positive semidefinite to round-off, which raises a
PosdefRepairErrorthroughposdef_repair!.
Returns
X::MatNum: The input matrixX, 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)trueThe 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.0Related
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).