Nonlinear Parameter Optimization Using R Tools

JOHN C. NASH, Telfer School of Management, University of Ottawa, Canada

"The book chapters are enriched by little anecdotes, and the reader obviously benefits from John C. Nash's experience of more than 30 years in the field of nonlinear optimization. This experience translates into many practical recommendations and tweaks. The book provides plenty of code examples and useful code snippets." (Biometrical Journal, 2016)

• Preface xv1 Optimization problem tasks and how they arise 11.1 The general optimization problem 11.2 Why the general problem is generally uninteresting 21.3 (Non-)Linearity 41.4 Objective function properties 41.4.1 Sums of squares 41.4.2 Minimax approximation 51.4.3 Problems with multiple minima 51.4.4 Objectives that can only be imprecisely computed 51.5 Constraint types 51.6 Solving sets of equations 61.7 Conditions for optimality 71.8 Other classifications 7References 82 Optimization algorithms – an overview 92.1 Methods that use the gradient 92.2 Newton-like methods 122.3 The promise of Newton’s method 132.4 Caution: convergence versus termination 142.5 Difficulties with Newton’s method 142.6 Least squares: Gauss–Newton methods 152.7 Quasi-Newton or variable metric method 172.8 Conjugate gradient and related methods 182.9 Other gradient methods 192.10 Derivative-free methods 192.10.1 Numerical approximation of gradients 192.10.2 Approximate and descend 192.10.3 Heuristic search 202.11 Stochastic methods 202.12 Constraint-based methods – mathematical programming 21References 223 Software structure and interfaces 253.1 Perspective 253.2 Issues of choice 263.3 Software issues 273.4 Specifying the objective and constraints to the optimizer 283.5 Communicating exogenous data to problem definition functions 283.5.1 Use of “global” data and variables 313.6 Masked (temporarily fixed) optimization parameters 323.7 Dealing with inadmissible results 333.8 Providing derivatives for functions 343.9 Derivative approximations when there are constraints 363.10 Scaling of parameters and function 363.11 Normal ending of computations 363.12 Termination tests – abnormal ending 373.13 Output to monitor progress of calculations 373.14 Output of the optimization results 383.15 Controls for the optimizer 383.16 Default control settings 393.17 Measuring performance 393.18 The optimization interface 39References 404 One-parameter root-finding problems 414.1 Roots 414.2 Equations in one variable 424.3 Some examples 424.3.1 Exponentially speaking 424.3.2 A normal concern 444.3.3 Little Polly Nomial 464.3.4 A hypothequial question 494.4 Approaches to solving 1D root-finding problems 514.5 What can go wrong? 524.6 Being a smart user of root-finding programs 544.7 Conclusions and extensions 54References 555 One-parameter minimization problems 565.1 The optimize() function 565.2 Using a root-finder 575.3 But where is the minimum? 585.4 Ideas for 1D minimizers 595.5 The line-search subproblem 61References 626 Nonlinear least squares 636.1 nls() from package stats 636.1.1 A simple example 636.1.2 Regression versus least squares 656.2 A more difficult case 656.3 The structure of the nls() solution 726.4 Concerns with nls() 736.4.1 Small residuals 746.4.2 Robustness – “singular gradient” woes 756.4.3 Bounds with nls() 776.5 Some ancillary tools for nonlinear least squares 796.5.1 Starting values and self-starting problems 796.5.2 Converting model expressions to sum-of-squares functions 806.5.3 Help for nonlinear regression 806.6 Minimizing Rfunctions that compute sums of squares 816.7 Choosing an approach 826.8 Separable sums of squares problems 866.9 Strategies for nonlinear least squares 93References 937 Nonlinear equations 957.1 Packages and methods for nonlinear equations 957.1.1 BB 967.1.2 nleqslv 967.1.3 Using nonlinear least squares 967.1.4 Using function minimization methods 967.2 A simple example to compare approaches 977.3 A statistical example 103References 1068 Function minimization tools in the base R system 1088.1 optim() 1088.2 nlm() 1108.3 nlminb() 1118.4 Using the base optimization tools 112References 1149 Add-in function minimization packages for R 1159.1 Package optimx 1159.1.1 Optimizers in optimx 1169.1.2 Example use of optimx() 1179.2 Some other function minimization packages 1189.2.1 nloptr and nloptwrap 1189.2.2 trust and trustOptim 1199.3 Should we replace optim() routines? 121References 12210 Calculating and using derivatives 12310.1 Why and how 12310.2 Analytic derivatives – by hand 12410.3 Analytic derivatives – tools 12510.4 Examples of use of R tools for differentiation 12510.5 Simple numerical derivatives 12710.6 Improved numerical derivative approximations 12810.6.1 The Richardson extrapolation 12810.6.2 Complex-step derivative approximations 12810.7 Strategy and tactics for derivatives 129References 13111 Bounds constraints 13211.1 Single bound: use of a logarithmic transformation 13211.2 Interval bounds: Use of a hyperbolic transformation 13311.2.1 Example of the tanh transformation 13411.2.2 A fly in the ointment 13411.3 Setting the objective large when bounds are violated 13511.4 An active set approach 13611.5 Checking bounds 13811.6 The importance of using bounds intelligently 13811.6.1 Difficulties in applying bounds constraints 13911.7 Post-solution information for bounded problems 139Appendix 11.A Function transfinite 141References 14212 Using masks 14312.1 An example 14312.2 Specifying the objective 14312.3 Masks for nonlinear least squares 14712.4 Other approaches to masks 148References 14813 Handling general constraints 14913.1 Equality constraints 14913.1.1 Parameter elimination 15113.1.2 Which parameter to eliminate? 15313.1.3 Scaling and centering? 15413.1.4 Nonlinear programming packages 15413.1.5 Sequential application of an increasing penalty 15613.2 Sumscale problems 15813.2.1 Using a projection 16213.3 Inequality constraints 16313.4 A perspective on penalty function ideas 16713.5 Assessment 167References 16814 Applications of mathematical programming 16914.1 Statistical applications of math programming 16914.2 R packages for math programming 17014.3 Example problem: L1 regression 17114.4 Example problem: minimax regression 17714.5 Nonlinear quantile regression 17914.6 Polynomial approximation 180References 18315 Global optimization and stochastic methods 18515.1 Panorama of methods 18515.2 R packages for global and stochastic optimization 18615.3 An example problem 18715.3.1 Method SANN from optim() 18715.3.2 Package GenSA 18815.3.3 Packages DEoptim and RcppDE 18915.3.4 Package smco 19115.3.5 Package soma 19215.3.6 Package Rmalschains 19315.3.7 Package rgenoud 19315.3.8 Package GA 19415.3.9 Package gaoptim 19515.4 Multiple starting values 196References 20216 Scaling and reparameterization 20316.1 Why scale or reparameterize? 20316.2 Formalities of scaling and reparameterization 20416.3 Hobbs’ weed infestation example 20516.4 The KKT conditions and scaling 21016.5 Reparameterization of the weeds problem 21416.6 Scale change across the parameter space 21416.7 Robustness of methods to starting points 21516.7.1 Robustness of optimization techniques 21816.7.2 Robustness of nonlinear least squares methods 22016.8 Strategies for scaling 222References 22317 Finding the right solution 22417.1 Particular requirements 22417.1.1 A few integer parameters 22517.2 Starting values for iterative methods 22517.3 KKT conditions 22617.3.1 Unconstrained problems 22617.3.2 Constrained problems 22717.4 Search tests 228References 22918 Tuning and terminating methods 23018.1 Timing and profiling 23018.1.1 rbenchmark 23118.1.2 microbenchmark 23118.1.3 Calibrating our timings 23218.2 Profiling 23418.2.1 Trying possible improvements 23518.3 More speedups of R computations 23818.3.1 Byte-code compiled functions 23818.3.2 Avoiding loops 23818.3.3 Package upgrades - an example 23918.3.4 Specializing codes 24118.4 External language compiled functions 24218.4.1 Building an R function using Fortran 24418.4.2 Summary of Rayleigh quotient timings 24618.5 Deciding when we are finished 24718.5.1 Tests for things gone wrong 248References 24919 Linking R to external optimization tools 25019.1 Mechanisms to link R to external software 25119.1.1 R functions to call external (sub)programs 25119.1.2 File and system call methods 25119.1.3 Thin client methods 25219.2 Prepackaged links to external optimization tools 25219.2.1 NEOS 25219.2.2 Automatic Differentiation Model Builder (ADMB) 25219.2.3 NLopt 25319.2.4 BUGS and related tools 25319.3 Strategy for using external tools 253References 25420 Differential equation models 25520.1 The model 25520.2 Background 25620.3 The likelihood function 25820.4 A first try at minimization 25820.5 Attempts with optimx 25920.6 Using nonlinear least squares 26020.7 Commentary 261Reference 26221 Miscellaneous nonlinear estimation tools for R 26321.1 Maximum likelihood 26321.2 Generalized nonlinear models 26621.3 Systems of equations 26821.4 Additional nonlinear least squares tools 26821.5 Nonnegative least squares 27021.6 Noisy objective functions 27321.7 Moving forward 274References 275Appendix A R packages used in examples 276Index 279