PRACTICAL
`OPTIMIZATION
`
`" ----.L
`
`Philip E. Gill
`I Walter Murray
`. and
`Margaret H. Wright
`
`Constellation Exhibit 2008
`LG Electronics, Inc. v. Constellation Designs, LLC
`IPR2022-01549
`Page 1 of 421
`
`

`

`Constellation Exhibit 2008, Page 2 of 421
`
`Constellation Exhibit 2008, Page 2 of 421
`
`

`

`PRACTICAL
`OPTIMIZATION
`
`Constellation Exhibit 2008, Page 3 of 421
`
`

`

`Constellation Exhibit 2008, Page 4 of 421
`
`Constellation Exhibit 2008, Page 4 of 421
`
`

`

`PRACTICAL
`OPTIMIZATION
`PHILIP E. GILL
`WALTER MURRAY
`
`Systems Optimization Laboratory
`MARGARET H. WRIGHT
`
`Department of Operations Research
`
`Stanford University
`
`California, USA
`
`@ ACADEMIC PRESS
`
`Harcourt Brace and Company, Publishers
`London San Diego New York
`Boston Sydney Tokyo Toronto
`
`Constellation Exhibit 2008, Page 5 of 421
`
`

`

`ACADEMIC PRESS LIMITED
`24/28 Oval Road,
`
`London NWI 7DX
`
`United States Edition published by
`
`ACADEMIC PRESS, INC.
`
`San Diego, CA 92101
`
`Copyright © 1981 by
`
`ACADEMIC PRESS LIMITED
`1997
`Eleventh Printing
`
`All rights reserved
`or any other
`microfilm,
`in any form by photostat,
`No part of this book may be reproduced
`from the publishers
`means, without written permission
`
`in Publication
`Data
`Library Cataloguing
`British
`Gill, P.E.
`optimization
`Practical
`optimization
`III. Wright, M.H.
`
`1. Mathematics
`I. Title II. Murray, W.
`515 QA402.5
`ISBN 0-12-283950-1
`ISBN 0-12-283952-8
`LCCCN 81-66366
`
`(hardback)
`(paperback)
`
`Printed in Great Britain by
`The Bath Press, Bath
`
`Constellation Exhibit 2008, Page 6 of 421
`
`

`

`PRE FACE
`
`As researchers at the National Physical Laboratory and Stanford University, and a s con­
`
`
`
`
`
`
`
`
`
`
`tributors to the Numerical Algorithms Group (NAG) software library, we have been involved for
`
`
`
`
`
`many years in the development of numerical methods and software for the solution of optimiza­
`
`
`
`tion problems. Within the past twenty years, there has been a dramatic increase in the efficiency
`
`
`
`
`
`and reliability of optimization methods for almost all problem categories. However, this improved
`
`
`
`
`
`capability has been achieved by the use of more complicated ideas, particularly from the areas of
`
`
`
`numerical linear algebra and finite-precision calculation.
`The best methods available today are extremely complex, and their manner of operation is far
`
`
`
`
`
`
`
`
`
`from obvious, especially to users from other disciplines. This book is intended as a treatment -
`
`necessarily broad - of the subject of
`
`
`The word "practical" is included in
`
`practical optimization.
`
`
`
`
`the title in order to convey our concern not only with the motivation for optimization methods,
`
`
`
`
`
`but also with details of implementation that affect the performance of a method in practice.
`
`
`
`
`
`In particular, we believe that some consideration of the effects of finite-precision computation
`
`
`
`
`is essential in order for any description of a method to be useful. We also believe that it is
`
`
`
`
`
`
`
`important to discuss the linear algebraic processes that are used to perform certain portions of
`
`all optimization methods.
`This book is meant to be largely self-contained; we have therefore devoted one chapter to
`
`
`
`
`
`
`
`
`
`a description of the essential results from numerical linear algebra and the analysis of rounding
`
`
`
`
`
`
`
`errors in computation, and a second chapter to a treatment of optimality conditions.
`
`
`
`
`
`Selected methods for unconstrained, linearly constrained, and nonlinearly constrained op­
`
`
`
`
`
`timization are described in three chapters. This discussion is intended to present an overview of
`
`
`
`
`
`the methods, including the underlying motivation as well as particular theoretical and computa­
`
`
`
`
`
`tional features. Illustrations have been used wherever possible in order to stress the geometric
`
`
`
`
`interpretation of the methods. The methods discussed are primarily those with which we have
`
`
`
`had extensive experience and success; other methods are described that provide special insights
`
`
`
`
`
`
`or background. References to methods not discussed and to further details are given in the ex­
`
`
`
`
`tensive Notes and Bibliography at the end of each section. The methods have been presented in
`
`
`sufficient detail to allow this book to be used as a text for a university-level course in numerical
`optimization.
`Two chapters are devoted to selected less formal, but nonetheless crucial, topics that might
`
`
`
`
`
`
`
`
`
`be viewed as "advice to users". For example, some suggestions concerning modelling are included
`
`
`
`
`because we have observed that an understanding of optimization methods can have a beneficial
`
`effect on the modelling of the activiti
`
`
`es to be optimized. In addition, we have presented an
`
`
`
`extensive discussion of topics that are crucial in using and understanding optimization
`
`
`
`
`
`method - such as selecting a method, interpreting the computed results, and diagnosing (and,
`
`
`
`
`
`if possible, curing) difficulties that may cause an algorithm to fail or perform poorly.
`
`Ii, numerical
`
`v
`
`Constellation Exhibit 2008, Page 7 of 421
`
`

