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
  • Linear complementarity problem  (2)
  • Piecewise Linear Homotopy  (2)
  • complementarity problem  (2)
  • 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
    A little theorem of the bigℳ in interior point algorithms (1993)
    Springer
    Mathematical programming 59 (1993), S. 361-375 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Interior point algorithm ; big ℳ ; linear program ; convex program ; complementarity problem ; potential reduction algorithm ; self-dual linear program
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract When we apply interior point algorithms to various problems including linear programs, convex quadratic programs, convex programs and complementarity problems, we often embed an original problem to be solved in an artificial problem having a known interior feasible solution from which we start the algorithm. The artificial problem involves a constantℳ (or constants) which we need to choose large enough to ensure the equivalence between the artificial problem and the original problem. Theoretically, we can always assign a positive number of the order O(2 L ) toℳ in linear cases, whereL denotes the input size of the problem. Practically, however, such a large number is impossible to implement on computers. If we choose too largeℳ, we may have numerical instability and/or computational inefficiency, while the artificial problem withℳ not large enough will never lead to any solution of the original problem. To solve this difficulty, this paper presents “a little theorem of the bigℳ”, which will enable us to find whetherℳ is not large enough, and to updateℳ during the iterations of the algorithm even if we start with a smallerℳ. Applications of the theorem are given to a polynomial-time potential reduction algorithm for positive semi-definite linear complementarity problems, and to an artificial self-dual linear program which has a close relation with the primal—dual interior point algorithm using Lustig's limiting feasible direction vector.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01581253
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 3
    Digitale Medien
    Digitale Medien
    Basic lemmas in polynomial-time infeasible-interiorpoint methods for linear programs (1996)
    Springer
    Annals of operations research 62 (1996), S. 1-28 
    Details
    ISSN: 1572-9338
    Schlagwort(e): Linear program ; interior point method ; initial point ; step length ; complementarity problem ; polynomial-time complexity
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Mathematik , Wirtschaftswissenschaften
    Notizen: Abstract The primal-dual infeasible-interior-point algorithm is known as one of the most efficient computational methods for linear programs. Recently, a polynomial-time computational complexity bound was established for special variants of the algorithm. However, they impose severe restrictions on initial points and require a common step length in the primal and dual spaces. This paper presents some basic lemmas that bring great flexibility and improvement into such restrictions on initial points and step lengths, and discusses their extensions to linear and nonlinear monotone complementarity problems.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF02206809
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 4
    Digitale Medien
    Digitale Medien
    A PL homotopy for finding all the roots of a polynomial (1979)
    Springer
    Mathematical programming 16 (1979), S. 37-62 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Roots of Polynomials ; Fixed Point Computing Methods ; Complementary Pivoting Methods ; Piecewise Linear Homotopy
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper presents a constructive method which gives, for any polynomialF(Z) of the degreen, approximate values of all the roots ofF(Z).. The point of the method is on the use of a piecewise linear function $$\bar H$$ (Z, t) which approximates a homotopyH(Z, t) betweenF(Z) and a polynomialG(Z) of the degreen withn known simple roots. It is shown that the set of solutions to $$\bar H$$ (Z, t) = 0 includesn distinct paths,m of which converges to a root ofF(Z) if and only if the root has the multiplicitym. Starting from givenn roots ofG(Z), a complementary pivot algorithm generates thosen paths.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01582093
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 5
    Digitale Medien
    Digitale Medien
    A modification of todd's triangulationJ 3 (1978)
    Springer
    Mathematical programming 15 (1978), S. 223-227 
    Details
    ISSN: 1436-4646
    Schlagwort(e): Triangulations ; Fixed Point Computing Methods ; Complementary Pivoting Methods ; Piecewise Linear Homotopy
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract When we apply the fixed point computing method to mappings which are affine in some variables, we show that, to generate a sequence which converges to a fixed point, the mesh size need not be decreased in these coordinates. This paper modifies the triangulationJ 3 with continuous refinement of mesh size to a triangulation $$\bar J_3$$ such that the mesh size of $$\bar J_3$$ in some given coordinates is constant and the mesh size in the other coordinates shrinks to zero.
    Materialart: Digitale Medien
    URL: http://dx.doi.org/10.1007/BF01609022
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
    Artikel (Nationallizenzen)
    Volltext
  • 6
    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...