pith. sign in

arxiv: 2504.10814 · v6 · submitted 2025-04-15 · 🧮 math.OC

An Operator Splitting Method for Large-Scale CVaR-Constrained Quadratic Programs

Eric Luxenberg , David P\'erez-Pi\~neiro , Steven Diamond , Stephen Boyd This is my paper

Pith reviewed 2026-05-22 20:42 UTC · model grok-4.3

classification 🧮 math.OC
keywords CVaR constraintsquadratic programmingoperator splittingprojection algorithmslarge-scale optimizationrisk measuresscenario-based optimization
0
0 comments X

The pith

Operator splitting with a fast CVaR projection solves quadratic programs with millions of scenarios orders of magnitude faster than general solvers.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops a method for quadratic programs whose constraints involve conditional value-at-risk over many scenarios. It uses operator splitting to alternate between solving a single linear system and performing projections, with a custom algorithm that projects onto the CVaR set in O(m log m) time and simple clipping for box constraints. This avoids expanding the full problem size with the scenario count, which renders standard solvers impractical. Numerical tests across application domains show the approach runs several orders of magnitude faster on instances with up to millions of scenarios. The method is released as open-source software named CVQP.

Core claim

The paper claims that operator splitting, which alternates between solving a linear system and applying a specialized O(m log m) projection onto CVaR constraints together with box projections by clipping, produces a scalable algorithm for quadratic programs that would otherwise grow linearly in size with the number of scenarios and become intractable for general-purpose solvers.

What carries the argument

Operator splitting that alternates linear system solves with an O(m log m) projection onto the CVaR constraint set.

If this is right

  • Problems with up to millions of scenarios become solvable in practical runtimes.
  • The method outperforms general-purpose solvers by several orders of magnitude on tested instances.
  • CVaR projections can be computed in O(m log m) time and executed in parallel.
  • Box constraints are handled exactly by elementwise clipping without extra cost.
  • The algorithm is realized in the open-source CVQP package.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same splitting pattern could be applied to quadratic programs with other coherent risk measures that admit fast projections.
  • Real-time portfolio or resource allocation decisions under uncertainty with very large scenario sets may now be feasible.
  • Warm-starting the linear system solves across iterations or outer loops could produce additional speedups not explored in the paper.
  • The approach may combine with existing first-order methods for even larger or more structured problems.

Load-bearing premise

The quadratic program structure permits efficient repeated solves of the linear system while the specialized CVaR projection remains the dominant cost.

What would settle it

A benchmark problem with one million scenarios on which the splitting method either fails to converge or takes more time than a general-purpose quadratic program solver such as OSQP.

Figures

Figures reproduced from arXiv: 2504.10814 by David P\'erez-Pi\~neiro, Eric Luxenberg, Stephen Boyd, Steven Diamond.

