In the above presentation, the DAM is generally
viewed as a stable monlinear dynamical system which performs associative
retrievals of stored vectors/memories from noisy initial states.
The fundamental idea is to store a set of desired memories as
local minima of an energy function which is minimized by the DAM's
dynamics. Memory storage is achieved by using recording recipes
which result in the proper synthesis of DAM parameters (weights).

The notion of minimizing an energy function by a
dynamical system (especially a physically realizable one) has
important implications to the solution of optimization problems.
Here, a stable dynamical system is designed whose energy function
*E*(**x**) matches the cost/objective function *J*
of a given optimization problem. Then, this dynamical system
is initialized at a random state **x**(0) and is allowed to
relax to a solution **x***.
This solution may be viewed as a solution to the optimization
problem. The degree of optimality of the solution **x***
does not depend on the initial state **x**(0) if the dynamical
system used has global search capability. Unfortunately, no design
methodology is available for designing such a stable dynamical
system for optimization problems of practical significance.

Gradient dynamical systems are often used to generate
solutions to optimization problems (Cichocki and Unbehauen, 1993)
because of their potential realization via physical systems and
their intrinsic stability. However, gradient systems are only
capable of local (gradient-based) search and thus the quality
of the solutions they generate depends greatly on the initial
state of the system. This problem may be partially treated if
fast analog hardware (or a fast parallel computer) is used to
implement the gradient system; this leads to fast convergence
time ranging from nanoseconds to microseconds and allows running
the system many times from different initial conditions, within
a short period of time, and may eventually lead to high quality
solutions.

One particular class of optimization problems frequently
encountered in many branches of science and technology consists
of problems with combinatorial complexity. Such problems have
a finite set of possible solutions but which scales exponentially
or factorially in problem size *n* (dimension of **x**).
Because of the combinatorial nature of these problems the time
needed to solve any one of them scales exponentially, thus making
the solution intractable for large *n* (for an example, the
reader is referred to the traveling salesman problem described
at the end of Section 3.5.3. See also Problem 7.5.3). These
problems are known as nondeterministic polynomial-time-complete
(NP-complete) for which no algorithm is known which provides the
global minimal solution in a polynomial computational time (Papadimitriou
and Steiglitz, 1982; Garey and Johnson, 1979). Heuristic algorithms
with polynomial-time complexity have been developed which provide
sub-optimal solutions to NP-complete problems (e.g., see Simeone,
1989). Unfortunately, these heuristic algorithms are problem-specific
and their sequential search nature prevents their implementation
on fast parallel computers or in hardware.

Many combinatorial optimization problems can be
cast as a problem of minimizing the sum of a cost term and a constraints
satisfaction term according to

*J* = (*cost term*) + (*constraints
satisfaction terms*) (7.5.1)

Furthermore, for a wide range of practical problems,
the objective function *J* can be put in the form of or approximated
by the quadratic function (Hopfield and Tank, 1985)

(7.5.2)

where **W** is a symmetric zero-diagonal real-valued
matrix and = [*I*1 *I*2 ... *I**n*]T
is a bias vector. Here, **W** and are determined by the optimization
problem to be solved. The vector **x** usually has binary
components, **x** {-1, +1}*n*
(or {0, 1}*n*),
reflecting the combinatorial nature of the problem.

