ńņš. 8 |

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

148 ITERATIVE METHODS FOR OPTIMIZATION

Step 3b requires care in implementation. If sf = 0 on exit from the ļ¬rst call to hjexplore,

one should only test f at those points on the stencil centered at x that have not been evaluated

before.

The Hookeā“Jeeves algorithm simply calls hjsearch repeatedly as h varies over a sequence

{hk } of scales.

Algorithm 8.3.3. hooke(x, f, {hk })

1. For k = 1, . . .

Call hjsearch(x, f, hk )

As is the case with implicit ļ¬ltering, the Hookeā“Jeeves algorithm can be applied to bound

constrained problems in a completely natural way [145], [227] by simply restricting the stencil

points to those that satisfy the bounds and avoiding pattern moves that leave the feasible region.

The Hookeā“Jeeves algorithm shares with implicit ļ¬ltering the property that extension to

bound constrained problems is trivial [145]. One simply restricts the exploratory and pattern

moves to the feasible set.

8.3.2 Convergence and the Simplex Gradient

As with MDS, if the set of sampling points remains bounded, only ļ¬nitely many explorations

can take place before hjsearch returns and the scale must be reduced. The conditions for

reduction in the scale include failure of an exploratory move centered at the current best point x.

This means that we can apply Theorem 6.2.9 with Īŗ+ = 1 to prove the same result we obtained

for MDS.

Theorem 8.3.1. Let f satisfy (6.1). Let {xk } be the sequence of Hookeā“Jeeves best points.

Assume that the set

{x | f (x) ā¤ f (x0 )}

is bounded. Then let hk ā’ 0 and if

Ļ Bk

lim = 0,

kā’ā Ļ+ (S k )

where B k is the ball of radius 2hk about xk , then every limit point of {xk } is a critical point of

fs .

8.4 Other Approaches

In this section we brieļ¬‚y discuss two methods that have been used successfully for noisy prob-

lems. These methods are substantially more difļ¬cult to implement than the ones that we have

discussed so far and we will give few details. The pointers to the literature are a good starting

place for the interested and energetic reader.

8.4.1 Surrogate Models

As any sampling method progresses, the function values can be used to build a (possibly)

quadratic model based, for example, on interpolation or least squares ļ¬t-to-data. Such mod-

els are called surrogates or response surfaces. Even for smooth f there are risks in doing this.

Points from early in the iteration may corrupt an accurate model that could be built from the

more recent points; however, the most recent points alone may not provide a rich enough set of

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 149

interpolatory data. The function being modeled could be too complex to be modeled in a sim-

ple way (think of the Lennardā“Jones function), and very misleading results could be obtained.

However, this approach is often very productive even for smooth problems in which evaluation

of f is very expensive (see [28] for a high-ļ¬‚ying example).

Initialization of the model requires an initial set of points at which to sample f . Selection of

this point set is not a trivial issue, and the regular stencils used in implicit ļ¬ltering and the direct

search algorithms are very poor choices. The study of this issue alone is a ļ¬eld in itself, called

design and analysis of computer experiments (DACE) [27], [167], [230].

Having built such a model, one then ļ¬nds one or more local minima of the model. One can

use either a conventional gradient-based method, a sampling algorithm of the type discussed in

Chapters 7 or 8, or an algorithm that is itself based on building models like the one described in

[62], the nongradient-based approaches being used when the model is expected to be multimodal

or nonconvex. Upon minimizing the model, one then evaluates f again at one or more new points.

The implementation of such a scheme requires careful coordination between the sampling

of the function, the optimization of the model, and the changing of the set of sample points. We

refer the reader to [28] and [4] for more information on recent progress in this area.

8.4.2 The DIRECT Algorithm

Suppose f is a Lipschitz continuous function on [a, b] with Lipschitz constant L. If one has a

priori knowledge of L, one can use this in a direct search algorithm to eliminate intervals of

possible optimal points based on the function values at the endpoints of these intervals. The

Shubert algorithm [146], [214], [241] is the simplest way to use this idea. The method begins

with the fact that

f (x) ā„ flow (x, a, b) = max(f (a) ā’ L(x ā’ a), f (b) ā’ L(b ā’ x))

(8.11)

for all x ā [a, b]. If one samples f repeatedly, one can use (8.11) on a succession of intervals

and obtain a piecewise linear approximation to f . If In = [an , bn ] ā‚ [a, b] then f (x) ā„

flow (x, an , bn ) on In , the minimum value of flow (x, an , bn ) is

Vn = (f (an ) + f (bn ) ā’ L(bn ā’ an ))/2,

and the minimizer is

Mn = (f (an ) ā’ f (bn ) + L(bn + an ))/(2L).

The algorithm begins with I0 = [a, b], selects the interval for which Vn is least, and divides at

Mn . This means that if K intervals have been stored we have, replacing In and adding IK+1 to

the list,

In = [an , Mn ] and IK+1 = [Mn , bn ].

The sequence of intervals is only ordered by the iteration counter, not by location. In this way

the data structure for the intervals is easy to manage.

If there are p and k such that p = k and Vp ā„ max(f (ak ), f (bk )), then Ip need not be

searched any longer, since the best value from Ip is worse than the best value in Ik . The

algorithmā™s rule for division automatically incorporates this information and will never sample

from Ip .

There are two problems with this algorithm. One cannot expect to know the Lipschitz

constant L, so it must be estimated. An estimated Lipschitz constant that is too low can lead to

erroneous rejection of an interval. An estimate that is too large will lead to slow convergence,

since intervals that should have been discarded will be repeatedly divided. The second problem

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

150 ITERATIVE METHODS FOR OPTIMIZATION

10

9

8

7

6

5

4

3

2

1

0

0 1 2 3 4 5 6 7

Figure 8.10: Selection of Intervals in DIRECT

is far more serious. The obvious generalization of the Shubert algorithm to more than one

dimension would replace intervals by N -dimensional hyperrectangles and require sampling at

