Convexity Certificates from Hessians (Supplementary Material)

Here, we (1) provide the grammar for the formal language of mathematical expressions to which our certification algorithm is applied, (2) we provide more algorithmic details about our implementation of the Hessian approach, (3) we show that our implementation of the Hessian approach can also certify the remaining differentiable CVX atoms with vector input, which we could not discuss in the main paper because of space constraints, and (4) we provide more examples of differentiable functions that can be certified by the Hessian approach but are missing from CVX's DCP implementation. The formal language for mathematical expressions to which our certification algorithm is applied is specified by the grammar depicted in Figure 1. The language is rich enough to cover all the examples in the main paper and this supplement. In this grammar, number is a placeholder for an arbitrary floating point number, variable is a placeholder for variable names starting with a Latin character and function is a placeholder for the supported elementary differentiable functions like exp, log and sum . Our implementation of the Hessian approach works on vectorized and normalized expression DAGs (directed acyclic graphs) for Hessians that contain every subexpression exactly once.