Neural Networks without Training for Optimization - Neural Networks: Methodology and Applications - page 482

doubly stochastic matrices, derived from the two following theorems [Sinkhorn
1964].
A doubly stochastic matrix is a matrix with real positive coe cients, such
that the sum of the coe cients of each row and of each column is equal to 1.
Theorem 1. To a strictly positive N

N matrix corresponds exactly a doubly
stochastic matrix T A which can be expressed under the form T A = D 1 AD 2 ,
where D 1 and D 2 are positive diagonal matrices. Matrices D 1 and D 2 are
unique, within a scalar factor.
Theorem 2. The alternative normalization of rows and columns of a strictly
positive N

×

× N matrix converges to a strictly positive doubly stochastic matrix.

Remark 1. That normalization consists, when considering an element of the
matrix, in dividing it successively by the sum of the row coe cients, and then
by the sum of the column coe cients.

Therefore, theorem 2 is a projection algorithm on the space of doubly
stochastic matrices. Combined with an analog annealed recurrent neural net-
work, it provides a powerful algorithm that guarantees the convergence of the
network to a valid solution (coded by a permutation matrix) of good quality.

Example of the TSP

Let us consider the TSP with the same coding as the one used by a Hopfield
network (permutation matrix coded by the neuron outputs).
The energy function is defined as follows:

N N N N N

γ
2

y 2
i,j

E = d i,k y i,j y k,j⊕ 1 − ,

i =1 j =1 i =1 j =1

k =1
k = i

where γ is a strictly positive real number.
The second term in this equation is called auto-amplification term; it is
useful to avoid converging to a null matrix.
The motion equation of an analog neuron ( i , j ) is defined by

N

d v i,j
d t

d E
d y i,j

= − = − d i,k y k,j⊕ 1 + γy i,j .

k =1
k = i

To enforce the strict positivity of the neuron outputs, the authors use an
exponential activation function instead of a sigmoid function,

y i,j =exp( βv i,j ) ,
where β is a positive real number.
The dynamics of that analog neural network can be either synchronous,
or random asynchronous. After an update of the neurons, the outputs are
projected on a close doubly stochastic matrix by an alternative normalization
of rows and columns: