scientific article; zbMATH DE number 3915531

From MaRDI portal
Publication:3690974





Subject of the book are computational methods for discrete approximation problems. Given a set of n data (measurements) an element of a given, p- dimensional, linear space V of functions is sought such that the deviation from the data is minimized w.r.t. some norm. Mathematically the problem amounts to minimizing a function \(f(x)=\| Mx-f\|\), M an \(n\times p\) matrix, f the n-vector of data. Possibly the set of approximating functions may be further restricted to elements in V which satisfy additional linear constraints. Then f(x) is to be minimized subject to constraints Ax\(\leq b\). Choosing either \(\|\) \(\| =\|\) \(\|_ 1\) or \(\|\) \(\| =\|\) \(\|_{\infty}\) results in a function f being the pointwise maximum of finitely many affine functions (polyhedral convex function). Such problems - in an obvious way - can be restated as linear programming problems. Thus, in principle, \(\ell_ 1\) or \(\ell_{\infty}\) approximation may be considered either in the context of classical linear programming or in that of non-differentiable convex programming. Of course, the two approaches are strongly related if the second is restricted to polyhedral convex functions. In Chapters 3 and 4 for \(\ell_ 1\) and \(\ell_{\infty}\) approximation both approaches are considered. Chapters 1 and 2 give the theoretical and practical foundations. In Chapter 1 a short introduction into the theory of convex functions and convex programming is given, including conjugate functions and (Fenchel) duality. In addition, subgradient and \(\epsilon\)- subgradient methods are sketched forming the basis for the descent methods in Chapters 3 and 4. Chapter 2 is dedicated to the theory and computational methods for linear programming. In addition to the standard simplex method for equality constrained problems descent methods are considered for the inequality constraint case which are well-known specializations of reduced and projected gradient algorithms for general linearly constrained problems. Very valuable is the discussion of scaling - a point which usually receives too little attention in linear programming textbooks. In Chapter 5 least squares regression is considered including problems subject to linear constraints and so-called M-estimation. Chapter 6 comprises some applications to non-convex problems such as total approximation and cluster analysis. In a final Chapter a survey on complexity is given which includes the ellipsoid method and the work of Smale concerning the expected behavior of Lemke's algorithm. The book contains a lot of material for all of the above subjects and certainly the concentration on those aspects of (linear) programming that are relevant for data analysis is very attractive. Therefore, the book is surely valuable and recommendable for specialists in this field. Nevertheless, some critical remarks may be allowed. From the practical point of view it is surprising that much emphasize is given to the problem of degeneracy whereas numerical stability is treated quite incidentally. In the introduction the author states that the problem of manipulating sparse matrices is irrelevant for his considerations. This surely is true. Instead, however, the problem of ill-conditioning and numerical instability is more serious in practice than in most Operations Research applications. Moreover, in the preface applications to nonlinear problems are indicated which are iteratively solved by linearization. With respect to these, again it is surprising that the problem of finding and transmitting starting points for the algorithms is treated only incidentally. A second point of criticism is the rather accidental choice of literature included in the references. For instance, it is difficult to understand why - in dealing with descent methods for nondifferential programming - the work of for example Lemaréchal, Mifflin or the whole Russian school (Shor a.o.) are not even mentioned. Finally, the presentation often is unnecessarily complicated and yet indeterminate. Altogether, the book is surely useful for specialists as it contains a lot of details w.r.t. certain aspects of data-analysis. It seems less appropriate, however, for practitioners or as introductory text for students.




Cited in
(80)








This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3690974)