scientific article; zbMATH DE number 3846334

From MaRDI portal
Publication:3316094





The book is devoted to systematic exposition of the linearization method - the one of universal methods for solving nonlinear programming problems. Besides the description of the method in the general case, the author presents also its several modifications appropriate for specific problems such as convex programming problems, solutions to systems of equalities and inequalities, minimax problems, etc. Much attention is given to conditions of convergence of the algorithms presented as well as to the analysis of the rate of convergence. Some sections of the book are devoted to computational aspects. In {\S}2, the author gives briefly some basic results concerning optimality conditions for convex and nonlinear programming problems. It is noteworthy that Theorem 2.14, which gives a sufficient condition for the existence of an exact penalty function for a general nonlinear programming problem, is (by my knowledge) new and interesting not only from the point of view of the linearization method. {\S}3 contains a detailed description of an algorithm for solving quadratic programming problems. This algorithm is finite (i.e., gives the exact solution after a finite number of steps) and is a generalization of the simplex method for linear programming. In {\S}4, a general algorithm of the linearization method is presented and its convergence is proved. Next, it is shown that this algorithm is finite for linear programming problems. These results were presented earlier in {\S}III.5 of the book by the author and \textit{Yu. M. Danilin} [Numerical methods in extremal problems. (Russian) (1975; Zbl 0315.65035)]. Moreover, {\S}4 contains a discussion of the algorithm for the case of simple constraints (on each coordinate separately) and a method of choice of parameters in the general algorithm. In {\S}5, a modification of the linearization method appropriate for solving systems of equalities and inequalities is given. Under some additional assumptions, it is proved that the rate of convergence of the algorithm is quadratic. In {\S}6, the author constructs a modified algorithm (for the general problem considered in {\S}4, but under additional regularity assumptions) such that the rate of convergence is quadratic in some neighbourhood of the solutions. The case of a convex programming problem is considered separately. {\S}7 contains some versions of the linearization algorithm for solving discrete minimax problems. {\S}8 presents a dual algorithm for convex programming problems (this paragraph is not connected with the linearization method). Finally, in {\S}9, the author gives some computational examples illustrating the theory presented. The book contains also bibliographical comments. The book is written carefully. With the exception of {\S}2, the author gives detailed proofs of all statements. In my opinion, this book is of interest to all scientists working in the field of numerical methods of optimization.











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 Q3316094)