scientific article; zbMATH DE number 3846334
discrete minimax problemsdual algorithmexact penalty functionlinearization methodrate of convergence
Research exposition (monographs, survey articles) pertaining to calculus of variations and optimal control (49-02) Optimality conditions for minimax problems (49K35) Numerical methods based on nonlinear programming (49M37) Research exposition (monographs, survey articles) pertaining to numerical analysis (65-02) Nonlinear algebraic or transcendental equations (65H99) Numerical mathematical programming methods (65K05) Research exposition (monographs, survey articles) pertaining to operations research and mathematical programming (90-02) Linear programming (90C05) Quadratic programming (90C20) Convex programming (90C25) Nonlinear programming (90C30) Methods of successive quadratic programming type (90C55)
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.
- Linear morphisms in a topos
- Mixed method for solving the general convex programming problem
- The linearization method: Principal concepts and perspective directions
- Linearization method using smooth penalties
- Academician V. S. Mikhalevich as a scientist and science organizer (on the occasion of his 70th birthday)
- Continuous-time switching regression method with unknown switching points
- On the problem of packing spheres in a cube
- Problems related to estimating the coefficients of exact penalty functions
- Method of linearization without analytic evaluation of derivatives
- A modification of the method of linearization for solving a mathematical programming problem on a simple set of ``parallelepiped type
- Nonsmooth optimization
- scientific article; zbMATH DE number 3991284 (Why is no real title available?)
- scientific article; zbMATH DE number 4068633 (Why is no real title available?)
- scientific article; zbMATH DE number 4076981 (Why is no real title available?)
- scientific article; zbMATH DE number 1524343 (Why is no real title available?)
- The linearization method
- On the existence of continuous selections of a multivalued mapping related to the problem of minimizing a functional
- On continuous and Lipschitz selections of multivalued mappings given by systems of inequalities
- On the 95th anniversary of the birth of Volodymyr Serhiyovych Mykhalevych
- Lexicographic solution of two-objective project planning problem under constrained reliability index
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)