each of the 2N vertices of the rectangle to be divided. This exponential complexity makes this

trivial generalization of the Shubert algorithm completely impractical.

The DIRECT algorithm [150] attempts to address these problems by sampling at the midpoint

of the hyperrectangle rather than the vertices and indirectly estimating the Lipschitz constant as

the optimization progresses. The scheme is not completely successful in that the mesh of sample

points becomes everywhere dense as the optimization progresses. Hence the algorithm becomes

an exhaustive search, a fact that is used in [150] to assert global convergence. In spite of the

exponential complexity of exhaustive search, even one with a ļ¬xed-size mesh (a problem with

any deterministic algorithm that is truly global [248]), DIRECT has been reported to perform well

in the early phases of the iteration [150], [108] and for suites of small test problems. DIRECT is

worth consideration as an intermediate algorithmic level between methods like implicit ļ¬ltering,

Nelderā“Mead, Hookeā“Jeeves, or MDS on the conservative side and nondeterministic methods

like simulated annealing or genetic algorithms on the radical side.

We will describe DIRECT completely only for the case N = 1. This will make clear how

the algorithm implicitly estimates the Lipschitz constant. The extension to larger values of N

requires careful management of the history of subdivision of the hyperrectangles, and we will give

a simple pictorial account of that. For more details we refer to [150], [147], or the documentation

[108] of the FORTRAN implementation of DIRECT from the software collection.

As with the Shubert algorithm we begin with an interval [a, b] but base our lower bound and

our subdivision strategy on the midpoint c = (a + b)/2. If the Lipschitz constant L is known

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 151

then

f (x) ā„ f (c) ā’ L(b ā’ a)/2.

If we are to divide an interval and also retain the current value c as the midpoint of an interval

in the set of intervals, we must divide an interval into three parts. If there are K intervals on

the list and an interval In = [an , bn ] with midpoint cn has been selected for division, the new

intervals are

IK+1 = [an , an + (bn ā’ an )/3], In = [an + (bn ā’ an )/3, bn ā’ (bn ā’ an )/3], and

IK+2 = [bn ā’ (bn ā’ an )/3, bn ].

So cn is still the midpoint of In and two new midpoints have been added.

The remaining part of the algorithm is the estimation of the Lipschitz constant and the

simultaneous selection of the intervals to be divided. If the Lipschitz constant were known, an

interval would be selected for division if f (c) ā’ L(b ā’ a)/2 were smallest. This is similar to

the Shubert algorithm. In order for there to even exist a Lipschitz constant that would force

an interval to be selected for division in this way, that interval must have the smallest midpoint

value of all intervals having the same length. Moreover, there should be no interval of a different

length for which f (c) ā’ L(b ā’ a)/2 was smaller.

The DIRECT algorithm applies this rule to all possible combinations of possible Lipschitz

constants and interval sizes. If one plots the values of f at the midpoints against the lengths of

the intervals in the list to obtain a plot like the one in Figure 8.10, one can visually eliminate

all but one interval for each interval length. By taking the convex hull of the lowest points, one

can eliminate interval lengths for which all function values are so high that f (c) ā’ L(b ā’ a)/2

would be smaller for the best point at a different length no matter what L was. For example, the

three points that intersect the line in Figure 8.10 would correspond to intervals that would be

subdivided at this step. The slopes of the line segments through the three points are estimates

of the Lipschitz constant. These estimates are not used explicitly, as they would be in the

Shubert algorithm, but implicitly in the process of selection of intervals to be divided. Unlike

the Shubert algorithm, where the Lipschitz constant is assumed known, the DIRECT algorithm

will eventually subdivide every interval.

The resulting algorithm may divide more than a single interval at each stage and the number

of intervals to be divided may vary. This is easy to implement for a single variable. However,

for more than one variable there are several ways to divide a hyperrectangle into parts and one

must keep track of how an interval has previously been divided in order not to cluster sample

points prematurely by repeatedly dividing an interval in the same way. Figures 8.11 and 8.12,

taken from [108], illustrate this issue for N = 2. In Figure 8.11 the entire rectangle will be

divided. Shading indicates that the rectangle has been selected for division. Four new midpoints

are sampled. The subdivision into new rectangles could be done in two ways: the ļ¬gure shows

an initial horizontal subdivision followed by a vertical division of the rectangle that contains the

original center. The second division is shown in Figure 8.12. The two shaded rectangles are

selected for division. Note that four new centers are added to the small square and two to the

larger, nonsquare, rectangle. In this way the minimum number of new centers is added.

DIRECT parallelizes in a natural way. All hyperrectangles that are candidates for division

may be divided simultaneously, and for each hyperrectangle the function evaluations at each of

the new midpoints can also be done in parallel. We refer the reader to [150] and [108] for details

on the data structures and to [108] for a FORTRAN implementation and additional discussion

on the exploitation of parallelism.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

152 ITERATIVE METHODS FOR OPTIMIZATION

6 6 6

5 9 8 5 9 8 5 9 8

2 2 2

Figure 8.11: Initial Division of Rectangles with DIRECT

6 6 6

9 9

5 9 8 7 5 6 9 8 7 5 6 9 8

4 4

2 3 2 6 3 2 6

Figure 8.12: Second Division of Rectangles with DIRECT

8.5 Examples

In each of the examples we compare the central difference BFGS form of implicit ļ¬ltering from

Ā§7.6 (solid line) with the Nelderā“Mead (dashed line), Hookeā“Jeeves (solid line with circles), and

MDS (dashed-dotted line) algorithms.

For each example we speciļ¬ed both an initial iterate and choice of scales. This is sufļ¬cient

to initialize both implicit ļ¬ltering and Hookeā“Jeeves. We used the implicit ļ¬ltering forward

difference stencil as the initial simplex for both Nelderā“Mead and MDS.

The plots reļ¬‚ect the differences in the startup procedures for the varying algorithms. In

particular, Nelderā“Mead and MDS sort the simplex and hence, if the initial iterate is not the best

point, report the lower value as the ļ¬rst iterate.

