Overview Statistic: PDF-Downloads (blue) and Frontdoor-Views (gray)
  • search hit 20 of 20
Back to Result List

A path-following method for linear complementarity problems based on the affine invariant Kantorovich Theorem

Please always quote using this URN: urn:nbn:de:0297-zib-5981
  • A path following algorithm for linear complementarity problems is presented. Given a point $z$ that approximates a point $z(\tau)$ on the central path with complementarity gap $\tau$, one determines a parameter $\theta\in (0,1)$ so that this point satisfies the hypothesis of the affine invariant Kantorovich Theorem for the equation defining $z((1-\theta)\tau)$. It is shown that $\theta$ is bounded below by a multiple of $n^{-1/2}$, where $n$ is the dimension of the problem. Since the hypothesis of of the Kantorovich Theorem is satisfied the sequence generated by Newton's method, or by the simplified Newton method, will converge to $z((1-\theta)\tau)$. We show that the number of steps required to obtain an acceptable approximation of $z((1-\theta)\tau)$ is bounded above by a number independent of $n$. Therefore the algorithm has $O(\sqrt{n}L)$-iteration complexity. The parameters of the algorithm can be determined in such a way that only one Newton step is needed each time the complementarity gap is decreased.

Download full text files

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics - number of accesses to the document
Metadaten
Author:Florian Potra
Document Type:ZIB-Report
Tag:Kantorovich Theorem; Linear complementarity problem; interior-point algorithm; path-following
MSC-Classification:49-XX CALCULUS OF VARIATIONS AND OPTIMAL CONTROL; OPTIMIZATION [See also 34H05, 34K35, 65Kxx, 90Cxx, 93-XX] / 49Mxx Numerical methods [See also 90Cxx, 65Kxx] / 49M15 Newton-type methods
65-XX NUMERICAL ANALYSIS / 65Hxx Nonlinear algebraic or transcendental equations / 65H10 Systems of equations
65-XX NUMERICAL ANALYSIS / 65Kxx Mathematical programming, optimization and variational techniques / 65K05 Mathematical programming methods [See also 90Cxx]
90-XX OPERATIONS RESEARCH, MATHEMATICAL PROGRAMMING / 90Cxx Mathematical programming [See also 49Mxx, 65Kxx] / 90C33 Complementarity and equilibrium problems and variational inequalities (finite dimensions)
Date of first Publication:2000/09/14
Series (Serial Number):ZIB-Report (00-30)
ZIB-Reportnumber:00-30
Published in:Appeared under the title "The Kantorovich Theorem and Interior Point Methods" in: Mathematical Programming, Ser. A 102:47-70(2005), electronic, (2004)
DOI:https://doi.org/10.1007/s10107-003-0501-8
Accept ✔
Diese Webseite verwendet technisch erforderliche Session-Cookies. Durch die weitere Nutzung der Webseite stimmen Sie diesem zu. Unsere Datenschutzerklärung finden Sie hier.