Interior point techniques in optimization. Complementarity, sensitivity and algorithms (Q1353364): Difference between revisions

This book on interior point techniques in optimization fulfils a great need since there are not many books available containing the latest developments in this area. The book deals with several aspects of interior point methods in linear, quadratic, nonlinear and semi-definite programming. The concept of complementarity is a fundamental tool used in the sensitivity analysis for linear and convex programming as well as the analysis of primal-dual algorithms for linear/nonlinear complementarity problems. The target-following approach adopted in this book presents a unifying framework for various known methods in literature. The following is the chapter-wise description of various topics covered in this book. Chapter 1 gives a brief account of the historical background of the subject including the fundamental paper of Karmarkar. In chapter 2 new proofs are given for two basic results of duality theory i.e. strong duality and existence of a strict complementarity solution for general linear programming problems. The space for complementarity products of positive primal-dual pairs called the \(v\)-space is defined and used in later chapters for adopting a target-following approach in the analysis of primal-dual interior point methods. Chapter 3 makes an interesting statement that a strictly complementary solution determines the optimal partition of the LP problem. The concept of an optimal partition is used to perform sensitivity analysis in LP based on interior point methods. The optimal set of LP is characterized by using three different approaches namely the simplex approach, the interior point approach and the optimal value approach and results on sensitivity analysis are presented in a unifying framework. In Chapter 4 the concept of maximal complementarity solution of convex quadratic programming (CQR) is defined. It is used to define tripartition of the problem and optimal value functions of the perturbed CQP. These ideas are then utilized to study the sensitivity of CQP as an extension of the approach for LP. The primal-dual Dikin-affine scaling algorithm is proposed in Chapter 5 and the polynomial complexity of the algorithm for the class of linear complementarity problems is established. Chapter 6 deals with a complexity analysis for a family of primal-dual affine scaling algorithms for nonlinear complementarity problems. A new smoothness condition is introduced and its applicability to problems involving nonmonotone functions and suitability for large neighbourhood algorithms is demonstrated. Chapter 7 reports on computational experience of the primal-dual affine scaling algorithms described in earlier chapters on various optimization problems arising in statistics. Cbapters 8 and 9 discuss the target-following approach which is claimed to offer a general framework for the analysis of primal-dual interior point methods. For convenience the methods and their analysis have been described in \(v\)-space and it has been shown that this approach leads to simple and unifom complexity proofs for various existing methods in the literature. In Chapter 10 a special but important class of mathematical programming problems called semidefinite programming problems (SUP) is described. The two applications of SDP discussed is the problem of optimizing a nonconvex quadratic function over ellipsoids and the computation of the smallest eigenvalue of a symmetric matrix. The last chapter deals with the use of interior point methods in decomposition schemes. The role of a Pareto-optimal cut is emphasized here and it is shown that modern interior cutting plane methods generate such a cut for free. It may, however, be mentioned that some recent results on the application of interior point methods to multiobjective programming or semi-infinite programming are not covered in this book. Nevertheless the book serves a useful purpose and I hope researchers and practitioners in the area of interior point methods will find it useful.