Package {sparsediff}

sparsediff: R interface to the SparseDiffEngine differentiation backend

Description

R bindings to the 'SparseDiffEngine' C library — the sparse Jacobian and Hessian differentiation backend used by 'CVXPY' for its Disciplined Nonlinear Programming (DNLP) extension. This package is the R analog of the 'sparsediffpy' Python package and wraps the same C library (pinned at the upstream v0.6.1 release).

Correspondence with 'sparsediffpy'

Every 'sparsediffpy' 0.6.1 function has an sd_* counterpart that calls the same engine routine with the same arguments in the same order. Names map make_<atom> to sd_<atom> and problem_<step> to sd_<step> (for example make_exp to sd_exp, problem_init_jacobian to sd_init_jacobian), with these exceptions:

• make_multiply: sd_elementwise_mult; make_param_scalar_mult / make_param_vector_mult: sd_scalar_mult / sd_vector_mult.

• make_left_matmul, make_right_matmul and make_quad_form, which take a format string, are split by format: "sparse" is sd_left_matmul, sd_right_matmul, sd_quad_form; "dense" is sd_left_matmul_dense, sd_right_matmul_dense, sd_quad_form_dense.

• make_rel_entr: sd_rel_entr, which dispatches on operand size the same way; the two scalar cases are also available directly as sd_rel_entr_first_scalar and sd_rel_entr_second_scalar.

• get_jacobian_sparsity_coo, problem_eval_jacobian_vals: sd_jacobian_sparsity, sd_jacobian_values; problem_init_hessian_coo_lower_triangular, get_problem_hessian_sparsity_coo, problem_eval_hessian_vals_coo: sd_init_hessian_coo, sd_hessian_sparsity, sd_hessian_values; get_jacobian, get_hessian, get_expr_dimensions, get_expr_size: sd_get_jacobian, sd_get_hessian, sd_get_expr_dimensions, sd_get_expr_size.

• Arguments that are optional in 'sparsediffpy' are required here (R stubs have no defaults): verbose of sd_problem, values of sd_parameter (the engine requires it anyway), and n_vars of sd_hstack / sd_vstack, which 'sparsediffpy' takes from the first argument.

• The parameter argument of the sparse matrix products is not exposed: the engine aborts on it.

Indices are 0-based as in 'sparsediffpy'. CSR results are a list with data, indices, indptr and shape, the pieces of its (data, indices, indptr, (m, n)) tuple.

Author(s)

Maintainer: Balasubramanian Narasimhan naras@stanford.edu

Authors:

• Balasubramanian Narasimhan naras@stanford.edu

• Daniel Cederberg (Author of the bundled SparseDiffEngine C library) [copyright holder]

• William Zijie Zhang (Author of the bundled SparseDiffEngine C library) [copyright holder]

See Also

Useful links:

• https://bnaras.github.io/sparsediff/

• https://github.com/bnaras/sparsediff

• Report bugs at https://github.com/bnaras/sparsediff/issues

Bundled SparseDiffEngine version

Description

Returns the version string of the SparseDiffEngine C library bundled with this package.

Usage

engine_version()

Value

A character scalar, e.g. "0.6.1".

Examples

engine_version()

Affine and shape atoms

Description

Affine combinations and shape manipulations of expressions. These have constant (zero) second derivatives but participate in the Jacobian.

Usage

sd_add(left, right)
sd_sum(child, axis)
sd_trace(c)
sd_transpose(c)
sd_diag_vec(c)
sd_diag_mat(c)
sd_upper_tri(c)
sd_promote(c, d1, d2)
sd_reshape(c, d1, d2)
sd_broadcast(c, d1, d2)
sd_index(child, d1, d2, indices)
sd_hstack(args, n_vars)
sd_vstack(args, n_vars)

Arguments

Details

sd_add

elementwise sum of two expressions.

sd_sum

sum reduction along axis.

sd_trace

matrix trace.

sd_transpose

matrix transpose.

sd_diag_vec

diagonal matrix from a vector.

sd_diag_mat

diagonal vector from a matrix.

sd_upper_tri

the strict upper-triangular entries.

sd_promote

promote a scalar to shape d1 x d2.

sd_reshape

reshape to d1 x d2 (column-major).

sd_broadcast

broadcast to d1 x d2.

sd_index

select entries by 0-based flat indices.

sd_hstack, sd_vstack

horizontal / vertical stacking.

Value

An expression handle.

See Also

sparsediff-elementwise, sparsediff-matrix

Bivariate atoms

Description

Functions of two expression arguments.

Usage