The relative performance of the various methods on these example problems should not be

taken as a deļ¬nitive evaluation, nor should these examples be thought of as a complete suite of test

problems. One very signiļ¬cant factor that is not reļ¬‚ected in the results in this section is that both

implicit ļ¬ltering [69], [55] and multidirectional search [85] are easy to implement in parallel,

while Nelderā“Mead and Hookeā“Jeeves are inherently sequential. The natural parallelism of

implicit ļ¬ltering and multidirectional search can be further exploited by using idle processors to

explore other points on the line search direction or the pattern.

8.5.1 Weberā™s Problem

The initial data were the same as that in Ā§7.6.1. Implicit ļ¬ltering does relatively poorly for this

problem because of the nonsmoothness at optimality. The resluts for these problems are plotted

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 153

ā’80

ā’100

ā’120

ā’140

ā’160

function value

ā’180

ā’200

ā’220

ā’240

ā’260

ā’280

0 50 100 150 200 250

function evaluations

Figure 8.13: First Weber Example

in Figures 8.13, 8.14, and 8.15. The other three algorithms perform equally well. Note in the

third example that MDS ļ¬nds a local minimum that is not the global minimum.

8.5.2 Parameter ID

In the computations reported in this section each algorithm was allowed 500 evaluations of f

and the sequence of scales was {2ā’j }12 .

j=1

We begin with the two examples from Ā§7.6.2. With the initial iterate of (5, 5)T , the exact

solution to the continuous problem lies on the grid that the Hookeā“Jeeves algorithm uses to search

for the solution. This explains the unusually good performance of the Hookeā“Jeeves optimization

shown in both Figures 8.16 and 8.17. When the initial iterate is changed to (5.1, 5.3)T , the

performance of Hookeā“Jeeves is very different as one can see from Figures 8.18 and 8.19. The

other algorithms do not have such a sensitivity to the initial iterate for this example. We have no

explanation for the good performance turned in by the Nelderā“Mead algorithm on this problem.

8.5.3 Convex Quadratics

The problems and initial data are the same as those in Ā§7.6.3. This is an example of how sampling

algorithms can perform poorly for very simple problems and how this poor performance is made

worse by increasing the problem size. Exercise 7.7.4 illustrates this point very directly. One

would expect implicit ļ¬ltering to do well since a central difference gradient has no error for

quadratic problems. For the larger problem (N = 32, Figures 8.21 and 8.23), both the Nelderā“

Mead and MDS algorithms perform poorly while the Hookeā“Jeeves algorithm does surprisingly

well. The difference in performance of the algorithms is much smaller for the low-dimensional

problem (N = 4, Figures 8.20 and 8.22).

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

154 ITERATIVE METHODS FOR OPTIMIZATION

70

60

50

function value

40

30

20

10

0

0 20 40 60 80 100 120 140

function evaluations

Figure 8.14: Second Weber Example

70

60

50

function value

40

30

20

10

0 20 40 60 80 100 120

function evaluations

Figure 8.15: Third Weber Example

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 155

2

10

1

10

0

10

function value

ā’1

10

ā’2

10

ā’3

10

0 100 200 300 400 500 600

function evaluations

Figure 8.16: Parameter ID, tol = 10ā’3 , x0 = (5, 5)T

2

10

0

10

ā’2

10

function value

ā’4

10

ā’6

10

ā’8

10

ā’10

10

0 100 200 300 400 500 600

function evaluations

Figure 8.17: Parameter ID, tol = 10ā’6 , x0 = (5, 5)T

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

156 ITERATIVE METHODS FOR OPTIMIZATION

2

10

1

10

0

10

function value

ā’1

10

ā’2

10

ā’3

10

0 100 200 300 400 500 600

function evaluations

Figure 8.18: Parameter ID, tol = 10ā’3 , x0 = (5.1, 5.3)T

2

10

1

10

0

10

ā’1

10

ā’2

10

function value

ā’3

10

ā’4

10

ā’5

10

ā’6

10

ā’7

10

ā’8

10

0 100 200 300 400 500 600

function evaluations

Figure 8.19: Parameter ID, tol = 10ā’6 , x0 = (5.1, 5.3)T

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 157

2

10

1

10

0

10

ā’1

10

ā’2

10

function value

ā’3

10

ā’4

10

ā’5

10

ā’6

10

ā’7

10

ā’8

10

0 50 100 150 200 250 300 350 400

function evaluations

Figure 8.20: Unperturbed Quadratic, N = 4

4

10

2

10

0

10

function value

ā’2

10

ā’4

10

ā’6

10

ā’8

10

0 500 1000 1500 2000 2500 3000 3500

function evaluations

Figure 8.21: Unperturbed Quadratic, N = 32

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

158 ITERATIVE METHODS FOR OPTIMIZATION

2

10

1

10

0

10

ā’1

function value

10

ā’2

10

ā’3

10

ā’4

10

ā’5

10

0 200 400 600 800 1000 1200 1400 1600 1800 2000

function evaluations

Figure 8.22: Perturbed Quadratic, N = 4

3

10

2

10

1

10

0

function value

10

ā’1

10

ā’2

10

ā’3

10

ā’4

10

0 500 1000 1500 2000 2500 3000 3500

function evaluations

Figure 8.23: Perturbed Quadratic, N = 32

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

SEARCH ALGORITHMS 159

8.6 Exercises on Search Algorithms

8.6.1. Let Sl for 1 ā¤ l ā¤ 3 be the simplices having one vertex at (xl )1 = (10, 10, 10, 10) and

direction vectors V l given by

V 1 = diag(1, 2, 3, 4), V2 = diag(4, 3, 2, 1), V3 = diag(2, 2, 2, 2).

For each l = 1, 2, 3, apply the Nelderā“Mead algorithm to the function f deļ¬ned for x ā R4

by

(x1 ā’ x2 x3 x4 )2 + (x2 ā’ x3 x4 )2 + (x3 ā’ x4 )2 + x24

