Title Stochastic Approximation Applications Mathematical Optimization Continuous Function Mathematical Analysis Physics & Mathematics Mathematics 6.2 MB 369
##### Document Text Contents
Page 184

172 STOCHASTIC APPROXIMATION AND ITS APPLICATIONS

Remark 4.2.2 Results in Sections 4.1 and 4.2 are proved for the case,

where the two-sided randomized differences are
used where and are given by (4.1.3) and (4.1.4), respectively.
But, all results presented in Sections 4.1 and 4.2 are also valid for the
case where the one-sided randomized differences

are used, where and are given by (4.1.3) and (4.1.6), respec-
tively.

In this case, in (4.1.27), (4.1.28) and in the expression of should
be replaced by 1, and (4.1.29)–(4.1.32) disappear. Accordingly, (4.1.36)
changes to

Theorems 4.1.1-4.1.4 and 4.2.1 remain unchanged. The conclusion of

Theorem 4.2.2 remains valid too, if in Condition iv)

changes to

4.3. Global Optimization
As pointed out at the beginning of the chapter, the KW algorithm may

lead to a local minimizer of Before the 1980s, the random search
or its combination with a local search method was the main stochastic
approach to achieve the global minimum when the values of L can exactly
be observed without noise. When the structural property of L is used
for local search, a rather rapid convergence rate can be derived, but it
is hard to escape a local attraction domain. The random search has
a chance to fall into any attraction domain, but its convergence rate
decreases exponentially as the dimension of the problem increases.

Simulating annealing is an attractive method for global optimization,
but it provides only convergence in probability rather than path-wise
convergence. Moreover, simulation shows that for functions with a few
local minima, simulated annealing is not efficient. This motivates one
to combine KW-type method with random search. However, a simple
combination of SA and random search does not work: in order to reach
the global minimum one has to reduce the noise effect as time goes on.

A hybrid algorithm composed of a search method and the KW algo-
rithm is presented in the sequel with main effort devoted to design eas-

Page 185

Optimization by Stochastic Approximation 173

ily realizable switching rules and to provide an effective noise-reducing
method.

We define a global optimization algorithm, which consists of three
parts: search, selection, and optimization. To be fixed, let us discuss
the global minimization problem. In the search part, we choose an ini-
tial value and make the local search by use of the KW algorithm with
randomized differences and expanding truncations described in Section
4.1 to approach the bottom of the local attraction domain. At the same
time, the average of the observations for L is used to serve as an estimate
of the local minimum of L in this attraction domain. In the selection
part, the estimates obtained for the local minima of L are compared with
each other, and the smallest one among them together with the corre-
sponding minimizer given by the KW algorithm are selected. Then, the
optimization part takes place, where again the local search is carried out,
i.e., the KW algorithm without any truncations is applied to improve
the estimate for the minimizer. At the same time, the corresponding
minimum of L is reestimated by averaging the noisy observations. After
this, the algorithm goes back to the search part again.

For the local search, we use observations (4.1.3) and (4.1.4), or (4.1.5)
and (4.1.6). To be fixed, let us use (4.1.5) and (4.1.6).

In the sequel, by KW algorithm with expanding truncations we mean
the algorithm defined by (4.1.11) and (4.1.12) with

where and are given by (4.1.5) and (4.1.6), respectively. Sim-
ilar to (4.1.9) and (4.1.10) we have

where

By KW algorithm we mean

with defined by (4.3.2).
It is worth noting that unlike (4.1.8), is used in (4.3.1).

Roughly speaking, this is because in the neighborhood of a miminizer

of is increasing, and in (4.1.11) should be an
observation on

Page 368

Nonconvex Optimization and Its Applications

22.

23.

24.

25.

26.

27.

28.

29.

30.

31.

32.

33.

34.

35.

36.

37.

38.

39.

40.

41.

42.

43.

H. Tuy: Convex Analysis and Global Optimization. 1998 ISBN 0�7923�4818�4

D. Cieslik: Steiner Minimal Trees. 1998 ISBN 0�7923�4983�0
N.Z. Shor: Nondifferentiable Optimization and Polynomial Problems. 1998

ISBN 0�7923�4997�0

R. Reemtsen and J.�J. Rückmann (eds.): Semi�Infinite Programming. 1998

ISBN 0�7923�5054�5

B. Ricceri and S. Simons (eds.): Minimax Theory and Applications. 1998

ISBN 0�7923�5064�2

J.�P. Crouzeix, J.�E. Martinez�Legaz and M. Volle (eds.): Generalized Convexitiy,
Generalized Monotonicity: Recent Results. 1998 ISBN 0�7923�5088�X

J. Outrata, M. Kočvara and J. Zowe: Nonsmooth Approach to Optimization Problems

with Equilibrium Constraints. 1998 ISBN 0�7923�5170�3

D. Motreanu and P.D. Panagiotopoulos: Minimax Theorems and Qualitative Proper�

ties of the Solutions of Hemivariational Inequalities. 1999 ISBN 0�7923�5456�7

J.F. Bard: Practical Bilevel Optimization. Algorithms and Applications. 1999

ISBN 0�7923�5458�3

H.D. Sherali and W.P. Adams: A Reformulation�Linearization Technique for Solving

Discrete and Continuous Nonconvex Problems. 1999 ISBN 0�7923�5487�7

