Primal—dual methods for linear programming

Autor:	Michael A. Saunders, Dulce B. Ponceleon, Walter Murray, Philip E. Gill
Rok vydání:	1995
Předmět:	Mathematical optimization Nonlinear system Transformation (function) Linear programming General Mathematics Numerical analysis Convergence (routing) Free variables and bound variables Mathematics::Optimization and Control Software Interior point method Mathematics Dual (category theory)
Zdroj:	Mathematical Programming. 70:251-277
ISSN:	1436-4646 0025-5610
Popis:	Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal--dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal--dual method. In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal--dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility. Finally, a new method for treating free variables is proposed.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::3da312267fc6ffbab22f3c071e8224aa https://doi.org/10.1007/bf01585940 Zobrazit plný text záznamu Full text from SpringerLink