`

`Preface
`
`In writing this book, the authors have had the benefit of advice and help from many people.
`
`
`
`
`
`
`
`In particular, we offer special thanks to our friend and colleague Michael Saunders, not only
`
`
`
`
`for many helpful comments on various parts of the book, but also for all of his characteristic
`
`
`
`
`good humour and patience when the task of writing this book seemed to go on forever. He has
`played
`
`
`a maj or role in much of the recent work on algorithms for large-scale problems described
`
`in Chapters 5 and 6.
`We gratefully acknowledge David Martin for his tireless help and support for the optimization
`
`
`
`
`
`group at the National Physical Laboratory, and George Dantzig for his efforts to assemble the
`
`
`
`algorithms group at the Systems Optimization Laboratory, Stanford University.
`
`We thank Brian Hinde, Susan Hodson, Enid Long and David Rhead for their work in
`
`
`
`
`developing and testing many of the algorithms described in this book.
`
`
`
`We are grateful to Greg Dobson, David Fuchs, Stefania Gai, Richard Stone and Wes Winkler,
`
`
`
`
`who have been helpful in many ways during the preparation of this manuscript. The clarity of
`
`
`
`
`certain parts of the text has been improved because of helpful comments from Paulo Benevides­
`
`
`Soares, Andy Conn, Laureano Escudero, Don Iglehart, James Lyness, Jorge More, Michael
`
`Overton and Danny Sorensen.
`on the Laserscan plotter
`We thank Clive Hall for producing the computer-generated figures
`
`
`
`
`
`
`
`at the National Physical Laboratory. The remaining diagrams were expertly drawn by Nancy
`Cimina.
`This book was typeset by the authors using the � mathematical typesetting system of Don
`
`
`
`
`
`
`Knuth*. We are grateful
`to Don Knuth for his efforts in devising the � system, and for making
`
`
`
`available to us various � macros that improved the quality of the final text. We also thank him
`
`
`
`for kindly allowing us to use the Alphatype CRS typesetter, and Chris Tucci for his substantial
`
`
`help in producing the final copy.
`Finally, we offer our deepest personal thanks to those closest to us, who have provided
`
`
`
`
`
`
`
`
`
`
`
`encouragement, support and humour during the time-consuming process of writing this book.
`
`Stanford University
`
`May, 1981
`
`P. E. G .
`W.M.
`M.H.W.
`
`*D. E. Knuth, TEX and METAFONT, New Directions
`
`
`
`
`
`in Typesetting, American Mathematical Society and Digital
`
`
`
`vi
`
`
`
`Press, Bedford, Massachusetts (1979).
`
`
`
`
`
`Constellation Exhibit 2008, Page 8 of 421
`
`

`

`CONTENTS
`
`Those sections marked with "*,, contain material of a rather specialized nature that may be
`
`
`
`
`
`
`
`omitted on first reading.
`
`CHAPTER 1. INTRODUC TION . . . . . . . . . .
`
`.
`
`2 . 1 . INTRODUCTION TO ERRORS I N NUMERICAL COMPUTATION
`7
`
`2.1 . 1 . Measurement of Error . . . . . . .
`7
`
`
`2 . 1 .2. Number Representation on a Computer . . .
`8
`
`2.1.3. Rounding Errors . . . . . . . . . . . . .
`9
`
`
`
`
`2.1 .4. Errors Incurred during Arithmetic Operations
`. 11
`
`2.1 . 5 . Cancellation Error . . . . . . . . .
`
`
`2.1 .6. Accuracy in a Sequence of Calculations
`
`2 . 1 . 7 . Error Analysis of Algorithms . . . . .
`
`
`
`
`Notes and Selected Bibliography for Section 2 . 1
`2.2.
`INTRODUCTION T O NUMERICAL LINEAR ALGEBRA
`
`2.2.1 . Preliminaries. .
`
`2.2. 1 . 1 . Scalars
`2.2.1 .2. Vectors
`2.2.1 .3. Matrices
`2.2.1 .4. Operations with vectors and matrices
`
`
`2.2.1 . 5 . Matrices with special structure
`2.2.2. Vector Spaces . . . . . . . . . . . . . .
`
`
`2.2. 2 .1 . Linear combinations . . . . . . .
`2.2.2.2.
`
`Linear dependence and independence
`2.2.2.3.
`Vector spaces; subspaces; basis
`
`
`2.2.2.4. The null space . . . . . .
`
`2.2.3. Linear Transformations . . . . . . .
`
`2.2.3.1 . Matrices as transformations
`
`
`2.2.3.2. Properties of linear transformations
`
`2.2.3.3. Inverses . . . . . . . .
`
`
`
`2.2.3.4. Eigenvalues; eigenvectors . . . .
`
`13
`14
`14
`14
`14
`
`15
`
`· 14
`· 16
`· 18
`· 19
`· 19
`· 20
`· 21
`· 22
`· 23
`· 23
`· 23
`· 24
`· 24
`
`1
`
`1
`3
`5
`
`7
`
`. 11 · 13
`
`1 . 1 . DEFINITION OF OPTIMIZATION PROBLEMS . .
`1 .2. CLASSIFICATION OF OPTIMIZATION PROBLEMS
`1 .3. OVERVIEW OF TOPICS . .
`
`CHAPTER 2. FUNDA M EN TALS
`
`.
`
`vii
`
`Constellation Exhibit 2008, Page 9 of 421
`
`

`

