📈 cvxcla - Critical Line Algorithm for Portfolio Optimization¶
Quick Links: 📖 Documentation • 🐛 Report Bug • 💡 Request Feature • 💬 Discussions
📋 Overview¶
cvxcla is a Python package that implements the Critical Line Algorithm (CLA)
for portfolio optimization.
The CLA efficiently computes the entire efficient frontier for portfolio optimization
problems with linear constraints and bounds on the weights.
The same parametric active-set engine also traces the LASSO regularisation path
(the Lasso class) — including general inequality constraints Gβ ≤ h and the
non-negative LASSO β ≥ 0 — so the Critical Line Algorithm and the LARS/LASSO
homotopy come out as two instances of one path-following engine.
The Critical Line Algorithm was introduced by Harry Markowitz in The Optimization of Quadratic Functions Subject to Linear Constraints and further described in his book Portfolio Selection.
The algorithm is based on the observation that the efficient frontier is a piecewise linear function when expected return is plotted against expected variance. The CLA computes the turning points (corners) of the efficient frontier, allowing for efficient representation of the entire frontier.
I gave the plenary talk at EQD's Singapore conference.
🧮 Why the Algorithm Works¶
The Markowitz problem is a quadratic program parametrized by a return target λ:
where Aw = b are linear equalities (the budget, sector/factor neutrality, …) and
Gw ≤ h are linear inequalities (group or sector exposure caps; a ≥ floor is the
negated row). As λ sweeps from ∞ (maximize return) down to 0 (minimize variance), the solution
traces the entire efficient frontier. The key insight is that between consecutive
events, the optimal weights are a linear function of λ:
This holds because the KKT optimality conditions are linear in λ whenever the active set — which assets sit at their bounds — is fixed. The algorithm exploits this in three steps:
-
Start at λ = ∞, where the portfolio concentrates on the highest-return asset within bounds (
init_algo). -
Solve the KKT system for the current active set to find α and β by block elimination, then decrease λ until one of two events occurs (main loop in
cla.py): - a free asset hits its bound (leaves the free set), or
- a blocked asset's KKT multiplier changes sign (enters the free set).
General inequality rows Gw ≤ h add the row analogue of these two events: an
inactive row becomes binding when its slack reaches zero, and an active row is
released when its multiplier reaches zero. An active row is carried through the
same block-eliminated solve as an extra equality row, so the structure is
preserved.
- Update the active set (exactly one asset or constraint row changes status) and repeat until λ ≤ 0.
Because only one coordinate changes per step and each step requires only a single linear solve, the algorithm traces the full frontier cheaply and exactly — no approximation needed.
✨ Features¶
- Efficient computation of the entire efficient frontier
- Fluent builder API —
CLA.problem(mean, cov).long_only().budget().trace()— as a readable alternative to the explicit constructor - Box bounds on every weight, plus general linear equality constraints
Aw = b(budget, dollar-neutral, sector/factor neutrality) and general linear inequality constraintsGw ≤ h(group or sector exposure caps) - Factor covariance backend: exact frontiers for diagonal-plus-low-rank covariances (factor models, RMT-cleaned matrices) in O(nk) memory via the Woodbury identity
- Visualization of the efficient frontier using Plotly
- Computation of the maximum Sharpe ratio portfolio
- LASSO regularisation path through the same engine (
Lasso), with the same fluent builder, general inequality constraintsGβ ≤ h, and the non-negative LASSOβ ≥ 0 - Fully tested and documented codebase
🚀 Installation¶
Using pip¶
To include plotting support (Plotly and Kaleido):
Development Setup¶
To set up a development environment:
-
Clone the repository:
-
Create a virtual environment and install dependencies:
This will:
- Install the uv package manager
- Create a Python 3.12 virtual environment
- Install all dependencies from pyproject.toml
🔧 Usage¶
Here's a simple example of how to use cvxcla to compute the efficient frontier:
import numpy as np
# Set a seed for reproducibility
np.random.seed(42)
from cvxcla import CLA
# Define your portfolio problem
n = 10 # Number of assets
mean = np.random.randn(n) # Expected returns
cov = np.random.randn(n, n)
covariance = cov @ cov.T # Covariance matrix
lower_bounds = np.zeros(n) # No short selling
upper_bounds = np.ones(n) # No leverage
# Create a CLA instance
cla = CLA(
mean = mean,
covariance = covariance,
lower_bounds = lower_bounds,
upper_bounds = upper_bounds,
a = np.ones((1, n)), # Fully invested constraint
b = np.ones(1)
)
# Access the efficient frontier
frontier = cla.frontier
# Get the maximum Sharpe ratio portfolio
max_sharpe_ratio, max_sharpe_weights = frontier.max_sharpe
print(f"Maximum Sharpe ratio: {max_sharpe_ratio:.6f}")
# Print first few weights to avoid long output
print(f"First 3 weights: {max_sharpe_weights[:3]}")
The same problem reads more declaratively through the fluent builder, reached via
CLA.problem(...). Each step maps onto one constructor argument, and the terminal
.trace() returns the identical CLA:
# Same fully-invested, long-only problem as above, assembled fluently.
built = CLA.problem(mean, covariance).long_only().budget().trace()
# Pure sugar over the constructor: it returns the identical frontier.
assert built.frontier.max_sharpe[0] == cla.frontier.max_sharpe[0]
.bounds, .equality, and .inequality add general bounds and constraints, as in
the examples below.
For visualization, you can plot the efficient frontier:
Group and sector constraints¶
Pass g and h to add general inequality rows Gw ≤ h on top of the box bounds and
the budget. For example, to cap the combined weight of the first three assets (a
sector) at 40%:
import numpy as np
from cvxcla import CLA
n = 10
rng = np.random.default_rng(42)
mean = rng.standard_normal(n)
factor = rng.standard_normal((n, n))
covariance = factor @ factor.T # symmetric positive definite
# sum of the first three weights ≤ 0.40
g = np.zeros((1, n))
g[0, :3] = 1.0
h = np.array([0.40])
cla = CLA(
mean=mean,
covariance=covariance,
lower_bounds=np.zeros(n),
upper_bounds=np.full(n, 0.35),
a=np.ones((1, n)), # fully invested
b=np.ones(1),
g=g, # inequality matrix G (p x n)
h=h, # inequality vector h (p,)
)
# every turning point now satisfies the sector cap
assert all(tp.weights[:3].sum() <= 0.40 + cla.tol for tp in cla.turning_points)
g/h default to None, so omitting them recovers the equality-only problem
unchanged. Stack multiple rows in g for several caps at once, and express a ≥
floor by negating a row (-Gw ≤ -h).
Factor models at scale¶
For diagonal-plus-low-rank covariances (factor risk models, eigenvalue-clipped
covariances) pass a FactorCovariance instead of a dense matrix; the algorithm
then never forms an n-by-n matrix:
import numpy as np
from cvxcla import CLA, FactorCovariance
rng = np.random.default_rng(42)
n, k = 10_000, 50
covariance = FactorCovariance(
d=rng.uniform(0.1, 0.5, n), # idiosyncratic variances
u=rng.standard_normal((n, k)), # factor loadings
delta=rng.uniform(0.5, 2.0, k), # factor variances, (k,) or (k, k)
)
See the factor backend documentation for the protocol, the math, and benchmarks against the dense path.
The LASSO through the same engine¶
The same path-tracer drives the LASSO regularisation path. Lasso plays the Gram
matrix XᵀX and the vector Xᵀy the way the CLA plays the covariance and the mean,
and traces the whole path from λ_max (where β = 0) down to the least-squares fit:
import numpy as np
from cvxcla import Lasso
rng = np.random.default_rng(0)
X = rng.standard_normal((60, 12))
y = X @ rng.standard_normal(12) + 0.1 * rng.standard_normal(60)
# plain LASSO path; .solution(lam) evaluates beta at any penalty
lasso = Lasso(x=X, y=y)
beta = lasso.solution(0.5 * lasso.lam_max)
# the same fluent builder as the CLA
lasso = Lasso.problem(X, y).trace()
It carries the same constraints the CLA does. Add general inequality rows Gβ ≤ h
(with h > 0, e.g. per-group exposure caps), or restrict to the non-negative
LASSO β ≥ 0 — where the ℓ₁ penalty collapses to the linear term λ·1ᵀβ, making
it exactly the CLA's box-bounded parametric QP:
# group-exposure caps G beta <= h (cap features 0–3 and 4–7)
G = np.zeros((2, 12))
G[0, :4] = 1.0
G[1, 4:8] = 1.0
h = np.array([1.0, 1.0])
lasso = Lasso.problem(X, y).inequality(G, h).trace()
# non-negative LASSO (beta >= 0)
lasso = Lasso.problem(X, y).non_negative().trace()
Both return the exact path, validated breakpoint-by-breakpoint against a per-λ QP
solver. (Equality constraints Aβ = b need a feasibility seed and are not yet
supported; the canonical sum-to-zero case cannot be traced one coordinate at a time.)
🧪 Testing¶
Run the test suite with:
or directly via pytest:
🧹 Code Quality¶
Format and lint the code with:
📖 Documentation¶
👥 Contributing¶
Contributions are welcome! Please feel free to submit a Pull Request.
- Fork the repository
- Create your feature branch (
git checkout -b feature/amazing-feature) - Run the tests to make sure everything works (
make test) - Format your code (
make fmt) - Commit your changes (
git commit -m 'Add some amazing feature') - Push to the branch (
git push origin feature/amazing-feature) - Open a Pull Request
📄 License¶
This project is licensed under the MIT License - see the LICENSE file for details.