with the initial simplex V l . What happened? This example is one of Nelderā™s favorites

[203].

8.6.2. Show that if the set {x | f (x) ā¤ f (x0 )} is bounded and S0 is either an equilateral or a

1

right simplex, then (8.9) holds.

8.6.3. One can modify MDS [260] by eliminating the expansion step and only computing re-

ļ¬‚ected points until one is found that is better than x1 . If no reļ¬‚ected points are better,

then perform a contraction step. Prove that Theorem 8.2.1 holds for this implementation.

Implement MDS in this way and compare it with Algorithm mds. Are the savings in calls

to f for each iterate realized in a savings for the entire optimization?

8.6.4. The easiest problem in optimization is to minimize xT x. Give the algorithms in this

section a chance to show what they can do by using them to solve this problem. Try several

initial iterates (or initial simplices/patterns) and several problem dimensions (especially

N = 8, 16, 32).

8.6.5. The search methods in this section impose a structure on the sampling and thereby hope

to ļ¬nd a useful optimal point far more efļ¬ciently than using an unstructured deterministic

or random search. Implement an unstructured search and use your algorithm to minimize

xT x when N = 2. For an example of such a method, take the one from [6], please.

8.6.6. The Spendley, Hext, and Himsworth algorithm [244] manages the simplices in a very

different way from those weā™ve discussed in the text. Use the information in [244] and

[267] to implement this algorithm. Use Theorem 6.2.9 to prove convergence for N = 2.

What happens to both your implementation and analysis when you try N = 3 or arbitrary

N ? Explain Table 5 in [244].

8.6.7. Use any means necessary to solve the Lennardā“Jones problem. Have your results improved

since you tried exercises 6.4.3 and 7.7.4?

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

Bibliography

[1] E. Aarts and J. Korst, Simulated Annealing and Boltzmann Machines, Wiley, New

York, 1989.

[2] L. Adams and J. L. Nazareth, eds., Linear and Nonlinear Conjugate Gradient-Related

Methods, SIAM, Philadelphia, 1996.

[3] M. Al-Baali, Descent property and global convergence of the Fletcher-Reeves method

with inexact line searches, IMA J. Numer. Anal., 5 (1985), pp. 121ā“124.

[4] N. Alexandrov, J. E. Dennis, R. M. Lewis, and V. Torczon, A Trust Region Frame-

work for Managing the Use of Approximation Models in Optimization, Tech. Rep. 97-50,

Institute for Computer Applications in Science and Engineering, Hampton, VA, October

1997.

[5] E. L. Allgower and K. Georg, Numerical path following, in Handbook of Numerical

Analysis, P. G. Ciarlet and J. L. Lions, eds., vol. 5, Northā“Holland, Amsterdam, 1997,

pp. 3ā“207.

[6] Anonymous, A new algorithm for optimization, Math. Programming, 3 (1972), pp. 124ā“

128.

[7] L. Armijo, Minimization of functions having Lipschitz-continuous ļ¬rst partial derivatives,

Paciļ¬c J. Math., 16 (1966), pp. 1ā“3.

[8] U. M. Ascher and L. R. Petzold, Computer Methods for Ordinary Differential Equa-

tions and Differential-Algebraic Equations, SIAM, Philadelphia, 1998.

[9] K. E. Atkinson, Iterative variants of the NystrĀØ m method for the numerical solution of

o

integral equations, Numer. Math., 22 (1973), pp. 17ā“31.

[10] B. M. Averick and J. J. MorĀ“ , User Guide for the MINPACK-2 Test Problem Collection,

e

Tech. Rep. ANL/MCS-TM-157, Math. and Comp. Science Div. Report, Argonne National

Laboratory, Argone, IL, October 1991.

[11] O. Axelsson, Iterative Solution Methods, Cambridge University Press, Cambridge, 1994.

[12] S. Banach, Sur les opĀ“ rations dans les ensembles abstraits et leur applications aux

e

equations intĀ“ grales, Fund. Math., 3 (1922), pp. 133ā“181.

Ā“ e

[13] H. T. Banks and H. T. Tran, Mathematical and Experimental Modeling of Physical

Processes, unpublished notes for MA 573-4, 1997, Department of Mathematics, North

Carolina State University, Raleigh, NC.

[14] M. S. Barlett, An inverse matrix adjustment arising in discriminant analysis, Ann. Math.

Stat., 22 (1951), pp. 107ā“111.

161

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

162 BIBLIOGRAPHY

[15] R. Barrett, M. Berry, T. F. Chan, J. Demmel, J. Donato, J. Dongarra, V. Eijkhout,

R. Pozo, C. Romine, and H. van der Vorst, Templates for the Solution of Linear

Systems: Building Blocks for Iterative Methods, SIAM, Philadelphia, 1994.

[16] K. J. Bathe and A. P. Cimento, Some practical procedures for the solution of nonlinear

ļ¬nite element equations, Comput. Methods. Appl. Mech. Engrg., 22 (1980), pp. 59ā“85.

[17] A. Ben-Israel, A Newton-Raphson method for the solution of systems of equations, J.

Math. Anal. Appl., 15 (1966), pp. 243ā“252.

[18] D. P. Bertsekas, On the Goldstein-Levitin-Polyak gradient projection method, IEEE

Trans. Automat. Control, 21 (1976), pp. 174ā“184.

, Projected Newton methods for optimization problems with simple constraints,

[19]

SIAM J. Control Optim., 20 (1982), pp. 221ā“246.

[20] J. T. Betts, An improved penalty function method for solving constrained parameter

optimization problems, J. Optim. Theory Appl., 16 (1975), pp. 1ā“24.

, Solving the nonlinear least square problem: Application of a general method, J.

[21]

Optim. Theory Appl., 18 (1976), pp. 469ā“483.

[22] J. T. Betts, M. J. Carter, and W. P. Huffman, Software for Nonlinear Optimization,

Tech. Rep. MEA-LR-083 R1, Mathematics and Engineering Analysis Library Report,

