10.2 Optimization Methods 287
simplex algorithm [23, 24, 22, 25, 26]. In principle, this algorithm starts from
a randomly chosen corner u
(k)
with the initial label k = 0. Then, a second
corner u
is chosen, so that (i) u
is the topological neighbor of u
(k)
and (ii)
H(u
) >H(u
(k)
). If such a corner was found, we set u
(k+1)
= u
and repeat
the algorithm. If no further u
can be detected so that both conditions are
fulfilled, the currently reached corner corresponds to the global maximum so-
lution. If the set G is nonconvex, it may be possible to separate the region
to exhaustive and mutually exclusive convex subsets G
i
and solve the linear
programming problem for each G
i
separately. The global maximum is then
the maximum of all local maxima related to the subsets.
10.2.4 Combinatorial Optimization Problems
If the control state has only discrete values, we speak about a combinatorial
optimization problem. Such problems play an important role for several tech-
nological and physical applications. A standard example is the so-called Ising
model. Usually, the Ising model is described by a physical is described by a
physical Hamiltonian given by
H = H
0
(X)+
n
i,j=1
J
ij
(X)S
i
S
j
+
n
i=1
B
i
S
j
(10.30)
where S
i
are the discrete spin variables, and B
i
is denoted as the local field
and J
ij
as the coupling constants. The physical standard problem is the de-
termination of the ground state of H or alternatively, the thermodynamical
weight of a spin configuration {S
1
,...,S
i
,...}. This is of course a repeatedly
investigated problem in the context of spin glasses [27, 28, 29, 30, 31, 32],
protein folding [33, 34, 35], or phase transitions in spin systems [36, 37, 38]
and it is strongly connected with the concept of optimization. However, this
is no real control problem.
But a control problem occurs if we are interested in the inverse situation.
Usually, the physical degrees of freedom represented by the spin variables S
i
are coupled with another set of internal degrees of freedom X. These quanti-
ties are assumed to be passive for the above mentioned spin dynamics, i.e., X
determines the coupling constants J
ij
(X) and the spin-independent contribu-
tion H
0
(X), but for a given physical problem X is assumed to be fixed. But
we may also ask for the dynamics of X under a certain spin configuration.
Then, the Hamiltonian (10.30), leads to evolution equations of the form
˙
X = F
(0)
(X)+
n
i,j=1
F
(1)
ij
(X)S
i
S
j
(10.31)
where we may identify the discrete spin variables as components of the n-
component control u. From here, we obtain, for example via the deterministic
Hamiltonian (2.94) or the corresponding stochastic version (7.65) a classical
combinatorial optimization problem.