`Table of Contents
`
`.
`
`2.2.3.5. Definiteness . . . . . . . .
`
`
`
`2.2.4. Linear Equations . . . . . . . . . .
`
`
`
`2.2.4.1 . Properties o f linear equations .
`2.2.4.2.
`Vector and matrix norms
`
`
`2.2.4.3. Perturbation theory; condition number
`
`
`2.2.4.4. Triangular linear systems
`
`
`2.2.4.5. Error analysis . . . . . . . . . . .
`
`
`2.2.5. Matrix Factorizations . . . . . . . . . . . .
`
`2.2.5.1 . The LU factori
`zation; Gaussian elimination
`The LDLT and Cholesky 2.2.5.2. factorizations . .
`
`
`
`
`
`2 . 2 . 5.3. The QR factorization . . . . . . . . . .
`
`
`
`2 . 2.5.4. The spectral decomposition of a symmetric matrix
`
`
`
`
`2.2.5.5. Singular-value decomposition .
`
`
`2.2.5.6. The pseudo-inverse . . . . .
`
`
`
`2.2.5.7. Updating matrix factorizations
`
`
`
`2.2.6. Multi-dimensional Geometry . . . .
`
`
`Notes and Selected Bibliography for Section 2 . 2
`2.3. ELEMENTS OF MULTIVARIATE ANALYSIS
`
`
`2.3.1 . Functions of Many Variables; Contour Plots
`2.3.2.
`
`Continuous Functions and their Derivatives
`
`2.3.3. Order Notation. . . . . . . . . . . . .
`
`2.3.4. Taylor's Theorem . . . . . . . . . . . .
`2.3.5.
`
`
`
`
`Finite-Difference Approximations to Derivatives.
`2.3.6.
`
`
`Rates of Convergence of Iterative Sequences
`
`
`Notes and Selected Bibliography for Section 2.3
`
`· 25
`· 25
`· 25
`· 27
`· 28
`· 30
`· 31
`· 32
`· 33
`· 36
`· 37
`· 40
`· 40
`· 41
`· 41
`· 43
`· 45
`· 45
`. 46 · 5 2
`· 52
`· 54
`· 56
`· 58
`· 59
`· 59
`· 61
`· 61
`. 63 · 65
`· 67
`· 68
`. 71 · 75
`· 76
`. 77 · 78
`· 8 1
`· 8 2
`
`. 45
`
`CHAPTER 3 . OPTIMALITY CONDITIONS .
`
`3.1 . CHARACTERIZATION O F A MINIMUM
`3.2. UNCONSTRAINED OPTIMIZATION
`3.2.1 .
`The Univariate Case
`
`3.2.2.
`The Multivariate Case . . . . . .
`
`
`3.2.3.
`
`
`Properties of Quadratic Functions
`3.3. LINEARLY CONSTRAINED OPTIMIZATION
`
`
`
`3.3.1 . Linear Equality Constraints . . . . .
`
`
`
`
`3.3.2. Linear Inequality Constraints. . . . .
`
`
`3.3. 2 . 1 . General optimality conditions
`
`
`3.3.2.2. Linear programming . . . .
`
`
`
`3.3.2.3. Quadratic programming . . .
`3.3.2.4.
`Optimization subject to bounds .
`3.4. NONLINEARLY CONSTRAINED OPTIMIZATION.
`
`
`
`3.4.1 . Nonlinear Equality Constraints . . . .
`
`
`
`3.4.2. Nonlinear Inequality Constraints . . .
`
`
`Notes and Selected Bibliography for Section 3.4
`
`viii
`
`. 71
`
`. 77
`
`Constellation Exhibit 2008, Page 10 of 421
`
`