F. Forgó, J. Szép and F. Szidarovszky: Introduction to the Theory of Games. Concepts,
Methods, Applications. 1999 ISBN 0�7923�5775�2

C.A. Floudas and P.M. Pardalos (eds.): Handbook of Test Problems in Local and

Global Optimization. 1999 ISBN 0�7923�5801�5

T. Stoilov and K. Stoilova: Noniterative Coordination in Multilevel Systems. 1999

ISBN 0�7923�5879�1

J. Haslinger, M. Miettinen and P.D. Panagiotopoulos: Finite Element Method for

Hemivariational Inequalities. Theory, Methods and Applications. 1999

ISBN 0�7923�5951�8

V. Korotkich: A Mathematical Structure of Emergent Computation. 1999

ISBN 0�7923�6010�9

C.A. Floudas: Deterministic Global Optimization: Theory, Methods and Applications.

2000 ISBN 0�7923�6014�1

F. Giannessi (ed.): Vector Variational Inequalities and Vector Equilibria. Mathemat�

ical Theories. 1999 ISBN 0�7923�6026�5

D. Y. Gao: Duality Principles in Nonconvex Systems. Theory, Methods and Applica�

tions. 2000 ISBN 0�7923�6145�3

C.A. Floudas and P.M. Pardalos (eds.): Optimization in Computational Chemistry

and Molecular Biology. Local and Global Approaches. 2000 ISBN 0�7923�6155�5

G. Isac: Topological Methods in Complementarity Theory. 2000 ISBN 0�7923�6274�8

P.M. Pardalos (ed.): Approximation and Complexity in Numerical Optimization: Con�

crete and Discrete Problems. 2000 ISBN 0�7923�6275�6

V. Demyanov and A. Rubinov (eds.): Quasidifferentiability and Related Topics. 2000

ISBN 0�7923�6284�5

Page 369

Nonconvex Optimization and Its Applications

44.

45.

46.
47.

48.

49.

50.

51.

52.

53.

54.

55.

56.

57.

58.

59.

60.

61.
62.

63.

A. Rubinov: Abstract Convexity and Global Optimization. 2000
ISBN 0-7923-6323-X

R.G. Strongin and Y.D. Sergeyev: Global Optimization with Non-Convex Constraints.
2000 ISBN 0-7923-6490-2
X.-S. Zhang: Neural Networks in Optimization. 2000 ISBN 0-7923-6515-1
H. Jongen, P. Jonker and F. Twilt: Nonlinear Optimization in Finite Dimen-
sions. Morse Theory, Chebyshev Approximation, Transversability, Flows, Parametric
Aspects. 2000 ISBN 0-7923-6561-5
R. Horst, P.M. Pardalos and N.V. Thoai: Introduction to Global Optimization. 2nd
Edition. 2000 ISBN 0-7923-6574-7
S.P. Uryasev (ed.): Probabilistic Constrained Optimization. Methodology and
Applications. 2000 ISBN 0-7923-6644-1
D.Y. Gao, R.W. Ogden and G.E. Stavroulakis (eds.): Nonsmooth/Nonconvex Mech-
anics. Modeling, Analysis and Numerical Methods. 2001 ISBN 0-7923-6786-3
A. Atkinson, B. Bogacka and A. Zhigljavsky (eds.): Optimum Design 2000. 2001

ISBN 0-7923-6798-7
M. do Rosário Grossinho and S.A. Tersian: An Introduction to Minimax Theorems
and Their Applications to Differential Equations. 2001 ISBN 0-7923-6832-0
A. Migdalas, P.M. Pardalos and P. Värbrand (eds.): From Local to Global Optimiza-
tion. 2001 ISBN 0-7923-6883-5
N. Hadjisavvas and P.M. Pardalos (eds.): Advances in Convex Analysis and Global
Optimization. Honoring the Memory of C. Caratheodory (1873-1950). 2001

ISBN 0-7923-6942-4
R.P. Gilbert, P.D. Panagiotopoulos† and P.M. Pardalos (eds.): From Convexity to
Nonconvexity. 2001 ISBN 0-7923-7144-5
D.-Z. Du, P.M. Pardalos and W. Wu: Mathematical Theory of Optimization. 2001

ISBN 1-4020-0015-4
M.A. Goberna and M.A. López (eds.): Semi-Infinite Programming. Recent Advances.
2001 ISBN 1-4020-0032-4
F. Giannessi, A. Maugeri and P.M. Pardalos (eds.): Equilibrium Problems: Nonsmooth
Optimization and Variational Inequality Models. 2001 ISBN 1-4020-0161-4
G. Dzemyda, V. Šaltenis and A. Žilinskas (eds.): Stochastic and Global Optimization.
2002 ISBN 1-4020-0484-2
D. Klatte and B. Kummer: Nonsmooth Equations in Optimization. Regularity, Cal-
culus, Methods and Applications. 2002 ISBN 1-4020-0550-4
S. Dempe: Foundations of Bilevel Programming. 2002 ISBN 1-4020-0631-4
P.M. Pardalos and H.E. Romeijn (eds.): Handbook of Global Optimization, Volume
2. 2002 ISBN 1-4020-0632-2
G. Isac, V.A. Bulavsky and V.V. Kalashnikov: Complementarity, Equilibrium, Effi-
ciency and Economics. 2002 ISBN 1-4020-0688-8

KLUWER ACADEMIC PUBLISHERS – DORDRECHT / BOSTON / LONDON