ArXiv

MixedComplementarityProblems.jl: A Fast, Batched, Open-Source Interior Point Solver for Mixed Complementarity Problems

2026-08-02 · 03:10 UTC ·David Fridovich-Keil ·1 min read
Authors
David Fridovich-Keil
Categories
cs.GT, cs.RO, eess.SY
arXiv
https://arxiv.org/abs/2608.00959v1
PDF
https://arxiv.org/pdf/2608.00959v1

Brief

MixedComplementarityProblems.jl is a pure-Julia interior-point solver for parametric MCPs (David Fridovich-Keil, arXiv 2026-08-02). It targets multi-agent trajectory-optimization and game problems, providing batched CPU-threaded and NVIDIA-GPU solves plus automatic differentiation. The implementation matches PATH's reliability and yields ≈100× speedups over sequential PATH on a lane-change game; GPU wins only when per-instance KKT systems grow large. Summary based on the paper abstract.

Why it matters

MixedComplementarityProblems.jl (David Fridovich-Keil, arXiv 2026-08-02) is a pure-Julia interior-point solver for parametric mixed complementarity problems (MCPs) that the author reports matches PATH's reliability on standard benchmarks.

Key details

  • On a multi-agent lane-change trajectory game, the CPU multithreaded batched solver clears a batch of parametric instances ~100× faster than sequential calls to PATH; an NVIDIA-GPU backend also outperforms PATH but does not beat the multithreaded CPU for that problem, only doing so when per-instance KKT systems become large.
  • The package natively supports batched parallel solves across CPU threads and NVIDIA GPUs, efficient automatic differentiation of solutions with respect to parameters, and a single solver implementation that runs unmodified across dense, batched-sparse, and single-large linear-algebra backends; benchmarks include random quadratic programs and trajectory games.
Source evidence

Abstract

Mixed complementarity problems (MCPs) arise as the first-order optimality conditions of nonlinear programs and noncooperative games, and provide a natural formulation for multi-agent trajectory optimization problems that appear throughout robotics. The dominant solver for problems of this form is PATH, which offers strong performance on robotics problems but remains closed-source. We present MixedComplementarityProblems.jl, an open-source, pure Julia implementation of an interior point method for parametric MCPs that: (i) matches PATH's reliability on standard benchmarks, (ii) natively supports batched, parallel processing of many parameter instances, either across CPU threads or on an NVIDIA GPU, and (iii) supports efficient automatic differentiation of solutions with respect to problem parameters. On a multi-agent lane-change trajectory game representative of robotics planning problems, our CPU-multithreaded batched solver clears a batch of parametric instances ~100x faster than sequential calls to PATH. A GPU backend, running the same solver implementation unmodified, also clears these batches far faster than PATH, but does not outperform the multithreaded CPU on this problem; the GPU pulls ahead only once each per-instance KKT system grows large, and we characterize this regime dependence. We describe the solver's interior point formulation, the abstraction that lets a single solver implementation run unmodified across dense, batched-sparse, and single-large linear-algebra backends, and report benchmarks against PATH on both randomly generated quadratic programs and trajectory games.