Bibliothek

X
feed icon rss

Ihre E-Mail wurde erfolgreich gesendet. Bitte prüfen Sie Ihren Maileingang.

Leider ist ein Fehler beim E-Mail-Versand aufgetreten. Bitte versuchen Sie es erneut.

Vorgang fortführen?

Exportieren
Filter
  • Digitale Medien  (3)
  • Linear complementarity problem  (2)
  • Infeasible-interior-point method  (1)
  • 1
    Digitale Medien
    Digitale Medien
    A polynomial-time algorithm for a class of linear complementarity problems (1989)
    Springer
    Mathematical programming 44 (1989), S. 1-26 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Linear complementarity problem ; polynomial-time algorithm ; path of centers ; Karmarkar's algorithm
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01587074
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 2
    Digitale Medien
    Digitale Medien
    Local convergence of predictor—corrector infeasible-interior-point algorithms for SDPs and SDLCPs (1998)
    Springer
    Mathematical programming 80 (1998), S. 129-160 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Semidefinite programming ; Infeasible-interior-point method ; Predictor—correctormethod ; Superlinear convergence ; Primal—dual nondegeneracy
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581723
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    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
    Schlagwort(e): Linear complementarity problem ; ellipsoid ; interior point algorithm ; path following algorithm
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01582266
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...