On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
From MaRDI portal
Publication:2288199
Abstract: 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.
Recommendations
- Efficient projection onto the intersection of a half-space and a box-like set and its generalized Jacobian
- The generalized Jacobian of the projection onto the intersection of a half-space and a variable box
- On degenerate doubly nonnegative projection problems
- Computing the Nearest Doubly Stochastic Matrix with A Prescribed Entry
- Projection onto a polyhedron that exploits sparsity
Cites work
- L_p-norm regularization algorithms for optimization over permutation matrices
- A dual algorithm for the solution of nonlinear variational problems via finite element approximation
- A Dual Approach to Semidefinite Least-Squares Problems
- A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
- A highly efficient semismooth Newton augmented Lagrangian method for solving lasso problems
- A new bound for the quadratic assignment problem based on convex quadratic programming
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A nonsmooth version of Newton's method
- A Quadratically Convergent Newton Method for Computing the Nearest Correlation Matrix
- An Algorithm for Restricted Least Squares Regression
- Asymptotic Convergence Analysis of the Proximal Point Algorithm
- Augmented Lagrangians and Applications of the Proximal Point Algorithm in Convex Programming
- Computing the nearest correlation matrix--a problem from finance
- Convex Analysis
- Generalized Hessian matrix and second-order optimality conditions for problems with \(C^{1,1}\) data
- How to differentiate the projection on a convex set in Hilbert space. Some applications to variational inequalities
- scientific article; zbMATH DE number 6610411 (Why is no real title available?)
- scientific article; zbMATH DE number 3850830 (Why is no real title available?)
- scientific article; zbMATH DE number 3574917 (Why is no real title available?)
- scientific article; zbMATH DE number 1012640 (Why is no real title available?)
- scientific article; zbMATH DE number 1502618 (Why is no real title available?)
- scientific article; zbMATH DE number 1559033 (Why is no real title available?)
- scientific article; zbMATH DE number 2201293 (Why is no real title available?)
- scientific article; zbMATH DE number 3078983 (Why is no real title available?)
- scientific article; zbMATH DE number 3095897 (Why is no real title available?)
- Newton and quasi-Newton methods for normal maps with polyhedral sets
- Newton's Method for B-Differentiable Equations
- On finite termination of an iterative method for linear complementarity problems
- Optimization and nonsmooth analysis
- Piecewise Smoothness, Local Invertibility, and Parametric Analysis of Normal Maps
- Projection onto a polyhedron that exploits sparsity
- QAPLIB - a quadratic assignment problem library
- QSDPNAL: a two-phase augmented Lagrangian method for convex quadratic semidefinite programming
- Semismooth and Semiconvex Functions in Constrained Optimization
- Some continuity properties of polyhedral multifunctions
- Sparse Reconstruction by Separable Approximation
- Variational Analysis
Cited in
(21)- An efficient Hessian based algorithm for singly linearly and box constrained least squares regression
- A semismooth Newton-based augmented Lagrangian algorithm for density matrix least squares problems
- An augmented Lagrangian method with constraint generation for shape-constrained convex regression problems
- An exact penalty approach for optimization with nonnegative orthogonality constraints
- Efficient projection onto the intersection of a half-space and a box-like set and its generalized Jacobian
- Bregman proximal point algorithm revisited: a new inexact version and its inertial variant
- Efficient sparse semismooth Newton methods for the clustered Lasso problem
- A primal-dual flow for affine constrained convex optimization
- A fast solver for generalized optimal transport problems based on dynamical system and algebraic multigrid
- The convergence properties of infeasible inexact proximal alternating linearized minimization
- A Global Optimization Approach for Multimarginal Optimal Transport Problems with Coulomb Cost
- An easily implementable algorithm for efficient projection onto the ordered weighted \(\ell_1\) norm ball
- A Corrected Inexact Proximal Augmented Lagrangian Method with a Relative Error Criterion for a Class of Group-Quadratic Regularized Optimal Transport Problems
- Optimization models and approaches for strongly correlated electrons systems
- Polyhedral Newton-min algorithms for complementarity problems
- Optimization over convex polyhedra via Hadamard parametrizations
- An efficient algorithm for the _p norm based metric nearness problem
- An inexact semismooth Newton-based augmented Lagrangian algorithm for multi-task Lasso problems
- A Jacobian-free method for the nearest doubly stochastic matrix problem
- An inexact proximal DC algorithm for the large-scale cardinality constrained mean-variance model in sparse portfolio selection
- A semismooth Newton based augmented Lagrangian algorithm for Lovász theta SDP problem
This page was built for publication: On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2288199)
