Nonlinear Parameter Optimization Using R Tools E-Book

John C. Nash

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 494

Veröffentlichungsjahr: 2014

Beschreibung

Nonlinear Parameter Optimization Using R
John C. Nash, Telfer School of Management, University of Ottawa, Canada

A systematic and comprehensive treatment of optimization software using R

In recent decades, optimization techniques have been streamlined by computational and artificial intelligence methods to analyze more variables, especially under non–linear, multivariable conditions, more quickly than ever before.

Optimization is an important tool for decision science and for the analysis of physical systems used in engineering. Nonlinear Parameter Optimization with R explores the principal tools available in R for function minimization, optimization, and nonlinear parameter determination and features numerous examples throughout.

Nonlinear Parameter Optimization with R:

• Provides a comprehensive treatment of optimization techniques
• Examines optimization problems that arise in statistics and how to solve them using R
• Enables researchers and practitioners to solve parameter determination problems
• Presents traditional methods as well as recent developments in R
• Is supported by an accompanying website featuring R code, examples and datasets

Researchers and practitioners who have to solve parameter determination problems who are users of R but are novices in the field optimization or function minimization will benefit from this book. It will also be useful for scientists building and estimating nonlinear models in various fields such as hydrology, sports forecasting, ecology, chemical engineering, pharmaco-kinetics, agriculture, economics and statistics.

Leseprobe

Table of Contents

Cover

Title Page

Copyright

Dedication

Preface

Chapter 1: Optimization problem tasks and how they arise

1.1 The general optimization problem

1.2 Why the general problem is generally uninteresting

1.3 (Non-)Linearity

1.4 Objective function properties

1.5 Constraint types

1.6 Solving sets of equations

1.7 Conditions for optimality

1.8 Other classifications

References

Chapter 2: Optimization algorithms—an overview

2.1 Methods that use the gradient

2.2 Newton-like methods

2.3 The promise of Newton's method

2.4 Caution: convergence versus termination

2.5 Difficulties with Newton's method

2.6 Least squares: Gauss–Newton methods

2.7 Quasi-Newton or variable metric method

2.8 Conjugate gradient and related methods

2.9 Other gradient methods

2.10 Derivative-free methods

2.11 Stochastic methods

2.12 Constraint-based methods—mathematical programming

References

Chapter 3: Software structure and interfaces

3.1 Perspective

3.2 Issues of choice

3.3 Software issues

3.4 Specifying the objective and constraints to the optimizer

3.5 Communicating exogenous data to problem definition functions

3.6 Masked (temporarily fixed) optimization parameters

3.7 Dealing with inadmissible results

3.8 Providing derivatives for functions

3.9 Derivative approximations when there are constraints

3.10 Scaling of parameters and function

3.11 Normal ending of computations

3.12 Termination tests—abnormal ending

3.13 Output to monitor progress of calculations

3.14 Output of the optimization results

3.15 Controls for the optimizer

3.16 Default control settings

3.17 Measuring performance

3.18 The optimization interface

References

Chapter 4: One-parameter root-finding problems

4.1 Roots

4.2 Equations in one variable

4.3 Some examples

4.4 Approaches to solving 1D root-finding problems

4.5 What can go wrong?

4.6 Being a smart user of root-finding programs

4.7 Conclusions and extensions

References

Chapter 5: One-parameter minimization problems

5.1 The

optimize()

function

5.2 Using a root-finder

5.3 But where is the minimum?

5.4 Ideas for 1D minimizers

5.5 The line-search subproblem

References

Chapter 6: Nonlinear least squares

6.1

nls()

from package

stats

6.2 A more difficult case

6.3 The structure of the

nls()

solution

6.4 Concerns with

nls()

6.5 Some ancillary tools for nonlinear least squares

6.6 Minimizing

R

functions that compute sums of squares

6.7 Choosing an approach

6.8 Separable sums of squares problems

6.9 Strategies for nonlinear least squares

References

Chapter 7: Nonlinear equations

7.1 Packages and methods for nonlinear equations

7.2 A simple example to compare approaches

7.3 A statistical example

References

Chapter 8: Function minimization tools in the base

R

system

8.1

optim()

8.2

nlm()

8.3

nlminb()

8.4 Using the base optimization tools

References

Chapter 9: Add-in function minimization packages for

R

9.1 Package

optimx

9.2 Some other function minimization packages

9.3 Should we replace

optim()

routines?

References

Chapter 10: Calculating and using derivatives

10.1 Why and how

10.2 Analytic derivatives—by hand

10.3 Analytic derivatives—tools

10.4 Examples of use of

R

tools for differentiation

10.5 Simple numerical derivatives

10.6 Improved numerical derivative approximations

