Fast Computation of Superquantile-Constrained Optimization Through Implicit Scenario Reduction
Authors: Jake Roth, Ying Cui
JMLR 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | In synthetic problems with linear and convex diagonal quadratic objectives, numerical experiments demonstrate that our method outperforms existing approaches by a large margin: It achieves speeds more than 750 times faster for linear and quadratic objectives than the alternating direction method of multipliers as implemented by OSQP for computing low-accuracy solutions. Additionally, it is up to 25 times faster for linear objectives and 70 times faster for quadratic objectives than the commercial solver Gurobi, and 20 times faster for linear objectives and 30 times faster for quadratic objectives than the Portfolio Safeguard optimization suite for high-accuracy solution computations. For the quantile regression problem involving over 30 million scenarios, our method computes solution paths up to 20 times faster than Gurobi. |
| Researcher Affiliation | Academia | Jake Roth EMAIL Department of Industrial and Systems Engineering University of Minnesota Minneapolis, MN 55414 Ying Cui EMAIL Department of Industrial Engineering and Operations Research University of California, Berkeley Berkeley, CA 94720 |
| Pseudocode | Yes | Algorithm 1 The ALM framework for problem (13) Initialize: Choose x0 = z0 Rn, y0, λ0 Rm L, and µ Rn. Choose σ0 > 0 and a positive semidefinite matrix M. Set iteration ν = 0, and repeat the following steps until a proper stopping criterion is satisfied. 1: Primal update: (xν+1, yν+1, zν+1) arg min x, y B, z X Lσν(x, y, z; λν, µν) + 1 2σν x xν 2 M. (14) 2: Dual update: λν+1 := max λν + σν G(xν+1 yν+1) , 0 µν+1 := µν + σν(xν+1 zν+1). 3: Check termination criteria and update σν. Algorithm 2 A semismooth Newton method for the ν-th subproblem (16) Initialize: Set t = 0, choose an initial point xν,0, and choose backtracking line search parameters δ, c (0, 1). Perform the following steps until a convergence criterion is reached. 1: Semismooth Newton direction: using direct factorization or an indirect method, obtain an approximate solution d t to the linear system V d + ϕσν(xν,t) = 0, (22) where V ( ϕσν(xν,t)). 2: Line search (backtracking): Set ρt = ρ, where ρ is the smallest nonnegative integer such that ϕσν(xν,t + δρd t) ϕσν(xν,t) + c δρ ϕσν(xν,t) d t. 3: Update solution: xν,t+1 = xν,t + δρtdt. |
| Open Source Code | Yes | The Julia implementation of the solver is available at https://github.com/jacob-roth/superquantile-opt. |
| Open Datasets | Yes | Using ride-share data from the NYC Taxi and Limousine Commission (2023) and weather data from Open Weather (2023) for October 2022 through September 2023, we construct a dataset containing m = 32,534,601 trips with n = 19 features to predict the tip received by the driver for rides paying with credit card. The full dataset {(ai, bi)}m i=1 is available at https://doi.org/10.5281/zenodo. 11183368. |
| Dataset Splits | No | The paper mentions generating synthetic data and using a full dataset for quantile regression, but it does not specify any training/test/validation dataset splits. For synthetic data, it describes generation procedure but not splits. For real data, it states 'The full dataset {(ai, bi)}m i=1 is available...' without detailing how it is partitioned for experiments. |
| Hardware Specification | Yes | The experiments are conducted on a Dell workstation running a Windows environment, equipped with 8 physical processors and 32GB of RAM. We compare our ALM with GRB, G-OA, and PSG for computing highly accurate solutions (where ϵ = 10 8), and with OSQP for computing solutions with lower accuracy (where ϵ = 10 3). While both ALM and Gurobi barrier methods are able to use multiple threads (via BLAS/LAPACK routines and parallelized matrix factorization, respectively), establishing a fair comparison is somewhat ambiguous since Gurobi s procedure is not well documented. Since OSQP s default solver is single-threaded, we limit GRB, G-OA, and ALM to one execution thread in our experiments. PSG s multithreading capabilities are not documented, and we use the default settings. Experiments are conducted in a Linux environment on a Dell workstation with eight physical Intel(R) Xeon(R) W-2145 CPUs @ 3.70GHz with two threads per core and 125GB of RAM. |
| Software Dependencies | Yes | We compare the performance of our semismooth-Newton-based ALM implemented in Julia v1.9.3 (Bezanson et al., 2017) against several other approaches: (i) The interior point methods for solving the nonlinear reformulation (3) by Gurobi v11.0 (Gurobi Optimization, LLC, 2023); (ii) The alternating direction method of multipliers implemented by OSQP v0.6.3 (Stellato et al., 2020); (iii) the Portfolio Safeguard v3.2 (American Optimal Decisions, Inc., 2011); and (iv) an implementation of the outer approximation algorithm based on Royset and Wets (2021, Chapter 6.C) that calls Gurobi as a subproblem solver. |
| Experiment Setup | Yes | The ALM is initialized at the feasible point x0 = 0, µ = 0, and λ = 0, and we find that the method performs similarly for initial points with elements drawn uniformly within the bounds of X. We set the feasibility and optimality tolerance to 10 8. To obtain OSQP solutions with ϵ = 10 3 precision, we set the relative and absolute tolerances to 10 5 and 10 3, respectively. In the PSG suite, we set the precision to 10 8. For PSG, we use the HELI solver, which uses Gurobi as a subproblem solver, for both linear and quadratic problems. For all of the above mentioned methods, we set a time limit of 3,600s. We conduct two experiments. For the first experiment, we predict the τ-th top-quantile for τ {1%, 10%, 50%} using all methods at a precision of ϵ = 10 4. |