Convex optimization in Julia

Madeleine Udell, Karanveer Mohan, David Zeng, Jenny Hong, Steven Diamond, Stephen P. Boyd

Introduction

In mathematical optimization, a persistent gap exists between human-readable problem formulations and the rigid, standard formats required by numerical solvers. While high-level modeling languages bridge this gap by translating intuitive mathematical expressions into solver-friendly matrices (such as conic form), the computational overhead of verifying convexity and performing this translation can become a significant bottleneck.

This paper introduces Convex.jl, a modeling framework for the Julia programming language designed to address these performance challenges. By leveraging Julia's unique language features—specifically multiple dispatch and just-in-time (JIT) compilation—Convex.jl rapidly translates optimization problems into conic forms, matching or exceeding the parsing performance of established tools like CVX (MATLAB) and CVXPY (Python).

Bridging the Gap: The Convex.jl Approach

Functional Representation and ASTs

At its core, Convex.jl represents optimization problems using a functional approach. Every expression—including variables, constants, and mathematical functions (atoms) like +, max, or norm—is stored as an Abstract Syntax Tree (AST).

Abstract Syntax Tree (AST) representation of a convex optimization problem in Convex.jl.

To optimize this representation, the framework employs a unique hashing system. Every expression is assigned an identifier based on its top-level atom and its children. This allows Convex.jl to identify reused expressions across a model, memoize computations, and ultimately reduce the complexity of the problem passed to the backend solver.

Multiple Dispatch for Disciplined Convex Programming

To ensure a problem is solvable via convex methods, the system applies Disciplined Convex Programming (DCP) rules. Traditional frameworks often rely on complex conditional logic to verify the curvature and monotonicity of nested functions. In contrast, Convex.jl utilizes Julia’s multiple dispatch.

Mathematical rules are defined directly on types. For instance, adding a ConvexVexity type to an AffineVexity type automatically dispatches to a method that returns ConvexVexity. This approach acts as a highly optimized lookup table at compile time, drastically reducing the overhead of verification compared to standard object-oriented or imperative approaches. This design also makes the framework highly extensible; users can add new mathematical atoms simply by defining their corresponding curvature and monotonicity types.

Performance Evaluation

The authors evaluated Convex.jl using synthetic micro-benchmarks designed to test parsing efficiency rather than solver speed. These tests included large-scale summation, iterative indexing, and matrix constraints.

Benchmark results comparing parsing and compilation times across CVX, CVXPY, and Convex.jl.

Key Results

When compared against CVX and CVXPY using the ECOS solver, Convex.jl demonstrated superior parsing times once the initial JIT compilation was complete:

  • Matrix Constraints: In tests involving equality constraints on a 500x500 matrix, Convex.jl parsed the problem in 0.34 seconds, significantly faster than CVX (1.38s) and CVXPY (0.54s).
  • Transpose Operations: For minimizing the norm of a transposed matrix, Convex.jl achieved a parse time of 0.40s, compared to 1.24s for CVX.
  • Iterative Algorithms: Because Julia is JIT-compiled, subsequent runs of the same optimization routine (common in sequential convex programming) benefit from pre-compiled code, leading to even greater performance gains in iterative contexts.

Conclusion and Future Directions

Convex.jl demonstrates that modern language features like multiple dispatch are a "killer feature" for mathematical modeling. By mirroring underlying mathematical rules in the type system, the framework achieves both high performance and high extensibility.

While current AST computations are performed serially, future work aims to leverage Julia’s evolving parallelism ecosystem to handle even larger-scale problems. Additionally, the authors suggest that the AST transformation pipeline could be extended to support other problem classes, such as integer linear programs and difference-of-convex programs, further broadening the utility of the Julia optimization ecosystem.

Summary updated

BibTeX
@inproceedings{udell2014convex,
  author = {Madeleine Udell and Karanveer Mohan and David Zeng and Jenny Hong and Steven Diamond and Stephen P. Boyd},
  title = {{Convex optimization in Julia}},
  booktitle = {HPTCDL@SC},
  year = {2014},
  doi = {10.1109/hptcdl.2014.5},
}
Figure