PaperlayerView exact revision on arXiv

Source-linked AI summary

Scen-Opt: A Scenario Optimization Toolbox for Data-Driven Convex Programming

Ben Wooding, Simone Garatti, Marco C. Campi, Abolfazl Lavaei

arXiv:2610.07846v1cs.MScs.LGcs.SYeess.SYmath.OC

TL;DR

Data-driven optimization often lacks principled guarantees about how decisions will perform on unseen situations. Scen-Opt combines sampled-data convex programming with scenario-theory guarantees, and its use is demonstrated across physical benchmarks covering its supported program classes and subclasses.

  • Problem

    Data-driven decisions are often tested ad hoc or post hoc, leaving their reliability on unseen situations uncertain.

    Source: §1 · p. 2

  • Method

    Scen-Opt applies scenario theory to sampled-data linear, quadratic, and semidefinite optimization, supporting robust, relaxed, regularized, and combined formulations.

    Source: §1 · pp. 2–3, §3 · p. 9

  • Results

    Scen-Opt is demonstrated on physical benchmarks spanning all three supported program classes and their four subclasses.

    Source: §1 · p. 3

  • Takeaways & Limitations

    The toolbox provides data-driven linear, quadratic, and semidefinite optimization with certified probabilistic performance guarantees using sampled uncertainty realizations.

    Source: §7 · p. 26

    The two-sided risk bound requires consistency and non-degeneracy; if non-degeneracy fails, only the upper bound remains theoretically sound.

    Source: §4.1 · p. 17

Abstract

from arXiv · show

The scenario approach is a well-established statistical framework for data-driven decision-making. In particular, in data-driven optimization, the scenario approach unveils how the problem structure governs out-of-sample generalization, and offers a principled basis for assessing and certifying the reliability of the optimal solution as per constraint satisfaction. Despite its strong theoretical development and wide applicability, no software toolbox has been available to date that enables user-friendly, data-driven convex optimization within the scenario-approach framework. In this paper, we introduce Scen-Opt, an open-source software tool that integrates convex programming with data samples while providing statistical guarantees grounded in scenario theory. Scen-Opt is implemented in Python, supporting data-driven linear, quadratic, and semidefinite programming, and offers a Python-based web application with an intuitive and reactive graphical user interface (GUI) built using modern web technologies. Scen-Opt can be used directly through its online interface or installed locally, accommodating both manual input and data-file uploads (CSV, JSON, TXT, TSV, MAT, Excel, NPY, NPZ, Parquet). Built on a Python backend with a modern JavaScript frontend, Scen-Opt offers a highly user-friendly experience and efficient usability across desktops, laptops, tablets, and mobile devices. In this paper, Scen-Opt is applied to a set of representative benchmarks, demonstrating its practical effectiveness for data-driven convex optimization with guaranteed performance.

1 Introduction

Data-driven decisions often lack principled assurances about performance on unseen situations. Scen-Opt brings scenario-theory guarantees to user-friendly convex optimization and is demonstrated across its supported program classes.

1 Introduction

  • Data-driven decisions are often assessed through ad-hoc or post-hoc testing, leaving their robustness beyond observed samples uncertain.The scenario approach offers a principled way to quantify that out-of-sample risk without assuming a known probability distribution.Source: §1 · p. 2
  • Scenario theory connects problem structure to generalization, with support-list-based guarantees developed for assessing risk after a solution is obtained.The introduction situates this framework within prior work on probabilistic bounds and instance-specific guarantees.Source: §1 · pp. 2, 4
  • Scen-Opt introduces a user-friendly tool that applies scenario theory to data-driven convex optimization with probabilistic guarantees.The paper presents it as the first such open-source tool, including when sampled data are limited.Source: §1 · p. 2
  • The toolbox supports linear, quadratic, and semidefinite programs, each with robust, relaxed, regularized, and combined relaxation-regularization formulations.It uses a Python backend with modern JavaScript frontend technologies.Source: §1 · pp. 2–3
  • Its responsive web application supports access across desktop and mobile devices, while local execution lets users use their own computing resources.The interface also supports manual data entry and data-file uploads.Source: §1 · p. 3
  • The paper demonstrates Scen-Opt on physical benchmarks spanning all three supported program classes and their four subclasses.The benchmarks are presented as evidence of practical effectiveness across the supported scenarios.Source: §1 · p. 3

