By Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise

ISBN-10: 354038426X

ISBN-13: 9783540384267

ISBN-10: 3540545093

ISBN-13: 9783540545095

Following Karmarkar's 1984 linear programming set of rules, a number of interior-point algorithms were proposed for numerous mathematical programming difficulties reminiscent of linear programming, convex quadratic programming and convex programming typically. This monograph offers a research of interior-point algorithms for the linear complementarity challenge (LCP) that's often called a mathematical version for primal-dual pairs of linear courses and convex quadratic courses. a wide relatives of strength aid algorithms is gifted in a unified means for the category of LCPs the place the underlying matrix has nonnegative crucial minors (P0-matrix). This category contains a number of very important subclasses akin to confident semi-definite matrices, P-matrices, P*-matrices brought during this monograph, and column adequate matrices. The family members comprises not just the standard strength relief algorithms but in addition course following algorithms and a damped Newton procedure for the LCP. the most themes are worldwide convergence, international linear convergence, and the polynomial-time convergence of strength relief algorithms incorporated within the family.

Show description

Read or Download A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems PDF

Similar linear programming books

Variational analysis - download pdf or read online

From its origins within the minimization of critical functionals, the concept of 'variations' has advanced drastically in reference to purposes in optimization, equilibrium, and regulate. It refers not just to limited move clear of some degree, but in addition to modes of perturbation and approximation which are top describable by way of 'set convergence', variational convergence of features' and so forth.

Download e-book for kindle: The SIAM 100-Digit Challenge: A Study in High-Accuracy by Folkmar Bornemann, Dirk Laurie, Stan Wagon, Jörg Waldvogel

It is a stable booklet containing much approximately excessive accuracy computation. Ten difficulties are mentioned with information relating to many parts of arithmetic. loads of codes of many arithmetic software program are proven with a worthwhile appendix. an online web page of this e-book is additionally a spotlight. you may as well perform with it exhaustingly and enjoyably.

New PDF release: Multivalued Analysis and Nonlinear Programming Problems with

From the reviews:"The objective of this e-book is to review countless dimensional areas, multivalued mappings and the linked marginal services … . the fabric is gifted in a transparent, rigorous demeanour. along with the bibliographical reviews … references to the literature are given in the textual content. … the unified method of the directional differentiability of multifunctions and their linked marginal features is a impressive characteristic of the e-book … .

Hierarchical Optimization and Mathematical Physics - download pdf or read online

This ebook can be regarded as an advent to a different dass of hierarchical structures of optimum keep an eye on, the place subsystems are defined by means of partial differential equations of assorted varieties. Optimization is performed through a two-level scheme, the place the heart optimizes coordination for the higher point and subsystems locate the optimum suggestions for self sustaining neighborhood difficulties.

Extra info for A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems

Example text

We further observe Z(6)={¢eRn:(l+46)E(i+E(I<0 for every I c N ) iE! i¢I from the definitions of the index sets I÷(¢) and _r (¢). Hence Z(~) turns out the interior of the polyhedral cone {~ERn:(l+4a)~'/+~-':~¢i_<0 i~I i~l forevery [ c N } that contains the nonpositive orthant R~. See Figure 12. It should be noted that the class P,, which is the union of P,(6) (6 > 0), remains a proper subclass of CS although the intersection of Z(t:) (t: _> 0) becomes R ~_ \ {0}. Finally in this section, we remark that all the classes mentioned so far, Po, CS, P,, P,(a), PSD, P and SS, enjoy a nice property that if a matrix M belongs to one of these classes then every principal submatrix of M also belongs to the dass.

The Class of Linear Complementarity with P0-Matrices Problems In this section we investigate linear complementarity problems with Po-matrices. 1, we introduce some characteristic numbers related to Po-matrices. 3. 4 gives an example of NP-complete linear complementarity problems with Po-matrices. 1. Some Characteristic Numbers Related to P0-Matrices An n x n matrix M is called a Po-matrix when all the principal manors of M are nonnegative and a P-matrix when they are positive. We also say that M belongs to the classes Po or P, respectively.

Similar studies were also done in Bayer and Lagarias [5, 6] and Megiddo and Shub [43]. 2). 8) is a descent direction of the potential function f . Recall that the search direction (din, dy) depends on the parameter fl E [0,1] and can be regarded as a convex combination of the centering direction (dinc, dy ~) and the affine scaling direction (dina, dya), which correspond to the cases fi = 1 and fl = 0, respectively. 10). 20). 14. Let V denote, as usual the gradient operator. 23) vf~"(x'u)r du =--7-' dy ~ dx" dY~ dy e Vf(n~, y ) r ( d:~ for every (~, y) e S++.

Download PDF sample

A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems by Masakazu Kojima, Nimrod Megiddo, Toshihito Noma, Akiko Yoshise


by Paul
4.5

Rated 4.28 of 5 – based on 45 votes