Library

X
feed icon rss

Your email was sent successfully. Check your inbox.

An error occurred while sending the email. Please try again.

Proceed reservation?

Export
  • 11
    Electronic Resource
    Electronic Resource
    A polynomial-time algorithm for a class of linear complementarity problems (1989)
    Springer
    Mathematical programming 44 (1989), S. 1-26 
    Details
    ISSN: 1436-4646
    Keywords: Linear complementarity problem ; polynomial-time algorithm ; path of centers ; Karmarkar's algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01587074
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    Electronic Resource
    Electronic Resource
    A primal—dual infeasible-interior-point algorithm for linear programming (1993)
    Springer
    Mathematical programming 61 (1993), S. 263-280 
    Details
    ISSN: 1436-4646
    Keywords: Infeasible-interior-point algorithm ; interior-point algorithm ; primal—dual algorithm ; linear program ; large step ; global convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582151
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    A modified layered-step interior-point algorithm for linear programming (1998)
    Springer
    Mathematical programming 82 (1998), S. 339-355 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Layered-step interior-point method ; Path of centers ; Crossover events
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The layered-step interior-point algorithm was introduced by Vavasis and Ye. The algorithm accelerates the path following interior-point algorithm and its arithmetic complexity depends only on the coefficient matrixA. The main drawback of the algorithm is the use of an unknown big constant $$\bar \chi _A $$ in computing the search direction and to initiate the algorithm. We propose a modified layered-step interior-point algorithm which does not use the big constant in computing the search direction. The constant is required only for initialization when a well-centered feasible solution is not available, and it is not required if an upper bound on the norm of a primal—dual optimal solution is known in advance. The complexity of the simplified algorithm is the same as that of Vavasis and Ye. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580074
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    A primal—dual affine-scaling potential-reduction algorithm for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 119-131 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; complexity ; potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585163
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    Global and polynomial-time convergence of an infeasible-interior-point algorithm using inexact computation (1999)
    Springer
    Mathematical programming 84 (1999), S. 105-122 
    Details
    ISSN: 1436-4646
    Keywords: Key words: linear programming problem – interior-point method – primal-dual – convergence – inexact computation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s10107980020a
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    A unified approach to infeasible-interior-point algorithms via geometrical linear complementarity problems (1996)
    Springer
    Applied mathematics & optimization 33 (1996), S. 315-341 
    Details
    ISSN: 1432-0606
    Keywords: Linear programming ; Quadratic programming ; Linear complementarity problem ; Infeasible-interior-point algorithm ; Polynomial time ; 90C33 ; 65F05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract There are many interior-point algorithms for LP (linear programming), QP (quadratic programming), and LCPs (linear complementarity problems). While the algebraic definitions of these problems are different from each other, we show that they are all of the same general form when we define the problems geometrically. We derive some basic properties related to such geometrical (monotone) LCPs and based on these properties, we propose and analyze a simple infeasible-interior-point algorithm for solving geometrical LCPs. The algorithm can solve any instance of the above classes without making any assumptions on the problem. It features global convergence, polynomial-time convergence if there is a solution that is “smaller” than the initial point, and quadratic convergence if there is a strictly complementary solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01204707
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    Virtual sculpting and virtual woodcut printing (1998)
    Springer
    The visual computer 14 (1998), S. 39-51 
    Details
    ISSN: 1432-2315
    Keywords: Key words: Virtual reality ; Interactive solid modeling ; CSG model ; Nonphotorealistic image
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s003710050122
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...