10.7 Strategy and tactics for derivatives

References

Chapter 11: Bounds constraints

11.1 Single bound: use of a logarithmic transformation

11.2 Interval bounds: Use of a hyperbolic transformation

11.3 Setting the objective large when bounds are violated

11.4 An active set approach

11.5 Checking bounds

11.6 The importance of using bounds intelligently

11.7 Post-solution information for bounded problems

Appendix 11.A Function

transfinite

References

Chapter 12: Using masks

12.1 An example

12.2 Specifying the objective

12.3 Masks for nonlinear least squares

12.4 Other approaches to masks

References

Chapter 13: Handling general constraints

13.1 Equality constraints

13.2 Sumscale problems

13.3 Inequality constraints

13.4 A perspective on penalty function ideas

13.5 Assessment

References

Chapter 14: Applications of mathematical programming

14.1 Statistical applications of math programming

14.2

R

packages for math programming

14.3 Example problem: L1 regression

14.4 Example problem: minimax regression

14.5 Nonlinear quantile regression

14.6 Polynomial approximation

References

Chapter 15: Global optimization and stochastic methods

15.1 Panorama of methods

15.2

R

packages for global and stochastic optimization

15.3 An example problem

15.4 Multiple starting values

References

Chapter 16: Scaling and reparameterization

16.1 Why scale or reparameterize?

16.2 Formalities of scaling and reparameterization

16.3 Hobbs' weed infestation example

16.4 The KKT conditions and scaling

16.5 Reparameterization of the weeds problem

16.6 Scale change across the parameter space

16.7 Robustness of methods to starting points

16.8 Strategies for scaling

References

Chapter 17: Finding the right solution

17.1 Particular requirements

17.2 Starting values for iterative methods

17.3 KKT conditions

17.4 Search tests

References

Chapter 18: Tuning and terminating methods

18.1 Timing and profiling

18.2 Profiling

18.3 More speedups of

R

computations

18.4 External language compiled functions

18.5 Deciding when we are finished

References

Chapter 19: Linking

R

to external optimization tools

19.1 Mechanisms to link

R

to external software

19.2 Prepackaged links to external optimization tools

19.3 Strategy for using external tools

References

Chapter 20: Differential equation models

20.1 The model

20.2 Background

20.3 The likelihood function

20.4 A first try at minimization

20.5 Attempts with

optimx

20.6 Using nonlinear least squares

20.7 Commentary

Reference

Chapter 21: Miscellaneous nonlinear estimation tools for

R

21.1 Maximum likelihood

21.2 Generalized nonlinear models

21.3 Systems of equations

21.4 Additional nonlinear least squares tools

21.5 Nonnegative least squares

21.6 Noisy objective functions

21.7 Moving forward

References

Appendix A:

R

packages used in examples

Index

End User License Agreement

Pages

xv

xvi

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

262

263

264

265

266

267

268

269

270

271

272

273

274

275

276

277

278

279

280

281

282

283

284

285

286

287

Guide

Cover

Table of Contents

Preface

Chapter 1: Optimization problem tasks and how they arise

List of Illustrations

Figure 1.1

Figure 4.1

Figure 4.2

Figure 5.1

Figure 5.2

Figure 6.1

Figure 6.2

Figure 6.3

Figure 6.4

Figure 6.5

Figure 10.1

Figure 11.1

Figure 14.1

Figure 15.1

Figure 15.2

Figure 16.1

Figure 16.2

Figure 20.1

Figure 20.2

Nonlinear Parameter Optimization Using R Tools

John C. Nash

Telfer School of Management

University of Ottawa

This edition first published 2014

© 2014 John Wiley and Sons Ltd

Registered office

John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex, PO19 8SQ, United Kingdom

For details of our global editorial offices, for customer services and for information about how to apply for permission to reuse the copyright material in this book please see our website at www.wiley.com.

The right of the author to be identified as the author of this work has been asserted in accordance with the Copyright, Designs and Patents Act 1988.

All rights reserved. No part of this publication may be reproduced, stored in a retrieval system, or transmitted, in any form or by any means, electronic, mechanical, photocopying, recording or otherwise, except as permitted by the UK Copyright, Designs and Patents Act 1988, without the prior permission of the publisher.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic books.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. It is sold on the understanding that the publisher is not engaged in rendering professional services and neither the publisher nor the author shall be liable for damages arising herefrom. If professional advice or other expert assistance is required, the services of a competent professional should be sought.

MATLAB® is a trademark of The MathWorks, Inc. and is used with permission. The MathWorks does not warrant the accuracy of the text or exercises in this book. This book's use or discussion of MATLAB® software or related products does not constitute endorsement or sponsorship by The MathWorks of a particular pedagogical approach or particular use of the MATLAB® software.

