Related Experiment Video
Updated: Jul 13, 2026

Operation of the Collaborative Composite Manufacturing (CCM) System
Published on: October 1, 2019
Convergence properties of the softassign quadratic assignment algorithm
A Rangarajan1, A Vuille, E Mjolsness
1Department of Diagnostic Radiology, 332 BML, Yale University, School of Medicine, 333 Cedar Street, New Haven, CT 06520-8042, USA.
Abstract:
The softassign quadratic assignment algorithm is a discrete-time, continuous-state, synchronous updating optimizing neural network. While its effectiveness has been shown in the traveling salesman problem, graph matching, and graph partitioning in thousands of simulations, its convergence properties have not been studied. Here, we construct discrete-time Lyapunov functions for the cases of exact and approximate doubly stochastic constraint satisfaction, which show convergence to a fixed point. The combination of good convergence properties and experimental success makes the softassign algorithm an excellent choice for neural quadratic assignment optimization.
Related Concept Videos
Convolution Properties I
The commutative property reveals that the input and the impulse response of an LTI (Linear Time-Invariant) system can be interchanged without affecting the output:
Quadratic Equations
Application of Nonlinear Inequalities
Lagrange Multipliers: One Constraint
Lagrange Multipliers: Two Constraints
Lagrange Multipliers: Problem Solving