L_p-norm regularization algorithms for optimization over permutation matrices
From MaRDI portal
\(L p\)-norm regularization algorithms for optimization over permutation matrices
Abstract: Optimization problems over permutation matrices appear widely in facility layout, chip design, scheduling, pattern recognition, computer vision, graph matching, etc. Since this problem is NP-hard due to the combinatorial nature of permutation matrices, we relax the variable to be the more tractable doubly stochastic matrices and add an -norm () regularization term to the objective function. The optimal solutions of the -regularized problem are the same as the original problem if the regularization parameter is sufficiently large. A lower bound estimation of the nonzero entries of the stationary points and some connections between the local minimizers and the permutation matrices are further established. Then we propose an regularization algorithm with local refinements. The algorithm approximately solves a sequence of regularization subproblems by the projected gradient method using a nonmontone line search with the Barzilai-Borwein step sizes. Its performance can be further improved if it is combined with certain local search methods, the cutting plane techniques as well as a new negative proximal point scheme. Extensive numerical results on QAPLIB and the bandwidth minimization problem show that our proposed algorithms can often find reasonably high quality solutions within a competitive amount of time.
Recommendations
Cites work
- scientific article; zbMATH DE number 3816913 (Why is no real title available?)
- scientific article; zbMATH DE number 3982880 (Why is no real title available?)
- scientific article; zbMATH DE number 1203226 (Why is no real title available?)
- scientific article; zbMATH DE number 714530 (Why is no real title available?)
- scientific article; zbMATH DE number 714537 (Why is no real title available?)
- scientific article; zbMATH DE number 3095897 (Why is no real title available?)
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- A Nonmonotone Line Search Technique and Its Application to Unconstrained Optimization
- A feasible method for optimization with orthogonality constraints
- A genetic approach to the quadratic assignment problem
- A greedy genetic algorithm for the quadratic assignment problem
- A level-2 reformulation-linearization technique bound for the quadratic assignment problem
- A new linearization method for quadratic assignment problems
- A note on the complexity of \(L _{p }\) minimization
- A smoothing SQP framework for a class of composite L_q minimization over polyhedron
- A survey for the quadratic assignment problem
- A survey of solved problems and applications on bandwidth, edgesum, and profile of graphs
- Algorithms for assignment problems on an array processor
- An efficient continuation method for quadratic assignment problems
- An implementation of the iterated tabu search algorithm for the quadratic assignment problem
- Assignment Problems and the Location of Economic Activities
- Comparison of iterative searches for the quadratic assignment problem
- Complexity analysis of interior point algorithms for non-Lipschitz and nonconvex minimization
- Compressed sensing
- Computing the Nearest Doubly Stochastic Matrix with A Prescribed Entry
- Convex relaxations for permutation problems
- Greedy randomized adaptive search procedures
- Handbook of combinatorial optimization. In 5 volumes
- Independent component analysis via nonparametric maximum likelihood estimation
- Iterative reweighted minimization methods for \(l_p\) regularized unconstrained nonlinear programming
- Joint Power and Admission Control: Non-Convex <formula formulatype="inline"><tex Notation="TeX">$L_{q}$</tex></formula> Approximation and An Effective Polynomial Time Deflation Approach
- Lower bound theory of nonzero entries in solutions of _2-_p minimization
- Nonmonotone Spectral Projected Gradient Methods on Convex Sets
- On bounding the bandwidth of graphs with symmetry
- On the Use of Exact and Heuristic Cutting Plane Methods for the Quadratic Assignment Problem
- Projected Barzilai-Borwein methods for large-scale box-constrained quadratic programming
- QAPLIB - a quadratic assignment problem library
- Recent advances in the solution of quadratic assignment problems
- Smallest compact formulation for the permutahedron
- Stable signal recovery from incomplete and inaccurate measurements
- The NP-completeness of the bandwidth minimization problem
- The Reactive Tabu Search
- The University of Florida sparse matrix collection
- The bandwidth problem for graphs and matrices—a survey
- The quadratic assignment problem
- Three Ideas for the Quadratic Assignment Problem
- Two-Point Step Size Gradient Methods
- Variable neighbourhood search for bandwidth reduction
Cited in
(9)- A quadratic penalty method for hypergraph matching
- Understanding the convergence of the preconditioned PDHG method: a view of indefinite proximal ADMM
- An exact penalty approach for optimization with nonnegative orthogonality constraints
- An extrapolated proximal iteratively reweighted method for nonconvex composite optimization problems
- A brief introduction to manifold optimization
- On the efficient computation of a generalized Jacobian of the projector over the Birkhoff polytope
- Enhanced joint sparsity via iterative support detection
- ADMM for the SDP relaxation of the QAP
- A time-triggered dimension reduction algorithm for the task assignment problem
This page was built for publication: \(L_p\)-norm regularization algorithms for optimization over permutation matrices
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2832890)