`

`Table of Contents
`
`CHAPTER 4. U N C ONSTRAINED M ETHODS . .
`4.1 . METHODS FOR UNNARIATE FUNCTIONS
`4.1.1 . Finding
`
`a Zero of a Univariate Function
`
`4.1 . 1 . 1 . The method of bisection . . .
`4.1.1.2. Newton's method . . . . . .
`
`4.1.1.3. Secant and regula
`
`falsi methods
`*4.1.1.4.
`
`Rational interpolation
`
`and higher-order methods
`
`4.1.1.5. Safeguarded
`
`zero-finding algorithms
`4.1.2. Univariate
`Minimization
`
`4.1.2.1. search . . . .
`Fibonacci
`4.1.2.2.
`search . .
`Golden section
`4.1.2.3.
`
`
`Polynomial interpolation .
`4.1.2.4.
`
`
`Safeguarded polynomial interpolation
`4.1 . . .
`
`
`Notes and Selected Bibliography for Section
`4.2. METHODS FOR MULTNARIATE
`NON-SMOOTH FUNCTIONS.
`4.2.1 . Use of Function
`Comparison Methods .
`4.2.2.
`. . . . . . .
`
`The Polytope Algorithm
`*4.2.3.
`
`
`Composite Non-Differentiable Functions
`4.2
`
`Notes and Selected Bibliography for Section
`4.3. METHODS FOR MULTNARIATE
`SMOOTH FUNCTIONS
`4.3.1 . A Model Algorithm
`for Smooth Functions
`4.3.2.
`
`Convergence of the Model Algorithm
`
`
`4.3.2.1 . Computing the step length. . . .
`4.3.2.2.
`
`
`Computing the direction of search
`for Section 4.3
`
`Notes and Selected Bibliography
`4.4. SECOND DERNATNE METHODS . . .
`
`4.4.1 . Newton's Method. . . . . . . . . .
`4.4.2.
`. .
`
`
`Strategies for an Indefinite Hessian
`4.4.2.1. A method based o n the spect
`ral decomposition
`*4.4.2.2. Methods
`
`
`based on the Cholesky factorization
`Bibliography for Section 4.4
`Notes and Selected
`4.5. FIRST DERNATNE METHODS
`4.5.1. Discrete Newton Methods
`
`4.5.2. Quasi-Newton Methods .
`
`4.5.2.1 . Theory . . . .
`4.5.2.2.
`
`Implementation.
`*4.5.2.3.
`Convergence; least-change characterization
`
`
`
`
`Notes and Selected Bibliography for Section
`4.6. NON-DERNATNE METHODS FOR SMOOTH FUNCTIONS
`4.6.1 . Finite-Diff
`
`
`erence Approximations to First Derivatives
`4.6. 1 . 1 .
`.
`
`
`Errors in a forward-difference approximation
`interval . . . .
`4.6.1.2. Choice
`of the finite-difference
`4.6.1 .3. Estimation
`
`of a set of finite-difference intervals
`4.6.1.4. The choice
`
`of finite-difference formulae
`ix
`
`4.5 . . . . .
`
`.
`
`· 83
`· 83 · 83
`· 84
`· 84
`· 85
`· 87
`· 87
`· 88 · 89
`· 90
`· 91
`· 92 · 92
`· 93
`· 93
`· 94 · 96
`· 98 · 99
`· 99
`· 99
`
`100
`102
`104
`105
`105
`107
`107
`108
`111
`115
`115
`116
`116
`122
`123
`125
`127
`127
`127
`128
`129
`130
`
`Constellation Exhibit 2008, Page 11 of 421
`
`

`

`Table of Contents
`
`131
`4.6.2.
`Non-Derivative Quasi-Newton Methods
`
`
`131
`4.6
`
`
`
`Notes and Selected Bibliography for Section
`4.7. METHODS FOR SUMS OF SQUARES
`133
`
`4.7.1. Origin of Least-Squares Problems; the Reason for Special Methods
`133
`134
`4.7.2. The Gauss-Newton Method
`4.7.3.
`136
`
`The Levenberg-Marquardt Method .
`137
`*4.7.4.
`
`
`Quasi-Newton Approximations . . .
`*4.7.5.
`138
`
`The Corrected Gauss-Newton Method
`139
`
`*4.7.6. Nonlinear Equations . . . . . . .
`4.7
`140
`
`
`Notes and Selected Bibliography for Section
`4.8. METHODS FOR LARGE-SCALE PROBLEMS
`141
`4.8.1.
`141
`Sparse Discrete Newton Methods
`*4.8.2.
`143
`Sparse Quasi-Newton Methods
`4.8.3.
`
`Conjugate-Gradient Methods . .
`144
`4.8.3.1.
`
`
`Quadratic functions . .
`144
`4.8.3.2.
`146
`
`
`The linear conjugate-gradient method
`4.8.3.3.
`
`
`General nonlinear functions . . . .
`147
`
`*4.8.3.4.
`149
`
`
`Conjugate-gradient methods with restarts
`*4.8.3.5.
`
`Convergence . . . . . . . . . .
`149
`*4.8.4.
`150
`
`Limited-Memory Quasi-Newton Methods
`*4.8.5.
`151
`
`
`Preconditioned Conjugate-Gradient Methods
`*4.8.5.1.
`. . . . . . .
`151
`Quadratic functions
`*4.8.5.2.
`
`
`Nonlinear functions . . . . . . .
`152
`*4.8.6.
`153
`
`
`Solving the Newton Equation by Linear Conjugate-Gradients
`4.8
`153
`
`
`Notes and Selected Bibliography for Section
`
`of Algorithms . . . . . . . .
`
`CHAPTER 5. LIN EAR C O NSTRAINTS . . . . .
`5.1. METHODS FOR LINEAR EQUALITY CONSTRAINTS
`5.1.1. The Formulation
`5.1.1.1.
`The effect of linear equality constraints
`
`5.1.1.2.
`
`A model algorithm . . . .
`
`5.1.2. Computation of the Search Direction
`5.1.2.1.
`
`Methods of steepest descent
`5.1.2.2.
`
`Second derivative methods
`
`5.1.2.3. Discrete Newton methods .
`5.1.2.4.
`
`Quasi-Newton methods . .
`5.1.2.5.
`Conjugate-gradient-related methods .
`
`
`
`
`
`5.1.3. Representation of the Null Space of the Constraints.
`
`5.1.3.1. The LQ factorization . . . . .
`5.1.3.2.
`
`
`
`The variable-reduction technique
`5.1.4. Special Forms of the Objective Function
`5.1.4.1.
`
`Linear objective function
`5.1.4.2.
`
`
`Quadratic objective function
`5.1.5.
`
`
`Lagrange Multiplier Estimates
`
`155
`155
`156
`156
`157
`158
`158
`159
`160
`160
`161
`162
`162
`163
`163
`163
`164
`164
`
`x
`
`Constellation Exhibit 2008, Page 12 of 421
`
`

`