Boeing Information and Support Services, Seattle, WA, June 6, 1997.

[23] J. T. Betts and P. D. Frank, A sparse nonlinear optimization algorithm, J. Optim. Theory

Appl., 82 (1994), pp. 519ā“541.

[24] P. T. Boggs, The convergence of the Ben-Israel iteration for nonlinear least squares

problems, Math. Comp., 30 (1976), pp. 512ā“522.

[25] P. T. Boggs and J. E. Dennis, A stability analysis for perturbed nonlinear iterative

methods, Math. Comp., 30 (1976), pp. 1ā“17.

[26] I. Bongatz, A. R. Conn, and P. L. Toint, CUTE: Constrained and unconstrained testing

environment, ACM Trans. Math. Software, 21 (1995), pp. 123ā“160.

[27] A. J. Booker, DOE for Computer Output, Tech. Rep. BCSTECH-94-052, Boeing Com-

puter Services, Seattle, WA, 1994.

[28] A. J. Booker, J. E. Dennis, P. D. Frank, D. B. Seraļ¬ni, V. Torczon, and M. W.

Trosset, A rigorous framework for optimization of expensive function by surrogates,

Structural Optimization, 17 (1999), pp. 1ā“13.

[29] D. M. Bortz and C. T. Kelley, The simplex gradient and noisy optimization problems,

in Computational Methods in Optimal Design and Control, J.T. Borggaard, J. Burns,

E. Cliff, S. Schrenk, eds., Birkhauser, Boston, 1998, pp. 77ā“90.

[30] A. Bouaricha, Tensor methods for large, sparse, unconstrained optimization, SIAM J.

Optim., 7 (1997), pp. 732ā“756.

ĀØ

[31] H. Brakhage, Uber die numerische Behandlung von Integralgleichungen nach der

Quadraturformelmethode, Numer. Math., 2 (1960), pp. 183ā“196.

[32] K. E. Brenan, S. L. Campbell, and L. R. Petzold, The Numerical Solution of Initial

Value Problems in Differential-Algebraic Equations, SIAM, Philadelphia, 1996.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

BIBLIOGRAPHY 163

[33] P. N. Brown and Y. Saad, Convergence theory of nonlinear Newtonā“Krylov algorithms,

SIAM J. Optim., 4 (1994), pp. 297ā“330.

[34] C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math.

Comp., 19 (1965), pp. 577ā“593.

, Quasi-Newton methods and their application to function minimization, Math.

[35]

Comp., 21 (1967), pp. 368ā“381.

, A new double-rank minimization algorithm, AMS Notices, 16 (1969), p. 670.

[36]

[37] C. G. Broyden, J. E. Dennis, and J. J. MorĀ“ , On the local and superlinear convergence

e

of quasi-Newton methods, J. Inst. Math. Appl., 12 (1973), pp. 223ā“246.

[38] R. H. Byrd, T. Derby, E. Eskow, K. P. B. Oldenkamp, and R. B. Schnabel, A new

stochastic/perturbation method for large-scale global optimization and its application to

water cluster problems, in Large Scale Optimization: State of the Art, W. W. Hager, D. W.

Hearn, and P. Pardalos, eds., Kluwer Academic Publishers B.V., Boston, 1994, pp. 68ā“81.

[39] R. H. Byrd, C. L. Dert, A. H. G. R. Kan, and R. B. Schnabel, Concurrent stochastic

methods for global optimization, Math. Programminng., 46 (1990), pp. 1ā“30.

[40] R. H. Byrd, E. Eskow, and R. B. Schnabel, A New Large-Scale Global Optimiza-

tion Method and Its Application to Lennard-Jones Problems, Tech. Rep. CU-CS-630-92,

University of Colorado at Boulder, November 1992.

[41] R. H. Byrd, H. F. Khalfan, and R. B. Schnabel, Analysis of a symmetric rank-one

trust region method, SIAM J. Optim., 6 (1996), pp. 1025ā“1039.

[42] R. H. Byrd, P. Lu, J. Nocedal, and C. Zhu, A limited memory algorithm for bound

constrained optimization, SIAM J. Sci. Comput., 16 (1995), pp. 1190ā“1208.

[43] R. H. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with

application to unconstrained minimization, SIAM J. Numer. Anal., 26 (1989), pp. 727ā“

739.

[44] R. H. Byrd, J. Nocedal, and R. B. Schnabel, Representation of quasi-Newton matrices

and their use in limited memory methods, Math. Programming, 63 (1994), pp. 129ā“156.

[45] R. H. Byrd, J. Nocedal, and Y. Yuan, Global convergence of a class of quasi-Newton

methods on convex problems, SIAM J. Numer. Anal., 24 (1987), pp. 1171ā“1190.

[46] R. H. Byrd, R. B. Schnabel, and G. A. Schultz, Parallel quasi-Newton methods for

unconstrained optimization, Math. Programming, 42 (1988), pp. 273ā“306.

[47] P. H. Calamai and J. MorĀ“ , Projected gradient methods for linearly constrained prob-

e

lems, Math. Programming, 39 (1987), pp. 93ā“116.

[48] S. L. Campbell, C. T. Kelley, and K. D. Yeomans, Consistent initial conditions for

unstructured higher index DAEs: A computational study, in Proc. Conference on Compu-

tational Engineering in Systems Applications (CESAā™96), Lille, France, 1996, pp. 416ā“

421.

[49] S. L. Campbell and C. D. Meyer, Generalized Inverses of Linear Transformations,

Dover Press, New York, 1991.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

164 BIBLIOGRAPHY

[50] S. L. Campbell and K. D. Yeomans, Behavior of the nonunique terms in general DAE

integrators, Appl. Numer. Math., (1998), to appear.

[51] R. G. Carter, On the global convergence of trust region algorithms using inexact gradient

information, SIAM J. Numer. Anal., 28 (1991), pp. 251ā“265.

[52] A. Cauchy, Methode generale pour la resolution des systemes dā™equations simultanees,

