Library

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
    Springer
    Mathematical programming 54 (1992), S. 267-279 
    ISSN: 1436-4646
    Keywords: Linear complementarity ; P-matrix ; interior point ; potential function ; linear programming ; quadratic programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The linear complementarity problem (LCP) can be viewed as the problem of minimizingx T y subject toy=Mx+q andx, y⩾0. We are interested in finding a point withx T y 〈ε for a givenε 〉 0. The algorithm proceeds by iteratively reducing the potential function $$f(x,y) = \rho \ln x^T y - \Sigma \ln x_j y_j ,$$ where, for example,ρ=2n. The direction of movement in the original space can be viewed as follows. First, apply alinear scaling transformation to make the coordinates of the current point all equal to 1. Take a gradient step in the transformed space using the gradient of the transformed potential function, where the step size is either predetermined by the algorithm or decided by line search to minimize the value of the potential. Finally, map the point back to the original space. A bound on the worst-case performance of the algorithm depends on the parameterλ *=λ*(M, ε), which is defined as the minimum of the smallest eigenvalue of a matrix of the form $$(I + Y^{ - 1} MX)(I + M^T Y^{ - 2} MX)^{ - 1} (I + XM^T Y^{ - 1} )$$ whereX andY vary over the nonnegative diagonal matrices such thate T XYe ⩾ε andX jj Y jj⩽n 2. IfM is a P-matrix,λ * is positive and the algorithm solves the problem in polynomial time in terms of the input size, |log ε|, and 1/λ *. It is also shown that whenM is positive semi-definite, the choice ofρ = 2n+ $$\sqrt {2n} $$ yields a polynomial-time algorithm. This covers the convex quadratic minimization problem.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...