`Table of Contents
`
`. . . .
`
`superbasic variables.
`
`165
`5 . 1 . 5 . 1 . First-order multiplier estimates .
`
`
`
`
`166
`
`
`5 . 1.5.2. Second-order multiplier estimates
`166
`
`
`
`Notes and Selected Bibliography for Section 5 . 1 .
`167
`5.2. ACTIVE SET METHODS FOR LINEAR INEQUALITY CONSTRAINTS
`
`5 .2.1 . A Model Algorithm . . . . . . . . . . . . . . . .
`168
`169
`
`
`
`and Step Length. 5 .2.2. Computation of the Search Direction
`170
`5.2.3.
`
`
`
`Interpretation of Lagrange Multiplier Estimates
`172
`
`* 5.2.4. Changes in the Working Set . . . . .
`of Z . . . . . .
`*5 .2.4.1 . Modification
`172
`173
`* 5.2.4.2.
`Modification of other matrices
`174
`
`
`
`
`Notes and Selected Bibliography for Section 5.2
`176
`5.3. SPECIAL PROBLEM CATEGORIES
`176
`5.3.1 . Linear Programming
`177
`
`
`5 .3.2. Quadratic Programming . . .
`177
`
`
`5.3.2.1 . Positive-definite quadratic programming
`178
`5.3.2.2. Indefinite
`
`
`quadratic programming . .
`*5.3.3. Linear Least-Squares with Linear Constraints
`180
`181
`
`
`Notes and Selected Bibliography for Section 5.3 . . .
`*5.4. PROBLEMS WITH FEW GENERAL LINEAR CONSTRAINTS
`182
`
`
`*5.4.1 . Positive-Definite Quadratic Programming
`. . . . . . . 183
`
`*5 .4.2. Second Derivative Methods. . . . . . . . . . . . . .
`184
`
`*5.4.2.1 . A method based on positive-definite quadratic
`programming 184
`*5.4.2.2. A method based on an approximation
`of the projected Hessian 185
`
`
`Notes and Selected Bibliography for Section 5.4
`185
`186
`5.5. SPECIAL FORMS OF THE CONSTRAINTS . . . . . . . . . . .
`186
`
`
`5.5.1 . Minimization Subject to Simple Bounds . . . . . . . . . .
`
`
`*5 . 5 .2. Problems with Mixed General Linear Constraints and Bounds
`188
`190
`
`Bibliography for Section 5.5 . . . . . . . .
`Notes and Selected
`190
`5.6. LARGE-SCALE LINEARLY CONSTRAINED OPTIMIZATION
`190
`
`
`5.6.1 . Large-scale Linear Programming . . . . . . . . . . .
`193
`
`
`
`5.6.2. General large-scale linearly constrained optimization
`*5.6.2.1 . Computation of the change in the
`1 94
`
`
`
`
`*5.6.2.2. Changes in the active set
`195
`1 96
`
`
`Notes and Selected Bibliography for Section 5.6
`198
`199
`
`*5.7. FINDING AN INITIAL FEASmLE POINT . .
`
`Notes and Selected Bibliography for Section 5.7
`
`
`
`*5.8. IMPLEMENTATION OF ACTIVE SET METHODS
`
`
`*5.8.1 . Finding the Initial Working Set.
`
`
`*5 .8.2. Linearly Dependent Constraints
`
`
`
`*5.8.3. Zero Lagrange Multipliers . . .
`
`
`Notes and Selected Bibliography for Section 5.8
`
`199
`199
`201
`201
`203
`
`xi
`
`Constellation Exhibit 2008, Page 13 of 421
`
`

`

