Interior point techniques in optimization. Complementarity, sensitivity and algorithms
type: Item
instance of: scholarly article
title: Interior point techniques in optimization. Complementarity, sensitivity and algorithms
zbMATH Open document ID: 0886.90098
author: Benjamin Jansen
published in: Applied Optimization
publication date: 1997-04-29T00:00:00Z
review text: 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 …
Mathematics Subject Classification ID: 90C05
Mathematics Subject Classification ID: 90C31
Mathematics Subject Classification ID: 90-01
Mathematics Subject Classification ID: 90C60
Mathematics Subject Classification ID: 90C33
zbMATH DE Number: 1005350
zbMATH Keywords: interior point techniques
zbMATH Keywords: complementarity
zbMATH Keywords: sensitivity
zbMATH Keywords: target-following approach
zbMATH Keywords: duality theory
zbMATH Keywords: primal-dual Dikin-affine scaling algorithm
zbMATH Keywords: polynomial complexity
zbMATH Keywords: linear complementarity
zbMATH Keywords: nonlinear complementarity
zbMATH Keywords: semidefinite programming
zbMATH Keywords: smallest eigenvalue
reviewed by: R. N. Kaul
describes a project that uses: GAMS
describes a project that uses: LOQO
describes a project that uses: LINDO
describes a project that uses: AIMMS
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1005350