Comp. Rend. Acad. Sci. Paris, (1847), pp. 536ā“538.

[53] T. D. Choi. Private Communication, 1998.

, Bound Constrained Optimization, PhD thesis, North Carolina State University,

[54]

Raleigh, North Carolina, 1999.

[55] T. D. Choi, O. J. Eslinger, C. T. Kelley, J. W. David, and M. Etheridge, Optimization

of automotive valve train components with implict ļ¬ltering, Optim. Engrg., 1 (2000),

pp. 9ā“28.

[56] T. D. Choi and C. T. Kelley, Superlinear convergence and implicit ļ¬ltering, SIAM J.

Optim., 10 (2000), pp. 1149ā“1162.

[57] T. F. Coleman and Y. Li, On the convergence of interior-reļ¬‚ective Newton methods for

nonlinear minimization subject to bounds, Math. Programming, 67 (1994), pp. 189ā“224.

, An interior trust region approach for nonlinear minimization subject to bounds,

[58]

SIAM J. Optim., 6 (1996), pp. 418ā“445.

[59] T. F. Coleman and J. J. MorĀ“ , Estimation of sparse Jacobian matrices and graph

e

coloring problems, SIAM J. Numer. Anal., 20 (1983), pp. 187ā“209.

[60] P. Concus, G. H. Golub, and D. P. Oā™Leary, A generalized conjugate gradient method

for the numerical solution of elliptic partial differential equations, in Sparse Matrix Com-

putations, J. R. Bunch and D. J. Rose, eds., Academic Press, NewYork, 1976, pp. 309ā“332.

[61] A. R. Conn, , K. Scheinberg, and P. L. Toint, On the convergence of derivative-free

methods for unconstrained optimization, in Approximation Theory and Optimization:

Tributes to M. J. D. Powell, A. Iserles and M. Buhmann, eds., Cambridge University

Press, 1997, pp. 83ā“108.

, Recent progress in unconstrained optimization without derivatives, Math. Pro-

[62]

gramming Ser. B, 79 (1997), pp. 397ā“414.

[63] A. R. Conn, N. I. M. Gould, and P. L. Toint, Global convergence of a class of trust

region algorithms for optimization problems with simple bounds, SIAM J. Numer. Anal.,

25 (1988), pp. 433ā“460.

, Testing a class of methods for solving minimization problems with simple bounds

[64]

on the variables, Math. Comp., 50 (1988), pp. 399ā“430.

, Convergence of quasi-Newton matrices generated by the symmetric rank one up-

[65]

date, Math. Programming Ser. A, 50 (1991), pp. 177ā“195.

, LANCELOT: A Fortran Package for Large-Scale Nonlinear Optimization (Release

[66]

A), Springer Series in Computational Mathematics, Springer-Verlag, Heidelberg, Berlin,

New York, 1992.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

BIBLIOGRAPHY 165

[67] A. R. Curtis, M. J. D. Powell, and J. K. Reid, On the estimation of sparse Jacobian

matrices, J. Inst. Math. Appl., 13 (1974), pp. 117ā“119.

[68] J. W. Daniel, The conjugate gradient method for linear and nonlinear operator equations,

SIAM J. Numer. Anal., 4 (1967), pp. 10ā“26.

[69] J. W. David, C. Y. Cheng, T. D. Choi, C. T. Kelley, and J. Gablonsky, Optimal Design

of High Speed Mechanical Systems, Tech. Rep. CRSC-TR97-18, Center for Research in

Scientiļ¬c Computation, North Carolina State University, Raleigh, July 1997; Math.

Modelling Sci. Comput., to appear.

[70] J. W. David, C. T. Kelley, and C. Y. Cheng, Use of an Implicit Filtering Algorithm

for Mechanical System Parameter Identiļ¬cation. SAE Paper 960358, 1996 SAE Interna-

tional Congress and Exposition Conference Proceedings, Modeling of CI and SI Engines,

Society of Automotive Engineers, pp. 189ā“194.

[71] W. C. Davidon, Variable Metric Methods for Minimization, Tech. Rep. ANL-5990, Ar-

gonne National Laboratory, Argone, IL, 1959.

, Variable metric method for minimization, SIAM J. Optim., 1 (1991), pp. 1ā“17.

[72]

[73] T. J. Dekker, Finding a zero by means of successive linear interpolation, in Constructive

Aspects of the Fundamental Theorem of Algebra, B. Dejon and P. Henrici, eds., Wiley-

Interscience, New York, 1969, pp. 37ā“48.

[74] R. S. Dembo, S. C. Eisenstat, and T. Steihaug, Inexact Newton methods, SIAM J.

Numer. Anal., 19 (1982), pp. 400ā“408.

[75] R. Dembo and T. Steihaug, Truncated Newton algorithms for large-scale optimization,

Math. Programming, 26 (1983), pp. 190ā“212.

[76] J. E. Dennis, Nonlinear least squares and equations, in The State of the Art in Numerical

Analysis, D. Jacobs, ed., Academic Press, London, 1977, pp. 269ā“312.

[77] J. E. Dennis, D. M. Gay, and R. E.Welsch, An adaptive nonlinear least-squares algo-

rithm, ACM Trans. Math. Software, 7 (1981), pp. 348ā“368.

, Algorithm 573: NL2SOL ā“ An adaptive nonlinear least-squares algorithm, ACM

[78]

Trans. Math. Software, 7 (1981), pp. 369ā“383.

[79] J. E. Dennis, M. Heinkenschloss, and L. N. Vicente, Trust-region interior-point SQP

algorithms for a class of nonlinear programming problems, SIAM J. Control Optim., 36

(1998), pp. 1750ā“1794.

[80] J. E. Dennis and H. H. W. Mei, Two unconstrained optimization algorithms which use

function and gradient values, J. Optim. Theory Appl., 28 (1979), pp. 453ā“482.

[81] J. E. Dennis and J. J. MorĀ“ , A characterization of superlinear convergence and its

e