`CHAPTER 6. N O N L I N EA R C O NSTRAINTS .
`
`Table of Contents
`
`205
`
`6 . 1 . THE FORMULATION O F ALGORITHMS
`6 . 1 . 1 .
`
`The Definition o f a Merit Function
`
`
`6 . 1 . 2 . The Nature of Subproblems . . .
`6.1 . 2 . 1 .
`
`
`Adaptive and deterministic subproblems
`
`6 . 1. 2 . 2 . Valid and defective subproblems
`
`6.2. PENALTY AND BARRIER FUNCTION METHODS
`. . .
`AND GRADIENT�PROJECTION METHODS
`.
`
`206
`206
`206
`206
`207
`207
`207
`6.2 . 1 . Differentiable Penalty and Barrier Function Methods
`
`
`
`
`208
`
`
`
`6.2. 1 . 1 . The quadratic penalty function
`2 1 2
`
`
`
`6 . 2 . 1 . 2 . The logarithmic barrier function . .
`2 1 4
`
`
`
`
`6.2.2. Non-Differentiable Penalty Function Methods.
`2 1 5
`
`
`
`6.2.2 . 1 . The absolute value penalty function .
`2 1 7
`
`
`A method for general non-differentiable problems
`6.2.2.2.
`2 1 8
`
`
`Notes and Selected Bibliography for Section 6 . 2 . . . . . . . .
`2 1 9
`6.3. REDUCED-GRADIENT
`2 1 9
`6.3.1 . Motivation for Reduced-Gradient-Type Methods
`
`
`
`220
`
`
`Definition of a Reduced-Gradient-Type Method.
`6.3.2.
`220
`
`
`. 6.3.2 . 1 . Definition o f the null-space component
`222
`
`
`
`6.3.2.2. Restoration of feasibility. . . . . .
`222
`6.3.2.3.
`
`
`
`Reduction of the objective function . .
`223
`
`
`
`Properties of reduced-gradient-type methods
`6.3.2.4.
`223
`
`6.3.3. Determination of the Working Set
`
`224
`
`Notes and Selected Bibliography for Section 6.3 . . . . .
`
`
`225
`6.4. AUGMENTED LAGRANGIAN METHODS. . . . . . .
`225
`
`
`Function Lagrangian 6.4.1 . Formulation o f an Augmented
`
`
`
`
`
`6.4.2. An Augmented Lagrangian Algorithm . . . . . .
`226
`227
`
`
`6.4. 2 . 1 . A model algorithm . . . .
`6.4.2.2.
`228
`
`
`
`Properties of the augmented Lagrangian function
`
`
`*6.4.3. Variations in Strategy . . . . . . . .
`230
`
`
`Notes and Selected Bibliography for Section 6.4 . . .
`231
`233
`233
`233
`233
`234
`234
`235
`236
`237
`237
`238
`240
`241
`242
`242
`
`. . . . . .
`
`6.5. PROJECTED LAGRANGIAN METHODS . .
`.
`.
`.
`•
`
`Method 6.5 . 1 . Motivation for a Projected Lagrangian
`
`
`6.5 . 1 . 1 .
`
`
`Formulation of a linearly constrained subproblem
`
`
`6 . 5 . 1.2. Definition of the subproblem . . . .
`
`
`
`A General Linearly Constrained Subproblem .
`6.5.2.
`
`
`
`6.5.2.1 . Formulation o f the objective function
`
`
`
`6.5.2.2. A simplified model algorithm . . . .
`*6.5.2.3.
`
`Improvements to the model algorithm
`6.5.3.
`
`A Quadratic Programming Subproblem
`
`
`6.5.3.1 . Motivation. . . . . . . .
`6.5.3.2.
`
`
`A simplified model algorithm .
`6.5.3.3.
`Use of a merit function
`
`*6.5.3.4. Other formulations of the subproblem
`
`
`
`*6.5.4. Strategies for a Defective Subproblem .
`
`*6.5.4 . 1 . Incompatible linear constraints
`
`xii
`
`Constellation Exhibit 2008, Page 14 of 421
`
`

`

`Table of Contents
`
`. . .
`Bibliography for Section 6.6 . . .
`
`243
`*6. 5 . 4 . 2 . Poor approximation of the Lagrangian function.
`
`
`
`
`243
`
`
`*6. 5 . 5 . Determination of the Active Set . . . . . .
`244
`
`
`*6. 5. 5 .1 . An equality-constrained subproblem .
`244
`
`
`*6. 5 . 5 . 2 . An inequality-constrained subproblem
`245
`
`Notes and Selected Bibliography for Section 6 . 5
`247
`6.6. LAGRANGE MULTIPLIER ESTIMATES
`248
`
`
`6.6.1 . First-Order Multiplier Estimates . . .
`248
`
`
`
`6.6.2. Second-Order Multiplier Estimates . .
`250
`
`
`
`*6.6.3. Multiplier Estimates for Inequality Constraints
`250
`
`
`6.6.4. Consistency Checks . . . . . . . . .
`251
`Notes and Selected
`251
`*6. 7 . LARGE-SCALE NONLINEARLY CONSTRAINED OPTIMIZATION
`252
`*6.7.1 . The Use of a Linearly Constrained Subproblem
`
`253
`
`*6. 7 . 2 . The Use o f a Q P Subproblem . . . . . . . . . . . .
`254
`
`
`
`*6. 7 . 2 .1 . Representing the basis inverse . . . . . . . .
`255
`*6. 7 . 2 . 2 .
`
`
`
`The search direction for the superbasic variables
`256
`
`
`Notes and Selected Bibliography for Section 6.7
`256
`6.8. SPECIAL PROBLEM CATEGORIES
`257
`
`6.8.1 . Special Non-Differentiable Functions
`257
`
`
`
`6.8.2. Special Constrained Problems
`257
`6.8. 2 . 1 . Convex programming .
`258
`
`
`6 . 8 . 2 . 2 . Separable programming
`258
`
`
`6.8.2.3. Geometric programming
`259
`
`
`Notes and Selected Bibliography for Section 6.8
`
`C H APTER 7. M O DELLING
`
`7 . 1 . INTRODUCTION . . . . . . . . . . . . .
`
`7 . 2 . CLASSIFICATION O F OPTIMIZATION PROBLEMS
`7.3. AVOIDING UNNECESSARY DISCONTINUITIES .
`
`. 7.3.1 . The Role of Accuracy in Model Functions
`
`7 . 3 . 2 .
`
`Approximation by Series o r Table Look-Up
`7.3.3.
`Subproblems Based on Iteration
`
`
`
`Notes and Selected Bibliography for Section 7.3
`7.4. PROBLEM TRANSFORMATIONS . . . . .
`
`
`
`7.4.1 . Simplifying or Eliminating Constraints
`
`Elimination of simple bounds.
`7 . 4. 1 . 1 .
`
`7.4.1 . 2 . Elimination o f inequality constraints
`
`
`7.4.1 .3 . General difficulties with transformations
`
`
`7.4.1 .4. Trigonometric transformations . . . .
`7.4.2.
`
`
`Problems Where the Variables are Continuous Functions .
`
`
`Notes and Selected Bibliography for Section 7.4
`
`7 . 5 . SCALING . . . . . . . . . . . . . . . .
`
`7 . 5 .1 . Scaling by Transformation of Variables
`7 . 5 . 2 .
`
`Scaling Nonlinear Least-Squares Problems
`
`7.6. FORMULATION OF CONSTRAINTS xiii
`
`261
`
`261
`262
`263
`263
`265
`266
`267
`267
`267
`268
`269
`270
`271
`272
`273
`273
`273
`275
`276
`
`Constellation Exhibit 2008, Page 15 of 421
`
`

`

