Differentiable optimization and equation solving. A treatise on algorithmic science and the Karmarkar revolution (Q1866737)

The monograph is organized in five parts, each comprising three chapters, as follows: In the first part, the author considers algorithms for the unconstrained minimization and nonlinear equation-solving problems, respectively. In Chapter 2, is shown that a single underlying technique, the Newton-Cauchy method, lies at the heart of most unconstrained minimization algorithms in current use. In Chapter 3, examples illustrating the well-known fact that solving nonlinear equations via nonlinear least squares is useful in a particular sense, but inherently flawed from a conceptual standpoint, are given. The three Chapters of Part II, cover lessons that can be learned from unidimensional programming. The first Chapter 4, explains why algorithms for solving unconstrained minimization and nonlinear equation-solving for the special case \(n=1\) are much more closely interrelated than their multidimensional counterparts. Next, the role of the unidimensional line search in the fortune of the Fletcher-Reeves nonlinear conjugate-gradient algorithm is the topic of Chapter 5. Chapter 6, establishes a link between classical golden-section search and the generic Nelder-Mead direct search algorithm restricted to \(n=1\). Part III addresses the linear programming problem. Both the simplex algorithm of Dantzig and the affine-scaling interior algorithm of Dikin can be conveniently approached from the convexity side. These key algorithms along with the primal-dual variants are the focus of Chapters 7 and 8. The complexity of linear programming algorithms discussed in these two chapters is not known to be polynomial. Diagonal metrics for nonlinear unconstrained minimization problems, under the rubric quasi-Cauchy, are also considered in the concluding Chapter 9. Part IV again addresses the linear programming problem. The homotopy-based Euler-Newton method, applied to the Karush-Kuhn-Tucker optimality equations of a linear program, yields a variety of basic path-following interior algorithms discussed in Chapter 10. Extracting the fundamental connection with the classical logarithmic-barrier approach to nonlinear programming is the topic of Chapter 11. Barrier functions, in turn, motivate potential functions-the centerpiece of Karmarkar's algorithms-as discussed in Chapter 12. Linear programming algorithms given in this part usually exhibit polynomial complexity. Chapter 13 of the last Part considers, within the specific setting of the unconstrained minimization problem, basic algorithmic principles on which variable-metric and related algorithms are premised. Chapter 14 develops a new paradigm for optimization and equation-solving based on the fundamental Darwinian ideas of population-thinking and variation. Finally, Chapter 15 concludes the monograph with a philosophy and vision for emerging discipline of algorithmic science.