Source-linked AI summary
CVXR: An R Package for Disciplined Convex Optimization
Anqi Fu, Balasubramanian Narasimhan, Stephen Boyd
TL;DR
CVXR addresses the difficulty of expressing and solving diverse convex optimization models in a solver-compatible form. It provides an R-based object-oriented modeling language with DCP verification and conic conversion, yielding flexible formulation and prototyping across applications. Its scope is bounded by DCP compliance and modeling assumptions such as knot choices for saturating splines.
Problem
Users need a flexible way to formulate diverse convex optimization problems in R without manually restructuring them into restrictive solver formats.
Method
CVXR combines R-based mathematical modeling with disciplined convex programming, graph implementations, parameters, and solver conversion to standard conic form.
Results
CVXR supports flexible formulation, modification, and solution of a broad range of convex optimization problems, including models and constraints that may require specialized methods elsewhere.
Takeaways & Limitations
CVXR is positioned as an intuitive, flexible tool for prototyping new statistical models and integrating convex optimization into larger R analyses.
Takeaways & Limitations
CVXR rejects convex formulations that violate DCP rules, and its saturating-spline construction assumes knots at the minimum and maximum observed x values.
Abstract
from arXiv · showhide
CVXR is an R package that provides an object-oriented modeling language for convex optimization, similar to CVX, CVXPY, YALMIP, and Convex.jl. It allows the user to formulate convex optimization problems in a natural mathematical syntax rather than the restrictive form required by most solvers. The user specifies an objective and set of constraints by combining constants, variables, and parameters using a library of functions with known mathematical properties. CVXR then applies signed disciplined convex programming (DCP) to verify the problem's convexity. Once verified, the problem is converted into standard conic form using graph implementations and passed to a cone solver such as ECOS or SCS. We demonstrate CVXR's modeling framework with several applications.
1. Introduction
CVXR provides an R-based language for expressing and solving a broad class of convex optimization problems, including statistical models that may require specialized solvers. Its main advantage is flexible, intuitive prototyping that integrates with R workflows.
- CVXR solves a broad class of convex optimization problems, including least squares, ridge, lasso, isotonic, Huber, and support vector regression models.
- Users formulate objectives and constraints with mathematically intuitive R syntax, while CVXR converts the problem into solver-ready conic form.The solve call converts the problem into a second-order cone program and sends it to a solver.
- Adding constraints lets users extend ordinary least squares to isotonic regression without finding a separate specialized solver or writing one.The monotonicity constraint is β_j ≤ β_j+1 for j = 1, . . . , n − 1.
- CVXR’s flexibility supports rapid modification and re-solving, native R integration, and resampling workflows such as the bootstrap.
- CVXR automatically analyzes objective and constraint types, unlike systems that require users to identify each type explicitly.
2. Disciplined convex optimization
Disciplined convex programming lets CVXR verify convexity from known properties of basic functions and their compositions. The resulting models can then be automatically transformed into standard form for generic convex solvers.
- CVXR allows users to specify problems in natural mathematical syntax and automatically converts them into the standard form required by generic convex solvers.
- CVXR uses a library of atoms with known curvature, monotonicity, and sign properties to define and analyze optimization problems.
- The DCP composition rule establishes convexity when an outer convex function receives compatible convex or concave arguments according to its monotonicity.
- Users must follow DCP rules when combining atoms to ensure the resulting problem is convex by construction.
- The atom library supports modeling a wide variety of sophisticated optimization problems, including examples that are cumbersome to prototype with other R packages.
3. Examples
CVXR expresses a broad range of convex statistical models with reusable objectives, losses, penalties, and constraints. The examples show how its modeling flexibility supports robust regression, classification, sparse estimation, splines, distribution estimation, and survey calibration.
- Regression: Huber regression reduces the influence of large residuals because its penalty grows linearly rather than quadratically beyond threshold M.The Huber loss matches least squares for small residuals and is more forgiving of outliers.
- Regression: CVXR supports quantile regression by allowing users to define a tilted l1 loss with a user-specified quantile parameter.The custom loss can be integrated into the problem definition and reused with the existing regression variable.
- Regularization and classification: Elastic net regularization combines l1 and squared l2 penalties, encompassing lasso and ridge regression while remaining modular across models.The same regularization code can be incorporated into Huber regression by changing the loss definition.
- Regularization and classification: Adding a constraint to logistic regression pulls the customer-age and customer-income coefficient estimates toward each other.The example constrains the nine non-intercept coefficients to the unit interval and adds a relation between the two covariate coefficients.
- Matrix estimation: For sparse inverse covariance estimation, α = 4 recovers the true 26% proportion of nonzero entries, while larger α produces denser estimates and α = 1 leaves most off-diagonal entries zero.The example uses m = 1000 observations and n = 10 variables.
- Saturating splines: On the bone-density data, increasing λ makes saturating splines flatter outside their boundaries, while Huber loss remains fairly smooth and follows the original shape with outliers.The squared-error fit is biased upward when 50 random outliers are added.
- Distribution estimation and calibration: CVXR’s log-concave estimator matches the results of Dümbgen and Rufibach’s approach exactly, and its survey-calibration results match those from the survey package.The survey example uses calibration weights for California Academic Performance Index data.
Nearly-isotonic and nearly-convex fits
CVXR lets users express diverse convex optimization problems in natural R syntax, then adapt models with penalties, constraints, and resampling. Examples cover nearly-isotonic and nearly-convex fitting, covariance estimation, catenary modeling, portfolio optimization, and Kelly betting.
- Nearly-isotonic and nearly-convex fits: The nearly-isotonic global-warming fit with λ = 0.44 follows the data but becomes choppy where the trend is steep, using 95% confidence bands from R = 400 bootstrap samples.The nearly-convex fit smooths the jagged staircase pattern and uses R = 200 bootstrap samples for its 95% confidence bands.
- Nearly-isotonic and nearly-convex fits: Nearly-isotonic fitting uses a nonnegative first-difference penalty, while nearly-convex fitting replaces it with an approximation to the second derivative.The nearly-convex formulation requires changing only the penalty line in the fitting function.
- Worst-case covariance: CVXR handles semidefinite covariance optimization with sign and bound constraints, and the formulation can be generalized to arbitrary convex constraints and penalized slack variables.The covariance problem models worst-case portfolio risk when only limited covariance information is available.
- Catenary problem: Adding a ground constraint to the catenary model requires changing the endpoint and imposing y ≥ g, producing a chain bounded below by the ground.The modified example uses m = 101 links and h = 0.02.
- Portfolio optimization: In portfolio optimization, increasing γ produces more diverse portfolios with lower risk and lower return, while convex extensions such as transaction costs and betting restrictions remain easy to incorporate.The risk-return curve is shown for n = 10 assets, with single-asset portfolios marked in red.
4. Implementation
CVXR represents optimization problems as structured expressions, verifies disciplined convexity, canonicalizes compliant problems into cone programs, and sends them to compatible solvers. Its flexibility includes extensible atoms, parameterized problems, and warm starts, but translation overhead can dominate runtime.
- Representation: CVXR builds expression trees from S4 objects, with operators as roots and variables, constants, or other expressions as leaves.These trees encapsulate objectives and constraints as users compose expressions.
- Canonicalization: When solve is called, CVXR recursively checks signs and curvature, then transforms compliant problems into equivalent cone programs through graph implementations.The resulting solver data are generated through the CVXcanon C++ library.
- Solver interfaces: CVXR interfaces with ECOS for accurate small and medium-sized solutions and SCS for larger problems and semidefinite constraints.SCS is a first-order solver and can be slow for poorly conditioned problems or problems with a f...
- Extensibility: Users can extend CVXR by defining new S4 atom classes, specifying their DCP properties, and providing graph implementations as linear operators.The absolute value function is presented as an example of this extension process.
- Speed considerations: CVXR is usually slower than direct solver calls because it performs problem translation and constructs solver matrices from the DCP formulation.The implementation stores data in sparse matrices, but R's sparse-matrix restrictions remain relevant.
- Speed considerations: Canonicalization and solver-data construction dominate computation time for complex expressions involving indexing, while vectorized operations provide substantial speed improvements.This overhead is especially important when expressions index individual matrix or vector elements.
- Speed considerations: 7.153 seconds versus 0.763 seconds: warm-starting a second lasso solve reduced runtime on a Macintosh laptop for X ∈R2000×500 and y ∈R2000.The two solves used different values of the penalization parameter λ.
5. Conclusion
CVXR provides a flexible, object-oriented language for formulating, modifying, and solving many convex optimization problems. The paper concludes that its intuitive syntax makes it especially useful for prototyping models without custom R code, despite faster alternatives on some problem subsets.
- Conclusion: CVXR lets users formulate, modify, and solve a broad range of convex optimization problems through an object-oriented language.The conclusion emphasizes flexibility and simple, intuitive syntax.
- Conclusion: CVXR is positioned as an ideal prototyping tool for new models when custom R code does not exist.The paper notes that other R packages may be faster for subsets of these problems.
A. Expressions and functions
CVXR uses function information and disciplined-convex-programming tools to assign signs and curvature to expressions involving symmetric matrices. The notation distinguishes positive and negative semidefinite matrix sets.
- Expression properties: CVXR uses function information and DCP tools to assign each expression a sign and curvature.These properties support the package's convexity analysis.
- Matrix notation: S_n denotes the set of symmetric matrices, while S_n^+ and S_n^- refer to positive semidefinite and negative semidefinite matrices.The passage introduces these matrix-domain conventions for later expressions.
A.1. Operators
CVXR treats common R operators as functions with disciplined affine rules. Matrix multiplication and division are affine only under specified constant-expression restrictions.
- Operators: The operators + and - are affine functions in CVXR.Multiplication is also affine only when one expression is constant, and division requires a scalar constant denominator.
- Operators: Transpose is affine, and expr^p is interpreted as the power(expr, p) function.These constructs are incorporated into CVXR's function-property system.
A.2. Indexing and slicing
CVXR supports indexing, slicing, and advanced index specifications for non-scalar expressions while preserving R-like semantics and column-vector outputs where appropriate.
- A.2. Indexing and slicing: Non-scalar expressions support two-dimensional indexing with expr[i, j], while vector expressions allow a one-index shorthand.For column vectors, expr[i] means expr[i, 1]; for row vectors, it means expr[1, i].
- A.2. Indexing and slicing: Indexing is affine, allowing indexed expressions to participate in affine modeling operations.
- A.2. Indexing and slicing: Standard R slicing selects contiguous rows or columns and returns a vector.For example, expr[i:j, r] selects rows i through j of column r.
- A.2. Indexing and slicing: CVXR supports lists of indices and boolean arrays with semantics matching R.
- A.2. Indexing and slicing: Whenever R would return a numeric vector, CVXR returns a column vector instead.
A.3. Scalar functions
CVXR supplies scalar functions for scalar, vector, and matrix expressions, including reductions, norms, extrema, and functions characterized by domain, sign, curvature, and monotonicity.
- A.3. Scalar functions: CVXR scalar functions accept scalars, vectors, or matrices and return a scalar.
- A.3. Scalar functions: cvxr_norm uses the Euclidean norm for vectors and the spectral norm for matrices by default.Matrix expressions can instead use the Frobenius or nuclear norm.
- A.3. Scalar functions: The nuclear norm of a matrix is also defined as the sum of its singular values.
- A.3. Scalar functions: max_entries and min_entries return the largest and smallest entry in one expression, unlike max_elemwise and min_elemwise.The elementwise functions return the maximum or minimum of a list of scalar expressions.
- A.3. Scalar functions: sum_entries sums all entries in one expression, whereas base R sum combines a list of expressions.The supplied example uses sum(expr1, expr2, expr3) for three expressions.
- A.3. Scalar functions: Several scalar functions operate along an axis, with axis = 1 applying across rows and axis = 2 applying across columns.For a matrix, the corresponding outputs have dimensions m by 1 and 1 by n.
- A.3. Scalar functions: The scalar-function tables characterize functions by meaning, domain, sign, curvature, and monotonicity.The supplied table excerpts include affine, convex, and concave function entries involving matrix expressions.
- A.3. Scalar functions: The default axis = NA treats a matrix as one long vector, except for cumsum_axis, which rejects axis = NA.CVXR aligns this behavior with base::apply.
A.4. Elementwise functions
CVXR’s elementwise functions preserve argument dimensions and apply operations independently to corresponding entries, with scalar promotion and dimension compatibility requirements.
- A.4. Elementwise functions: Elementwise functions act on each argument element and preserve the expression’s dimensions.For a 5 by 4 matrix X, abs(X) is a 5 by 4 matrix expression.
- A.4. Elementwise functions: Indexing an elementwise result is equivalent to applying the function to the indexed input.For example, abs(X)[1, 2] equals abs(X[1, 2]).
- A.4. Elementwise functions: Multi-argument elementwise functions operate on corresponding entries of their arguments.For example, max_elemwise(X, Y)[2, 1] equals max_elemwise(X[2, 1], Y[2, 1]).
- A.4. Elementwise functions: Multi-argument elementwise operations require equal dimensions or scalar arguments, which are promoted appropriately.
A.5. Vector and matrix functions
CVXR provides vector and matrix functions that return vector or matrix expressions, including block construction, flattening, and column-major reshaping.
- A.5. Vector and matrix functions: Vector and matrix functions accept scalars, vectors, or matrices and return a vector or matrix.
- A.5. Vector and matrix functions: bmat constructs a block matrix by stacking each inner list horizontally and the resulting blocks vertically.
- A.5. Vector and matrix functions: vec(X) flattens X into a vector in column-major order.
- A.5. Vector and matrix functions: reshape_expr(X, c(m1, n1)) casts X into an m1 by n1 matrix using column-major order for both reading and storage.