`Table of Contents
`
`7.6.1 . Indeterminacy in Constraint Formulation
`
`7.6.2.
`
`
`The Use of Tolerance Constraints . . . .
`
`
`
`Notes and Selected Bibliography for Section 7.6 .
`7.7. PROBLEMS WITH DISCRETE OR INTEGER VARIABL ES
`
`
`7.7.1 . Pseudo-Discrete Variables . . . . . .
`
`
`
`7.7.2. Integer Variables . . . . . . . . . .
`
`
`
`Notes and Selected Bibliography for Section 7.7
`
`CHAPTER 8. PRACTICALITIES
`
`276
`277
`280
`281
`281
`282
`283
`
`285
`
`285
`8 . 1 . USE OF SOFTWARE
`285
`
`8.1 . 1 . Selecting a Method .
`8.1 . 1 . 1 . Selecting an unconstrained method
`
`
`
`286
`
`
`8 . 1 . 1 .2. Selecting a method for linear constraints
`287
`
`
`8.1 . 1 .3. Selecting a method for nonlinear constraints
`290
`290
`
`8.1.2. The User Interface . . . .
`291
`
`
`
`8 . 1 . 2 . 1 . Default parameters . . . .
`
`
`
`8 . 1 . 2 . 2 . Service routines . . . . .
`291
`292
`
`
`8.1.3. Provision of User-Defined Parameters
`
`
`8 . 1 .3. 1 . The precision of the problem functions
`292
`
`
`
`8 . 1 .3.2. Choice of step-length algorithm.
`293
`
`
`8 . 1.3.3. Step-length accuracy . . . . . . . . 294
`8 . 1.3.4. Maximum step length . . . . . . . . 294
`
`
`
`8 . 1 .3.5. A bound on the number of function evaluations.
`295
`8.1.3.6. Local search . . . . . . . . . . . . . . . .
`295
`
`
`
`
`8 . 1.3.7. The penalty parameter in an augmented Lagrangian method 295
`
`
`8.1.3.8. The penalty parameter for a non-smooth problem.
`296
`296
`
`
`8.1.4. Solving the Correct Problem . . . . . .
`296
`
`
`8.1.4.1 . Errors in evaluating the function
`297
`
`
`
`8.1.4.2. Errors in computing derivatives.
`298
`
`8.1 . 5 . Making the Best o f the Available Software
`298
`
`
`
`8 . 1 . 5 . 1 . Nonlinear least-squares problems
`298
`
`
`
`8 . 1 . 5 . 2 . Missing derivatives . . . . . .
`
`
`
`
`8 . 1 . 5 .3. Solving constrained problems with an unconstrained routine 299
`
`8.1.5.4. Treatment of linear and nonlinear constraints
`299
`
`
`
`8 . 1 . 5 . 5 . Nonlinear equations . . . . .
`299
`
`
`Notes and Selected Bibliography for Section 8 . 1
`300
`
`8.2. PROPERTIES OF THE COMPU TED SOLUTION
`300
`
`8.2.1 . What is a Correct Answer? . .
`300
`8.2.2.
`
`
`The Accuracy of the Solution . . . . . .
`301
`
`
`8.2.2 . 1 . Unconstrained problems . . . . .
`301
`8.2.2.2.
`
`
`
`Accuracy in constrained problems .
`303
`
`
`8.2.3. Termination Criteria . . . . . . . . . .
`305
`
`
`8.2.3.1 . The need for termination criteria .
`305
`8.2.3.2.
`
`
`Termination criteria for unconstrained optimization
`306
`
`
`
`
`8.2.3.3. Termination criteria for linearly constrained optimization
`308
`
`xiv
`
`Constellation Exhibit 2008, Page 16 of 421
`
`

