PaperlayerView exact revision on arXiv

Source-linked AI summary

Clarabel: An interior-point solver for conic programs with quadratic objectives

Paul J. Goulart, Yuwen Chen

arXiv:2405.12762v1math.OC

TL;DR

Convex conic programs with quadratic objectives require solvers that handle general cones and high-precision solution demands. The paper develops Clarabel by specializing homogeneous embedding methods to a primal-dual interior-point solver. Clarabel is competitive across broad benchmarks and particularly outperforms state-of-the-art solvers on quadratic programs, large-scale SOCPs, and sparse SDPs.

  • Problem

    Active-set methods do not generalize well to non-polyhedral constraints, while ADMM can have poor tail convergence at high precision.

  • Method

    Clarabel specializes a homogeneous embedding for monotone complementarity problems to convex conic programs with quadratic objectives and symmetric or nonsymmetric cones.

  • Results

    Clarabel outperforms state-of-the-art solvers on quadratic programs, large-scale SOCPs, and sparse semidefinite programs across a wide range of problem classes.

  • Takeaways & Limitations

    Clarabel is distributed through CVXPY and is its default solver for linear and second-order cone programs as of version 1.5.

  • Takeaways & Limitations

    Chordal clique-merging metrics may be inefficient, and success rates can differ slightly between Julia and Rust implementations on difficult high-accuracy problems.

Abstract

from arXiv · show

We present a general-purpose interior-point solver for convex optimization problems with conic constraints. Our method is based on a homogeneous embedding method originally developed for general monotone complementarity problems and more recently applied to operator splitting methods, and here specialized to an interior-point method for problems with quadratic objectives. We allow for a variety of standard symmetric and non-symmetric cones, and provide support for chordal decomposition methods in the case of semidefinite cones. We describe the implementation of this method in the open-source solver Clarabel, and provide a detailed numerical evaluation of its performance versus several state-of-the-art solvers on a wide range of standard benchmarks problems. Clarabel is faster and more robust than competing commercial and open-source solvers across a range of test sets, with a particularly large performance advantage for problems with quadratic objectives. Clarabel is currently distributed as a standard solver for the Python CVXPY optimization suite.

1 Introduction

Convex conic optimization covers many practical applications, but active-set methods do not generalize well beyond polyhedral constraints. Operator splitting and interior-point methods therefore dominate general conic optimization, with interior-point methods favored for high precision.

  • Convex conic optimization models applications ranging from optimal control and image processing to portfolio optimization and mixed-integer methods.
  • 1.1 Solution methods: Active-set methods rely on polyhedral constraint structure and do not generalize well to non-polyhedral cones.
  • 1.1 Solution methods: Operator splitting methods such as ADMM are attractive for moderate accuracy because of their scalability and implementation simplicity.
  • 1.1 Solution methods: ADMM can exhibit poor tail convergence at high precision, motivating interior-point methods for more accurate solutions.
  • 1.1 Solution methods: Interior-point methods support general conic constraints, including nonnegative orthants, second-order cones, and positive semidefinite cones.
  • 1.1 Solution methods: Nonsymmetric cones, including exponential and power cones, extend the range of conic models but require alternatives to NT scaling.

2 Algorithmic approach

The paper specializes homogeneous embedding methods for monotone complementarity problems to convex conic programs with quadratic objectives. It retains the quadratic term and solves the resulting homogeneous system directly with a primal-dual interior-point method.

  • 2 Algorithmic approach: Clarabel specializes a monotone-complementarity homogeneous embedding to convex conic problems with quadratic objectives and symmetric or nonsymmetric cones.
  • 2 Algorithmic approach: The formulation uses primal-dual KKT conditions and a nonnegative duality gap to characterize optimality under strong duality.
  • 2 Algorithmic approach: The quadratic objective term is retained rather than replaced by an epigraph and an additional second-order cone constraint.
  • 2 Algorithmic approach: The resulting embedding remains homogeneous but is no longer self-dual when the quadratic term is retained.
  • 2 Algorithmic approach: The method directly solves the embedded nonlinear system with a primal-dual interior-point approach.