2 Foundational Concepts in Scenario (Convex) Optimization

Scenario optimization uses sampled constraints to produce decisions whose out-of-sample risk can be bounded. The section defines the problem setup, complexity measure, and conditions behind its risk certificates.

2 Foundational Concepts in Scenario (Convex) Optimization

  • The general formulation allows per-scenario slack variables and objective penalties that trade constraint violations against cost, alongside regularization controlled by a separate weight.The slack penalty weight is ρ, and the regularization weight is τ.Source: §2 · pp. 5–6
  • The framework assumes an optimal solution exists and is unique; relaxation can ensure existence under compactness, while strictly convex regularization with τ > 0 ensures uniqueness when existence holds.Without compactness, a small ρ can make the relaxed problem unbounded.Source: §2 · p. 6
  • Scenario programs use sampled uncertainty realizations as constraints, and the samples are modeled as i.i.d. even though the underlying probability distribution need not be known.The resulting guarantees are distribution-free.Source: §2 · p. 7
  • Risk is the probability that a new scenario makes a decision inappropriate, and its value for the computed solution cannot be directly calculated when the probability measure is unknown.Scenario optimization can bound or estimate this risk without additional samples or knowledge of the underlying distribution.Source: §2 · p. 7
  • A support list is an irreducible subset of scenarios sufficient to reconstruct the solution, and complexity is the smallest cardinality of any support list.Different support lists can have different sizes.Source: §2 · p. 7
  • The risk upper bound is a confidence-dependent function of solution complexity; the two-sided certificate additionally requires consistency and non-degeneracy.The upper bound applies to any Scen-Opt solution, but the lower bound may not be valid when its assumptions fail, and users must judge applicability if no violation is flagged.Source: §2 · pp. 8–9

3 Scenario Optimization Schemes Covered by the Toolbox

Scen-Opt presents scenario-based LP, QP, and SDP schemes, organizing each around a general relaxation-regularization formulation and adaptations to other variants.

3 Scenario Optimization Schemes Covered by the Toolbox

  • Scen-Opt implements scenario optimization for LP, QP, and SDP, introducing each class through its most general relaxation-regularization formulation and deriving other subclasses by adaptation.The four variants are robust, relaxed, regularized, and combined relaxation-regularization.Source: §3 · p. 9

3.1 Linear Programming (LP)

  • Robust LP sets τ = 0, ρ = 0, and ζi = 0; relaxed LP sets τ = 0, while regularized LP sets ρ = 0 and ζi = 0.The robust form is described as the strictest LP variant.Source: §3.1 · p. 10
  • The robust LP example finds the smallest interval enclosing one-dimensional samples, with the interval center and half-width as decision variables.The illustration is identified as a robust LP example.Source: Figure 1 · p. 11, §3.1 · p. 11

3.2 Quadratic Programming (QP)

  • The robust QP example encodes a maximum-margin separating hyperplane for labeled two-dimensional samples; its relaxed form uses slack variables for misclassified points.Scen-Opt supports different regularization norms for QP.Source: §3.2 · pp. 12–13, Figure 2 · p. 13

3.3 Semidefinite Programming (SDP)

  • The inequality-form SDP uses LMIs for hard and soft constraints and generalizes the inequality-based formulations used for LPs and QPs.The program supports robust, relaxed, regularized, and combined relaxation-regularization SDP variants.Source: §3.3 · pp. 14–15

Example 3 (SDP Inequality Form)

  • The LPV example seeks a common quadratic Lyapunov function certifying stability across parameter values, using a relaxed Lyapunov inequality and light quadratic regularization.The objective amounts to maximizing trace(P), with τ = 0 and ρ = 1.Source: Example 3 (SDP Inequality Form) · p. 15, Figure 3 · p. 16

4 Scen-Opt: Implementation Details

Scen-Opt computes scenario-based risk bounds and complexity by validating and reducing support lists. Its implementation also detects degeneracy, interfaces with available solvers, and currently runs sequentially.

