Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    A polynomial-time algorithm for a class of linear complementarity problems (1989)
    Springer
    Mathematical programming 44 (1989), S. 1-26 
    Details
    ISSN: 1436-4646
    Keywords: Linear complementarity problem ; polynomial-time algorithm ; path of centers ; Karmarkar's algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given ann × n matrixM and ann-dimensional vectorq, the problem of findingn-dimensional vectorsx andy satisfyingy = Mx + q, x ≥ 0,y ≥ 0,x i y i = 0 (i = 1, 2,⋯,n) is known as a linear complementarity problem. Under the assumption thatM is positive semidefinite, this paper presents an algorithm that solves the problem in O(n 3 L) arithmetic operations by tracing the path of centers,{(x, y) ∈ S: x i y i =μ (i = 1, 2,⋯,n) for some μ 〉 0} of the feasible regionS = {(x, y) ≥ 0:y = Mx + q}, whereL denotes the size of the input data of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01587074
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Variable dimension algorithms: Basic theory, interpretations and extensions of some existing methods (1982)
    Springer
    Mathematical programming 24 (1982), S. 177-215 
    Details
    ISSN: 1436-4646
    Keywords: Variable Dimension Algorithm ; Fixed Point ; Subdivided Manifold ; Nonlinear Equations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we establish a basic theory for variable dimension algorithms which were originally developed for computing fixed points by Van der Laan and Talman. We introduce a new concept ‘primal—dual pair of subdivided manifolds’ and by utilizing it we propose a basic model which will serve as a foundation for constructing a wide class of variable dimension algorithms. Our basic model furnishes interpretations to several existing methods: Lemke's algorithm for the linear complementarity problem, its extension to the nonlinear complementarity problem, a variable dimension algorithm on conical subdivisions and Merrill's algorithm. We shall present a method for solving systems of equations as an application of the second method and an efficient implementation of the fourth method to which our interpretation leads us. A method for constructing triangulations with an arbitrary refinement factor of mesh size is also proposed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585103
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    An $$O(\sqrt n L)$$ iteration potential reduction algorithm for linear complementarity problems (1991)
    Springer
    Mathematical programming 50 (1991), S. 331-342 
    Details
    ISSN: 1436-4646
    Keywords: Potential reduction algorithm ; linear complementarity problem ; interior point algorithm ; Karmarkar's algorithm ; path of centers ; central trajectory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper proposes an interior point algorithm for a positive semi-definite linear complementarity problem: find an (x, y)∈ℝ 2n such thaty=Mx+q, (x,y)⩾0 andx T y=0. The algorithm reduces the potential function $$f(x,y) = (n + \sqrt n )\log x^T y - \sum\limits_{i = 1}^n {\log x_i y_i } $$ by at least 0.2 in each iteration requiring O(n 3) arithmetic operations. If it starts from an interior feasible solution with the potential function value bounded by $$O(\sqrt n L)$$ , it generates, in at most $$O(\sqrt n L)$$ iterations, an approximate solution with the potential function value $$ - O(\sqrt n L)$$ , from which we can compute an exact solution in O(n 3) arithmetic operations. The algorithm is closely related with the central path following algorithm recently given by the authors. We also suggest a unified model for both potential reduction and path following algorithms for positive semi-definite linear complementarity problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01594942
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...