DiscoverDCP: A Data-Driven Approach for Construction of Disciplined Convex Programs via Symbolic Regression

AI summary

Overview

Research area: Machine learning and convex optimization — specifically, the intersection of symbolic regression (automated discovery of mathematical formulas from data) and Disciplined Convex Programming (DCP).

Technical level: Intermediate. Readers should be comfortable with convex functions, convex optimization basics, and the general idea of genetic/evolutionary search. No deep proof machinery is required to follow the paper.

Scope: The paper proposes and evaluates a framework that restricts a symbolic regression search to DCP-compliant operations so that every discovered model expression is globally convex by construction.

What This Paper Is About

Convex optimization is attractive because convex problems are tractable and have global optimality guarantees, but practitioners usually have to assume a simple convex shape up front — most often a quadratic — which limits how well the model can capture real system behavior. The paper asks whether a machine can instead discover a convex expression directly from data, in a form a human can read and a convex solver can accept. DiscoverDCP answers this by combining symbolic regression with the composition rules of Disciplined Convex Programming, so convexity is guaranteed during the search rather than verified afterward.

Key Contributions

1. DiscoverDCP framework: A method that restricts the symbolic regression search space to DCP-compliant operations, guaranteeing global convexity of learned models by construction.
2. Elimination of post-hoc convexity verification: The authors argue this removes the need for intractable post-hoc convexity checks (verifying general convexity is described as NP-hard, whereas determining whether a function is DCP is described as algorithmically straightforward), while offering greater interpretability than neural network-based approaches.
3. Synthetic demonstration against a quadratic baseline: Via synthetic experiments, the method is shown to better recover exact convex formulations in cases where traditional quadratic baselines fail.
4. A complexity-versus-parameter-count benchmark: The paper notes the number of unique parameters in a positive semidefinite (PSD) quadratic, P_quad = n(n+1)/2 + n + 1, and proposes using it as a benchmark: a symbolic model that achieves lower loss than the quadratic baseline with a lower complexity score is a superior representation of the convex system.

The authors state that, to the best of their knowledge, this is the first direct integration of symbolic regression with Disciplined Convex Programming rulesets.

Main Findings

• Quadratic baselines miss sharp nonlinear structure: On a hidden 1D model containing nested max and exponential terms, the paper reports that the PSD quadratic fit fails to capture the sharp non-linearities introduced by the max operator, while DiscoverDCP finds a highly accurate model.
• Ground truth and baseline fit for the 1D experiment: The ground truth was y = exp(x + max(x, −5x) + x²) + 4x, and the PSD quadratic fit was approximately y ≈ 61.6x² − 20.4x − 4.9.
• Parsimonious DiscoverDCP solution: A low-complexity approximation found by DiscoverDCP was y = e^(3.2x) + e^(−4.9x).
• Higher-complexity DiscoverDCP solution: A higher-complexity model recovered a structure very similar to the ground truth, capturing the nested non-linearities, while maintaining convexity guarantees throughout.
• Convexity is not the bottleneck — flexibility is: The paper states that while the quadratic model is convex, it lacks the flexibility to model exponential growth and switching behavior simultaneously.
• Complexity can favor the symbolic model in high dimensions: Because a PSD quadratic has n(n+1)/2 + n + 1 unique parameters, the paper argues that in high-dimensional systems a quadratic model may have a higher parameter count than a sparse symbolic expression discovered by DiscoverDCP.
• Data setting: Experiments used synthetic datasets with known convex ground truths. Input points were sampled uniformly from a polytope domain defined by Ax ≤ b, with Gaussian white noise added to the outputs.
• No quantitative error metrics are reported: The paper presents figures and example expressions rather than tabulated loss or error numbers.

Methodology in Plain English

The approach has two moving parts.

First, the set of allowed building blocks is restricted to operations that DCP recognizes as convexity-preserving. The binary operators used are addition (unrestricted), multiplication (restricted to constant scaling or specific convex-preserving forms), and max. The unary operators used are exp, square, and absolute value. Nesting rules are also enforced — for example, a convex function can only be composed with a convex, non-decreasing function and remain convex.

Second, the search itself is run with PySR, which represents candidate formulas as trees and evolves them. The key modification is a constraint check inserted at the mutation step of the genetic algorithm. If a mutation produces a tree that breaks the DCP rules — such as subtracting a convex function, or composing a convex function into a non-monotone function — the candidate is either assigned an infinite loss or rejected outright. This keeps the entire population of candidate models strictly inside the set of DCP-compliant functions. A complexity measure equal to the number of nodes in the tree is used to penalize overly convoluted expressions and preserve interpretability.

For evaluation, the authors generated synthetic data from known convex functions, sampled inputs from a polytope with added Gaussian noise, and compared DiscoverDCP against a standard quadratic baseline whose matrix A was constrained to be positive semidefinite using CVXPY.

Why This Matters

Impact on research. The paper offers a different route to convex modeling: instead of fitting a fixed parametric family and hoping it is expressive enough, or training a black-box convex neural network and hoping it is interpretable, it searches for a readable algebraic expression that is convex by construction. It also positions the DCP rule set as a search-space constraint for symbolic regression, which the authors present as a new combination.

Real-world applications (as framed by the paper, not evaluated in it):

• Safety-critical control, where a model that is provably convex supports reliable optimization.
• Engineering system identification, where interpretable algebraic models of dynamics are preferred over opaque ones.
• Statistics and machine learning, where convex objectives and constraints underpin tractable learning problems.
• Optimization modeling workflows built on DCP-compatible tools such as CVXPY, since discovered expressions are intended to slot directly into such solvers.

Industry relevance. The stated appeal is practical: interpretable, verifiable, flexible convex models. The paper contrasts this with Input Convex Neural Networks, which enforce convexity through weight and activation constraints but remain "black box" models that are difficult to interpret mathematically. The released code at https://github.com/svemyh/DiscoverDCP lowers the barrier to trying the method.

Future Directions

• Scaling to high-dimensional systems: The parameter-count formula for PSD quadratics is presented as a benchmark, but the experiments shown are on 1D synthetic data; whether the advantage holds in higher dimensions is an open question the paper does not resolve.
• Evaluation on real data and more benchmarks: The reported experiments are synthetic with known convex ground truths; performance on messy, real-world system identification tasks is not reported.
• Head-to-head comparison with convex neural network approaches: The paper contrasts DiscoverDCP with ICNNs conceptually but reports no experimental comparison.
• Managing the accuracy-complexity trade-off systematically: The paper describes the trade-off and shows both a parsimonious and a high-complexity solution, but does not report a procedure for selecting among them or quantify where the trade-off turns.

Target Audience

Researchers and practitioners working on convex optimization, system identification, and interpretable machine learning — particularly those who already use DCP-based modeling tools such as CVXPY and want models that go beyond linear and quadratic forms. It is also relevant to anyone applying symbolic regression who needs structural guarantees such as convexity, and to control engineers who need models that are both interpretable and provably convex.

Authors’ abstract

We propose DiscoverDCP, a data-driven framework that integrates symbolic regression with the rule sets of Disciplined Convex Programming (DCP) to perform system identification. By enforcing that all discovered candidate model expressions adhere to DCP composition rules, we ensure that the output expressions are globally convex by construction, circumventing the computationally intractable process of post-hoc convexity verification. This approach allows for the discovery of convex surrogates that exhibit more relaxed and accurate functional forms than traditional fixed-parameter convex expressions (e.g., quadratic functions). The proposed method produces interpretable, verifiable, and flexible convex models suitable for safety-critical control and optimization tasks.