4 Scen-Opt: Implementation Details

  • The implementation computes risk and complexity from the scenario count, support-list complexity, and user-selected confidence level.Identifying the support list requires finding violated constraints and an irreducible subset of active constraints that jointly reconstruct the solution.Source: §4 · p. 16

4.1 Risk

  • Risk bounds are computed from the scenario count, calculated complexity, and confidence level; when non-degeneracy fails, only the upper bound remains theoretically sound.The bound algorithm uses the incomplete beta function; users remain responsible for assessing whether a lower bound is applicable when no violation is flagged.Source: §4.1 · pp. 17–18

4.2 Support List Validation

  • TEST_SUPPORT re-solves the problem using candidate scenario constraints and hard constraints, accepting the list when its optimal value matches the full problem.Comparing optimal values keeps the test well posed when the optimizer is non-unique; irreducibility is checked separately.Source: §4.2 · p. 18, §4.1 · p. 18

4.3 Complexity Computation

  • Algorithm 3 screens constraints by dual value, validates the candidates, and prunes them to compute complexity as the returned support-list cardinality.If screening fails to reproduce the optimum, pruning restarts from the full scenario list; in degenerate cases the returned list need not have minimum cardinality, yielding a more conservative risk bound.Source: §4.3 · p. 19

4.4 Solvers

  • CVXPY gives Scen-Opt access to 27 solvers at the time of writing, and the interface filters the solver menu by installed solver and program compatibility.A dedicated subprocess handles licensed commercial solvers; uploaded licenses are held only in RAM and are not persisted on disk.Source: §4.4 · p. 21

4.5 Parallelism

  • Scen-Opt currently runs sequentially; pruning iterations depend on earlier removal decisions, while independent solves across different ρ and τ values are a future parallelization opportunity.Parallel solves need separate problem copies to prevent overwritten variables from causing incorrect support lists and under-counted complexity, which could make risk certificates too optimistic.Source: §4.5 · p. 21

5 Web Interface

The web interface supports configuring and running scenario programs through manual or file-based inputs. It presents results in tables and interactive plots for exploring risk and cost across parameter settings.

Interface and inputs

  • The interface adapts its fields to the selected program and formulation, with dimension controls, matrix entry or upload, tooltips, and full-program upload options.Scenario-dependent inputs can be entered symbolically and paired with scenario rows, or supplied as pre-evaluated numerical constraint blocks; both modes solve the same program and return identical results.Source: §5 · pp. 22–23

File workflows

  • Scenario data and programs can be uploaded in supported file formats, and uploaded programs can be downloaded and re-uploaded for repeated analyses.Supported scenario-data formats include CSV, JSON, MAT, TXT, TSV, Excel, NPY, NPZ, and Parquet.Source: §5 · pp. 23, 26

Results display

  • The results table reports optimal cost and solution, risk bounds, degeneracy, complexity, constraint count, solve and risk-computation times, and numerical issues.When degeneracy is flagged, the lower risk bound is withheld; multiple ρ and τ settings add a column for each trial and report an overall confidence bound.Source: Figure 5 · p. 24, §5 · p. 25

Graphical summaries

  • Interactive Pareto-front slices plot risk bounds and cost against one varied parameter while the user fixes the other, ρ or τ.The plots support exploration of the risk–objective trade-off across relaxation and regularization settings.Source: §5 · pp. 25–26, Figure 6 · p. 25

6 Benchmarking

The evaluation uses twelve case studies spanning LP, QP, and SDP benchmarks, with variable dimensions from 2 to 120 and uncertainty dimensions up to 48.

6 Benchmarking

  • Twelve case studies cover LP, QP, and SDP benchmarks, with decision-variable dimensions from d = 2 to d = 120 and uncertainty dimensions up to q = 48.Solve times were measured on a desktop with an Intel Core Ultra 9 285K and 64 GB RAM, using MOSEK; degeneracy was detected for Growth Bound and Radiation Therapy, whose lower risk bounds were marked N/A.Source: §6 · p. 26

7 Conclusions and Future Work

Scen-Opt brings scenario-theory guarantees to practical data-driven convex optimization and is evaluated on representative benchmarks. The inventory example illustrates how its scenario constraints shape produce orders and quantify risk.

