Library

feed icon rss

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 1 (1986), S. 499-515 
    ISSN: 1432-0541
    Keywords: Linear program ; Karmarkar's algorithm ; Optimal basis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper establishes a sufficient condition for a variable of a linear program to be positive at all optimal solutions. A numerical test using the condition is incorporated into Karmarkar's new LP algorithm to determine columns of optimal basis. Experimental results on the test are also reported.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 12 (1977), S. 110-130 
    ISSN: 1436-4646
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A complementarity problem is said to be globally uniquely solvable (GUS) if it has a unique solution, and this property will not change, even if any constant term is added to the mapping generating the problem. A characterization of the GUS property which generalizes a basic theorem in linear complementarity theory is given. Known sufficient conditions given by Cottle, Karamardian, and Moré for the nonlinear case are also shown to be generalized. In particular, several open questions concerning Cottle's condition are settled and a new proof is given for the sufficiency of this condition. A simple characterization for the two-dimensional case and a necessary condition for then-dimensional case are also given.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 85-93 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 80 (1998), S. 129-160 
    ISSN: 1436-4646
    Keywords: Semidefinite programming ; Infeasible-interior-point method ; Predictor—correctormethod ; Superlinear convergence ; Primal—dual nondegeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract An example of an SDP (semidefinite program) exhibits a substantial difficulty in proving the superlinear convergence of a direct extension of the Mizuno—Todd—Ye type predictor—corrector primal-dual interior-point method for LPs (linear programs) to SDPs, and suggests that we need to force the generated sequence to converge to a solution tangentially to the central path (or trajectory). A Mizuno—Todd—Ye type predictor—corrector infeasible-interior-point algorithm incorporating this additional restriction for monotone SDLCPs (semidefinite linear complementarity problems) enjoys superlinear convergence under strict complementarity and nondegeneracy conditions. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 16 (1979), S. 37-62 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 44 (1989), S. 1-26 
    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
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 65 (1994), S. 43-72 
    ISSN: 1436-4646
    Keywords: Monotone complementarity problem ; Interior-point algorithm ; Potential reduction algorithm ; Infeasibility ; Global convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 89 (2000), S. 79-111 
    ISSN: 1436-4646
    Keywords: Key words: nonconvex quadratic optimization problem – semidefinite programming – linear matrix inequality – global optimization – SDP relaxation – semi-infinite LP relaxation – interior-point method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract. Based on the authors’ previous work which established theoretical foundations of two, conceptual, successive convex relaxation methods, i.e., the SSDP (Successive Semidefinite Programming) Relaxation Method and the SSILP (Successive Semi-Infinite Linear Programming) Relaxation Method, this paper proposes their implementable variants for general quadratic optimization problems. These problems have a linear objective function c T x to be maximized over a nonconvex compact feasible region F described by a finite number of quadratic inequalities. We introduce two new techniques, “discretization” and “localization,” into the SSDP and SSILP Relaxation Methods. The discretization technique makes it possible to approximate an infinite number of semi-infinite SDPs (or semi-infinite LPs) which appeared at each iteration of the original methods by a finite number of standard SDPs (or standard LPs) with a finite number of linear inequality constraints. We establish:¶•Given any open convex set U containing F, there is an implementable discretization of the SSDP (or SSILP) Relaxation Method which generates a compact convex set C such that F⊆C⊆U in a finite number of iterations.¶The localization technique is for the cases where we are only interested in upper bounds on the optimal objective value (for a fixed objective function vector c) but not in a global approximation of the convex hull of F. This technique allows us to generate a convex relaxation of F that is accurate only in certain directions in a neighborhood of the objective direction c. This cuts off redundant work to make the convex relaxation accurate in unnecessary directions. We establish:¶•Given any positive number ε, there is an implementable localization-discretization of the SSDP (or SSILP) Relaxation Method which generates an upper bound of the objective value within ε of its maximum in a finite number of iterations.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 24 (1982), S. 177-215 
    ISSN: 1436-4646
    Keywords: Variable Dimension Algorithm ; Fixed Point ; Subdivided Manifold ; Nonlinear Equations
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 43 (1989), S. 107-113 
    ISSN: 1436-4646
    Keywords: Complementarity problem ; continuation method ; P-function ; homeomorphism
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...