sd_elementwise_mult(l, r)
sd_matmul(x, y)
sd_quad_over_lin(l, r)
sd_rel_entr(l, r)
sd_rel_entr_first_scalar(l, r)
sd_rel_entr_second_scalar(l, r)

Arguments

Details

sd_elementwise_mult

elementwise (Hadamard) product.

sd_matmul

matrix product x y.

sd_quad_over_lin

the quadratic-over-linear \lVert x \rVert^2 / y.

sd_rel_entr

relative entropy x \log(x / y). Like 'sparsediffpy' make_rel_entr, it dispatches on operand size: a scalar l with a non-scalar r uses sd_rel_entr_first_scalar, the reverse uses sd_rel_entr_second_scalar, and otherwise it is elementwise.

sd_rel_entr_first_scalar, sd_rel_entr_second_scalar

relative entropy with a scalar first or second argument broadcast against the other.

Value

An expression handle.

See Also

sparsediff-elementwise, sparsediff-reduction

Elementwise atoms

Description

Smooth elementwise functions of a single expression. Each returns an expression of the same shape as its argument.

Usage

sd_exp(child)
sd_log(c)
sd_sin(c)
sd_cos(c)
sd_tan(c)
sd_sinh(c)
sd_tanh(c)
sd_asinh(c)
sd_atanh(c)
sd_logistic(c)
sd_xexp(c)
sd_normal_cdf(c)
sd_entr(c)
sd_power(c, p)
sd_neg(child)

Arguments

Details

sd_exp, sd_log

exponential and natural logarithm.

sd_sin, sd_cos, sd_tan

trigonometric functions.

sd_sinh, sd_tanh, sd_asinh, sd_atanh

hyperbolic and inverse-hyperbolic functions.

sd_logistic

the logistic \log(1 + e^x).

sd_xexp

x e^x.

sd_normal_cdf

the standard normal CDF.

sd_entr

the elementwise entropy -x \log x.

sd_power

the power x^p.

sd_neg

negation -x.

Value

An expression handle.

See Also

sparsediff-affine, sparsediff-bivariate

Expression shape

Description

The dimensions and the number of entries of an expression node (the 'sparsediffpy' get_expr_dimensions and get_expr_size).

Usage

sd_get_expr_dimensions(node)
sd_get_expr_size(node)

Arguments

Value

sd_get_expr_dimensions: an integer vector c(d1, d2), the node's rows and columns. sd_get_expr_size: an integer scalar, the number of entries d1 * d2.

See Also

sparsediff-leaves

Leaf expressions: variables and parameters

Description

Create the leaves of an expression graph. A variable is a slice of the differentiation vector; a parameter is fixed data that can be updated between evaluations (see sd_register_params).

Usage

sd_variable(d1, d2, var_id, n_vars)
sd_parameter(d1, d2, param_id, n_vars, values)

Arguments

Value

An expression handle.

See Also

sparsediff-elementwise, sd_problem

Parameter- and constant-matrix atoms

Description

Operations that combine an expression with fixed data — a registered parameter node or a constant matrix — so the data can flow through the differentiated graph (and, for parameters, be updated between evaluations).

Usage

sd_scalar_mult(param, child)
sd_vector_mult(param, child)
sd_convolve(param, child)
sd_quad_form(child, Qp, Qi, Qx)
sd_quad_form_dense(param, child, data)
sd_left_matmul(child, Ap, Ai, Ax, ncol)
sd_right_matmul(child, Ap, Ai, Ax, ncol)
sd_left_matmul_dense(param, child, m, n, data)
sd_right_matmul_dense(param, child, m, n, data)
sd_left_kron(param, child, p, q, r, s, active_blocks)
sd_right_kron(param, child, p, q, r, s, active_blocks)

Arguments

Details

sd_scalar_mult, sd_vector_mult

multiply a child by a scalar / vector parameter.

sd_convolve

convolution of a parameter kernel with a child.

sd_quad_form

the quadratic form x^\top Q x with sparse constant Q.

sd_quad_form_dense

the quadratic form x^\top Q x with a dense symmetric n \times n Q, where n is the length of the vector child. Supply exactly one source: param = NULL and data for a constant Q (checked for symmetry), or a parameter handle of size n^2 with data = numeric(0) for a parametric Q that follows sd_update_params. A parametric Q is not checked: keeping it symmetric is the caller's responsibility.

sd_left_matmul, sd_right_matmul

left / right product with a sparse constant matrix A.

sd_left_matmul_dense, sd_right_matmul_dense

left / right product with a dense constant or parametric matrix.

sd_left_kron, sd_right_kron

