Differentiable Optimization and Equation Solving: A Treatise on Algorithmic Science and the Karmarkar Revolution

Cover......Page 1
Title Page......Page 4
ISBN 0387955720......Page 5
Preface......Page 8
Contents......Page 12
I Foundations......Page 20
1.1 Classical Portrait of the Field......Page 22
1.2 Modern Portrait of the Field......Page 25
1.3 Overview of Monograph......Page 27
1.4 Notes......Page 29
2.1 Introduction......Page 30
2.2 Model-Based Perspective......Page 32
2.3 Metric-Based Perspective......Page 35
2.4 Newton–Cauchy Framework......Page 41
2.5 Notes......Page 43
3.1 Introduction......Page 44
3.2 The EN Method......Page 47
3.3 The LNC Method......Page 54
3.4 Notes......Page 64
II Lessons from One Dimension......Page 66
4 A Misleading Paradigm......Page 68
4.1 The Unidimensional Potential Function......Page 69
4.2 Globally Convergent Algorithms......Page 70
4.3 Rapidly Convergent Local Algorithms......Page 71
4.5 Summary......Page 73
5 CG and the Line Search......Page 76
5.1 The Linear CG Algorithm......Page 77
5.2 Nonlinear CG-Related Algorithms......Page 79
5.3 The Key Role of the Line Search......Page 81
5.4 A Line-Search Fortran Routine......Page 82
5.5 CG: Whither or Wither?......Page 85
5.6 Notes......Page 91
6 Gilding the Nelder–Mead Lily......Page 92
6.1 Golden-Section Search......Page 93
6.2 The Nelder–Mead Algorithm......Page 94
6.3 Gilding the Lily......Page 95
6.4 Numerical Experiments......Page 97
6.6 Notes......Page 98
III Choosing the Right Diagonal Scale......Page 100
7 Historical Parallels......Page 102
7.1 The Simplex Algorithm......Page 103
7.2 The Affine-Scaling Algorithm......Page 105
7.3 Numerical Illustration......Page 106
7.4 Historical Parallels......Page 110
7.5 Notes......Page 112
8 LP from the Newton–Cauchy Perspective......Page 114
8.1 Primal Affine Scaling......Page 115
8.2 Dual Affine Scaling......Page 117
8.3 Primal–Dual Affine Scaling......Page 118
8.5 Convergence and Implementation......Page 120
8.6 Notes......Page 121
9 Diagonal Metrics and the QC Method......Page 122
9.1 A Quasi-Cauchy Algorithm......Page 124
9.2 The QC Method......Page 127
9.3 Extension of the NC Framework......Page 130
9.4 Notes......Page 132
IV Linear Programming Post-Karmarkar......Page 134
10 LP from the Euler–Newton Perspective......Page 136
10.1 The Parameterized Homotopy System......Page 137
10.2 Path-Following Building Blocks......Page 143
10.3 Numerical Illustration......Page 148
10.4 Path-Following Algorithms......Page 151
10.5 Mehrotra’s Implementation......Page 159
10.6 Summary......Page 163
10.7 Notes......Page 164
11 Log-Barrier Transformations......Page 166
11.1 Derivation......Page 167
11.2 Special Cases......Page 170
11.3 Discussion......Page 171
11.4 Notes......Page 172
12 Karmarkar Potentials and Algorithms......Page 174
12.1 Derivation......Page 175
12.2 A Potential-Reduction Algorithm......Page 177
12.3 Discussion......Page 180
12.5 Notes......Page 182
V Algorithmic Science......Page 184
13.1 Introduction......Page 186
13.2 Duality......Page 187
13.3 Invariance......Page 190
13.4 Symmetry......Page 191
13.5 Conservation......Page 193
13.6 The “Essentialist” View......Page 194
13.7 Notes......Page 196
14.1 Background......Page 198
14.2 Population-Thinking and Multialgorithms......Page 205
14.3 CG Multialgorithms: A Case Study......Page 206
14.4 The Multialgorithms Paradigm......Page 214
14.5 Parallel Computing Platform......Page 217
14.6 Other Topics......Page 218
14.7 Recapitulation......Page 221
14.8 Notes......Page 222
15 An Emerging Discipline......Page 224
15.1 Background......Page 225
15.2 What Is an Algorithm?......Page 227
15.3 Models of Computation......Page 230
15.4 Conceptual Algorithms......Page 234
15.5 Implementable Algorithms......Page 235
15.6 Algorithmic Science......Page 241
15.7 Notes......Page 242
References......Page 244
A......Page 270
F......Page 271
L......Page 272
N......Page 273
Q......Page 274
W......Page 275