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
Filter
  • Articles: DFG German National Licenses  (3)
  • Linear complementarity problem  (2)
  • complexity bound  (1)
  • 1
    Electronic Resource
    Electronic Resource
    Ellipsoids that contain all the solutions of a positive semi-definite linear complementarity problem (1990)
    Springer
    Mathematical programming 48 (1990), S. 415-435 
    Details
    ISSN: 1436-4646
    Keywords: Linear complementarity problem ; ellipsoid ; interior point algorithm ; path following algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper deals with the LCP (linear complementarity problem) with a positive semi-definite matrix. Assuming that a strictly positive feasible solution of the LCP is available, we propose ellipsoids each of which contains all the solutions of the LCP. We use such an ellipsoid for computing a lower bound and an upper bound for each coordinate of the solutions of the LCP. We can apply the lower bound to test whether a given variable is positive over the solution set of the LCP. That is, if the lower bound is positive, we know that the variable is positive over the solution set of the LCP; hence, by the complementarity condition, its complement is zero. In this case we can eliminate the variable and its complement from the LCP. We also show how we efficiently combine the ellipsoid method for computing bounds for the solution set with the path-following algorithm proposed by the authors for the LCP. If the LCP has a unique non-degenerate solution, the lower bound and the upper bound for the solution, computed at each iteration of the path-following algorithm, both converge to the solution of the LCP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582266
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
  • 3
    Electronic Resource
    Electronic Resource
    A Complexity Analysis of a Smoothing Method Using CHKS-functions for Monotone Linear Complementarity Problems (2000)
    Springer
    Computational optimization and applications 17 (2000), S. 183-201 
    Details
    ISSN: 1573-2894
    Keywords: smoothing method ; complexity bound ; linear complementarity problem ; monotonicity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Notes: Abstract We consider the standard linear complementarity problem (LCP): Find (x, y) ∈ R 2n such that y = M x + q, (x, y) ≥ 0 and x i y i = 0 (i = 1, 2, ... , n), where M is an n × n matrix and q is an n-dimensional vector. Recently several smoothing methods have been developed for solving monotone and/or P 0 LCPs. The aim of this paper is to derive a complexity bound of smoothing methods using Chen-Harker-Kanzow-Smale functions in the case where the monotone LCP has a feasible interior point. After a smoothing method is provided, some properties of the CHKS-function are described. As a consequence, we show that the algorithm terminates in $$O\left( {\frac{{\gamma ^{ - 6} n}}{{\varepsilon ^6 }}\log \frac{{\gamma ^{ - 2} n}}{{\varepsilon ^2 }}} \right)$$ Newton iterations where $${\bar \gamma }$$ is a number which depends on the problem and the initial point. We also discuss some relationships between the interior point methods and the smoothing methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1026550331760
    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...