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
Filter
  • interior point algorithm  (3)
  • Linear complementarity problem  (2)
  • Piecewise Linear Homotopy  (2)
  • complementarity problem  (2)
  • 1
    Electronic Resource
    Electronic Resource
    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
    Keywords: Potential reduction algorithm ; linear complementarity problem ; interior point algorithm ; Karmarkar's algorithm ; path of centers ; central trajectory
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01594942
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    On the bigℳ in the affine scaling algorithm (1993)
    Springer
    Mathematical programming 62 (1993), S. 85-93 
    Details
    ISSN: 1436-4646
    Keywords: Bigℳ ; affine scaling algorithm ; linear program ; interior point algorithm ; infeasibility ; global convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585161
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    A little theorem of the bigℳ in interior point algorithms (1993)
    Springer
    Mathematical programming 59 (1993), S. 361-375 
    Details
    ISSN: 1436-4646
    Keywords: Interior point algorithm ; big ℳ ; linear program ; convex program ; complementarity problem ; potential reduction algorithm ; self-dual linear program
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581253
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    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
    Keywords: Linear complementarity problem ; ellipsoid ; interior point algorithm ; path following algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582266
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    A PL homotopy for finding all the roots of a polynomial (1979)
    Springer
    Mathematical programming 16 (1979), S. 37-62 
    Details
    ISSN: 1436-4646
    Keywords: Roots of Polynomials ; Fixed Point Computing Methods ; Complementary Pivoting Methods ; Piecewise Linear Homotopy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582093
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A modification of todd's triangulationJ 3 (1978)
    Springer
    Mathematical programming 15 (1978), S. 223-227 
    Details
    ISSN: 1436-4646
    Keywords: Triangulations ; Fixed Point Computing Methods ; Complementary Pivoting Methods ; Piecewise Linear Homotopy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01609022
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    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
    Keywords: Linear program ; interior point method ; initial point ; step length ; complementarity problem ; polynomial-time complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206809
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    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
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...