# On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope

arXiv: https://arxiv.org/abs/1702.05934 · HTML: https://mlsanity.com/paper/1702.05934/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Feb 2017.

## Built on by (most cited first, 4 of 4)

- [Mirror Sinkhorn: Fast Online Optimization on Transport Polytopes](https://mlsanity.com/paper/2211.10420/) (2022)
- [Fast and Provably Convergent Algorithms for Gromov-Wasserstein in Graph Data](https://mlsanity.com/paper/2205.08115/) (2022)
- [NewVEM: A Newton Vertex Exchange Method for a Class of Constrained Self-Concordant Minimization Problems](https://mlsanity.com/paper/2407.03294/) (2024)
- [Efficient and provably convergent end-to-end training of deep neural networks with linear constraints](https://mlsanity.com/paper/2605.11526/) (2026)

## Abstract (arXiv)

We derive an explicit formula, as well as an efficient procedure, for constructing a generalized Jacobian for the projector of a given square matrix onto the Birkhoff polytope, i.e., the set of doubly stochastic matrices. To guarantee the high efficiency of our procedure, a semismooth Newton method for solving the dual of the projection problem is proposed and efficiently implemented. Extensive numerical experiments are presented to demonstrate the merits and effectiveness of our method by comparing its performance against other powerful solvers such as the commercial software Gurobi and the academic code PPROJ [sc Hager and Zhang, SIAM Journal on Optimization, 26 (2016), pp.~1773--1798]. In particular, our algorithm is able to solve the projection problem with over one billion variables and nonnegative constraints to a very high accuracy in less than 15 minutes on a modest desktop computer. More importantly, based on our efficient computation of the projections and their generalized Jacobians, we can design a highly efficient augmented Lagrangian method (ALM) for solving a class of convex quadratic programming (QP) problems constrained by the Birkhoff polytope. The resulted ALM is demonstrated to be much more efficient than Gurobi in solving a collection of QP problems arising from the relaxation of quadratic assignment problems.