Library of Congress Cataloging-in-Publication Data

Nash, John C., 1947-

Nonlinear parameter optimization using R tools / John C. Nash.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-56928-3 (cloth)

1. Mathematical optimization. 2. Nonlinear theories. 3. R (Computer program language) I. Title.

QA402.5.N34 2014

519.60285′5133–dc23

2013051141

A catalogue record for this book is available from the British Library.

ISBN: 9781118569283

This work is a part of and is dedicated to that effort by the many community-minded people who create, support, promote, and use free and open source software, and who generously share these ideas, without which R in particular would not exist.

Preface

This book is about tools for finding parameters of functions that describe phenomena or systems where these parameters are implicated in ways that do not allow their determination by solving sets of linear equations. Furthermore, it is about doing so with R.

R is a computer language and suite of libraries intended primarily to be used for statistical and mathematical computations. It has a strong but quite small base system that is rich in functions for scientific computations as well as a huge collection of add-in packages for particular extra problems and situations.

Among both the base and add-in tools are facilities for finding the “best” parameters of functions that describe systems or phenomena. Such tools are used to fit equations to data or improve the performance of devices or find the most efficient path from A to B, and so on. Some such problems have a structure where we only need solve one or two sets of linear equations. Others—the subject of this book—require iterative methods to approximate the solution we desire. Generally we refer to these as nonlinear parameters. A formal definition will be given later, but the tools we shall discuss can be applied anyway.

Sometimes the problems involve constraints as well as objective functions. Dealing with constraints is also a subject for this book. When there are many constraints, the problem is usually called mathematical programming, a field with many subspecialties depending on the nature of the objective and constraints. While some review of the R tools for mathematical programming is included, such problems have not been prominent in my work, so there is less depth of treatment here. This does not imply that the subject should be ignored, even though for me, and also to some extent for R, mathematical programming has been a lower priority than nonlinear function minimization with perhaps a few constraints. This reflects the origins of R in the primarily statistical community.

The topics in this book are most likely to be of interest to researchers and practitioners who have to solve parameter determination problems. In some cases, they will be developing specialized tools, such as packages for maximum likelihood estimation, so the tools discussed here are like the engines used by car designers to prepare their particular offering. In other cases, workers will want to use the tools directly. In either case, my aim is to provide advice and suggestions of what is likely to work well and what should generally be avoided.

The book should also interest the serious users of composite packages that use optimization internally. I have noticed that some such packages call the first or most obvious tool in sight. I believe the user really should be offered a choice or at least informed of what is used. Those who stand most to benefit from the book in this way are workers who have large computationally intensive problems or else awkward problems where standard methods may “fail”—or more likely simply terminate before finding a satisfactory solution.

Thus my goal in preparing this book is to provide an appreciation of the tools and where they are most useful. Most users of R are not specialists in computation, and the workings of the specialized tools are a black box. This can lead to mis application. A lumberjack's chain saw is a poor choice for a neurosurgeon's handiwork. But a system like R needs to have a range of choices for different occasions. Users also need to help in making appropriate choices.

I also hope to provide enough simplified examples to both help users and stimulate developers. While we have a lot of tools for nonlinear parameter determination in R, we do not have enough well-organized guidance on their use or ways to effectively retire methods that are not good enough.

As a developer of such tools, I have found myself confronted on a number of occasions by users telling me that a colleague said my program was very good, but “it didn't work.” This has almost always been because the mode of use or choice of tool was inappropriate. Ideally, I aim to have the software identify such misapplication but that is a very difficult challenge that I have spent a good deal of my career addressing.

That said, I must note that many many items that appear in this book were developed or adjusted during its writing. The legacy of a very large and widely used open source system leaves much detritus that is not useful and many inconvenient loose ends. Some have been addressed as the writing progressed.

A word about the structure of this book. Readers who read cover to cover will find a certain amount of duplication. I have tried to make each chapter somewhat self-contained. This does not mean that I will not refer the reader to other chapters, but it does mean that sometimes there is repetition of ideas that are also treated elsewhere. This is done to make it easier to read chapters independently.

Any book, of course, owes a lot to people other than the author. I cannot hope to do justice to every person who has helped with ideas or support, but the following, in no particular order, are the names of some people who I feel have contributed to the writing of this book: Mary Nash, Ravi Varadhan, Stephen Nash, Hans Werner Borchers, Claudia Beleites, Nathan Lemoine, Paul Gilbert, Dirk Eddelbeuttel, John Fox, Ben Bolker, Doug Bates, Kate Mullen, Richard Alexander and Gabor Grothendieck.

John C. Nash