7 Conclusions and Future Work

  • Scen-Opt is an open-source tool for sampled-data linear, quadratic, and semidefinite programs with probabilistic guarantees and web or local use.The paper identifies extending the framework to nonconvex scenario optimization as future work.Source: §7 · p. 26

A Case Studies

  • Twelve benchmark case studies are grouped by program type, with solve times measured on an Intel Core Ultra 9 285K desktop.The table notes that degeneracy can leave the lower risk bound uncertified.Source: Table 1 · p. 27, A Case Studies · p. 29

A.1.1 Inventory Management

  • The produce LP orders five perishables under a $12,000 budget and 800-ft³ warehouse limit, with scenario constraints for demand and capacity.The produce data are synthetic, calibrated to real data and USDA Terminal Market Prices.Source: §A.1.1 · pp. 29–30, Table 2 · p. 29
  • 6.7% is the maximum reported chance that a new sample nullifies the inventory LP's optimal cost; expected stockout loss is $66.20, about 0.5% of the ordering budget.The manager spends the full $12,000 budget while accepting lettuce shortfalls in favor of higher-yield avocados.Source: §A.1.1 · p. 30

A.1.2 Power Dispatch

The power-dispatch example schedules thermal generation against uncertain wind and solar, while the portfolio and interval examples also report scenario-based risk bounds. Reported outcomes include an approximately 55% likelihood of a correct dispatch result on unseen data, 1.20% daily CVaR loss, and a 0.209 upper risk bound for the interval problem.

A.1.2 Power Dispatch

  • An approximately 55% likelihood of a correct result on unseen data suggests more samples are likely needed for power dispatch.The LP schedules three thermal generators over 24 hours, balancing demand against uncertain wind and solar; it uses 150 scenarios.Source: §A.1.2 · pp. 31–32

A.1.3 Portfolio Management - Conditional Value at Risk (CVaR)

  • 1.20% daily loss is the reported CVaR(95%), with equities at the 30% floor and fixed income at its 25% minimum.The LP uses historical market scenarios and per-asset position limits; alternatives GLD and VNQ absorb allocation not consumed by regulatory minimums.Source: §A.1.3 · p. 32, Figure 9 · p. 33

A.1.4 Smallest Enclosing Interval

  • 0.209 is the upper risk bound reported for the 1.2-second robust LP finding the smallest interval enclosing 100 sampled points.The solution consists of the interval center and half-width.Source: §A.1.4 · pp. 32–33, Figure 10 · p. 33

A.1.5 Data-Driven Growth Bound for Finite Abstraction

Scen-Opt uses a sampled-data linear program to compute a growth bound for constructing a finite abstraction. In this example, degeneracy prevents a lower risk bound from being certified.

A.1.5 Data-Driven Growth Bound for Finite Abstraction

  • The growth bound is used in building a finite abstraction of an unknown deterministic system.Finite abstractions group continuous states into grid cells represented by a single point.Source: §A.1.5 · p. 33
  • The example uses 3,127 sampled trajectories from a three-dimensional hypercube under fixed input u = (0.3, 0.3).The growth bound is computed by an LP; each scenario concatenates the absolute deviations of a trajectory and its successor from the center and its successor.Source: §A.1.5 · pp. 33–34
  • Using the pre-selected bias γ = 0.067 and confidence parameter β = 10−6, the resulting growth bound is computed.Solving the optimization yields a rounded solution.Source: §A.1.5 · p. 34
  • The growth-bound solution has complexity k = 6, but degeneracy leaves only the upper risk bound, ε = 0.0103, reportable.Although essentially all 3,127 scenario constraints are numerically active, only six are needed to reproduce the solution, so the active constraints do not form a support list.Source: §A.1.5 · p. 34

A.2.1 Radiation Therapy - Prostate Brachytherapy

Scen-Opt is applied to prostate brachytherapy planning and robot motion planning under scenario-dependent uncertainty. The examples report feasible plans and risk bounds for new random scenarios.