the Kronecker product A \otimes B with the variable-free operand param on the left (A) or on the right (B) and the variable operand child on the other side. param may be a parameter or a constant made with sd_parameter(..., param_id = -1, ...).

A parameter cannot be the source of the sparse products sd_left_matmul / sd_right_matmul (the engine does not support it; 'sparsediffpy' accepts the argument but the engine then aborts); use the dense products for a parametric matrix.

Value

An expression handle.

See Also

sd_parameter, sd_register_params

Sparse derivative oracle

Description

Initialize and evaluate the value, gradient, sparse constraint Jacobian and sparse Lagrangian Hessian of a problem built with sd_problem. Derivatives come in two forms, matching 'sparsediffpy': coordinate (COO) form, with the Hessian as its lower triangle (the form CVXPY uses), and compressed-sparse-row (CSR) form, with the full Hessian.

Usage

sd_init_derivatives(prob)
sd_init_jacobian(prob)
sd_init_jacobian_coo(prob)
sd_init_hessian_coo(prob)
sd_objective_forward(prob, u)
sd_constraint_forward(prob, u)
sd_gradient(prob)
sd_jacobian_sparsity(prob)
sd_jacobian_values(prob)
sd_hessian_sparsity(prob)
sd_hessian_values(prob, obj_w, w)
sd_jacobian(prob)
sd_get_jacobian(prob)
sd_init_hessian(prob)
sd_hessian(prob, obj_w, w)
sd_get_hessian(prob)

Arguments

Details

Evaluation is ordered: a forward pass first (sd_objective_forward / sd_constraint_forward) populates the node values at u, after which sd_gradient, sd_jacobian_values and sd_hessian_values read them. Sparsity patterns are structural — fixed once the corresponding sd_init_* routine has run — so they are queried once and reused, while the values are recomputed at each new point. Row and column indices are 0-based (the engine convention; a higher-level modeling layer such as CVXR translates them to 1-based as needed).

Value

sd_init_derivatives, sd_init_jacobian, sd_init_jacobian_coo, sd_init_hessian, sd_init_hessian_coo

called for their side effect; return NULL invisibly.

sd_jacobian, sd_get_jacobian, sd_hessian, sd_get_hessian

a list with the CSR arrays of the matrix: data (double), indices (0-based column indices) and indptr (row pointers), plus shape = c(nrow, ncol). sd_jacobian evaluates the constraint Jacobian (after sd_init_jacobian and a forward pass) and sd_hessian the full Lagrangian Hessian \sigma\nabla^2 f + \sum_i w_i \nabla^2 g_i (after sd_init_hessian); the sd_get_* forms return the matrix as last evaluated, without re-evaluating it.

sd_objective_forward

the scalar objective value at u.

sd_constraint_forward

the constraint vector at u.

sd_gradient

the objective gradient, length n_vars.

sd_jacobian_sparsity, sd_hessian_sparsity

a list with integer rows/cols (0-based COO indices) and nrow/ncol.

sd_jacobian_values

the constraint-Jacobian nonzeros, matching the Jacobian sparsity order.

sd_hessian_values

the nonzeros of \sigma\nabla^2 f + \sum_i w_i \nabla^2 g_i, lower triangle, matching the Hessian sparsity order.

See Also

sd_problem

Assemble a differentiable problem

Description

Combine an objective expression and a list of constraint expressions (built with the sd_* atom constructors) into a single problem object whose value and sparse derivatives can be evaluated repeatedly.

Usage

sd_problem(objective, constraints, verbose)
sd_register_params(prob, params)
sd_update_params(prob, theta)

Arguments

Details

The typical lifecycle is: build expressions with the sd_* constructors, assemble them with sd_problem(), initialise the derivative structures once (sd_init_derivatives and friends), then evaluate the objective/constraints and their sparse derivatives at as many primal points as needed. When the problem has parameters, register them once with sd_register_params() and push new values with sd_update_params() to re-evaluate without rebuilding the graph (the DPP-style fast path).

Value

sd_problem() returns an external-pointer problem handle. The handle owns the underlying expression graph and frees it when garbage collected. sd_register_params() and sd_update_params() are called for their side effect and return NULL invisibly.

See Also

sd_init_derivatives for the evaluation oracle, sd_variable and the atom constructors for building expressions.

Product-reduction atoms

Description

Multiplicative reductions of an expression.

Usage

sd_prod(c)
sd_prod_axis_zero(c)
sd_prod_axis_one(c)

Arguments

Details

sd_prod

product of all entries.

sd_prod_axis_zero

column-wise products (reduce down rows).

sd_prod_axis_one

row-wise products (reduce across columns).

Value

An expression handle.

See Also

sparsediff-affine