Figure 1
Figure 1. Figure 1: CVaR projection solve times, with η = 0.5. at m = 104 and 1.98 s at m = 107 , more than two orders of magnitude faster than both Mosek and Clarabel across all tested sizes. Mosek does not solve instances with m ≥ 3 × 106 within the time limit. 5.3 Portfolio optimization We consider a portfolio optimization problem with n assets and m return scenarios. The matrix R ∈ R m×n contains asset returns, where Rij … view at source ↗
Figure 2
Figure 2. Figure 2: Portfolio optimization solve times, with n = 2000 assets. CVaR reformulation. Defining the feature matrix U ∈ R m×n with rows u T i , the response vector y ∈ R m, and ¯u = 1 m Pm i=1 ui , we use the identity ρτ (z) = (1 − τ )(−z) + (z)+ to write the objective as (1 − τ ) [PITH_FULL_IMAGE:figures/full_fig_p018_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: Quantile regression solve times, with n = 500 features. CVQP form. We introduce an auxiliary variable s with the constraint s = 1, and define ˜x = (x, t, s) ∈ R n+2. The CVQP parameters, with CVaR level β = τ , are P = 0, q =   u¯ 1 0   , A = [PITH_FULL_IMAGE:figures/full_fig_p019_3.png] view at source ↗
read the original abstract

We introduce a fast and scalable method for solving quadratic programs with conditional value-at-risk (CVaR) constraints. While these problems can be formulated as standard quadratic programs, the number of variables and constraints grows linearly with the number of scenarios, making general-purpose solvers impractical for large-scale problems. Our method combines operator splitting with a specialized $O(m\log m)$ algorithm for projecting onto CVaR constraints, where $m$ is the number of scenarios. The method alternates between solving a linear system and performing parallel projections, onto CVaR constraints using our specialized algorithm and onto box constraints by simple clipping. Numerical examples from several application domains demonstrate that our method outperforms general-purpose solvers by several orders of magnitude on problems with up to millions of scenarios. Our method is implemented in an open-source package called CVQP.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The paper introduces an operator splitting method for large-scale quadratic programs with CVaR constraints. The approach alternates between solving a fixed-size linear system (from the quadratic term on decision variables) and performing parallel projections: an O(m log m) specialized routine onto the CVaR constraint set and simple clipping onto box constraints. Numerical experiments across application domains report orders-of-magnitude speedups over general-purpose solvers on instances with up to millions of scenarios; an open-source implementation (CVQP) is provided.

Significance. If the claimed scaling and projection complexity hold, the method enables practical solution of CVaR-constrained QPs at scales previously inaccessible to general solvers, which is relevant for risk-aware optimization in finance and operations research. Strengths include the open-source code, the separation of the fixed linear system from scenario-dependent projections, and the absence of free parameters in the core splitting construction.

minor comments (1)
  1. [Abstract / §3] The abstract and introduction would benefit from an explicit statement of the convergence rate or iteration complexity of the overall splitting scheme (e.g., in §3 or §4) to support the performance claims.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, including the recognition of the method's scalability, the separation of the fixed linear system from scenario-dependent projections, the parameter-free construction, and the open-source implementation. We are pleased that the referee recommends acceptance.

Circularity Check

0 steps flagged

No significant circularity detected

full rationale

The paper presents an algorithmic construction: operator splitting applied to a CVaR-constrained QP, alternating between a fixed-size linear solve and a specialized O(m log m) CVaR projection (plus box clipping). No step reduces a claimed result to a fitted parameter, self-referential definition, or load-bearing self-citation chain. The central claim (scalable solution via this splitting) is a direct description of the proposed procedure rather than a prediction derived from prior fitted quantities. The method is self-contained against external benchmarks (general-purpose solvers) and does not invoke uniqueness theorems or ansatzes from the authors' prior work as the sole justification for the core algorithm.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The method relies on standard properties of convex optimization and operator splitting without introducing new free parameters or postulated entities.

axioms (1)
  • domain assumption CVaR defines a convex constraint set amenable to projection
    Invoked to justify the existence and use of the specialized projection step.

pith-pipeline@v0.9.0 · 5678 in / 1141 out tokens · 48657 ms · 2026-05-22T20:42:25.671000+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    The isotonic regression problem and its dual,

    R. Barlow and H. Brunk, “The isotonic regression problem and its dual,”Jour- nal of the American Statistical Association, vol. 67, no. 337, pp. 140–147, 1972

    work page 1972

  2. [2]

    Applications of the method of multipliers to variational inequali- ties,

    D. Gabay, “Applications of the method of multipliers to variational inequali- ties,” inAugmented Lagrangian methods: applications to the numerical solution of boundary-value problems, ser. Studies in Mathematics and Its Applications, M. Fortin and R. Glowinski, Eds., vol. 15, Elsevier, 1983, pp. 299–331

    work page 1983

  3. [3]

    Two-metric projection methods for constrained optimization,

    E. Gafni and D. Bertsekas, “Two-metric projection methods for constrained optimization,”SIAM Journal on Control and Optimization, vol. 22, no. 6, pp. 936–964, 1984

    work page 1984

  4. [4]

    On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,

    J. Eckstein and D. Bertsekas, “On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,”Mathematical Programming, vol. 55, pp. 293–318, 1992

    work page 1992

  5. [5]

    Parallel alternating direction multiplier decomposition of convex programs,

    J. Eckstein, “Parallel alternating direction multiplier decomposition of convex programs,”Journal of Optimization Theory and Applications, vol. 80, no. 1, pp. 39–62, 1994

    work page 1994

  6. [6]

    Optimization of conditional value-at- risk,

    R. T. Rockafellar, S. Uryasev, et al., “Optimization of conditional value-at- risk,”Journal of Risk, vol. 2, pp. 21–42, 2000

    work page 2000

  7. [7]

    Portfolio optimization with con- ditional value-at-risk objective and constraints,

    P. Krokhmal, J. Palmquist, and S. Uryasev, “Portfolio optimization with con- ditional value-at-risk objective and constraints,”Journal of Risk, vol. 4, pp. 43– 68, 2002

    work page 2002

  8. [8]

    A novel linear programming approach to fluence map optimization for intensity mod- ulated radiation therapy treatment planning,

    H. E. Romeijn, R. K. Ahuja, J. F. Dempsey, A. Kumar, and J. G. Li, “A novel linear programming approach to fluence map optimization for intensity mod- ulated radiation therapy treatment planning,”Physics in Medicine & Biology, vol. 48, no. 21, pp. 3521–3542, 2003

    work page 2003

  9. [9]

    Risk management of power port- folios and valuation of flexibility,

    J. Doege, P. Schiltknecht, and H.-J. L¨ uthi, “Risk management of power port- folios and valuation of flexibility,”OR Spectrum, vol. 28, no. 2, pp. 267–287, 2006

    work page 2006

  10. [10]

    Newsvendor solutions via conditional value-at-risk minimization,

    J. Gotoh and Y. Takano, “Newsvendor solutions via conditional value-at-risk minimization,”European Journal of Operational Research, vol. 179, no. 1, pp. 80–96, 2007. 21

    work page 2007

  11. [11]

    Distributed opti- mization and statistical learning via the alternating direction method of multi- pliers,

    S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al., “Distributed opti- mization and statistical learning via the alternating direction method of multi- pliers,”Foundations and Trends in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011

    work page 2011

  12. [12]

    Selection of supply portfolio under disruption risks,

    T. Sawik, “Selection of supply portfolio under disruption risks,”Omega, vol. 39, no. 2, pp. 194–208, 2011

    work page 2011

  13. [13]

    Risk-averse two-stage stochastic programming with an application to disaster management,

    N. Noyan, “Risk-averse two-stage stochastic programming with an application to disaster management,”Computers & Operations Research, vol. 39, no. 3, pp. 541–559, 2012

    work page 2012

  14. [14]

    Computational risk management techniques for fixed charge network flow problems with un- certain arc failures,

    A. Sorokin, V. Boginski, A. Nahapetyan, and P. M. Pardalos, “Computational risk management techniques for fixed charge network flow problems with un- certain arc failures,”Journal of Combinatorial Optimization, vol. 25, no. 1, pp. 99–122, 2013

    work page 2013

  15. [15]

    Distributionally robust control of constrained stochastic systems,

    B. P. Van Parys, D. Kuhn, P. J. Goulart, and M. Morari, “Distributionally robust control of constrained stochastic systems,”IEEE Transactions on Au- tomatic Control, vol. 61, no. 2, pp. 430–442, 2015

    work page 2015

  16. [16]

    Conditional value-at-risk beyond finance: A survey,

    C. Filippi, G. Guastaroba, and M. G. Speranza, “Conditional value-at-risk beyond finance: A survey,”International Transactions in Operational Research, vol. 27, no. 3, pp. 1277–1319, 2020

    work page 2020

  17. [17]

    Superquantiles at work: Machine learning applications and efficient subgradient computation,

    Y. Laguel, K. Pillutla, J. Malick, and Z. Harchaoui, “Superquantiles at work: Machine learning applications and efficient subgradient computation,”Set- Valued and Variational Analysis, vol. 29, no. 4, pp. 967–996, 2021

    work page 2021

  18. [18]

    Roth and Y

    J. Roth and Y. Cui,On O(n) algorithms for projection onto the top-k-sum sublevel set, 2023

    work page 2023

  19. [19]

    Roth and Y

    J. Roth and Y. Cui,Fast computation of superquantile-constrained optimization through implicit scenario reduction, 2024

    work page 2024

  20. [20]

    On O(n) algorithms for projection onto the top-k-sum sublevel set,

    J. Roth and Y. Cui, “On O(n) algorithms for projection onto the top-k-sum sublevel set,”Mathematical Programming Computation, pp. 1–42, 2025. 22

    work page 2025