A.2.1 Radiation Therapy - Prostate Brachytherapy

  • The brachytherapy QP models 50 dwell-position intensities and 100 representative voxels, with 200 synthetic scenarios for three-direction catheter shifts.The dose-influence data are subsampled from a patient dataset; synthetic scenarios combine a five-level grid with 75 truncated-Gaussian samples.Source: §A.2.1 · p. 35
  • The brachytherapy objective maximizes target dose while using ℓ2 regularization to encourage smooth dwell-time profiles, with ρ = 0 requiring constraints to hold without slack relaxation.Most dwell channels operate near their upper intensity bound, while positions far from the target or near OARs are suppressed.Source: §A.2.1 · pp. 35–36
  • The brachytherapy plan achieves tumor D95 = 145.12 Gy, with maximum rectum and bladder doses of 84.6 Gy and 101.6 Gy, respectively.These values are below the stated minimum tumor dose of 137.75 Gy and OAR limits of 100 Gy and 120 Gy.Source: §A.2.1 · p. 35, Figure 11 · p. 35
  • For catheter-placement uncertainty, the upper risk bound is εu = 0.1414 at 99.9999% confidence, guaranteeing at least 85.9% probability of satisfying dose constraints for a new random placement.Degeneracy is detected: 20 constraints are active, but only five form the support list, so no lower risk bound is certified.Source: §A.2.1 · p. 36

A.2.2 Robot Motion Planning

  • The robot-planning QP models a 20-timestep double-integrator path around an uncertain wall, with safety clearance of 0.3 m and 1,500 scenario constraints.The objective trades off control effort and position tracking; the model also includes dynamics, control, workspace, initial-state, and goal constraints.Source: §A.2.2 · p. 36
  • With N = 500 scenarios, the solver returns a smooth arc trajectory of path length 9.79 m and minimum wall clearance 0.19 m; at β = 10−6, violation risk is at most 4% with 99.9999% confidence.The risk bounds are [0.0000, 0.040]. No degeneracy is detected, and there is no regularization or relaxation (τ = 0 and ρ = 0).Source: §A.2.2 · p. 36

A.2.3 Minimal Iris Classification

The section demonstrates scenario-based classification with a minimal iris feature set and covariance domination using wine data. Both examples report risk bounds for new samples or subsamples.

A.2.3 Minimal Iris Classification

  • The iris task separates Setosa from the other two species using petal length and petal width, with a linear hard-margin SVM.The separating hyperplane maximizes the margin between the two classes.Source: §A.2.3 · pp. 36–37
  • For iris classification, N = 150 and complexity k = 2 yield risk bounds ε = 0 and ε = 0.144 at β = 10−6.The resulting classifier is 3.79 = 1.29x1 + 0.82x2.Source: §A.2.3 · p. 37, Figure 13 · p. 37

A.3.1 Robust Covariance Estimation

  • The minimum-trace positive semidefinite covariance matrix is designed to dominate subsample covariances drawn from the Wine dataset.The example uses five standardized features and the 178 wines as scenarios; the diagonal errors are positive, while off-diagonal errors are smaller and mixed in sign.Source: §A.3.1 · p. 38
  • For wine covariance estimation, k = 7 yields risk bounds [εℓ, εu] = [0.0000, 0.178] at 99.9999% confidence.The estimated covariance is guaranteed to dominate a new random 50-wine subsample with probability at least 82.2%; the SDP solves in 2.1 seconds.Source: §A.3.1 · p. 38, Figure 14 · p. 38

A.3.2 Minimum Enclosing Ellipsoid - Breast Cancer Wisconsin

The examples apply semidefinite scenario programs to enclose breast-cancer data and certify stability of an LPV system. They report out-of-sample risk bounds for both applications.

A.3.2 Minimum Enclosing Ellipsoid - Breast Cancer Wisconsin

  • The breast-cancer SDP seeks the tightest ellipsoid containing the sampled observations, using 569 scenarios drawn from five standardized features.The shape matrix is constrained positive definite and the objective maximizes its trace.Source: §A.3.2 · p. 39
  • For the breast-cancer ellipsoid, k = 5 gives risk bounds [εℓ, εu] = [0.000, 0.052] at 99.9999% confidence, guaranteeing at least 94.8% containment for a new random data point.All 569 sampled points are contained; the estimated shape matrix has trace 44.59 and a single non-negligible eigenvalue, consistent with the five selected features’ high correlation.Source: §A.3.2 · p. 39