2.1 Existence of solutions and infeasibility detection

The homogeneous embedding is asymptotically feasible and complementary, and its solutions can recover primal or dual optima or certify infeasibility. Positive scaling variables determine whether the embedded limit yields an optimizer or an infeasibility certificate.

  • 2.1 Existence of solutions and infeasibility detection: The embedding is solved by finding a root of a nonlinear system subject to membership in R^n × K × K* × R+ × R+.
  • 2.1 Existence of solutions and infeasibility detection: Asymptotically feasible points are defined as limits of bounded feasible sequences whose residuals converge appropriately.
  • 2.1 Existence of solutions and infeasibility detection: The embedding is asymptotically feasible, and every asymptotically feasible point is asymptotically complementary.
  • 2.1 Existence of solutions and infeasibility detection: The construction uses positive semidefiniteness of P and closedness of the cones to establish the limiting certificate conditions.
  • 2.1 Existence of solutions and infeasibility detection: When τ* > 0, rescaling the embedded variables by τ* produces optimal primal and dual solutions.
  • 2.1 Existence of solutions and infeasibility detection: When κ* > 0, the embedded solution identifies either primal or dual infeasibility through a corresponding cone-valued certificate.

2.2 Supported constraint types and barrier functions

Clarabel supports compositions of symmetric, nonsymmetric, and zero cones, using barrier functions and conjugate barriers to formulate conic interior-point steps.

  • Supported cones: The method supports arbitrary compositions of symmetric and nonsymmetric basic cone types, including the zero cone for equality constraints.Supported symmetric cones include the nonnegative, second-order, and positive semidefinite cones.
  • Semidefinite representation: Symmetric-matrix variables use scaled triangular vectorization, whose scaling preserves matrix inner products under vectorization.The inverse operator restores the original matrix representation.
  • Supported cones: The implementation supports two nonsymmetric cones defined as subsets of R3, together with their corresponding dual cones.The nonsymmetric cone support extends the solver beyond self-dual cone families.
  • Barrier functions: For each nonzero cone, Clarabel defines a strictly convex barrier f and its conjugate barrier f∗ on the dual cone.The barriers satisfy the logarithmically homogeneous self-concordant barrier framework with degree ν ≥ 1.
  • Barrier functions: The conjugate-barrier gradient can be computed by solving an optimization problem when no closed-form representation is available.The implementation therefore supports barrier functions whose conjugates are defined implicitly.

2.3 The central path

Clarabel computes a central path for its homogeneous conic formulation and uses Newton-like steps, scaling, equilibration, and cone-specific initialization to begin near that path.

  • Central-path definition: The central path is defined as the unique solution associated with a ν–LHSCB barrier and an initial point v0 in the feasible embedding set.For symmetric cones, one central-path condition can be replaced by a Jordan-product condition.
  • Newton steps: The core algorithm uses a Newton-like method to solve the central-path equations.Step-direction calculations are described separately from initialization, termination, and preprocessing.
  • Preprocessing: Clarabel equilibrates matrix-valued data with Ruiz scaling before solving.Termination checks later revert this scaling and use unscaled problem data and iterates.
  • Initialization: Initialization seeks an interior iterate sufficiently near the central path, with separate strategies for symmetric and nonsymmetric cones.Symmetric-cone initialization distinguishes between P = 0 and P ≠ 0, while nonsymmetric cones use a unit initialization strategy.
  • Initialization: For nonsymmetric cones, unit initialization places primal and dual variables on the central path with μ0 = 1.The resulting unconstrained problem is strictly convex and has a unique solution.

2.5 Chordal Decomposition