`

`Table of Contents
`
`
`
`
`
`
`
`
`8.2.3.5. Conditions for abnormal termination
`
`
`
`
`8.2.3.6. The selection of termination criteria.
`
`
`
`Notes and Selected Bibliography for Section 8.2
`
`8.2.3.4. Termination criteria for nonlinearly constrained optimization 308
`309
`310
`312
`
`8.3. ASSESSMENT OF RESULTS. . . . . . .
`312
`312
`8.3.1 . Assessing the Validity of the Solution
`
`312
`
`
`8.3. 1 . 1 . The unconstrained case . .
`315
`
`8.3.1.2. The constrained case
`Some Other Ways to Verify Optimality
`319
`8.3.2.
`
`8.3.2.1 . Varying the parameters of the algorithm
`319
`
`8.3.2.2. Using a different method
`319
`320
`
`
`
`8.3.2.3. Changing the problem .
`
`
`8.3.3. Sensitivity Analysis . . . . . .
`320
`320
`8.3.3 . 1 . The role o f the Hessian
`320
`number of the Hessian 8.3.3.2. Estimating the condition
`
`
`323
`8.3.3.3.
`
`
`Sensitivity of the constraints .
`
`
`
`Notes and Selected Bibliography for Section 8.3 . . . . . . .
`323
`
`8.4. WHAT CAN GO WRONG (AND WHAT TO DO ABOUT IT)
`
`8.4.1 . Overflow in the User-Defined Problem Functions
`
`
`8.4.2. Insufficient Decrease in the Merit Function
`
`
`
`
`8.4.2.1 . Errors in programming . . . .
`
`8.4.2.2. Poor scaling . . . . . . . . .
`
`
`
`8.4.2.3. Overly-stringent termination criteria
`8.4.2.4.
`
`
`Inaccuracy in a finite-difference approximation
`
`8.4.3. Consistent Lack of Progress . . . . . . .
`
`
`8.4.3.1 . Unconstrained optimization
`
`
`8.4.3.2. Linearly constrained optimization.
`
`
`
`8.4.3.3. Nonlinearly constrained optimization
`
`
`
`8.4.4. Maximum Number of Function Evaluations or Iterations
`
`
`
`
`Failure to Achieve the Expected Convergence Rate
`8.4.5.
`
`
`
`Failure to Obtain a Descent Direction . . . . . . . .
`8.4.6.
`
`324
`324
`324
`325
`325
`327
`327
`328
`328
`328
`328
`329
`329
`330
`
`8.5. ESTIMATING THE ACCURACY OF THE PROBLEM FUNCTIONS
`331
`. . . . . . . . . . . . . . . . . .
`331
`8.5.1 . The Role of Accuracy
`331
`
`
`8 . 5 .1 . 1 . A definition of accuracy . . . . . . . . . . . . .
`
`
`
`8.5.1 . 2 . How accuracy estimates affect optimization algorithms.
`331
`
`
`8 . 5 . 1.3. The expected accuracy . . . . . . .
`Accuracy. . . . . . . . . . . . . . . . . .
`333
`Estimating the
`8.5.2.
`
`
`
`8.5.2 . 1 . Estimating the accuracy when higher precision is available 333
`
`
`
`8.5.2.2. Estimating the accuracy when derivatives are available
`334
`
`
`
`8.5.2.3. Estimating the accuracy when only function values are available 335
`
`
`8.5.2.4. Numerical examples. . . . .
`336
`338
`
`
`
`8.5.3. Re-Estimation of the Accuracy . . . .
`
`
`Notes and Selected Bibliography for Section 8.5
`339
`
`.. . . . . . 332
`
`xv
`
`Constellation Exhibit 2008, Page 17 of 421
`
`

`

`Table of Contents
`
`339
`8.6. COMPUTING FINITE
`DIFFERENCES
`339
`8.6.1.
`ions; The Well-Scaled Case .
`
`
`Errors in Finite-Difference Approximat
`339
`8.6.1.1.
`
`The forward-difference formula
`
`8.6.1.2. The central-dformula . . . . .
`340
`ifference
`341
`
`8.6.1.3. Second-order . . .
`differences
`8.6.2.
`. 341
`
`
`
`A Procedure for Automatic Estimation of Finite-Difference Intervals
`342
`8.6.2.1.
`
`
`Motivation for the procedure
`8.6.2.2.
`. . . . . . . . . . . . . .
`343
`
`Statement of the algorithm
`
`8.6.2.3. examples. . . . . . . . . . . . . . . . . .
`344
`Numerical
`
`8.6.2.4. Estimating
`point 344
`
`the finite-difference interval at an arbitrary
`8.6.2.5.
`problems 345
`
`
`Finite-difference approximations in constrained
`346
`for Section 8.6
`
`Notes and Selected Bibliography
`
`. . . . . . .
`
`8.7. MORE ABOUT SCALING . . . . . . . . . 346
`8.7.1. Scaling the Variables . . . . . . . .
`346
`8.7.1.1. Scale-invariance
`346
`of an algorithm
`347
`8.7.1.2. The conditioning
`of the Hessian matrix
`8.7.1.3. Obtaining
`348
`
`well-scaled derivatives
`8.7.2.
`. . . . .
`351
`
`Scaling the Objective Function
`
`8.7.3. Scaling the Constraints . . . . . . . . 352
`8.7.3.1. Some effects of constraint.,scaling
`352
`353
`8.7.3.2.
`
`Methods for scaling linear constraints
`8.7.3.3.
`354
`
`
`Methods for scaling nonlinear constraints
`354
`8.7
`
`
`Notes and Selected Bibliography for Section
`
`QUESTIONS AND ANSWERS
`
`BIBLIOGRAPHY
`
`INDEX
`
`357
`363
`389
`
`xvi
`
`Constellation Exhibit 2008, Page 18 of 421
`
`

`

`Constellation Exhibit 2008, Page 19 of 421
`
`Constellation Exhibit 2008, Page 19 of 421
`
`

`

`CHAPTER ONE
`
`INTRODUCTION
`-KA RL MARX (1859)
`Msnkind slwsys sets itself only such problems ss it csn solve ... ,
`
`1.1. DEF I N ITION OF O PTIMIZATION PROBLEMS
`
`An optimization problem begins with a set of independent variables or parameters, and often
`
`
`
`
`
`
`
`
`
`
`includes conditions or restrictions that define acceptable values of the variables. Such restrictions
`
`
`are termed the constraints of the problem. The other essential component of an optimization
`
`problem is a single measure of "goodness" , termed the objective function, which depends in some
`
`
`
`
`
`
`
`way on the variables. The solution of an optimization problem is a set of allowed values of the
`
`
`
`
`
`variables for which the objective function