A.3.3 LPV Stability

  • The LPV stability program seeks a common quadratic Lyapunov function V(x) = x⊤Px with P ≻ 0 that certifies stability across parameter values.The SDP uses three decision variables for the symmetric 2 × 2 matrix P and maximizes its trace with light quadratic regularization.Source: §A.3.3 · p. 40
  • For LPV stability, Scen-Opt reports complexity k = 1 and risk bounds [0.0, 0.1858] at 99.9999% confidence, with no degeneracy detected.One scenario constraint supports the solution, corresponding to the smallest sampled δ ≈ −0.19; the SDP solves in 1.7 seconds.Source: §A.3.3 · p. 40

A.3.4 Quadratic Stability - Coupled Oscillator

The coupled-oscillator example uses a scenario-based SDP to assess quadratic stability, with one supporting scenario and risk bounds of [0, 0.0400] at 99.9999% confidence. The examples appendix also shows how to load complete problems from JSON program files.

A.3.4 Quadratic Stability - Coupled Oscillator

  • The example maps the coupled oscillator to an SDP with a six-entry symmetric 3×3 Lyapunov matrix and scenario-dependent constraint matrices.The objective minimizes trace(P) with no regularization.Source: §A.3.4 · p. 41
  • With k = 1 and no degeneracy, the risk bounds are [0, 0.0400] at 99.9999% confidence.The SDP uses N = 500 scenarios sampled uniformly over [−1, 1]2.Source: §A.3.4 · p. 41
  • One scenario constraint supports the solution, near the (δ1, δ2) = (1, 1) corner where the stability margin is tightest.The Lyapunov matrix is not a scalar multiple of the identity, reflecting the need for additional weight on the second state to certify stability across the parameter space.Source: §A.3.4 · p. 41

B JSON Program Files for the Illustrative Examples

  • A complete example problem can be loaded from a JSON program file, while scenarios are uploaded separately to reproduce the appendix results.The file keys encode the program class, input mode, matrices, dimensions, and confidence; matrix entries may be expressions in scenario components.Source: B JSON Program Files for the… · pp. 41–42

C Detailed Function Implementation

The implementation parses scenario-dependent expressions into solver inputs, returns optimization and support information, quantifies risk, and validates candidate support lists by re-solving reduced problems.

C Detailed Function Implementation

  • Parsing helpers convert user-supplied expressions into evaluable matrix or tensor functions, and all three solvers call get_support() after solving.Static helper counterparts generate constant matrices and tensors.Source: C Detailed Function Implementation · p. 45

Parameters:

  • Solver inputs include scenario rows, callable constraint data, objective and regularization weights, and optional slack variables with a penalty.The norm order p may be any p ≥ 1, with default 2, or may be specified as "inf" or "fro".Source: Parameters · p. 45

Return values:

  • Solver outputs include the optimizer, objective value, scenario count, support-list complexity, scenario constraints, and a degeneracy flag.LP and QP optimizers are column vectors; the SDP optimizer is a one-dimensional array.Source: Return values · p. 45, §C.2 · p. 46

Exceptions and Error Checking:

C.2 solve_qp

  • The QP solver accepts a symmetric positive-semidefinite quadratic cost matrix Q alongside the shared objective and regularization parameters.Its slack variables are added when requested, or by default when ρ is nonzero.Source: §C.2 · p. 46

C.3 solve_sdp

  • The SDP solver takes scenario-dependent F_d matrices and optional hard-constraint matrices E, with the same regularization and slack options.The SDP optimizer is returned as a one-dimensional array.Source: §C.3 · p. 47

C.4 quantify_risk

  • Risk bounds are computed from support-list complexity k, scenario count N, and confidence β; when k = N, the upper bound is set to 1.0.The bounds use the regularized incomplete beta function and binary search with convergence tolerance 1e-10.Source: §C.4 · p. 48, Implementation details · p. 48

C.5 get_support

  • Candidate support lists are validated by re-solving with those constraints plus always-enforced hard constraints and checking whether the optimal value matches.The final support comprises violated or active scenario constraints whose removal changes the optimal value; reduction may flag degeneracy.Source: §C.5 · pp. 48–49
Loading 2610.07846v1…