ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

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
  • Articles  (376)
  • stability  (223)
  • Linear programming  (153)
  • Springer  (376)
  • Mathematics  (375)
  • Philosophy  (1)
  • 1
    Electronic Resource
    Electronic Resource
    On the stability of wavelet and Gabor frames (Riesz bases) (1999)
    Springer
    The journal of Fourier analysis and applications 5 (1999), S. 105-125 
    Details
    ISSN: 1531-5851
    Keywords: 26B05 ; 42B10 ; 42C99 ; frame ; Gabor system ; Riesz basis ; stability ; wavelet
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract If the sequence of functions ϕj, k is a wavelet frame (Riesz basis) or Gabor frame (Riesz basis), we obtain its perturbation system ψj,k which is still a frame (Riesz basis) under very mild conditions. For example, we do not need to know that the support of ϕ or ψ $$(\hat \phi or\hat \psi )$$ is compact as in [14]. We also discuss the stability of irregular sampling problems. In order to arrive at some of our results, we set up a general multivariate version of Littlewood-Paley type inequality which was originally considered by Lemarié and Meyer [17], then by Chui and Shi [9], and Long [16].
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01274192
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 2
    Electronic Resource
    Electronic Resource
    Decomposition of linear programs using parallel computation (1988)
    Springer
    Mathematical programming 42 (1988), S. 391-405 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; large-scale-systems ; decomposition ; parallel computing
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes DECOMPAR: an implementation of the Dantzig-Wolfe decomposition algorithm for block-angular linear programs using parallel processing of the subproblems. The software is based on a robust experimental code for LP decomposition and runs on the CRYSTAL multicomputer at the University of Wisconsin-Madison. Initial computational experience is reported. Promising directions in future development of this approach are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01589413
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 3
    Electronic Resource
    Electronic Resource
    Feasibility issues in a primal-dual interior-point method for linear programming (1990)
    Springer
    Mathematical programming 49 (1990), S. 145-162 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; primal—dual algorithms ; feasibility
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A new method for obtaining an initial feasible interior-point solution to a linear program is presented. This method avoids the use of a “big-M”, and is shown to work well on a standard set of test problems. Conditions are developed for obtaining a near-optimal solution that is feasible for an associated problem, and details of the computational testing are presented. Other issues related to obtaining and maintaining accurate feasible solutions to linear programs with an interior-point method are discussed. These issues are important to consider when solving problems that have no primal or dual interior-point feasible solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588785
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 4
    Electronic Resource
    Electronic Resource
    Near boundary behavior of primal—dual potential reduction algorithms for linear programming (1993)
    Springer
    Mathematical programming 58 (1993), S. 243-255 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; primal—dual potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper is concerned with selection of theρ-parameter in the primal—dual potential reduction algorithm for linear programming. Chosen from [n + $$\sqrt n $$ , ∞), the level ofρ determines the relative importance placed on the centering vs. the Newton directions. Intuitively, it would seem that as the iterate drifts away from the central path towards the boundary of the positive orthant,ρ must be set close ton + $$\sqrt n $$ . This increases the relative importance of the centering direction and thus helps to ensure polynomial convergence. In this paper, we show that this is unnecessary. We find for any iterate thatρ can be sometimes chosen in a wide range [n + $$\sqrt n $$ , ∞) while still guaranteeing the currently best convergence rate of O( $$\sqrt n $$ L) iterations. This finding is encouraging since in practice large values ofρ have resulted in fast convergence rates. Our finding partially complements the recent result of Zhang, Tapia and Dennis (1990) concerning the local convergence rate of the algorithm.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581269
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 5
    Electronic Resource
    Electronic Resource
    Combining phase I and phase II in a potential reduction algorithm for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 133-150 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; combined phase I—phase II
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes an affine potential reduction algorithm for linear programming that simultaneously seeks feasibility and optimality. The algorithm is closely related to a similar method of Anstreicher. The new features are that we use a two-dimensional programming problem to derive better lower bounds than Anstreicher, that our direction-finding subproblem treats phase I and phase II more symmetrically, and that we do not need an initial lower bound. Our method also allows for the generation of a feasible solution (so that phase I is terminated) during the course of the iterations, and we describe two ways to encourage this behavior.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581241
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 6
    Electronic Resource
    Electronic Resource
    A quadratically convergent O( $$\sqrt n $$ L)-iteration algorithm for linear programming (1993)
    Springer
    Mathematical programming 59 (1993), S. 151-162 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; superlinear and quadratic convergence ; polynomiality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Recently, Ye, Tapia and Zhang (1991) demonstrated that Mizuno—Todd—Ye's predictor—corrector interior-point algorithm for linear programming maintains the O( $$\sqrt n $$ L)-iteration complexity while exhibiting superlinear convergence of the duality gap to zero under the assumption that the iteration sequence converges, and quadratic convergence of the duality gap to zero under the assumption of nondegeneracy. In this paper we establish the quadratic convergence result without any assumption concerning the convergence of the iteration sequence or nondegeneracy. This surprising result, to our knowledge, is the first instance of a demonstration of polynomiality and superlinear (or quadratic) convergence for an interior-point algorithm which does not assume the convergence of the iteration sequence or nondegeneracy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581242
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 7
    Electronic Resource
    Electronic Resource
    A note on the prize collecting traveling salesman problem (1993)
    Springer
    Mathematical programming 59 (1993), S. 413-420 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; prize collecting ; rounding fractional solutions ; traveling salesman problem ; worst-case analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the version of the prize collecting traveling salesman problem, where the objective is to find a tour that visits a subset of vertices such that the length of the tour plus the sum of penalties associated with vertices not in the tour is as small as possible. We present an approximation algorithm with constant bound. The algorithm is based on Christofides' algorithm for the traveling salesman problem as well as a method to round fractional solutions of a linear programming relaxation to integers, feasible for the original problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581256
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 8
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 9
    Electronic Resource
    Electronic Resource
    Comparative analysis of affine scaling algorithms based on simplifying assumptions (1991)
    Springer
    Mathematical programming 52 (1991), S. 405-414 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; primal and dual ; potential reduction algorithm ; affine scaling algorithm
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We analyze several affine potential reduction algorithms for linear programming based on simplifying assumptions. We show that, under a strong probabilistic assumption regarding the distribution of the data in an iteration, the decrease in the primal potential function will be $$\Omega (\rho /\sqrt {log(n)} )$$ with high probability, compared to the guaranteedΩ(1). (ρ ⩾2n is a parameter in the potential function andn is the number of variables.) Under the same assumption, we further show that the objective reduction rate of Dikin's affine scaling algorithm is $$(1 - 1/\sqrt {log(n)} )$$ with high probability, compared to no guaranteed convergence rate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582897
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 10
    Electronic Resource
    Electronic Resource
    Global convergence of the affine scaling methods for degenerate linear programming problems (1991)
    Springer
    Mathematical programming 52 (1991), S. 377-404 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point methods ; affine scaling methods ; global analysis ; degenerate problems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we show the global convergence of the affine scaling methods without assuming any condition on degeneracy. The behavior of the method near degenerate faces is analyzed in detail on the basis of the equivalence between the affine scaling methods for homogeneous LP problems and Karmarkar's method. It is shown that the step-size 1/8, where the displacement vector is normalized with respect to the distance in the scaled space, is sufficient to guarantee the global convergence of the affine scaling methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582896
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 11
    Electronic Resource
    Electronic Resource
    A combined phase I—phase II scaled potential algorithm for linear programming (1991)
    Springer
    Mathematical programming 52 (1991), S. 429-439 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; potential function ; phase I ; phase II ; artificial variable
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We develop an extension of the affinely scaled potential reduction algorithm which simultaneously obtains feasibility and optimality in a standard form linear program, without the addition of any “M” terms. The method, and its lower-bounding procedure, are particularly simple compared with previous interior algorithms not requiring feasibility.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582899
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 12
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 13
    Electronic Resource
    Electronic Resource
    Primal—dual methods for linear programming (1995)
    Springer
    Mathematical programming 70 (1995), S. 251-277 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Barrier methods ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Many interior-point methods for linear programming are based on the properties of the logarithmic barrier function. After a preliminary discussion of the convergence of the (primal) projected Newton barrier method, three types of barrier method are analyzed. These methods may be categorized as primal, dual and primal—dual, and may be derived from the application of Newton's method to different variants of the same system of nonlinear equations. A fourth variant of the same equations leads to a new primal—dual method. In each of the methods discussed, convergence is demonstrated without the need for a nondegeneracy assumption or a transformation that makes the provision of a feasible point trivial. In particular, convergence is established for a primal—dual algorithm that allows a different step in the primal and dual variables and does not require primal and dual feasibility. Finally, a new method for treating free variables is proposed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585940
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 14
    Electronic Resource
    Electronic Resource
    The fleet assignment problem: Solving a large-scale integer program (1995)
    Springer
    Mathematical programming 70 (1995), S. 211-232 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Mixed-integer programming ; Large-scale optimization ; Airline fleet assignment
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a flight schedule and set of aircraft, the fleet assignment problem is to determine which type of aircraft should fly each flight segment. This paper describes a basic daily, domestic fleet assignment problem and then presents chronologically the steps taken to solve it efficiently. Our model of the fleet assignment problem is a large multi-commodity flow problem with side constraints defined on a time-expanded network. These problems are often severely degenerate, which leads to poor performance of standard linear programming techniques. Also, the large number of integer variables can make finding optimal integer solutions difficult and time-consuming. The methods used to attack this problem include an interior-point algorithm, dual steepest edge simplex, cost perturbation, model aggregation, branching on set-partitioning constraints and prioritizing the order of branching. The computational results show that the algorithm finds solutions with a maximum optimality gap of 0.02% and is more than two orders of magnitude faster than using default options of a standard LP-based branch-and-bound code.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585938
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 15
    Electronic Resource
    Electronic Resource
    Partitioning mathematical programs for parallel solution (1998)
    Springer
    Mathematical programming 80 (1998), S. 35-61 
    Details
    ISSN: 1436-4646
    Keywords: Graph partitioning ; Linear programming ; Bundle method ; Parallel optimization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes heuristics for partitioning a generalM × N matrix into arrowhead form. Such heuristics are useful for decomposing large, constrained, optimization problems into forms that are amenable to parallel processing. The heuristics presented can be easily implemented using publicly available graph partitioning algorithms. The application of such techniques for solving large linear programs is described. Extensive computational results on the effectiveness of our partitioning procedures and their usefulness for parallel optimization are presented. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582130
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 16
    Electronic Resource
    Electronic Resource
    Long steps in an O(n 3 L) algorithm for linear programming (1992)
    Springer
    Mathematical programming 54 (1992), S. 251-265 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; potential function ; standard form ; modified method ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider partial updating in Ye's affine potential reduction algorithm for linear programming. We show that using a Goldstein—Armijo rule to safeguard a linesearch of the potential function during primal steps is sufficient to control the number of updates. We also generalize the dual step construction to apply with partial updating. The result is the first O(n 3 L) algorithm for linear programming whose steps are not constrained by the need to remain approximately centered. The fact that the algorithm has a rigorous “primal-only” initialization actually reduces the complexity to less than O(m 1.5 n 1.5 L).
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586053
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 17
    Electronic Resource
    Electronic Resource
    On Anstreicher's combined phase I—phase II projective algorithm for linear programming (1992)
    Springer
    Mathematical programming 55 (1992), S. 1-15 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point method ; projective algorithm ; combining phase I–phase II
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Anstreicher has proposed a variant of Karmarkar's projective algorithm that handles standard-form linear programming problems nicely. We suggest modifications to his method that we suspect will lead to better search directions and a more useful algorithm. Much of the analysis depends on a two-constraint linear programming problem that is a relaxation of the scaled original problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581187
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 18
    Electronic Resource
    Electronic Resource
    Strict monotonicity and improved complexity in the standard form projective algorithm for linear programming (1993)
    Springer
    Mathematical programming 62 (1993), S. 517-535 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; Projective algorithm ; Standard form
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In a recent paper, Shaw and Goldfarb show that a version of the standard form projective algorithm can achieve $$O\left( {\sqrt {nL} } \right)$$ step complexity, as opposed to the O(nL) step complexity originally demonstrated for the algorithm. The analysis of Shaw and Goldfarb shows that the algorithm, using a constant, fixed steplength, approximately follows the central trajectory. In this paper we show that simple modifications of the projective algorithm obtain the same complexity improvement, while permitting a linesearch of the potential function on each step. An essential component is the addition of a single constraint, motivated by Shaw and Goldfarb's analysis, which makes the standard form algorithm strictly monotone in the true objective.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585181
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 19
    Electronic Resource
    Electronic Resource
    Linear programming, complexity theory and elementary functional analysis (1995)
    Springer
    Mathematical programming 70 (1995), S. 279-351 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Complexity theory ; Interior-point methods ; Semi-definite programming ; Condition numbers ; Convex programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose analyzing interior-point methods using notions of problem-instance size which are direct generalizations of the condition number of a matrix. The notions pertain to linear programming quite generally; the underlying vector spaces are not required to be finite-dimensional and, more importantly, the cones defining nonnegativity are not required to be polyhedral. Thus, for example, the notions are appropriate in the context of semi-definite programming. We prove various theorems to demonstrate how the notions can be used in analyzing interior-point methods. These theorems assume little more than that the interiors of the cones (defining nonnegativity) are the domains of self-concordant barrier functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585941
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 20
    Electronic Resource
    Electronic Resource
    Presolving in linear programming (1995)
    Springer
    Mathematical programming 71 (1995), S. 221-245 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Presolving ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible. In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve. Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586000
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 21
    Electronic Resource
    Electronic Resource
    Zur Modellierung logischer Aussagen ergänzend zu Linearen Programmen (1992)
    Springer
    OR spectrum 14 (1992), S. 149-160 
    Details
    ISSN: 1436-6304
    Keywords: Lineare Programmierung ; logische Aussagen ; Binärvariablen ; Modellgenerator ; Linear programming ; predicates ; binary variables ; model generator
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Summary We introduce in the field of formulating logical predicates in addition to linear programs. The error prone process of developing linear constraints including binary variables (“auxilliary formulations”) to accomplish this leads us to discuss the possibilities and capabilities of model generation. Based on Williams [12] we develop the formulae apparatus and discuss formulation and design problems for the development of our model generator now being implemented.
    Notes: Zusammenfassung Wir geben eine Einführung in das Gebiet der Formulierung logischer Aussagen ergänzend zu Linearen Programmen. Der dazu notwendige, fehlerträchtige Prozeß der Aufstellung linearer Restriktionen unter der Verwendung von Binärvariablen („Ersatzformulierungen“) führt uns dazu, die Möglichkeiten und Fähigkeiten eines Modellgenerators für diesen Zweck zu diskutieren. Auf der Grundlage von Williams [12] entwickeln wir den Formelapparat und erörtern Formulierungs- und Entwurfsprobleme für die Entwicklung unseres sich jetzt in der Implementationsphase befindlichen Modellgenerators.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01783518
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 22
    Electronic Resource
    Electronic Resource
    Reachability of locational Nash equilibria (1998)
    Springer
    OR spectrum 20 (1998), S. 101-107 
    Details
    ISSN: 1436-6304
    Keywords: Competitive location model ; Nash equilibria ; stability ; reachability ; Wettbewerbsmodelle in der Standorttheorie ; Nash Gleichgewicht ; Stabilität ; Erreichbarkeit
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In der Arbeit werden die Standorte von Duopolisten in einem Baum untersucht. Unter der Annahme festgesetzter Preise werden notwendige und hinreichende Bedingungen für Nash Gleichgewichte für Standorte auf Bäumen hergeleitet. Unter Verwendung dieser Bedingungen wird dann gezeigt, daß — angenommen Nash Gleichgewichte existieren — diese in einem wiederholt angewandten sequentiellen Standortfindungsprozeß, in dem beide Duopolisten als Zielfunktion kurzfristige Gewinnmaximierung haben, auch erreicht werden.
    Notes: Abstract This paper examines the location of duopolists on a tree. Given parametric prices, we first delineate necessary and sufficient conditions for locational Nash equilibria on trees. Given these conditions, we then show that Nash equilibria, provided they exist, can be reached in a repeated sequential relocation process in which both facilities follow short-term profit maximization objectives.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01539861
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 23
    Electronic Resource
    Electronic Resource
    Reachability of locational Nash equilibria (1998)
    Springer
    OR spectrum 20 (1998), S. 101-107 
    Details
    ISSN: 1436-6304
    Keywords: Key words: Competitive location model ; Nash equilibria ; stability ; reachability ; Schlüsselwörter: Wettbewerbsmodelle in der Standorttheorie ; Nash Gleichgewicht ; Stabilität ; Erreichbarkeit
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung. In der Arbeit werden die Standorte von Duopolisten in einem Baum untersucht. Unter der Annahme festgesetzter Preise werden notwendige und hinreichende Bedingungen für Nash Gleichgewichte für Standorte auf Bäumen hergeleitet. Unter Verwendung dieser Bedingungen wird dann gezeigt, daß– angenommen Nash Gleichgewichte existieren – diese in einem wiederholt angewandten sequentiellen Standortfindungsprozeß, in dem beide Duopolisten als Zielfunktion kurzfristige Gewinnmaximierung haben, auch erreicht werden. “Equilibrium is a place in heaven, but how do we get there from here?”
    Notes: Abstract. This paper examines the location of duopolists on a tree. Given parametric prices, we first delineate necessary and sufficient conditions for locational Nash equilibria on trees. Given these conditions, we then show that Nash equilibria, provided they exist, can be reached in a repeated sequential relocation process in which both facilities follow short-term profit maximization objectives.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/s002910050058
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 24
    Electronic Resource
    Electronic Resource
    Stability results for approximately efficient solutions (1994)
    Springer
    OR spectrum 16 (1994), S. 47-52 
    Details
    ISSN: 1436-6304
    Keywords: Vector optimization ; approximately efficient solutions ; stability ; Vektoroptimierung ; Näherungslösungen ; Stabilität
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung Wir führen ein Konzept für Näherungslösungen in der Vektoroptimierung ein und vergleichen dieses mit einem neuen Konzept aus [8]. Weiterhin untersuchen wir Beziehungen zwischen der Menge der Näherungslösungen eines Vektoroptimierungsproblems und den Näherungslösungen eines entsprechenden parametrischen Ersatzproblems. Schließlich beweisen wir Stabilitätseigenschaften des skalaren Ersatzproblems.
    Notes: Abstract We introduce a concept for approximately efficient solutions in vector optimization and compare it with another recent concept given in [8]. Further, we study relations between the set of approximately efficient solutions of a vector optimization problem and the approximate solutions of a corresponding parametric surrogate optimization problem. Finally, we prove stability properties for the scalar surrogate problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01719703
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 25
    Electronic Resource
    Electronic Resource
    Generalized linear complementarity in a problem ofn-person games (1996)
    Springer
    OR spectrum 18 (1996), S. 231-239 
    Details
    ISSN: 1436-6304
    Keywords: Generalized polymatrix games ; generalized linear complementarity problem ; stability ; degree theory ; Verallgemeinerte Polymatrix-Spiele ; verallgemeinertes lineares Komplementaritätsproblem ; Stabilität ; Grad-Theorie
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Description / Table of Contents: Zusammenfassung In dieser Arbeit führen wir eine Verallgemeinerung des Polymatrix-Spiels (eines Nicht-Nullsummen- und nicht-kooperativenn-Personen-Spiels), das von Howson betrachtet wurde, ein und führen das Problem, eine Gleichgewichtsmenge von Strategien für ein solches Spiel zu berechnen, auf das verallgemeinerte lineare Komplementaritätsproblem von Cottle und Dantzig zurück. Für eine noch allgemeinere Version des Spiels beweisen wir die Existenz einerε-Gleichgewichtsmenge von Strategien. Wir präsentieren auch ein Ergebnis über die Stabilität der Gleichgewichte, das auf der Grad-Theorie beruht.
    Notes: Abstract In this paper, we introduce a generalization of the polymatrix game (a nonzero sum noncooperativen-person game) considered by Howson and relate the problem of computing an equilibrium set of strategies for such a game to the generalized linear complementarity problem of Cottle and Dantzig. For an even more general version of the game we prove the existence of anε-equilibrium set of strategies. We also present a result on the stability of the equilibria based on degree theory.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01540162
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 26
    Electronic Resource
    Electronic Resource
    An implementation of Karmarkar's algorithm for linear programming (1989)
    Springer
    Mathematical programming 44 (1989), S. 297-335 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper describes the implementation of power series dual affine scaling variants of Karmarkar's algorithm for linear programming. Based on a continuous version of Karmarkar's algorithm, two variants resulting from first and second order approximations of the continuous trajectory are implemented and tested. Linear programs are expressed in an inequality form, which allows for the inexact computation of the algorithm's direction of improvement, resulting in a significant computational advantage. Implementation issues particular to this family of algorithms, such as treatment of dense columns, are discussed. The code is tested on several standard linear programming problems and compares favorably with the simplex codeMinos 4.0.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01587095
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 27
    Electronic Resource
    Electronic Resource
    A polynomial-time algorithm, based on Newton's method, for linear programming (1988)
    Springer
    Mathematical programming 40 (1988), S. 59-93 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior method ; computational complexity ; Newton's method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A new interior method for linear programming is presented and a polynomial time bound for it is proven. The proof is substantially different from those given for the ellipsoid algorithm and for Karmarkar's algorithm. Also, the algorithm is conceptually simpler than either of those algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580724
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 28
    Electronic Resource
    Electronic Resource
    A “build-down” scheme for linear programming (1990)
    Springer
    Mathematical programming 46 (1990), S. 61-72 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex method ; ellipsoid method ; Karmarkar's algorithm ; primal and dual
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a “build-down” scheme for Karmarkar's algorithm and the simplex method for linear programming. The scheme starts with an optimal basis “candidate” setΞ including all columns of the constraint matrix, then constructs a dual ellipsoid containing all optimal dual solutions. A pricing rule is developed for checking whether or not a dual hyperplane corresponding to a column intersects the containing ellipsoid. If the dual hyperplane has no intersection with the ellipsoid, its corresponding column will not appear in any of the optimal bases, and can be eliminated fromΞ. As these methods iterate,Ξ is eventually built-down to a set that contains only the optimal basic columns.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585727
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 29
    Electronic Resource
    Electronic Resource
    Computing Karmarkar projections quickly (1988)
    Springer
    Mathematical programming 41 (1988), S. 61-71 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's method ; Cholesky factorization ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The paper presents a numerical method for computing the projections for Karmarkar's new algorithm for linear programming. The method is simple to implement, fully exploits sparsity, and appears in limited experimentation to have good stability properties. Preliminary numerical experience indicates that the method promises advantages over methods that refactor a matrix at every iteration.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580753
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 30
    Electronic Resource
    Electronic Resource
    On the solution of highly degenerate linear programmes (1988)
    Springer
    Mathematical programming 41 (1988), S. 385-392 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; simplex method ; degeneracy ; scheduling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The solution of scheduling problems often gives rise to highly degenerate linear programmes which cause significant computational difficulties for the revised simplex method. Wolfe's highly effective “ad hoc” method for overcoming the cycling or stalling problems associated with degeneracy is described. Here it is given a geometric interpretation in terms of finding a direction of recession for a reduced problem which is fundamental to a full understanding of the procedure. An example of an aircrew scheduling problem is used to illustrate the effectiveness of the method.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580776
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 31
    Electronic Resource
    Electronic Resource
    Polynomial affine algorithms for linear programming (1990)
    Springer
    Mathematical programming 49 (1990), S. 7-21 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; affine algorithms ; Karmarkar's algorithm ; interior methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The method of steepest descent with scaling (affine scaling) applied to the potential functionq logc′x — ∑ i=1 n logx i solves the linear programming problem in polynomial time forq ⩾ n. Ifq = n, then the algorithm terminates in no more than O(n 2 L) iterations; if q ⩾ n + $$\sqrt n $$ withq = O(n) then it takes no more than O(nL) iterations. A modified algorithm using rank-1 updates for matrix inversions achieves respectively O(n 4 L) and O(n 3.5 L) arithmetic computions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01588776
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 32
    Electronic Resource
    Electronic Resource
    Linear programming and the newton barrier flow (1988)
    Springer
    Mathematical programming 41 (1988), S. 367-373 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; interior algorithm ; central trajectory ; barrier function ; Newton's method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this note we report a simple characteristic of linear programming central trajectories which has a surprising consequence. Specifically, we show that given a bounded polyhedral setP with nonempty interior, the logarithmic barrier function (with no objective component) induces a vector field of negative Newton directions which flows from the center ofP, along central trajectories, to solutions of every possible linear program onP.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580774
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 33
    Electronic Resource
    Electronic Resource
    A bifurcation analysis of the nonlinear parametric programming problem (1990)
    Springer
    Mathematical programming 47 (1990), S. 117-141 
    Details
    ISSN: 1436-4646
    Keywords: Bifurcation ; singularity ; parametric programming ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The structure of solutions to the nonlinear parametric programming problem with a one dimensional parameter is analyzed in terms of the bifurcation behavior of the curves of critical points and the persistence of minima along these curves. Changes in the structure of the solution occur at singularities of a nonlinear system of equations motivated by the Fritz John first-order necessary conditions. It has been shown that these singularities may be completely partitioned into seven distinct classes based upon the violation of one or more of the following: a complementarity condition, a constraint qualification, and the nonsingularity of the Hessian of the Lagrangian on a tangent space. To apply classical bifurcation techniques to these singularities, a further subdivision of each case is necessary. The structure of curves of critical points near singularities of lowest (zero) codimension within each case is analyzed, as well as the persistence of minima along curves emanating from these singularities. Bifurcation behavior is also investigated or discussed for many of the subcases giving rise to a codimension one singularity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580856
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 34
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 35
    Electronic Resource
    Electronic Resource
    Linear programming with spheres and hemispheres of objective vectors (1991)
    Springer
    Mathematical programming 51 (1991), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; parametric ; homeomorphisms ; spheres ; hemispheres
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Given a linear program with a boundedp-dimensional feasible region let the objective vector range over ans-sphere, that is, ans-dimensional sphere centered at the origin wheres does not exceedp−1. If the feasible region and the sphere are in general position with respect to each other, then the corresponding set of all optimal solutions is a topologicals-sphere. Similar results are developed for unbounded feasible regions and hemispheres of objective vectors.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586923
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 36
    Electronic Resource
    Electronic Resource
    Random walks, totally unimodular matrices, and a randomised dual simplex algorithm (1994)
    Springer
    Mathematical programming 64 (1994), S. 1-16 
    Details
    ISSN: 1436-4646
    Keywords: Random walks ; Totally unimodular matrices ; Uniform generation ; Linear programming ; Diameter of polytopes
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We discuss the application of random walks to generating a random basis of a totally unimodular matrix and to solving a linear program with such a constraint matrix. We also derive polynomial upper bounds on the combinatorial diameter of an associated polyhedron.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582563
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 37
    Electronic Resource
    Electronic Resource
    Dynamic factorization in large-scale optimization (1994)
    Springer
    Mathematical programming 64 (1994), S. 17-51 
    Details
    ISSN: 1436-4646
    Keywords: Factorization ; Linear programming ; Generalized upper bounds ; Pure networks ; Generalized networks
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Factorization of linear programming (LP) models enables a large portion of the LP tableau to be represented implicitly and generated from the remaining explicit part. Dynamic factorization admits algebraic elements which change in dimension during the course of solution. A unifying mathematical framework for dynamic row factorization is presented with three algorithms which derive from different LP model row structures: generalized upper bound rows, pure network rows, and generalized network rows. Each of these structures is a generalization of its predecessors, and each corresponding algorithm exhibits just enough additional richness to accommodate the structure at hand within the unified framework. Implementation and computational results are presented for a variety of real-world models. These results suggest that each of these algorithms is superior to the traditional, non-factorized approach, with the degree of improvement depending upon the size and quality of the row factorization identified.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582564
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 38
    Electronic Resource
    Electronic Resource
    Interior-point algorithms for semi-infinite programming (1994)
    Springer
    Mathematical programming 65 (1994), S. 217-245 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Semi-infinite programming ; Interior-point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In order to study the behavior of interior-point methods on very large-scale linear programming problems, we consider the application of such methods to continuous semi-infinite linear programming problems in both primal and dual form. By considering different discretizations of such problems we are led to a certain invariance property for (finite-dimensional) interior-point methods. We find that while many methods are invariant, several, including all those with the currently best complexity bound, are not. We then devise natural extensions of invariant methods to the semi-infinite case. Our motivation comes from our belief that for a method to work well on large-scale linear programming problems, it should be effective on fine discretizations of a semi-infinite problem and it should have a natural extension to the limiting semi-infinite case.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581697
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 39
    Electronic Resource
    Electronic Resource
    The maximum entropy method on the mean: Applications to linear programming and superresolution (1994)
    Springer
    Mathematical programming 66 (1994), S. 103-122 
    Details
    ISSN: 1436-4646
    Keywords: 42B05 ; 62A99 ; Maximum entropy ; Linear programming ; Inverse problems ; Superresolution
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper, we give two different results. We propose new methods to solve classical optimization problems in linear programming. We also obtain precise quantitative results for the superresolution phenomenon, as observed earlier by practical searchers on specific algorithms. The common background of our work is the generalized moment problem, which is known to be connected with linear programming and superresolution. We describe the Maximum Entropy Method on the Mean that provides solution to the problem and leads to computational criteria to decide the existence of solutions or not.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581139
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 40
    Electronic Resource
    Electronic Resource
    Superlinear convergence of infeasible-interior-point methods for linear programming (1994)
    Springer
    Mathematical programming 66 (1994), S. 361-377 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Infeasible-interior-point methods ; Superlinear convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract At present the interior-point methods of choice are primal—dual infeasible-interior-point methods, where the iterates are kept positive, but allowed to be infeasible. In practice, these methods have demonstrated superior computational performance. From a theoretical point of view, however, they have not been as thoroughly studied as their counterparts — feasible-interior-point methods, where the iterates are required to be strictly feasible. Recently, Kojima et al., Zhang, Mizuno and Potra studied the global convergence of algorithms in the primal—dual infeasible-interior-point framework. In this paper, we continue to study this framework, and in particular we study the local convergence properties of algorithms in this framework. We construct parameter selections that lead toQ-superlinear convergence for a merit function andR-superlinear convergence for the iteration sequence, both at rate 1 +τ whereτ can be arbitrarily close to one.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581155
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 41
    Electronic Resource
    Electronic Resource
    On the choice of parameters for power-series interior point algorithms in linear programming (1995)
    Springer
    Mathematical programming 68 (1995), S. 49-71 
    Details
    ISSN: 1436-4646
    Keywords: Power-series interior point algorithms: Parameter transformations ; Best parameter ; k-parameter ; Truncated power-series approximation ; Higher-order derivatives ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract In this paper we study higher-order interior point algorithms, especially power-series algorithms, for solving linear programming problems. Since higher-order differentials are not parameter-invariant, it is important to choose a suitable parameter for a power-series algorithm. We propose a parameter transformation to obtain a good choice of parameter, called ak-parameter, for general truncated powerseries approximations. We give a method to find ak-parameter. This method is applied to two powerseries interior point algorithms, which are built on a primal—dual algorithm and a dual algorithm, respectively. Computational results indicate that these higher-order power-series algorithms accelerate convergence compared to first-order algorithms by reducing the number of iterations. Also they demonstrate the efficiency of thek-parameter transformation to amend an unsuitable parameter in power-series algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585757
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 42
    Electronic Resource
    Electronic Resource
    Superlinear primal-dual affine scaling algorithms for LCP (1995)
    Springer
    Mathematical programming 69 (1995), S. 311-333 
    Details
    ISSN: 1436-4646
    Keywords: Interior-point methods ; Primal-dual affine scaling ; Linear programming ; Linear complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe an interior-point algorithm for monotone linear complementarity problems in which primal-dual affine scaling is used to generate the search directions. The algorithm is shown to have global and superlinear convergence with Q-order up to (but not including) two. The technique is shown to be consistent with a potential-reduction algorithm, yielding the first potential-reduction algorithm that is both globally and superlinearly convergent.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585562
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 43
    Electronic Resource
    Electronic Resource
    Characterization of stable matchings as extreme points of a polytope (1992)
    Springer
    Mathematical programming 54 (1992), S. 57-67 
    Details
    ISSN: 1436-4646
    Keywords: Matchings ; stability ; extreme points ; polytope
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract The purpose of this paper is to extend a modified version of a recent result of Vande Vate (1989) which characterizes stable matchings as the extreme points of a certain polytope. Our proofs are simpler and more transparent than those of Vande Vate.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01586041
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 44
    Electronic Resource
    Electronic Resource
    Minimizing average completion time in the presence of release dates (1998)
    Springer
    Mathematical programming 82 (1998), S. 199-223 
    Details
    ISSN: 1436-4646
    Keywords: Scheduling ; Preemptive scheduling ; Average weighted completion time ; Approximation algorithms ; Relaxations ; Linear programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract A natural and basic problem in scheduling theory is to provide good average quality of service to a stream of jobs that arrive over time. In this paper we consider the problem of schedulingn jobs that are released over time in order to minimize the average completion time of the set of jobs. In contrast to the problem of minimizing average completion time when all jobs are available at time 0, all the problems that we consider are NP-hard, and essentially nothing was known about constructing good approximations in polynomial time. We give the first constant-factor approximation algorithms for several variants of the single and parallel machine models. Many of the algorithms are based on interesting algorithmic and structural relationships between preemptive and nonpreemptive schedules and linear programming relaxations of both. Many of the algorithms generalize to the minimization of averageweighted completion time as well. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585872
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 45
    Electronic Resource
    Electronic Resource
    Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices (1992)
    Springer
    Mathematical programming 57 (1992), S. 121-143 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; polynomial-time algorithms ; strongly polynomial-time algorithms ; circulant matrices ; algebraic numbers
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show that a modified variant of the interior point method can solve linear programs (LPs) whose coefficients are real numbers from a subring of the algebraic integers. By defining the encoding size of such numbers to be the bit size of the integers that represent them in the subring, we prove the modified algorithm runs in time polynomial in the encoding size of the input coefficients, the dimension of the problem, and the order of the subring. We then extend the Tardos scheme to our case, obtaining a running time which is independent of the objective and right-hand side data. As a consequence of these results, we are able to show that LPs with real circulant coefficient matrices can be solved in strongly polynomial time. Finally, we show how the algorithm can be applied to LPs whose coefficients belong to the extension of the integers by a fixed set of square roots.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581077
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 46
    Electronic Resource
    Electronic Resource
    Quantitative stability of variational systems: III.ε-approximate solutions (1993)
    Springer
    Mathematical programming 61 (1993), S. 197-214 
    Details
    ISSN: 1436-4646
    Keywords: Epi-convergence ; epi-distance ; stability ; convex optimization ; approximate solutions ; subgradients ; level sets
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We prove that theε-optimal solutions of convex optimization problems are Lipschitz continuous with respect to data perturbations when these are measured in terms of the epi-distance. A similar property is obtained for the distance between the level sets of extended real valued functions. We also show that these properties imply that theε-subgradient mapping is Lipschitz continuous.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582147
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 47
    Electronic Resource
    Electronic Resource
    Limiting behavior of weighted central paths in linear programming (1994)
    Springer
    Mathematical programming 65 (1994), S. 347-363 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; (Weighted) central paths ; Limiting behavior on central paths ; Local convergence rates of interior point algorithms ; Primary: 90C05 ; Secondary: 90C33
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the limiting behavior of the weighted central paths{(x(μ), s(μ))} μ 〉 0 in linear programming at bothμ = 0 andμ = ∞. We establish the existence of a partition (B ∞,N ∞) of the index set { 1, ⋯,n } such thatx i(μ) → ∞ ands j (μ) → ∞ asμ → ∞ fori ∈ B ∞, andj ∈ N ∞, andx N∞ (μ),s B∞ (μ) converge to weighted analytic centers of certain polytopes. For allk ⩾ 1, we show that thekth order derivativesx (k) (μ) ands (k) (μ) converge whenμ → 0 andμ → ∞. Consequently, the derivatives of each order are bounded in the interval (0, ∞). We calculate the limiting derivatives explicitly, and establish the surprising result that all higher order derivatives (k ⩾ 2) converge to zero whenμ → ∞.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01581702
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 48
    Electronic Resource
    Electronic Resource
    Asymptotic analysis of the exponential penalty trajectory in linear programming (1994)
    Springer
    Mathematical programming 67 (1994), S. 169-187 
    Details
    ISSN: 1436-4646
    Keywords: 90C05 ; 90C25 ; 90C31 ; 49M30 ; Linear programming ; Exponential penalty ; Optimal trajectory ; Asymptotic expansion ; Interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider the linear program min{c′x: Ax⩽b} and the associated exponential penalty functionf r(x) = c′x + rΣexp[(A ix − bi)/r]. Forr close to 0, the unconstrained minimizerx(r) off r admits an asymptotic expansion of the formx(r) = x * + rd* + η(r) wherex * is a particular optimal solution of the linear program and the error termη(r) has an exponentially fast decay. Using duality theory we exhibit an associated dual trajectoryλ(r) which converges exponentially fast to a particular dual optimal solution. These results are completed by an asymptotic analysis whenr tends to ∞: the primal trajectory has an asymptotic ray and the dual trajectory converges to an interior dual feasible solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01582220
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 49
    Electronic Resource
    Electronic Resource
    On the improvement per iteration in Karmarkar's algorithm for linear programming (1990)
    Springer
    Mathematical programming 46 (1990), S. 299-320 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar ; projective ; potential
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We investigate the decrease in potential at an iteration of Karmarkar's projective method for linear programming. For a fixed step length parameterα (so that we must have 0 〈α ≤ 1) the best possible guaranteeδ n (α) inn dimensional space is essentially ln 2 ≃ 0.69; and to achieve this we must takeα about 1. Indeed we show the precise result thatδ n (α) equals ln(1 +α)-ln(1 −α/(n − 1)) forn sufficiently large. If we choose an optimal step length at each iteration then this guarantee increases only to aboutδ * ≃ 0.72. We also shed some light on the remarkable empirical observation that the number of iterations required seems scarcely to grow with the size of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01585747
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 50
    Electronic Resource
    Electronic Resource
    Exploiting special structure in Karmarkar's linear programming algorithm (1988)
    Springer
    Mathematical programming 41 (1988), S. 97-113 
    Details
    ISSN: 1436-4646
    Keywords: Linear programming ; Karmarkar's algorithm ; special structure
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose methods to take advantage of specially-structured constraints in a variant of Karmarkar's projective algorithm for standard form linear programming problems. We can use these constraints to generate improved bounds on the optimal value of the problem and also to compute the necessary projections more efficiently, while maintaining the theoretical bound on the algorithm's performance. It is shown how various upper-bounding constraints can be handled implicitly in this way. Unfortunately, the situation for network constraints appears less favorable.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01580755
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 51
    Electronic Resource
    Electronic Resource
    The dynamics of coupled planar rigid bodies. II. Bifurcations, periodic solutions, and chaos (1989)
    Springer
    Journal of dynamics and differential equations 1 (1989), S. 269-298 
    Details
    ISSN: 1572-9222
    Keywords: Geometric mechanics ; reduction ; stability ; chaos ; rigid body dynamics ; periodic orbits ; 58F
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We give a complete bifurcation and stability analysis for the relative equilibria of the dynamics of three coupled planar rigid bodies. We also use the equivariant Weinstein-Moser theorem to show the existence of two periodic orbits distinguished by symmetry type near the stable equilibrium. Finally we prove that the dynamics is chaotic in the sense of Poincaré-Birkhoff-Smale horseshoes using the version of Melnikov's method suitable for systems with symmetry due to Holmes and Marsden.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01053929
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 52
    Electronic Resource
    Electronic Resource
    Stability and Instability of Fourth-Order Solitary Waves (1998)
    Springer
    Journal of dynamics and differential equations 10 (1998), S. 151-188 
    Details
    ISSN: 1572-9222
    Keywords: Fourth-order solitary waves ; stability ; instability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We study ground-state traveling wave solutions of a fourth-order wave equation. We find conditions on the speed of the waves which imply stability and instability of the solitary waves. The analysis depends on the variational characterization of the ground states rather than information about the linearized operator.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1022644629950
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 53
    Electronic Resource
    Electronic Resource
    Linear stability of relative equilibria with a dominant mass (1994)
    Springer
    Journal of dynamics and differential equations 6 (1994), S. 37-51 
    Details
    ISSN: 1572-9222
    Keywords: Celestial mechanics ; relative equilibria ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A criterion for the linear stability of relative equilibria of the Newtoniann-body problem is found in the case whenn−1 of the masses are small. Several stable periodic orbits of the problem are presented as examples.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02219187
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 54
    Electronic Resource
    Electronic Resource
    Interval stability and interval covering property in finite posets (1992)
    Springer
    Order 9 (1992), S. 163-175 
    Details
    ISSN: 1572-9273
    Keywords: Primary 06A07 ; secondary 05C70 ; Partial order ; interval ; stability ; covering ; Sperner property ; symmetric chains ; NP-completeness
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Given a finite ranked posetP, let α(P) be the maximum size of a subset ofP such that no two elements of it belong simultaneously to some interval ofP and let ϱ(P) be the minimum number of intervals covering all elements ofP. We say thatP has the strong interval stability property (resp. the strong interval covering property) if for each subposetP′ induced by consecutive levels ofP, i.e.,P′=P (l)∪...∪P (u), one has α(P′)=max{|P (l)|, |P (u)|} (resp. ϱ(P′)=max{|P (l)|, |P (u)|}). We prove these properties for several classes of posets and discuss some general facts concerning the numbers α(P) and ϱ(P), e.g., NP-completeness and min-max relations.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00814408
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 55
    Electronic Resource
    Electronic Resource
    Stability of Semilinear Delay Equations with Positive Solutions (1997)
    Springer
    Positivity 1 (1997), S. 319-330 
    Details
    ISSN: 1572-9281
    Keywords: delay equations ; stability ; positive solutions ; spectral growth condition
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We prove stability for a semilinear delay equation, whose nonlinearity is majorized by a linear positive operator. The key ingredients are a spectral condition, positivity of solutions to the linear problem, and lattice properties of the Banach space.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009725823213
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 56
    Electronic Resource
    Electronic Resource
    Some Results on Stability of Retarded Functional Differential Equations Using Dichotomic Map Techniques (1998)
    Springer
    Positivity 2 (1998), S. 229-238 
    Details
    ISSN: 1572-9281
    Keywords: asymptotic stability ; dichotomic maps ; retarded functional differential equation ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper deals with the study of the stability of nonautonomous retarded functional differential equations using the theory of dichotomic maps. After some preliminaries, we prove the theorems on simple and asymptotic stability. Some examples are given to illustrate the application of the method. Main results about asymptotic stability of the equation $$x'(t) = - b(t)x(t - r)$$ and of itsnonlinear generalization $$x'(t) = b(t)f(x(t - r))$$ are established.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009742807025
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 57
    Electronic Resource
    Electronic Resource
    Optimal capacity in fisheries; A case where randomness is of minor importance (1984)
    Springer
    Annals of operations research 1 (1984), S. 79-83 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; stochastic analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Linear programming is applied to assess the optimal capacity of the Norwegian industrial fishing fleet when quotas are random. A great potential for profit is identified and the significance of resource uncertainty for practical management is de-emphasized.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01874454
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 58
    Electronic Resource
    Electronic Resource
    A strictly improving linear programming Phase I algorithm (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 409-430 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; Phase I ; nonlinear programming ; least squares ; quadratic programming ; strict improvement ; degeneracy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Instead of trying to recognize and avoid degenerate steps in the simplex method (as some variants do), we have developed a new Phase I algorithm that is impervious to degeneracy. The new algorithm solves a non-negative least-squares problem in order to find a Phase I solution. In each iteration, a simple two-variable least-squares subproblem is used to select an incoming column to augment a set of independent columns (called “basic”) to get a strictly better fit to the right-hand side. Although this is analogous in many ways to the simplex method, it can be proved that strict improvement is attained at each iteration, even in the presence of degeneracy. Thus cycling cannot occur, and convergence is guaranteed. This algorithm is closely related to a number of existing algorithms proposed for non-negative least-squares and quadratic programs. When used on the 30 smallest NETLIB linear programming test problems, the computational results for the new Phase I algorithm were almost 3.5 times faster than a particular implementation of the simplex method; on some problems, it was over 10 times faster. Best results were generally seen on the more degenerate problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023107
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 59
    Electronic Resource
    Electronic Resource
    A simplified homogeneous and self-dual linear programming algorithm and its implementation (1996)
    Springer
    Annals of operations research 62 (1996), S. 151-171 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; homogeneous and self-dual linear feasibility model ; predictor-corrector algorithm ; implementation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We present a simplification and generalization of the recent homogeneous and self-dual linear programming (LP) algorithm. The algorithm does not use any Big-M initial point and achieves $$O(\sqrt {nL} )$$ -iteration complexity, wheren andL are the number of variables and the length of data of the LP problem. It also detects LP infeasibility based on a provable criterion. Its preliminary implementation with a simple predictor and corrector technique results in an efficient computer code in practice. In contrast to other interior-point methods, our code solves NETLIB problems, feasible or infeasible, starting simply fromx=e (primal variables),y=0 (dual variables),z=e (dual slack variables), wheree is the vector of all ones. We describe our computational experience in solving these problems, and compare our results with OB1.60, a state-of-the-art implementation of interior-point algorithms.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206815
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 60
    Electronic Resource
    Electronic Resource
    A New ADI Scheme for Solving Three-Dimensional Parabolic Equations with First-Order Derivatives and Variable Coefficients (2000)
    Springer
    Journal of computational analysis and applications 2 (2000), S. 293-308 
    Details
    ISSN: 1572-9206
    Keywords: parabolic equations ; ADI scheme ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An ADI scheme for solving three-dimensional parabolic equations withfirst-order derivatives and variable coefficients has been developed basedon our previous papers and the idea of the modified upwind differencescheme. This ADI scheme is second-order accurate and unconditionallystable. Further, a small parameter can be chosen which makes it suitablefor simulating fast-transient phenomena or for computations on fine spatialmeshes. The method is illustrated with numerical examples.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1010108620966
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 61
    Electronic Resource
    Electronic Resource
    Stability characteristics of transition layer solutions (1993)
    Springer
    Journal of dynamics and differential equations 5 (1993), S. 625-671 
    Details
    ISSN: 1572-9222
    Keywords: Scalar reaction-diffusion equation ; singular perturbation methods ; internal layer ; Neumann layer ; stability ; 35K57 ; 35B25 ; 35B35
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The multiple existences and their stability properties of stationary solutions with a single transition layer in some scalar reaction-diffusion equation are shown. Each solution is constructed by using classical singular perturbation methods and its stability property is determined by a simple algebraic quantity, say index, appearing in the construction of a solution.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01049142
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 62
    Electronic Resource
    Electronic Resource
    Symmetrization properties of parabolic equations in symmetric domains (1994)
    Springer
    Journal of dynamics and differential equations 6 (1994), S. 639-658 
    Details
    ISSN: 1572-9222
    Keywords: Symmetry ; parabolic equations ; positive solutions ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Symmetry properties of positive solutions of a Dirichlet problem for a strongly nonlinear parabolic partial differential equation in a symmetric domainD ⊂ R n are considered. It is assumed that the domainD and the equation are invariant with respect to a group {Q} of transformations ofD. In examples {Q} consists of reflections or rotations. The main result of the paper is the theorem which states that any compact inC(D) negatively invariant set which consists of positive functions consists ofQ-symmetric functions. Examples of negatively invariant sets are (in autonomous case) equilibrium points, omega-limit sets, alpha-limit sets, unstable sets of invariant sets, and global attractors. Application of the main theorem to equilibrium points gives the Gidas-Ni-Nirenberg theorem. Applying the theorem to omega-limit sets, we obtain the asymptotical symmetrization property. That means that a bounded solutionu(t) asr→∞ approaches subspace of symmetric functions. One more result concerns properties of eigenfunctions of linearizations of the equations at positive equilibrium points. It is proved that all unstable eigenfunctions are symmetric.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02218852
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 63
    Electronic Resource
    Electronic Resource
    Stability-Like Properties of Differential Inclusions (1997)
    Springer
    Set-valued analysis 5 (1997), S. 73-88 
    Details
    ISSN: 1572-932X
    Keywords: differential inclusion ; invariance ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The properties of invariance, stability, asymptotic stability and attainability of a given compact set $$K \subset \mathbb{R}^n $$ with respect to a differential inclusion, have weak and strong versions: the weak version requires existence of a trajectory with the corresponding property, while the strong one requires this property for all trajectories. The following statement is proven in the paper (under slight restrictions) for each of the above-mentioned properties: if K has the weak property with respect to $$\dot x \in F(x) $$ , then there is a (regulation) mapping G such that G(x) ⊂ F(x) ∀ x and G has the strong property with respect to $${\dot x}$$ ε G(x). In addition, certain regularity of the set of solutions of the last inclusion is claimed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008683223676
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 64
    Electronic Resource
    Electronic Resource
    Planning under uncertainty using parallel computing (1988)
    Springer
    Annals of operations research 14 (1988), S. 1-16 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; planning under uncertainty ; large-scale systems ; parallel processors ; stochastic programming ; decomposition principle
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Industry and government routinely solve deterministic mathematical programs for planning and schelduling purposes, some involving thousands of variables with a linear or non-linear objective and inequality constraints. The solutions obtained are often ignored because they do not properly hedge against future contingencies. It is relatively easy to reformulate models to include uncertainty. The bottleneck has been (and is) our capability to solve them. The time is now ripe for finding a way to do so. To this end, we describe in this paper how large-scale system methods for solving multi-staged systems, such as Bender's Decomposition, high-speed sampling or Monte Carlo simulation, and parallel processors can be combined to solve some important planning problems involving uncertainty. For example, parallel processors may make it possible to come to better grips with the fundamental problems of planning, scheduling, design, and control of complex systems such as the economy, an industrial enterprise, an energy system, a water-resource system, military models for planning-and-control, decisions about investment, innovation, employment, and health-delivery systems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02186471
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 65
    Electronic Resource
    Electronic Resource
    Optimization and Stability Results Through Cone Lower Semicontinuity (1997)
    Springer
    Set-valued analysis 5 (1997), S. 365-375 
    Details
    ISSN: 1572-932X
    Keywords: set-valued mappings ; vector optimization ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We establish optimization results for set-valued mappings, with the image space given by a topological vector space partially ordered by a cone. Moreover, we obtain stability results relative to parametrized optimization problems. We use a weak semicontinuity concept related to the order structure of the image space and show how compactness assumptions used in previous papers can be lightened.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008653120360
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 66
    Electronic Resource
    Electronic Resource
    Bifurcations in parametric nonlinear programming (1990)
    Springer
    Annals of operations research 27 (1990), S. 343-369 
    Details
    ISSN: 1572-9338
    Keywords: Bifurcation ; singularities ; continuation ; parametric nonlinear programming ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Bifurcation and continuation techniques are introduced as a class of methods for investigating the parametric nonlinear programming problem. Motivated by the Fritz John first-order necessary conditions, the parametric programming problem is first reformulated as a closed system of nonlinear equations which contains all Karush-Kuhn-Tucker and Fritz John points, both feasible and infeasible solutions, and relative minima, maxima, and saddle points. Since changes in the structure of the solution set and critical point type can occur only at singularities, necessary and sufficient conditions for the existence of a singularity are developed in terms of the loss of a complementarity condition, the linear dependence constraint qualification, and the singularity of the Hessian of the Lagrangian on a tangent space. After a brief introduction to elementary bifurcation theory, some simple singularities in this parametric problem are analyzed for both branching and persistence of local minima. Finally, a brief introduction to numerical continuation and bifurcation procedures is given to indicate how these facts can be used in a numerical investigation of the problem.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02055201
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 67
    Electronic Resource
    Electronic Resource
    Modifying the forrest-tomlin and saunders updates for linear programming problems with variable upper bounds (1986)
    Springer
    Annals of operations research 5 (1986), S. 501-515 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; variable upper bounds ; rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The author previously described a modification of the simplex method to handle variable upper bounds implicitly. This method can easily be used when the representation of the basis inverse (e.g. a triangular decomposition of the basis) is maintained as a dense matrix in core, but appears to cause difficulties for large problems where secondary storage and packed matrices may be employed. Here we show how the Forrest-Tomlin and Saunders updating schemes, which are designed for such large problems, can be adapted.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02022088
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 68
    Electronic Resource
    Electronic Resource
    Stability in multistage stochastic programming (1995)
    Springer
    Annals of operations research 56 (1995), S. 79-93 
    Details
    ISSN: 1572-9338
    Keywords: Multistage stochastic programs ; optimization in Banach spaces ; stability ; approximation
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Multistage stochastic programs are regarded as mathematical programs in a Banach spaceX of summable functions. Relying on a result for parametric programs in Banach spaces, the paper presents conditions under which linearly constrained convex multistage problems behave stably when the (input) data process is subjected to (small) perturbations. In particular, we show the persistence of optimal solutions, the local Lipschitz continuity of the optimal value and the upper semicontinuity of optimal sets with respect to the weak topology inX. The linear case with deterministic first-stage decisions is studied in more detail.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02031701
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 69
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 70
    Electronic Resource
    Electronic Resource
    A relaxed primal-dual path-following algorithm for linear programming (1996)
    Springer
    Annals of operations research 62 (1996), S. 173-196 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; primal-dual method ; interior path-following algorithm ; relaxation method
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we provide an easily satisfied relaxation condition for the primaldual interior path-following algorithm to solve linear programming problems. It is shown that the relaxed algorithm preserves the property of polynomial-time convergence. The computational results obtained by implementing two versions of the relaxed algorithm with slight modifications clearly demonstrate the potential in reducing computational efforts.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206816
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 71
    Electronic Resource
    Electronic Resource
    An affine scaling method with an infeasible starting point: Convergence analysis under nondegeneracy assumption (1996)
    Springer
    Annals of operations research 62 (1996), S. 325-355 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; infeasible-interior-point methods ; affine scaling algorithm ; global convergence analysis ; nondegeneracy assumption ; AMS(MOS) 90C05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we propose an infeasible-interior-point algorithm for linear programning based on the affine scaling algorithm by Dikin. The search direction of the algorithm is composed of two directions, one for satisfying feasibility and the other for aiming at optimality. Both directions are affine scaling directions of certain linear programming problems. Global convergence of the algorithm is proved under a reasonable nondegeneracy assumption. A summary of analogous global convergence results without any nondegeneracy assumption obtained in [17] is also given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206822
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 72
    Electronic Resource
    Electronic Resource
    Large step volumetric potential reduction algorithms for linear programming (1996)
    Springer
    Annals of operations research 62 (1996), S. 521-538 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; interior algorithm ; potential reduction ; volumetric barrier
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract We consider the construction of potential reduction algorithms using volumetric, and mixed volumetric — logarithmic, barriers. These are true “large step” methods, where dual updates produce constant-factor reductions in the primal-dual gap. Using a mixed volumetric — logarithmic barrier we obtain an $$O(\sqrt {nmL} )$$ iteration algorithm, improving on the best previously known complexity for a large step method. Our results complement those of Vaidya and Atkinson on small step volumetric, and mixed volumetric — logarithmic, barrier function algorithms. We also obtain simplified proofs of fundamental properties of the volumetric barrier, originally due to Vaidya.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206828
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 73
    Electronic Resource
    Electronic Resource
    The primal power affine scaling method (1996)
    Springer
    Annals of operations research 62 (1996), S. 375-417 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; affine scaling methods ; interior point methods ; power barrier method ; power center ; merit function ; superlinear convergence ; three-step quadratic convergence ; efficient acceleration
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we present a variant of the primal affine scaling method, which we call the primal power affine scaling method. This method is defined by choosing a realr〉0.5, and is similar to the power barrier variant of the primal-dual homotopy methods considered by den Hertog, Roos and Terlaky and Sheu and Fang. Here, we analyze the methods forr〉1. The analysis for 0.50〈r〈1 is similar, and can be readily carried out with minor modifications. Under the non-degeneracy assumption, we show that the method converges for any choice of the step size α. To analyze the convergence without the non-degeneracy assumption, we define a power center of a polytope. We use the connection of the computation of the power center by Newton's method and the steps of the method to generalize the 2/3rd result of Tsuchiya and Muramatsu. We show that with a constant step size α such that α/(1-α)2r 〉 2/(2r-1) and with a variable asymptotic step size αk uniformly bounded away from 2/(2r+1), the primal sequence converges to the relative interior of the optimal primal face, and the dual sequence converges to the power center of the optimal dual face. We also present an accelerated version of the method. We show that the two-step superlieear convergence rate of the method is 1+r/(r+1), while the three-step convergence rate is 1+ 3r/(r+2). Using the measure of Ostrowski, we note thet the three-step method forr=4 is more efficient than the two-step quadratically convergent method, which is the limit of the two-step method asr approaches infinity.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206824
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 74
    Electronic Resource
    Electronic Resource
    New complexity results for the Iri-Imai method (1996)
    Springer
    Annals of operations research 62 (1996), S. 539-564 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; Iri-Imai method ; primal-dual potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we show that the number of main iterations required by the Iri-Imai algorithm to solve a linear programming problem isO(nL). Moreover, we show that a modification of this algorithm requires only $$\mathcal{O}(\sqrt {nL} )$$ main iterations. In this modification, we measure progress by means of a primal-dual potential function.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206829
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 75
    Electronic Resource
    Electronic Resource
    The ANALYZE rulebase for supporting LP analysis (1996)
    Springer
    Annals of operations research 65 (1996), S. 91-126 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; large-scale systems ; computer-assisted analysis ; computational economics ; sensitivity analysis ; model management
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper describes how to design rules to support linear programming analysis in three functional categories: postoptimal sensitivity, debugging, and model management. The ANALYZE system is used to illustrate the behavior of the rules with a variety of examples. Postoptimal sensitivity analysis answers not only the paradigmWhat if …? question, but also the more frequently askedWhy …? question. The latter is static, asking why some solution value is what it is, or why it is not something else. The former is dynamic, asking how the solution changes if some element is changed. Debugging can mean a variety of things; here the focus is on diagnosing an infeasible instance. Model management includes documentation, verification, and validation. Rules are illustrated to provide support in each of these related functions, including some that require reasoning about the linear program's structure. Another model management function is to conduct a periodic review, with one of the goals being to simplify the model, if possible. The last illustration is how to test new rule files, where there is a variety of ways to communicate a result to someone who is not expert in linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02187328
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 76
    Electronic Resource
    Electronic Resource
    A recursive linear programming analysis of the future of the pulp and paper industry in the United States: Changes in supplies and demands, and the effects of recycling (1996)
    Springer
    Annals of operations research 68 (1996), S. 109-139 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; economic model ; pulp and paper ; recycling ; capacity ; demand and supply ; international trade
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The impacts of increased paper recycling on the U.S. pulp and paper sector are investigated, using the North American Pulp And Paper (NAPAP) model. This dynamic spatial equilibrium model forecasts the amount of pulp, paper and paperboard exchanged in a multi-region market, and the corresponding prices. The core of the model is a recursive price-endogenous linear programming system that simulates the behavior of a competitive industry. The model has been used to make forecasts of key variables describing the sector from 1986 to 2012, demand for paper would have the greatest impact on the amount of wood used. But the minimum recycled content policies envisaged currently would have no more effect than what will come about due to unregulated market forces.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02205451
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 77
    Electronic Resource
    Electronic Resource
    The Stability of Self-Organized Rule-Following Work Teams (1999)
    Springer
    Computational & mathematical organization theory 5 (1999), S. 5-30 
    Details
    ISSN: 1572-9346
    Keywords: network models ; organization theory ; rule following ; self organized ; stability ; work teams ; work routine
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Self-organized rule-following systems are increasingly relevant objects of study in organization theory due to such systems&2018; capacity to maintain control while enabling decentralization of authority. This paper proposes a network model for such systems and examines the stability of the networks&2018; repetitive behavior. The networks examined are Ashby nets, a fundamental class of binary systems: connected aggregates of nodes that individually compute an interaction rule, a binary function of their three inputs. The nodes, which we interpret as workers in a work team, have two network inputs and one self-input. All workers in a given team follow the same interaction rule. We operationalize the notion of stability of the team&2018;s work routine and determine stability under small perturbations for all possible rules these teams can follow. To study the organizational concomitants of stability, we characterize the rules by their memory, fluency, homogeneity, and autonomy. We relate these measures to work routine stability, and find that stability in ten member teams is enhanced by rules that have low memory, high homogeneity, and low autonomy.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009689326098
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 78
    Electronic Resource
    Electronic Resource
    Bifurcation Phenomena from Standing Pulse Solutions in Some Reaction-Diffusion Systems (2000)
    Springer
    Journal of dynamics and differential equations 12 (2000), S. 117-167 
    Details
    ISSN: 1572-9222
    Keywords: singular perturbation ; standing pulses ; stability ; Hopf bifurcation ; reaction-diffusion system
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Bifurcation phenomena from standing pulse solutions of the problem $$\varepsilon \tau u_t = \varepsilon ^2 u_{xx} + f(u,v),{\text{ }}v_t = v_{xx} + g(u,v)$$ is considered. ε(〉0) is a sufficiently small parameter and τ is a positive one. It is shown that there exist two types of destabilization of standing pulse solutions when τ decreases. One is the appearance of travelling pulse solutions via the static bifurcation and the other is that of in-phase breathers via the Hopf bifurcation. Furthermore which type of destabilization occurs first with decreasing τ is discussed for the piecewise linear nonlinearities f and g.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1009098719440
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 79
    Electronic Resource
    Electronic Resource
    Equivariant multiparameter bifurcation via singularity theory (1993)
    Springer
    Journal of dynamics and differential equations 5 (1993), S. 189-218 
    Details
    ISSN: 1572-9222
    Keywords: Equivariant bifurcation ; symmetry ; singularity ; equivariant jets and transversality ; normal forms ; universal unfolding ; stability ; structural stability ; 58F14 ; 58E07 ; 58C27
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The theoretical machinery from singularity theory introduced by Golubitsky, Stewart, and Schaeffer, to study equivariant bifurcation problems, is completed and expanded while generalized to the multiple parameter context. In this setting the finite determinacy theorems or normal forms, the stability of equivariant bifurcation problems, and the structural stability of the universal unfolding are discussed.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01053160
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 80
    Electronic Resource
    Electronic Resource
    A free boundary problem modeling thermal instabilities: Stability and bifurcation (1994)
    Springer
    Journal of dynamics and differential equations 6 (1994), S. 447-486 
    Details
    ISSN: 1572-9222
    Keywords: Free boundary problems ; gasless combustion ; stability ; Hopf bifurcation ; 35R35 ; 35B40 ; 80A25
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we analyze a simple free boundary model associated with solid combustion and some phase transition processes. There is strong evidence that this “one-phase” model captures all major features of dynamical behavior of more realistic (and complicated) combustion and phase transition models. The principal results concern the dynamical behavior of the model as a bifurcation parameter (which is related to the activation energy in the case of combustion) varies. We prove that the basic uniform front propagation is asymptotically stable against perturbations for the bifurcation parameter above the instability threshold and that a Hopf bifurcation takes place at the threshold value. Results of numerical simulations are presented which confirm that both supercritical and subcritical Hofp bifurcation may occur for physically reasonable nonlinear kinetic functions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02218858
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 81
    Electronic Resource
    Electronic Resource
    Discrete time semigroup transformations with random perturbations (1997)
    Springer
    Journal of dynamics and differential equations 9 (1997), S. 463-505 
    Details
    ISSN: 1572-9222
    Keywords: Difference equations ; random perturbation ; averaging ; diffusion approximation ; randomly perturbed iterations ; stability ; 3SR60 ; 60H15 ; 60J99
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Let (X, ℬ) and (Y,C) be two measurable spaces withX being a linear space. A system is determined by two functionsf(X): X→ X andϕ:X×Y→X, a (small) positive parameterε and a homogeneous Markov chain {y n } in (Y,C) which describes random perturbations. States of the system, say {x n ɛ ∈X, n=0, 1,⋯}, are determined by the iteration relations:x n+1 ɛ =f(x n ɛ )+ɛϕ(x n ɛ ,Yn+1) forn≥0, wherex 0 ɛ =x 0 is given. Here we study the asymptotic behavior of the solutionx n ɛ asε → 0 andn → ∞ under various assumptions on the data. General results are applied to some problems in epidemics, genetics and demographics.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02227491
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 82
    Electronic Resource
    Electronic Resource
    On Stability and Boundedness for Lipschitzian Differential Inclusions: The Converse of Lyapunov's Theorems (1997)
    Springer
    Set-valued analysis 5 (1997), S. 377-390 
    Details
    ISSN: 1572-932X
    Keywords: differential inclusions ; stability ; boundedness of solutions ; Lyapunov functions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract For Lipschitzian differential inclusions, we prove that the existence of suitable Lyapunov functions is necessary for uniform stability and uniform boundedness of solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008603707291
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 83
    Electronic Resource
    Electronic Resource
    Singularly perturbed differential inclusions: An averaging approach (1996)
    Springer
    Set-valued analysis 4 (1996), S. 361-374 
    Details
    ISSN: 1572-932X
    Keywords: 34A60 ; 34E15 ; 34C29 ; differential inclusion ; singular perturbation ; averaging method ; controlability ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We consider nonlinear, singularly perturbed differential inclusions and apply the averaging method in order to construct a limit differential inclusion for slow motion. The main approximation result states that the existence and regularity of the limit differential inclusion suffice to describe the limit behavior of the slow motion. We give explicit approximation rates for the uniform convergence on compact time intervals. The approach works under controllability or stability properties of fast motion.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF00436111
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 84
    Electronic Resource
    Electronic Resource
    Implicit Multifunction Theorems (1999)
    Springer
    Set-valued analysis 7 (1999), S. 209-238 
    Details
    ISSN: 1572-932X
    Keywords: nonsmooth analysis ; subdifferentials ; coderivatives ; implicit function theorem ; solvability ; stability ; open mapping theorem ; metric regularity ; multidirectional mean value inequality
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We prove a general implicit function theorem for multifunctions with a metric estimate on the implicit multifunction and a characterization of its coderivative. Traditional open covering theorems, stability results, and sufficient conditions for a multifunction to be metrically regular or pseudo-Lipschitzian can be deduced from this implicit function theorem. We prove this implicit multifunction theorem by reducing it to an implicit function/solvability theorem for functions. This approach can also be used to prove the Robinson–Ursescu open mapping theorem. As a tool for this alternative proof of the Robinson–Ursescu theorem, we also establish a refined version of the multidirectional mean value inequality which is of independent interest.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008775413250
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 85
    Electronic Resource
    Electronic Resource
    Perturbed unstable variational inequalities with unbounded operators on approximately given sets (1993)
    Springer
    Set-valued analysis 1 (1993), S. 393-402 
    Details
    ISSN: 1572-932X
    Keywords: Primary: 49J40, 65K10, 47A55, 47H05, 65L20 ; Variational inequality ; perturbation ; unbounded and nonsmooth operators ; convex sets ; Hausdorff distance ; regularization ; monotonicity ; convergence ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The stability and convergence of the solutions of perturbed and regularized variational inequality to the solutions of the primary (unstable a priori) variational inequality with proper monotone operator are investigated. All the objects of inequality: the operatorA, the right-hand partf and the set of constrains Ω are to be perturbed. At the same time no assumptions of boundedness and smoothness of the operatorA are used. The connection between the parameters of perturbations, which guarantees strong convergence of approximate solutions, is established. It is proved that the existence of the solution to the unperturbed variational inequality is necessary and sufficient condition for convergence of the regularized perturbed inequality solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01027828
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 86
    Electronic Resource
    Electronic Resource
    Degeneracy in interior point methods for linear programming: a survey (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 107-138 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; interior point methods ; degeneracy ; polynomial algorithms ; global and local convergence ; basis recovery ; numerical performance ; sensitivity analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The publication of Karmarkar's paper has resulted in intense research activity into Interior Point Methods (IPMs) for linear programming. Degeneracy is present in most real-life problems and has always been an important issue in linear programming, especially in the Simplex method. Degeneracy is also an important issue in IPMs. However, the difficulties are different in the two methods. In this paper, we survey the various theoretical and practical issues related to degeneracy in IPMs for linear programming. We survey results, which, for the most part, have already appeared in the literature. Roughly speaking, we shall deal with the effect of degeneracy on the following: the convergence of IPMs, the trajectories followed by the algorithms, numerical performance, and finding basic solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02096259
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 87
    Electronic Resource
    Electronic Resource
    Studies of lexicography in the generalized network simplex method (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 235-248 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; generalized networks ; simplex method ; degeneracy ; lexicography ; cycling
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper introduces an analytical approach for studying lexicography in generalized network problems. The equations obtained can help us to understand and to extend the existing theory. First, it is verified that all nonzero elements have the same sign in each row vector of a basis inverse for a generalized network (GN) problem with positive multipliers. However, this property does not necessarily hold when there exist negative multipliers. Second, we developed a strategy to select the dropping arc in the GN simplex algorithm when addressing GN problems with positive andnegative multipliers. This strategy is also based on lexicography and requires performing some comparisons. However, the values to be compared are already known since they can be obtained as a by-product of the calculations necessary to compute the basis representation of the entering arc. Consequently, the computational effort per pivot step isO(n) in the worst case. This worst case effort is the same as that required by the strongly convergent rules for selecting the dropping arc in the method of strong convergence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023097
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 88
    Electronic Resource
    Electronic Resource
    A simple proof of a primal affine scaling method (1996)
    Springer
    Annals of operations research 62 (1996), S. 303-324 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; affine scaling methods ; interior point methods
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract In this paper, we present a simpler proof of the result of Tsuchiya and Muramatsu on the convergence of the primal affine scaling method. We show that the primal sequence generated by the method converges to the interior of the optimum face and the dual sequence to the analytic center of the optimal dual face, when the step size implemented in the procedure is bounded by 2/3. We also prove the optimality of the limit of the primal sequence for a slightly larger step size of 2q/(3q−1), whereq is the number of zero variables in the limit. We show this by proving the dual feasibility of a cluster point of the dual sequence.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206821
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 89
    Electronic Resource
    Electronic Resource
    Consumer memory and price fluctuations in commodity markets: An integrodifferential model (1989)
    Springer
    Journal of dynamics and differential equations 1 (1989), S. 299-325 
    Details
    ISSN: 1572-9222
    Keywords: Commodity markets ; time delays ; stability ; Hopf bifurcation ; 34K15 ; 45J05 ; 90A16
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A model for the dynamics of price adjustment in a single commodity market is developed. Nonlinearities in both supply and demand functions are considered explicitly, as are delays due to production lags and storage policies, to yield a nonlinear integrodifferential equation. Conditions for the local stability of the equilibrium price are derived in terms of the elasticities of supply and demand, the supply and demand relaxation times, and the equilibrium production-storage delay. The destabilizing effect of consumer memory on the equilibrium price is analyzed, and the ensuing Hopf bifurcations are described.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01053930
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 90
    Electronic Resource
    Electronic Resource
    Stable steady state of some population models (1992)
    Springer
    Journal of dynamics and differential equations 4 (1992), S. 161-190 
    Details
    ISSN: 1572-9222
    Keywords: Delay differential equations ; equilibrium ; stability ; limiting equations ; population dynamics ; 34K20 ; 34K25 ; 92A15
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Applying an analytical method and several limiting equations arguments, some sufficient conditions are provided for the existence of a unique positive equilibriumK for the delay differential equationx=−γx+D(x t ), which is the general form of many population models. The results are concerned with the global attractivity, uniform stability, and uniform asymptotic stability ofK. Application of the results to some known population models, which shows the effectiveness of the methods applied here, is also presented.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01048159
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 91
    Electronic Resource
    Electronic Resource
    The relative variance criterion for stability of delay systems (1993)
    Springer
    Journal of dynamics and differential equations 5 (1993), S. 105-128 
    Details
    ISSN: 1572-9222
    Keywords: Delay system ; stability ; relative variance ; dynamical disease
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A new approach to the study of delay systems, applicable to physiological control systems and other systems where little information about the time delays is available, is examined. The method is based on the fact that stability information can be deduced from the statistical properties of the probability distribution that encodes the structure of the time delay. The main statistical variables used are the usual expectation parameter,E, and a modified variance, calledrelative variance and denotedR, that is invariant under time scale changes. Recent work of the author has shown that stability often improves asR increases whileE remains fixed. A four-parameter family of delay models is analysed in this paper, and the (E, R) pair is found to be a reliable indicator of stability over the global parameter domain of the family.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF01063737
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 92
    Electronic Resource
    Electronic Resource
    Stability of standing waves for the generalized Davey-Stewartson system (1994)
    Springer
    Journal of dynamics and differential equations 6 (1994), S. 325-334 
    Details
    ISSN: 1572-9222
    Keywords: Nonlinear Schrödinger equations ; anisotropic standing waves ; stability ; concentration compactness principle ; Davey-Stewartson system ; 35Q35 ; 35B35
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We study the stability of standing waves for a nonlinear Schrödinger equation, which derives from the generalized Davey-Stewartson system in the elliptic-elliptic case. We prove the existence of stable standing waves under certain conditions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02218533
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 93
    Electronic Resource
    Electronic Resource
    The index of lyapunov stable fixed points in two dimensions (1994)
    Springer
    Journal of dynamics and differential equations 6 (1994), S. 631-637 
    Details
    ISSN: 1572-9222
    Keywords: stability ; fixed point index ; periodic solutions
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we prove that a stable isolated fixed point of an orientation preserving local homeomorphism onR 2 has fixed point index 1. We also give a number of applications to differential equations. In particular, we deduce that a number of existence methods for producing periodic solutions of differential equations in the plane always produce unstable solutions.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02218851
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 94
    Electronic Resource
    Electronic Resource
    Stability of Linear Inequality Systems Measured by the Hausdorff Metric (2000)
    Springer
    Set-valued analysis 8 (2000), S. 253-266 
    Details
    ISSN: 1572-932X
    Keywords: Hausdorff metric ; linear inequality systems ; stability
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract In this paper, we propose a Hausdorff metric to measure the “distance” between two linear inequality systems on a real normed space X. For this topology, which comes through a pseudo-metric in the set Σ of linear inequality systems, the closedness of the feasible set mapping is studied, and at the same time a characterization of the stability of the subset Σ c of consistent sytems is given.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1008701026782
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 95
    Electronic Resource
    Electronic Resource
    MODLER: Modeling by object-driven linear elemental relations (1992)
    Springer
    Annals of operations research 38 (1992), S. 239-280 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; large-scale systems ; modeling ; language design
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper describes a system to represent linear programming models and their instances. In addition to a modeling language, MODLER has an extensive query capability which includes a multi-view architecture. Further, randomization options provide rapid prototyping. The MODLER system is part of a workbench for building and managing decision support systems that are based on linear programming.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02283655
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 96
    Electronic Resource
    Electronic Resource
    Advanced basis construction in linear programming (1986)
    Springer
    Annals of operations research 5 (1986), S. 413-424 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; basis construction ; matrix rearrangement
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract This paper considers basis construction in a linear program when the number of activities with basic status is not equal to the number of rows in the particular scenario. This arises when starting with an ‘advanced basis’, obtained from a solution to another scenario. The goal here is to provide a triangular-seeking algorithm that takes advantage of structural properties during the construction of a basis agenda. For completeness, some facts, which are known but have not been published, are given about choosing an advanced basis and about spikes.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02022083
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 97
    Electronic Resource
    Electronic Resource
    Pivot rules for linear programming: A survey on recent theoretical developments (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 203-233 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; simplex method ; pivot rules ; cycling ; recursion ; minimal index rule ; parametric programming
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The purpose of this paper is to discuss the various pivot rules of the simplex method and its variants that have been developed in the last two decades, starting from the appearance of the minimal index rule of Bland. We are mainly concerned with finiteness properties of simplex type pivot rules. Well known classical results concerning the simplex method are not considered in this survey, but the connection between the new pivot methods and the classical ones, if there is any, is discussed. In this paper we discuss three classes of recently developed pivot rules for linear programming. The first and largest class is the class of essentially combinatorial pivot rules including minimal index type rules and recursive rules. These rules only use labeling and signs of the variables. The second class contains those pivot rules which can actually be considered as variants or generalizations or specializations of Lemke's method, and so they are closely related to parametric programming. The last class has the common feature that the rules all have close connections to certain interior point methods. Finally, we mention some open problems for future research.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02096264
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 98
    Electronic Resource
    Electronic Resource
    A practical anti-degeneracy row selection technique in network linear programming (1993)
    Springer
    Annals of operations research 46-47 (1993), S. 431-442 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; degeneracy ; network simplex algorithm ; pivoting ; minimal cost network flow
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract A characteristic feature of the primal network simplex algorithm (NSA) is that it usually makes a large number of degenerate iterations. Though cycling and even stalling can be avoided by recently introduced pivot rules for NSA, the practical efficiency of these rules is not known yet. For the case when the simplex algorithm is used to solve the continuous linear programming (LP) problem there exists a practical anti-cycling procedure that proved to be efficient. It is based on an expanding relaxation of the individual bound on the variables. In this paper we discuss the adaptation of this method to NSA, taking advantage of the special integer nature of network problems. We also give an account of our experience with these ideas as they are experimentally implemented in the MINET network LP solver. Reductions of CPU time have been achieved on a smaller set of specially structured real-life problems.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02023108
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 99
    Electronic Resource
    Electronic Resource
    A lower bound on the number of iterations of long-step primal-dual linear programming algorithms (1996)
    Springer
    Annals of operations research 62 (1996), S. 233-252 
    Details
    ISSN: 1572-9338
    Keywords: Linear programming ; primal-dual interior-point algorithms ; lower bounds
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract Recently, Todd has analyzed in detail the primal-dual affine-scaling method for linear programming, which is close to what is implemented in practice, and proved that it may take at leastn 1/3 iterations to improve the initial duality gap by a constant factor. He also showed that this lower bound holds for some polynomial variants of primal-dual interior-point methods, which restrict all iterates to certain neighborhoods of the central path. In this paper, we further extend his result to long-step primal-dual variants that restrict the iterates to a wider neighborhood. This neigh-borhood seems the least restrictive one to guarantee polynomiality for primal-dual path-following methods, and the variants are also even closer to what is implemented in practice.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1007/BF02206818
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
    Paper (German National Licenses)
    Fulltext
  • 100
    Electronic Resource
    Electronic Resource
    Stability Properties of a Bond Portfolio Management Problem (2000)
    Springer
    Annals of operations research 99 (2000), S. 251-265 
    Details
    ISSN: 1572-9338
    Keywords: stochastic programming ; bond portfolio management ; interest ratescenarios ; stability ; sensitivity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics , Economics
    Notes: Abstract The bond portfolio management problem is formulated as a multiperiod two-stage or multistage stochastic program based on interest rate scenarios. These scenarios depend on the available market data, on the applied estimation and sampling techniques, etc., and are used to evaluate coefficients of the resulting large scale mathematical program. The aim of the contribution is to analyze stability and sensitivity of this program on small changes of the coefficients – the (scenario dependent) values of future interest rates and prices. We shall prove that under sensible assumptions, the scenario subproblems are stable linear programs and that also the optimal first-stage decisions and the optimal value of the considered stochastic program possess acceptable continuity properties.
    Type of Medium: Electronic Resource
    URL: http://dx.doi.org/10.1023/A:1019275817688
    Location Call Number Expected 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...