Clarabel supports chordal decomposition for semidefinite programs through clique merging, compact conversion, and an edge-weight metric inherited from COSMO.

  • Decomposition and merging: Semidefinite programs use chordal decomposition and clique merging with both parent-child and clique-graph merge strategies.Both strategies are reformulated using compact, or range-space, conversion.
  • Decomposition and merging: The clique-graph strategy accepts candidate merges when the edge-weight metric is positive.The metric is the same one used in the ADMM-based COSMO solver.
  • Computational considerations: The metric relates to projection complexity, but Hessian blocks and linking variables complicate KKT factorization time in Clarabel.For a conic variable in S^n, the Hessian block has dimension R(n(n+1)/2)×(n(n+1)/2).
  • Computational considerations: The authors note that more efficient clique-merge metrics may be possible for this interior-point setting.This caveat follows from the additional factorization complications introduced by overlapping cliques.

2.6 Termination Criteria

Clarabel evaluates convergence and infeasibility using residual, objective, and certificate conditions on unscaled iterates, with separate normalization rules for optimality and infeasibility checks.

  • Optimality termination: Termination checks revert Ruiz scaling before evaluating unscaled problem data and iterates.For feasibility and optimality checks, primal, slack, and dual variables are normalized by τ.
  • Optimality termination: Convergence requires all three specified residual and objective conditions to hold simultaneously.The implementation uses a default feasibility threshold of ϵf = 10^-8.
  • Optimality termination: Early termination can be labeled near optimality using the weaker threshold ϵ = 10^-5.Examples include lack of progress, timeouts, and iteration limits.
  • Infeasibility termination: Infeasibility certificates are tested directly on unscaled variables because infeasibility corresponds to τ approaching zero.Primal and dual infeasibility are checked with separate certificate conditions.
  • Infeasibility termination: The default infeasibility tolerances are ϵi,r = ϵi,a = 10^-8, with weaker near-infeasibility thresholds permitted after early termination.The weaker thresholds apply when termination occurs before standard certificate conditions are met.

3 Computing step directions

Clarabel computes interior-point search directions by condensing Newton-like systems, using cone-specific scaling and correction strategies. Regularized direct factorization improves efficiency, especially when quadratic objectives are present.

  • Linear system formation: Newton-like directions solve a linearized central-path system for residual right-hand sides involving primal, dual, and embedding variables.The scaling matrix and residual terms depend on the search direction, cone symmetry, and scaling strategy.
  • Linear system formation: Eliminating Δs and Δκ produces a reduced system solved through two linear systems sharing a common left-hand side.The remaining updates recover Δτ, then Δx and Δz, before reconstructing the eliminated variables.
  • Cone scaling: NT scaling is used for symmetric cones, while symmetric or nonsymmetric primal-dual scaling strategies handle nonsymmetric cones.The zero cone uses H = 0, and nonsymmetric scaling relies on secant equations and a BFGS-based update.
  • Iteration steps: Each iteration uses one condensed-system factorization followed by three linear solves across two right-hand-side terms.The shared factorization exploits the common term (−q, b) in the reduced system.
  • Linear algebra: Regularized LDLᵀ factorization preserves quasidefiniteness and makes the factor sparsity pattern depend only on problem sparsity.The specialized formulation avoids the additional second-order-cone block of the epigraphical reformulation, reducing potential fill-in.

4 Implementation: the Clarabel solver

Clarabel is implemented as an open-source solver in Rust and Julia with matching conic functionality. It provides broad language access, configurable linear algebra, chordal decomposition support, and multiple floating-point types.

  • Software distribution: Clarabel provides separate open-source Rust and Julia implementations under the Apache v2.0 license.Both implementations are publicly available with extensive documentation.
  • Software distribution: The Rust implementation supports Python, C, C++, and R through wrappers, and integrates with CVXPY.Clarabel is installed in the standard CVXPY distribution and is its default solver for linear and second-order cone programs as of version 1.5.
  • Linear algebra: Rust includes native QDLDL functionality, user-selectable BLAS interfaces for semidefinite programs, and optional alternative direct solvers.The implementation also offers a multithreaded supernodal LDL factorization through faer-rs.
  • Linear algebra: Julia serves both as a standalone solver and as a prototyping platform, with optional CHOLMOD, Pardiso, and HSL MA57 linear solvers.The Julia implementation provides its own QDLDL package alongside native Julia linear algebra.
  • Common functionality: Both implementations support the same conic constraints and functionality, including standard and extended floating-point types.Supported types include 32- and 64-bit precision and Julia’s BigFloat type.

