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
  • 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
    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
    Schlagwort(e): Variable Dimension Algorithm ; Fixed Point ; Subdivided Manifold ; Nonlinear Equations
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01585103
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    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
    Schlagwort(e): Potential reduction algorithm ; linear complementarity problem ; interior point algorithm ; Karmarkar's algorithm ; path of centers ; central trajectory
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: 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.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01594942
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    Global convergence in infeasible-interior-point algorithms (1994)
    Springer
    Mathematical programming 65 (1994), S. 43-72 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Monotone complementarity problem ; Interior-point algorithm ; Potential reduction algorithm ; Infeasibility ; Global convergence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper presents a wide class of globally convergent interior-point algorithms for the nonlinear complementarity problem with a continuously differentiable monotone mapping in terms of a unified global convergence theory given by Polak in 1971 for general nonlinear programs. The class of algorithms is characterized as: Move in a Newton direction for approximating a point on the path of centers of the complementarity problem at each iteration. Starting from a strictly positive but infeasible initial point, each algorithm in the class either generates an approximate solution with a given accuracy or provides us with information that the complementarity problem has no solution in a given bounded set. We present three typical examples of our interior-point algorithms, a horn neighborhood model, a constrained potential reduction model with the use of the standard potential function, and a pure potential reduction model with the use of a new potential function.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581689
    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...