application to quasi-Newton methods, Math. Comp., 28 (1974), pp. 549ā“560.

, Quasi-Newton methods, methods, motivation and theory, SIAM Rev., 19 (1977),

[82]

pp. 46ā“89.

[83] J. E. Dennis and R. B. Schnabel, Least change secant updates for quasi-Newton meth-

ods, SIAM Rev., 21 (1979), pp. 443ā“459.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

166 BIBLIOGRAPHY

, Numerical Methods for Unconstrained Optimization and Nonlinear Equations,

[84]

SIAM, Philadelphia, 1996.

[85] J. E. Dennis and V. Torczon, Direct search methods on parallel machines, SIAM J.

Optim., 1 (1991), pp. 448ā“474.

[86] J. E. Dennis and L. N. Vicente, Trust-region interior-point algorithms for minimization

problems with simple bounds, inApplied Mathematics and Parallel Computing, H. Fischer,

B. Riedmiller, and S. Schafļ¬‚er, eds., Hidelberg, 1997, Springer, pp. 97ā“109.

[87] J. E. Dennis and H. F. Walker, Convergence theorems for least-change secant update

methods, SIAM J. Numer. Anal., 18 (1981), pp. 949ā“987.

, Inaccuracy in quasi-Newton methods: Local improvement theorems, in Mathe-

[88]

matical Programming Study 22: Mathematical Programming at Oberwolfach II, Northā“

Holland, Amsterdam, 1984, pp. 70ā“85.

[89] J. E. Dennis and D. J. Woods, Optimization on microcomputers: The Nelder-Mead

simplex algorithm, in New Computing Environments: Microcomputers in Large-Scale

Scientiļ¬c Computing, A. Wouk, ed., SIAM, Philadelphia, 1987, pp. 116ā“122.

[90] P. Deuļ¬‚hard and V. Apostolescu, A Study of the Gauss-Newton Algorithm for the

Solution of Nonlinear Least Squares Problems, Tech. Rep. 51, Univ. Heidelberg, 1980,

preprint.

[91] P. Deuļ¬‚hard, R. W. Freund, and A. Walter, Fast secant methods for the iterative

solution of large nonsymmetric linear systems, Impact Comput. Sci. Engrg., 2 (1990),

pp. 244ā“276.

[92] P. Deuļ¬‚hard and G. Heindl, Afļ¬ne invariant convergence theorems for Newtonā™s

method and extensions to related methods, SIAM J. Numer. Anal., 16 (1979), pp. 1ā“10.

[93] W. J. Duncan, Some devices for the solution of large sets of simultaneous linear equations

(with an appendix on the reciprocation of partitioned matrices), The London, Edinburgh,

and Dublin Philosophical Magazine and Journal of Science, Seventh Series, 35 (1944),

pp. 660ā“670.

[94] J. C. Dunn, Global and asymptotic convergence rate estimates for a class of projected

gradient processes, SIAM J. Control Optim., 19 (1981), pp. 368ā“400.

, On the convergence of projected gradient processes to singular critical points, J.

[95]

Optim. Theory Appl., 55 (1987), pp. 203ā“215.

, A projected Newton method for minimization problems with nonlinear inequality

[96]

constraints, Numer. Math., 53 (1988), pp. 377ā“409.

[97] J. C. Dunn and E. W. Sachs, The effect of perturbations on the convergence rates of

optimization algorithms, Appl. Math. Optim., 10 (1983), pp. 143ā“147.

[98] J. C. Dunn and T. Tian, Variants of the Kuhnā“Tucker sufļ¬cient conditions in cones of

nonnegative functions, SIAM J. Control Optim., 30 (1992), pp. 1361ā“1384.

[99] S. C. Eisenstat and H. F. Walker, Choosing the forcing terms in an inexact Newton

method, SIAM J. Sci. Comput., 17 (1996), pp. 16ā“32.

[100] E. Eskow and R. B. Schnabel, Algorithm 695: Software for a new modiļ¬ed Cholesky

factorization, ACM Trans. Math. Software, 17 (1991), pp. 306ā“312.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

BIBLIOGRAPHY 167

[101] A. V. Fiacco and G. P. McCormick, Nonlinear Programming: Sequential Unconstrained

Minimization Techniques, SIAM, Philadelphia, 1990.

[102] R. Fletcher, Generalized inverse methods for the best least squares solution of systems

of nonlinear equations, Comput. J., 10 (1968), pp. 392ā“399.

, A new approach to variable metric methods, Comput. J., 13 (1970), pp. 317ā“322.

[103]

, Practical Methods of Optimization, John Wiley and Sons, New York, 1987.

[104]

[105] R. Fletcher and M. J. D. Powell, A rapidly convergent descent method for minimiza-

tion, Comput. J., 6 (1963), pp. 163ā“168.

[106] R. Fletcher and C. M. Reeves, Function minimization by conjugate gradients, Comput.

J., 7 (1964), pp. 149ā“154.

[107] S. J. Fortune, D. M. Gay, B. W. Kernighan, O. Landron, R. A. Valenzuela, and

M. H. Wright, WISE design of indoor wireless systems, IEEE Computational Science

and Engineering, Spring (1995), pp. 58ā“68.

[108] J. Gablonsky, An Implemention of the Direct Algorithm, Tech. Rep. CRSC-TR98-29,

Center for Research in Scientiļ¬c Computation, North Carolina State University, Raleigh,

August 1998.

[109] D. M. Gay, Computing optimal locally constrained steps, SIAM J. Sci. Statist. Comput.,

2 (1981), pp. 186ā“197.

[110] C. W. Gear, Numerical Initial Value Problems in Ordinary Differential Equations,

Prenticeā“Hall, Englewood Cliffs, NJ, 1971.

[111] R. R. Gerber and F. T. Luk, A generalized Broydenā™s method for solving simultaneous

linear equations, SIAM J. Numer. Anal., 18 (1981), pp. 882ā“890.

[112] J. C. Gilbert and J. Nocedal, Global convergence properties of conjugate gradient

