Bibliothek

Sprache
Bevorzugter Suchindex
Ergebnisse pro Seite
Sortieren nach
Sortierung
Anzahl gespeicherter Suchen in der Suchhistorie
E-Mail-Adresse
Voreingestelltes Exportformat
Voreingestellte Zeichencodierung für Export
Anordnung der Filter
Maximale Anzahl angezeigter Filter
Autovervollständigung
Feed-Format
Anzahl der Ergebnisse pro Feed
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
  • Artikel: DFG Deutsche Nationallizenzen  (5)
  • linear program  (4)
  • global convergence  (3)
  • Complementarity problem  (1)
  • 1
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 1-21 
    ISSN: 1436-4646
    Schlagwort(e): Primal—dual interior point algorithm ; linear program ; large step ; global convergence ; polynomial-time convergence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract This paper proposes two sets of rules, Rule G and Rule P, for controlling step lengths in a generic primal—dual interior point method for solving the linear programming problem in standard form and its dual. Theoretically, Rule G ensures the global convergence, while Rule P, which is a special case of Rule G, ensures the O(nL) iteration polynomial-time computational complexity. Both rules depend only on the lengths of the steps from the current iterates in the primal and dual spaces to the respective boundaries of the primal and dual feasible regions. They rely neither on neighborhoods of the central trajectory nor on potential function. These rules allow large steps without performing any line search. Rule G is especially flexible enough for implementation in practically efficient primal—dual interior point algorithms.
    Materialart: Digitale Medien
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 2
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 62 (1993), S. 85-93 
    ISSN: 1436-4646
    Schlagwort(e): Bigℳ ; affine scaling algorithm ; linear program ; interior point algorithm ; infeasibility ; global convergence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract When we apply the affine scaling algorithm to a linear program, we usually construct an artificial linear program having an interior feasible solution from which the algorithm starts. The artificial linear program involves a positive number called the bigℳ. Theoretically, there exists anℳ * such that the original problem to be solved is equivalent to the artificial linear program ifℳ 〉ℳ *. Practically, however, such anℳ * is unknown and a safe estimate ofℳ is often too large. This paper proposes a method of updatingℳ to a suitable value during the iteration of the affine scaling algorithm. Asℳ becomes large, the method gives information on infeasibility of the original problem or its dual.
    Materialart: Digitale Medien
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 3
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 59 (1993), S. 361-375 
    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
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 4
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 43 (1989), S. 107-113 
    ISSN: 1436-4646
    Schlagwort(e): Complementarity problem ; continuation method ; P-function ; homeomorphism
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract The complementarity problem with a nonlinear continuous mappingf from the nonnegative orthantR + n ofR n intoR n can be written as the system of equationsF(x, y) = 0 and(x, y) ∈ R + 2n , whereF denotes the mapping from the nonnegative orthantR + 2n ofR 2n intoR + n × Rn defined byF(x, y) = (x 1y1,⋯,xnyn, f1(x) − y1,⋯, fn(x) − yn) for every(x, y) ∈ R + 2n . Under the assumption thatf is a uniformP-function, this paper establishes that the mappingF is a homeomorphism ofR + 2n ontoR + n × Rn. This result provides a theoretical basis for a new continuation method of tracing the solution curve of the one parameter family of systems of equationsF(x, y) = tF(x 0, y0) and(x, y) ∈ R + 2n from an arbitrary initial point(x 0, y0) ∈ R + 2n witht = 1 until the parametert attains 0. This approach is an extension of the one used in the polynomially bounded algorithm recently given by Kojima, Mizuno and Yoshise for solving linear complementarity problems with positive semi-definite matrices.
    Materialart: Digitale Medien
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
  • 5
    Digitale Medien
    Digitale Medien
    Springer
    Mathematical programming 61 (1993), S. 263-280 
    ISSN: 1436-4646
    Schlagwort(e): Infeasible-interior-point algorithm ; interior-point algorithm ; primal—dual algorithm ; linear program ; large step ; global convergence
    Quelle: Springer Online Journal Archives 1860-2000
    Thema: Informatik , Mathematik
    Notizen: Abstract As in many primal—dual interior-point algorithms, a primal—dual infeasible-interior-point algorithm chooses a new point along the Newton direction towards a point on the central trajectory, but it does not confine the iterates within the feasible region. This paper proposes a step length rule with which the algorithm takes large distinct step lengths in the primal and dual spaces and enjoys the global convergence.
    Materialart: Digitale Medien
    Bibliothek Standort Signatur Band/Heft/Jahr Verfügbarkeit
    BibTip Andere fanden auch interessant ...
Schließen ⊗
Diese Webseite nutzt Cookies und das Analyse-Tool Matomo. Weitere Informationen finden Sie hier...