A proximal DC approach for quadratic assignment problem
From MaRDI portal
Publication:2028476
Abstract: In this paper, we show that the quadratic assignment problem (QAP) can be reformulated to an equivalent rank constrained doubly nonnegative (DNN) problem. Under the framework of the difference of convex functions (DC) approach, a semi-proximal DC algorithm (DCA) is proposed for solving the relaxation of the rank constrained DNN problem whose subproblems can be solved by the semi-proximal augmented Lagrangian method (sPALM). We show that the generated sequence converges to a stationary point of the corresponding DC problem, which is feasible to the rank constrained DNN problem. Moreover, numerical experiments demonstrate that for most QAP instances, the proposed approach can find the global optimal solutions efficiently, and for others, the proposed algorithm is able to provide good feasible solutions in a reasonable time.
Recommendations
- A low-rank bilinear programming approach for sub-optimal solution of the quadratic assignment problem
- Comparison of Quadratic Convex Reformulations to Solve the Quadratic Assignment Problem
- Recent approaches to the quadratic assignment problem
- Solving quadratic assignment problems using convex quadratic programming relaxations
- scientific article; zbMATH DE number 5152705
Cites work
- A Copositive Programming Approach to Graph Partitioning
- A D.C. Optimization Algorithm for Solving the Trust-Region Subproblem
- A Lagrangian-DNN relaxation: a fast method for computing tight lower bounds for a class of quadratic optimization problems
- A Newton-CG augmented Lagrangian method for semidefinite programming
- A refined convergence analysis of \(\mathrm{pDCA}_{e}\) with applications to simultaneous sparse recovery and outlier detection
- A sequential semismooth Newton method for the nearest low-rank correlation matrix problem
- Alternating direction augmented Lagrangian methods for semidefinite programming
- An Invitation to Tame Optimization
- Assignment Problems and the Location of Economic Activities
- Bounds for the quadratic assignment problem using the bundle method
- Clarke Subgradients of Stratifiable Functions
- Convex Analysis
- Convex analysis approach to d. c. programming: Theory, algorithms and applications
- Copositive and semidefinite relaxations of the quadratic assignment problem
- DC programming and DCA: thirty years of developments
- Error bounds for rank constrained optimization problems and applications
- Exact penalty and error bounds in DC programming
- scientific article; zbMATH DE number 517393 (Why is no real title available?)
- Implicit Functions and Solution Mappings
- Lectures on modern convex optimization. Analysis, algorithms, and engineering applications
- Majorization-minimization procedures and convergence of SQP methods for semi-algebraic and tame programs
- Matrix Analysis
- Maxima for Graphs and a New Proof of a Theorem of Turán
- On doubly positive semidefinite programming relaxations
- On Lagrangian relaxation of quadratic matrix constraints
- On the convergence of the proximal algorithm for nonsmooth functions involving analytic features
- On the copositive representation of binary and continuous nonconvex quadratic programs
- P-Complete Approximation Problems
- Proximal alternating linearized minimization for nonconvex and nonsmooth problems
- Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality
- Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods
- Recent advances in the solution of quadratic assignment problems
- SDPNAL+: a majorized semismooth Newton-CG augmented Lagrangian method for semidefinite programming with nonnegative constraints
- SDPNAL+: A Matlab software for semidefinite programming with bound constraints (version 1.0)
- Semidefinite optimization
- Semidefinite Programming
- Semidefinite programming relaxations for the quadratic assignment problem
- Some NP-complete problems in quadratic and nonlinear programming
- Strong Duality for Semidefinite Programming
- The computational complexity of some problems of linear algebra
- The Łojasiewicz Inequality for Nonsmooth Subanalytic Functions with Applications to Subgradient Dynamical Systems
Cited in
(4)- An inexact proximal DC algorithm with sieving strategy for rank constrained least squares semidefinite programming
- Calmness of partial perturbation to composite rank constraint systems and its applications
- A matrix nonconvex relaxation approach to unconstrained binary polynomial programs
- Numerical reduction method for doubly nonnegative optimization problems
This page was built for publication: A proximal DC approach for quadratic assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2028476)
