Library

X
Your search history is empty.
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
    Theoretical convergence of large-step primal—dual interior point algorithms for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 1-21 
    Details
    ISSN: 1436-4646
    Keywords: Primal—dual interior point algorithm ; linear program ; large step ; global convergence ; polynomial-time convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: 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.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581234
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    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
  • 3
    Electronic Resource
    Electronic Resource
    Polynomiality of infeasible-interior-point algorithms for linear programming (1994)
    Springer
    Mathematical programming 67 (1994), S. 109-119 
    Details
    ISSN: 1436-4646
    Keywords: Polynomial-time ; Linear programming ; Primal-dual ; Interior-point algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Kojima, Megiddo, and Mizuno investigate an infeasible-interior-point algorithm for solving a primal—dual pair of linear programming problems and they demonstrate its global convergence. Their algorithm finds approximate optimal solutions of the pair if both problems have interior points, and they detect infeasibility when the sequence of iterates diverges. Zhang proves polynomial-time convergence of an infeasible-interior-point algorithm under the assumption that both primal and dual problems have feasible points. In this paper, we show that a modification of the Kojima—Megiddo—Mizuno algorithm “solves” the pair of problems in polynomial time without assuming the existence of the LP solution. Furthermore, we develop anO(nL)-iteration complexity result for a variant of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582216
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    An O(n 3 L) adaptive path following algorithm for a linear complementarity problem (1991)
    Springer
    Mathematical programming 52 (1991), S. 587-595 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; linear complementarity problem ; interior point algorithms ; path following algorithms
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we propose an O(n 3 L) algorithm which is a modification of the path following algorithm [8] for a linear complementarity problem. The path following algorithm has to take a short step size in each iteration in order to bound the number of overall arithmetic operations by O(n 3 L). In practical computation, we can determine the step size adaptively. Mizuno, Yoshise, and Kikuchi [11] reported that such an adaptive algorithm required about O(L) iterations for some test problems. Here we show that we can use a rank one update technique in the adaptive algorithm so that the number of overall arithmetic operations is theoretically bounded by O(n 3 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582906
    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 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
  • 6
    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
  • 7
    Electronic Resource
    Electronic Resource
    Determination of optimal vertices from feasible solutions in unimodular linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 23-31 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; duality theorem ; unimodular ; totally unimodular ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we consider a linear programming problem with the underlying matrix unimodular, and the other data integer. Given arbitrary near optimum feasible solutions to the primal and the dual problems, we obtain conditions under which statements can be made about the value of certain variables in optimal vertices. Such results have applications to the problem of determining the stopping criterion in interior point methods like the primal—dual affine scaling method and the path following methods for linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581235
    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 new polynomial time method for a linear complementarity problem (1992)
    Springer
    Mathematical programming 56 (1992), S. 31-43 
    Details
    ISSN: 1436-4646
    Keywords: Linear complementarity problem ; polynomial time method ; path following method ; potential reduction method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The purpose of this paper is to present a new polynomial time method for a linear complementarity problem with a positive semi-definite matrix. The method follows a sequence of points. If we generate the sequence on a path, we can construct a path following method, and if we generate the sequence based on a potential function, we can construct a potential reduction method. The method has the advantage that it requires at most $$O(\sqrt n L)$$ iterations for any initial feasible point whose components lie between 2−O(L) and 2O(L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580891
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    An infeasible-interior-point algorithm using projections onto a convex set (1996)
    Springer
    Annals of operations research 62 (1996), S. 59-80 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; infeasible-interior-point method ; polynomiality ; projection ; 90C05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present a new class of primal-dual infeasible-interior-point methods for solving linear programs. Unlike other infeasible-interior-point algorithms, the iterates generated by our methods lie in general position in the positive orthant of ℝ2 and are not restricted to some linear manifold. Our methods comprise the following features: At each step, a projection is used to “recenter” the variables to the domainx i s i ≥μ. The projections are separable into two-dimensional orthogonal projections on a convex set, and thus they are seasy to implement. The use of orthogonal projections allows that a full Newton step can be taken at each iteration, even if the result violates the nonnegativity condition. We prove that a short step version of our method converges in polynomial time.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206811
    Library Location Call Number Volume/Issue/Year Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    A new continuation method for complementarity problems with uniformP-functions (1989)
    Springer
    Mathematical programming 43 (1989), S. 107-113 
    Details
    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
    URL: http://dx.doi.org/10.1007/BF01582283
    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...