Portfolio Construction as Linearly Constrained Separable Optimization

Nicholas Moehle, Jack Gindi, Stephen Boyd, Mykel J. Kochenderfer

Abstract

Real-world portfolio management often involves complex, nonconvex constraints such as transaction costs, tax liabilities, and minimum trade sizes. While these factors are critical for practical implementation, they transform elegant mean-variance optimization into computationally intensive problems. This paper introduces the Separable-Affine Optimization (SAP) framework, a heuristic approach using the Alternating Direction Method of Multipliers (ADMM) to solve these nonconvex problems in milliseconds. By leveraging the separable nature of asset-specific costs, the authors achieve near-optimal results with provable performance bounds, offering a scalable solution for large-scale, tax-aware portfolio construction.

Introduction

In the idealized framework of Markowitz’s mean-variance optimization, the investment landscape is smooth and convex. However, practitioners operate in a "messy" reality where friction is the norm. Transaction costs, tax-loss harvesting, and integer share constraints introduce nonconvexities that standard convex solvers cannot handle. While Mixed-Integer Linear Programming (MILP) can solve these problems exactly, its computational unpredictability makes it unsuitable for real-time applications or large-scale backtesting. This research, authored by Nicholas Moehle and colleagues from Stanford and BlackRock, proposes a fast, reliable alternative that bridges the gap between theoretical elegance and practical necessity.

The Challenges of Real-World Portfolio Management

The authors identify several key frictions that complicate the optimization process:

  • Transaction Costs: Fixed fees for executing trades create a "buy, sell, or do nothing" hurdle.
  • Minimum Trade Sizes: Constraints that prevent the purchase of fractional or negligible amounts of shares.
  • Tax Liability: The "kinked" cost curves associated with realizing capital gains and losses.
  • Integer Constraints: The requirement to hold whole numbers of shares, which is particularly relevant for high-priced securities or smaller portfolios.

These factors make the objective function nonconvex. In a standard optimization environment, this would typically require exhaustive search methods that scale poorly with the number of assets.

The Separable-Affine Optimization (SAP) Framework

The core insight of the paper is that while the global objective is nonconvex, it is often separable. This means the total cost is the sum of independent costs associated with each individual asset. The authors define this as a Separable-Affine Problem (SAP), where the objective is a sum of univariate nonconvex functions subject to linear (affine) constraints, such as budget neutrality or factor exposure limits.

Solving SAP via ADMM

To solve the SAP, the authors employ the Alternating Direction Method of Multipliers (ADMM). This algorithm decomposes the problem into two alternating steps:

  1. The x-update: This step solves $n$ independent, one-dimensional optimization problems (one for each asset). Because these are 1D, the nonconvexity is easily managed via proximal operators, even for complex piecewise quadratic functions.
  2. The z-update: This step handles the linear constraints by solving a linear system of equations. By utilizing a standard factor model for risk, the authors ensure this system remains small and computationally efficient regardless of the total number of assets.

Performance Bounds

Because ADMM is a heuristic for nonconvex problems, it does not guarantee a global optimum. To address this, the authors utilize convex relaxation. By replacing nonconvex functions with their convex envelopes (the tightest possible convex lower bound), they can solve a relaxed version of the problem to find a theoretical lower bound on the objective. This allows managers to quantify exactly how much performance might be "left on the table."

Empirical Performance

The researchers evaluated the SAP framework using a 17-year tax-aware backtest (2002–2019) involving 692 problem instances based on the S&P 500. Each instance involved approximately 500 securities and 100 risk factors.

Key Results

  • Computational Speed: The ADMM heuristic solved nonconvex problems in an average of 251 milliseconds. The convex relaxation took only 152 ms. This level of performance enables interactive "what-if" analysis for advisors and high-frequency rebalancing.
  • Optimality: The "suboptimality gap"—the difference between the ADMM result and the theoretical lower bound—averaged only 0.6 basis points (0.006%). This suggests that for financial applications, the heuristic is nearly as effective as an exact solver.
  • Reliability: The algorithm demonstrated consistent convergence across all 692 test cases, avoiding the "hangs" or timeouts sometimes associated with MILP solvers on difficult instances.

Conclusion and Future Work

The SAP framework demonstrates that separability is a powerful tool in portfolio optimization. By isolating nonconvexities into asset-specific subproblems, ADMM provides a path to solve complex, tax-aware problems with extreme speed and high accuracy.

While the method is highly effective for affine constraints, future work may explore extending the framework to handle non-polyhedral constraints, such as complex quadratic risk limits that do not fit a standard factor model. Additionally, automating the tuning of ADMM scaling parameters could further enhance the "plug-and-play" utility of the algorithm for diverse financial applications.

Summary updated

BibTeX
@inproceedings{moehle2022portfolio,
  author = {Nicholas Moehle and Jack Gindi and Stephen Boyd and Mykel J. Kochenderfer},
  title = {{Portfolio Construction as Linearly Constrained Separable Optimization}},
  booktitle = {Optimization},
  year = {2022},
  doi = {10.1007/s11081-022-09748-x},
}
Figure