5 Numerical Experiments

Clarabel was benchmarked against open-source and commercial solvers across quadratic, linear, exponential-cone, power-flow, and semidefinite problems. It was strongest on quadratic and semidefinite benchmarks, while remaining broadly comparable on linear and exponential-cone problems.

  • Benchmark design: Benchmarks compare Clarabel with ECOS, HiGHS, Mosek, and Gurobi using default settings, disabled presolve where applicable, and no iteration limit.Experiments were single-threaded on an Intel Xeon Platinum 8268 system with 64 GB RAM.
  • Benchmark metrics: Relative profiles show the fraction solved within a factor τ of the best solver, while absolute profiles show the fraction solved within τ seconds independently of the solver pool.Normalized shifted geometric means assign the lowest-time solver a score of 1 and penalize failures with the maximum allowable time.
  • Quadratic objectives: Clarabel is fastest overall on the 138-problem Maros-Meszaros quadratic-program set, with Rust marginally faster than Julia.All solvers fail on some cases; Gurobi has the lowest full-accuracy failure rate, while Clarabel has the lowest reduced-accuracy failure rate.
  • Quadratic objectives: Clarabel is fastest and the only solver with a 100% full-accuracy success rate on the constrained optimal-control benchmark.These finite-horizon problems reflect repeated online solves used in model predictive control.
  • Linear and nonsymmetric cones: On feasible NETLIB LPs Clarabel is broadly comparable to Mosek and Gurobi, but it is somewhat slower on infeasible LPs.The authors attribute the smaller advantage to the absence of quadratic objectives.
  • Linear and nonsymmetric cones: Clarabel performs similarly to Mosek on CBLIB exponential-cone problems, with slightly faster Rust solve times despite generally higher iteration counts.This evaluates performance on nonsymmetric cone programs.
  • Optimal power flow: Clarabel outperforms the other tested solvers on optimal-power-flow benchmarks, while Rust solves over 99% of SOCP cases to reduced accuracy.At full accuracy, LP failures are 3.3% for Clarabel versus 0% for Gurobi; ECOS and Mosek fail on more than 50% of SOCP cases even at reduced accuracy.

6 Conclusions

Clarabel is presented as a novel interior-point solver for conic optimization with quadratic objectives, competitive across diverse problem classes and particularly strong on QPs, large-scale SOCPs, and sparse SDPs.

  • Clarabel uses a homogeneous embedding specialized for conic optimization problems with quadratic objectives.
  • The solver is competitive with state-of-the-art methods across a wide range of problem classes.
  • Clarabel particularly outperforms state-of-the-art solvers on quadratic programs, large-scale second-order cone programs, and sparse semidefinite programs.
  • Clarabel is available as open-source software in Rust and Julia and as a standard solver in CVXPY.

A Detailed benchmark results

The detailed benchmark materials organize solver evaluations across multiple standard problem sets, reporting problem dimensions, sparsity statistics, solve times, iteration counts, and failure rates.

  • The benchmark tables report solve times and iteration counts for the Maros-Meszaros problem set.
  • Problem listings provide variables, constraints, nnz(A), and nnz(P), with solver columns including ClarabelRs, ECOS, and Mosek.
  • The benchmark materials include optimal-control, least-squares, feasible-LP, and infeasible-LP problem sets.
  • Additional evaluations cover optimal-power-flow, exponential-cone, second-order-cone, and semidefinite-programming problem sets.
Loading 2405.12762v1…