TY - GEN A1 - Potra, Florian T1 - A path-following method for linear complementarity problems based on the affine invariant Kantorovich Theorem N2 - 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. T3 - ZIB-Report - 00-30 KW - Linear complementarity problem KW - interior-point algorithm KW - path-following KW - Kantorovich Theorem Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-5981 ER - TY - GEN A1 - Deuflhard, Peter A1 - Potra, Florian T1 - A Refined Gauss-Newton- Mysovskii Theorem. N2 - The present paper contains a generalization of a refinement of the Newton- Mysovskii theorem, recently obtained by the authors, to the case of Gauss-Newton procedures for solving nonlinear least-squares problems with full Jacobians. Invariant sufficient conditions are given that ensure the convergence of the Gauss-Newton iterates towards a solution of the problem, as well as the uniqueness of that solution in an explicitely defined neighborhood. It is shown by a counter- example that the results do not carry over to the rank deficient case. T3 - ZIB-Report - SC-91-04 Y1 - 1991 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-541 ER - TY - GEN A1 - Deuflhard, Peter A1 - Potra, Florian T1 - Asymptotic Mesh Independence of Newton-Galerkin Methods via a Refined Mysovskii Theorem. N2 - The paper presents a theoretical characterization of the often observed asymptotic mesh independence of Newton's method, which means that Newton's method applied to discretized operator equations behaves essentially the same for all sufficiently fine discretizations. The theory does not need any uniform Lipschitz assumptions that were necessary in comparable earlier treatments. The refined Newton-Mysovskii theorem, which will be of interest in a wider context, gives both existence and uniqueness of the solution and quadratic convergence for sufficiently good starting points. Attention is restricted to Galerkin approximations even though similar results should hold for finite difference methods - but corresponding proofs would certainly be more technical. As an illustrative example, adaptive 1-D collocation methods are discussed. T3 - ZIB-Report - SC-90-09 Y1 - 1990 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-379 ER -