The cost function *J* in Equation (7.5.2) has
the same functional form as the energy function in Equation (7.1.24)
minimized by the discrete Hopfield DAM. The cost function *J*
is also approximately equal to the energy function of the continuous-time
continuous-state Hopfield net (Equation (7.1.23) in the limit
of large amplifier gain . This suggests that one may map the
cost function in Equation (7.5.2) onto a Hopfield DAM and let
the DAM relax to a local minimum of this cost function, hoping
that such a local minimum is a good solution to the optimization
problem at hand. In practice, the continuous model is more preferable
than the discrete model since it can avoid some of the numerous
poor local minima of *J* (located at vertices of the hypercube
) encountered by the discrete model. When the continuous Hopfield
net is used, the amplifier gains are initially set to a value
close to 1 so that sufficient time is given for the net to "explore"
the solution space before converging to a vertex solution. After
some time, though, the gains should be gradually increased in
order to force all local minima of the network's energy to move
to corners of the hypercube where the desired solutions are located.
This gradual increase in gain is known as "hardware annealing"
(Lee and Shen, 1991. Also see Section 8.4.1). Another technique
is to add to the cost function *J* (and thus to the energy
function *E*) an additional quadratic constraint satisfaction
(penalty) term which is equal to zero only if *x**i* {-1, +1}
for all *i*.

With finite gain, the continuous Hopfield net may
be viewed as a gradient system in terms of the Energy function
*E*(**x**) of Equation (7.1.23). Formally,

(7.5.3)

where , *i* > 0
are as defined in Section 7.1.2. Writing Equation (7.5.3) in
terms of the cost function *J* to be minimized gives

(7.5.4)

Solving for the partial derivative term in Equation
(7.5.4) leads to

(7.5.5)

Now, the time derivative of *J*(**x**) is

(7.5.6)

Where Equation (7.5.5) was used. The first term
on the right hand side of Equation (7.5.6) is always positive.
However, the second term can become positive and, therefore,
may become positive. This means that Equation (7.5.3) is not
a gradient system in *J* unless the decay terms are eliminated
(Takefuji and Lee, 1991). This can be physically accomplished
by assuming lossless amplifiers in the Hopfield net. With all
*i* = 0,
the Hopfield net's dynamics reduce to the stable gradient system

(7.5.7)

To summarize, the lossless amplifier Hopfield net
whose energy function is exactly matched to a quadratic objective
function *J*(**x**) is guaranteed to converge to a local
minimum of *J*. It should be noted here that the cost and
the constraint satisfaction terms comprising *J* compete
with each other and may develop local minima in *J* which
may violate one or more constraints (in which case the solution
is not acceptable) or may satisfy all constraints at the expense
of suboptimal solutions.

This section is concluded by an illustrative example
of mapping an objective function representing a simple computational
task onto a continuous Hopfield net. Problems 7.5.2 and 7.5.3
further explore the ideas of this section. A large body of research
on, and applications of the Hopfield net have appeared since the
original introduction of the idea of optimization via gradient
neural-like nets by Hopfield and Tank (1985) ,(see also Tank and
Hopfield, 1986). A good sample of this research can be found
in the books by Hertz et al. (1991), and Cichocki and Unbehauen
(1993). See also Watta (1994) for an extension of the Hopfield
net idea to constrained mixed integer optimization problems.

**Example 7.5.1:**
Design of a 2-bit A/D converter

The objective in this example is to demonstrate
via a specific simple example the procedure for mapping a computational
(optimization) task onto a continuous Hopfield net, thus resulting
in a fast parallel analog implementation of the desired task.
The computational task here is to convert a continuous analog
signal into its 2-bit binary representation (*x*0, *x*1)
where *x*0 is the
least significant bit. First, the problem is expressed in terms
of a quadratic objective function *J*(*x*0, *x*1).
The main objective here is for the equivalent decimal value of
the desired digital representation of *z* to be as close
as possible to the analog value of *z*. In other words,
it is desired to minimize the quantity . Furthermore, it is important
that the variables *x*0
and *x*1 take on
unipolar binary values. This can be accomplished by minimizing
the constraint satisfaction terms *x*1(1 - *x*1)
and *x*0(1 - *x*0).
Therefore, a suitable objective function is given by (note the
intentional quadratic nature of *J*)

(7.5.8)

Equation (7.5.8) should now be minimized. Expanding
*J* gives

(7.5.9)

Since *J* should ultimately match a Hopfield
net's energy function which has no and terms, the last two terms
on the right-hand side of Equation (7.5.9) must vanish. This
is accomplished by choosing and . The term is not a function
of the states *x*0
and *x*1 and its
presence only shifts *J* by a positive amount. Thus, the
term can be deleted without affecting the local minima of *J*.
Hence, the following alternative objective function may be used:

(7.5.10)

Because of the unipolar nature of *x*0
and *x*1, the transfer
function of the Hopfield net amplifiers will be assumed to have
the following unipolar sigmoidal form:

(7.5.11)

Now, by matching the net's energy function given
by (here, *w*00 = *w*11 = 0,
*w*01 = *w*10,
and high amplifier gain are assumed):

(7.5.12)

to *J* in Equation (7.9.10), one gets *w*10 = *w*01 = -2,
*I*0 = *z* - ,
and *I*1 = 2(*z* - 1).
According to Equations (7.5.7) and (7.5.10), the network dynamics
are given by (assuming )

(7.5.13)

Finally, a circuit realization of this system is
given in Figure 7.5.1 (Actually, this circuit does not exactly
model the dynamics in Equation (7.5.13). See Problem 7.5.1 for
further exploration into this matter).