methods for optimization, SIAM J. Optim., 2 (1992), pp. 21ā“42.

[113] P. E. Gill and W. Murray, Newton-type methods for unconstrained and linearly con-

strained optimization, Math. Programming, 28 (1974), pp. 311ā“350.

, Safeguarded Steplength Algorithms for Optimization Using Descent Methods,

[114]

Tech. Rep. NAC 37, National Physical Laboratory Report, Teddington, England, 1974.

, Non-linear least squares and nonlinearly constrained optimization, in Numerical

[115]

Analysis, Lecture Notes in Mathematics 506, Springer-Verlag, Berlin, 1976.

, Algorithms for the solution of the nonlinear least-squares problem, SIAM J. Numer.

[116]

Anal., 15 (1978), pp. 977ā“992.

[117] P. E. Gill, W. Murray, and M. H. Wright, Practical Optimization, Academic Press,

London, 1981.

[118] P. Gilmore, An Algorithm for Optimizing Functions with Multiple Minima, Ph.D. thesis,

North Carolina State University, Raleigh, 1993.

, IFFCO: Implicit Filtering for Constrained Optimization, Tech. Rep. CRSC-TR93-

[119]

7, Center for Research in Scientiļ¬c Computation, North Carolina State University, May

1993. Available by anonymous ftp from math.ncsu.edu in pub/kelley/iffco/ug.ps.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

168 BIBLIOGRAPHY

[120] P. Gilmore and C. T. Kelley, An implicit ļ¬ltering algorithm for optimization of functions

with many local minima, SIAM J. Optim., 5 (1995), pp. 269ā“285.

[121] P. A. Gilmore, S. S. Berger, R. F. Burr, and J. A. Burns, Automated optimization

techniques for phase change piezoelectric ink jet performance enhancement. in Proc.

IS&Tā™s NIP 13: 1997 International Conference on Digital Printing Technologies, Society

for Imaging Science and Technology, 1997, pp. 716ā“721.

[122] R. Glowinski, Numerical Methods for Nonlinear Variational Problems, Springer-Verlag,

New York, 1984.

[123] D. E. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning,

Addisonā“Wesley, Reading, MA., 1989.

[124] D. Goldfarb, A family of variable metric methods derived by variational means, Math.

Comp., 24 (1970), pp. 23ā“26.

[125] A. A. Goldstein, Constructive Real Analysis, Harper and Row, New York, 1967.

[126] G. H. Golub and V. Pereyra, The differentiation of pseudo-inverses and nonlinear least

squares problems whose variables separate, SIAM J. Numer. Anal., 10 (1973), pp. 413ā“

432.

[127] G. H. Golub and C. G. Van Loan, Matrix Computations, Johns Hopkins University

Press, Baltimore, MD, 1983.

[128] A. Greenbaum, Iterative Methods for Solving Linear Systems, SIAM, Philadelphia, 1997.

[129] A. Griewank, On automatic differentiation, in Mathematical Programming: Recent De-

velopments and Applications, M. Iri and K. Tanabe, eds., Kluwer, Dordrecht, the Nether-

lands, 1989, pp. 83ā“108.

[130] A. Griewank and G. F. Corliss, eds., Automatic Differentiation of Algorithms: Theory,

Implementation, and Application, SIAM, Philadelphia, 1991.

[131] A. Griewank and P. L. Toint, Local convergence analysis for partitioned quasi-Newton

updates, Numer. Math., 39 (1982), pp. 429ā“448.

, On the unconstrained optimization of partially separable functions, in Nonlinear

[132]

Optimization, M. J. D. Powell, ed., Academic Press, London, 1982.

, Partitioned variable metric methods for large sparse optimization problems, Nu-

[133]

mer. Math., 39 (1982), pp. 119ā“137.

[134] L. Grippo and S. Lucidi, A globally convergent version of the Polak-Ribi` re conjugate

e

gradient method, Math. Programming, 78 (1997), pp. 375ā“392.

[135] W. A. Gruver and E. Sachs, Algorithmic Methods in Optimal Control, Pitman, London,

1980.

[136] W. Hackbusch, On the fast solving of parabolic boundary control problems, SIAM J.

Control Optim., 17 (1979), pp. 231ā“244.

, Optimal H p,p/2 error estimates for a parabolic Galerkin method, SIAM J. Numer.

[137]

Anal., 18 (1981), pp. 681ā“692.

, Multi-Grid Methods and Applications, Springer Ser. Comput. Math. 4, Springer-

[138]

Verlag, New York, 1985.

Buy this book from SIAM at http://www.ec-securehost.com/SIAM/FR18.html.

Copyright Ā©1999 by the Society for Industrial and Applied Mathematics. This electronic version is for personal use and may not be duplicated or distributed.

BIBLIOGRAPHY 169

[139] W. W. Hager, Rates of convergence for discrete approximations to unconstrained optimal

control problems, SIAM J. Numer. Anal., 13 (1976), pp. 449ā“472.

[140] M. Heinkenschloss, M. Ulbrich, and S. Ulbrich, Superlinear and Quadratic Conver-

gence of Afļ¬ne Scaling Interior-Point Newton Methods for Problems with Simple Bounds

and Without Strict Complementarity Assumption, Tech. Rep. TR97-30, Department of

Computational and Applied Mathematics, Rice University, Houston, TX, December 1997.

[141] M. R. Hestenes and E. Steifel, Methods of conjugate gradient for solving linear sys-

tems, J. Res. Nat. Bureau Standards, 49 (1952), pp. 409ā“436.

[142] M. R. Hoare and P. Pal, Physical cluster mechanics: Statics and energy surfaces for

monoatomic systems, Adv. Phys., 20 (1971), pp. 161ā“196.

[143] J. H. Holland, Genetic algorithms and the optimal allocation of trials, SIAM J. Comput.,

2 (1973), pp. 88ā“105.

, Adaption in Natural and Artiļ¬cial Systems, University of Michigan Press, Ann

ńņš. 8 |