ALBERT

All Library Books, journals and Electronic Records Telegrafenberg

Your email was sent successfully. Check your inbox.

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

Proceed reservation?

Export
Filter
  • Articles  (44)
  • 41A15  (23)
  • Linear programming  (21)
  • Springer  (44)
  • American Chemical Society
  • American Institute of Physics (AIP)
  • Blackwell Publishing Ltd
  • Cambridge University Press
  • 2020-2024
  • 1990-1994  (37)
  • 1985-1989  (7)
  • 1975-1979
  • 1965-1969
  • 1940-1944
  • 1930-1934
  • 2020
  • 1993  (37)
  • 1985  (7)
  • 1933
  • Mathematics  (43)
  • Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition  (1)
  • Education
  • Geography
  • Energy, Environment Protection, Nuclear Power Engineering
Collection
  • Articles  (44)
Keywords
Publisher
  • Springer  (44)
  • American Chemical Society
  • American Institute of Physics (AIP)
  • Blackwell Publishing Ltd
  • Cambridge University Press
Years
  • 2020-2024
  • 1990-1994  (37)
  • 1985-1989  (7)
  • 1975-1979
  • 1965-1969
  • +
Year
Topic
  • 1
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 58 (1993), S. 243-255 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 2
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 133-150 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 3
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 151-162 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 4
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 413-420 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 5
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 517-535 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 6
    Electronic Resource
    Electronic Resource
    Springer
    European journal of nutrition 32 (1993), S. 79-92 
    ISSN: 1436-6215
    Keywords: Lineare Programmierung ; Ernährungsoptimierung ; Privathaushalt ; Optimierungsmodelle ; Linear programming ; nutrition optimization ; private households ; optimization models
    Source: Springer Online Journal Archives 1860-2000
    Topics: Agriculture, Forestry, Horticulture, Fishery, Domestic Science, Nutrition , Medicine
    Description / Table of Contents: Summary Members of private households have different nutrient requirements. In general, they eat the same dishes in different quantities. The menu plan is admissible if it corresponds to the recommended dietary allowances. It is acceptable if it meets the eating habits. It is optimal if it meets the constraints mentioned and best reaches an objective. It is the aim of this paper to describe models for the determination of optimal nutrition and to evaluate them with respect to their suitability for solving decision problems in private, multi-person-households. The fewer the model-intern restrictions in the variability of quantities of food stuffs, kind and/or quantities of dishes, the better are the “optimal” solutions that are found with the model. A simultaneous determination of kind and quantity of dishes reaches the model purpose better than a stepwise determination. This is shown in an example problem.
    Notes: Zusammenfassung In privaten Haushalten haben die Mitglieder unterschiedliche Nährstoffbedarfe. Sie verzehren im allgemeinen gleiche Speisen in unterschiedlichen Mengen. Der Speisenplan ist bedarfsgerecht, wenn er den Empfehlungen für die Nährstoffzufuhr der einzelnen Personen entspricht. Er ist akzeptabel, wenn er den Verzehrgewohnheiten der Personen entspricht. Er ist optimal, wenn er die genannten Bedingungen einhält und zusätzlich ein gegebenes Ziel bestmöglich erreicht. Die Bestimmung eines optimalen Speisenplans erfolgt anhand von Modellen. Es ist das Ziel des Beitrags, verschiedene Modelle zur Bestimmung einer optimalen Ernährung darzustellen und im Hinblick auf ihre Eignung zur Anwendung auf Entscheidungsprobleme im privaten Mehrpersonenhaushalt zu beurteilen. Je geringer die modellinterne Einschränkung in der Variabilität von Lebensmittelmengen, Speisenarten und/oder Speisenmengen, desto bessere ‚optimale‘ Lösungen können mit dem Modell gefunden werden. Eine simultane Bestimmung von Speisenart und -menge erfüllt den Modellzweck besser als eine sukzessive Bestimmung. Dies konnte anhand eines Beispielproblems gezeigt werden.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 7
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 23-31 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 8
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 409-430 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 9
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 107-138 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 10
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 235-248 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 11
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 203-233 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 12
    Electronic Resource
    Electronic Resource
    Springer
    Annals of operations research 46-47 (1993), S. 431-442 
    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
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 13
    Electronic Resource
    Electronic Resource
    Springer
    BIT 33 (1993), S. 512-528 
    ISSN: 1572-9125
    Keywords: 65D10 ; 65D07 ; 41A15 ; 41A29 ; Data fitting ; smoothing ; shape preservation ; constrained least squares approximation ; polynomial splines ; B-splines
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract An efficient algorithm for computing a smoothing polynomial splines under inequality constraints on derivatives is introduced where both order and breakpoints ofs can be prescribed arbitrarily. By using the B-spline representation ofs, the original semi-infinite constraints are replaced by stronger finite ones, leading to a least squares problem with linear inequality constraints. Then these constraints are transformed into simple box constraints by an appropriate substitution of variables so that efficient standard techniques for solving such problems can be applied. Moreover, the smoothing term commonly used is replaced by a cheaply computable approximation. All matrix transformations are realized by numerically stable Givens rotations, and the band structure of the problem is exploited as far as possible.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 14
    Electronic Resource
    Electronic Resource
    Springer
    Advances in computational mathematics 1 (1993), S. 1-37 
    ISSN: 1572-9044
    Keywords: Refinement equations ; up-function ; entire functions of exponential type ; subdivision algorithms ; cube spline ; (AMS) 34K99 ; 41A15 ; 41A25 ; 41A63
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract This paper is concerned with the study of a general class of functional equations covering as special cases the relation which defines theup-function as well as equations which arise in multiresolution analysis for wavelet construction. We discuss various basic properties of solutions to these functional equations such as regularity, polynomial containment within the space spanned by their integer shifts and their computability by subdivision algorithms.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 15
    Electronic Resource
    Electronic Resource
    Springer
    Numerische Mathematik 66 (1993), S. 123-137 
    ISSN: 0945-3245
    Keywords: 41A55 ; 41A15 ; 41A05 ; 65D32 ; 65D30 ; 65D07 ; 65D05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The Gregory rule is a well-known example in numerical quadrature of a trapezoidal rule with endpoint corrections of a given order. In the literature, the methods of constructing the Gregory rule have, in contrast to Newton-Cotes quadrature,not been based on the integration of an interpolant. In this paper, after first characterizing an even-order Gregory interpolant by means of a generalized Lagrange interpolation operator, we proceed to explicitly construct such an interpolant by employing results from nodal spline interpolation, as established in recent work by the author and C.H. Rohwer. Nonoptimal order error estimates for the Gregory rule of even order are then easily obtained.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 16
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 59 (1993), S. 345-360 
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point method ; active set strategy
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We will present a potential reduction method for linear programming where only the constraints with relatively small dual slacks—termed “active constraints”—will be taken into account to form the ellipsoid constraint at each iteration of the process. The algorithm converges to the optimal feasible solution in O( $$\sqrt n $$ L) iterations with the same polynomial bound as in the full constraints case, wheren is the number of variables andL is the data length. If a small portion of the constraints is active near the optimal solution, the computational cost to find the next direction of movement in one iteration may be considerably reduced by the proposed strategy.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 17
    ISSN: 1436-4646
    Keywords: Linear programming ; quadratic programming ; convex programming ; randomized algorithms ; fixed dimension optimization problems ; complexity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We extend Clarkson's randomized algorithm for linear programming to a general scheme for solving convex optimization problems. The scheme can be used to speed up existing algorithms on problems which have many more constraints than variables. In particular, we give a randomized algorithm for solving convex quadratic and linear programs, which uses that scheme together with a variant of Karmarkar's interior point method. For problems withn constraints,d variables, and input lengthL, ifn = Ω(d 2), the expected total number of major Karmarkar's iterations is O(d 2(logn)L), compared to the best known deterministic bound of O( $$\sqrt n$$ L). We also present several other results which follow from the general scheme.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 18
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 41-67 
    ISSN: 1436-4646
    Keywords: Linear programming ; Dantzig—Wolfe decomposition ; large-scale systems ; parallel processing ; hypercube architecture
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Decomposition algorithms for block-angular linear programs give rise to a natural, coarse-grained parallelism that can be exploited by processing the subproblems concurrently within a distributed-memory environment. The parallel efficiency of the distributed approach, however, is critically dependent on the duration of the inherently serial master phase relative to that of the bottleneck subproblem. This paper investigates strategies for improving efficiency in distributed Dantzig—Wolfe decomposition by better balancing the load between the master and subproblem processors. We report computational experience on an Intel iPSC/2 hypercube multiprocessor with test problems having dimensions up to about 30 000 rows, 87 000 columns, and 200 coupling constraints.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 19
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 15-39 
    ISSN: 1436-4646
    Keywords: Linear programming ; interior-point methods ; symmetric indefinite systems
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We describe an implementation of a primal—dual path following method for linear programming that solves symmetric indefinite “augmented” systems directly by Bunch—Parlett factorization, rather than reducing these systems to the positive definite “normal equations” that are solved by Cholesky factorization in many existing implementations. The augmented system approach is seen to avoid difficulties of numerical instability and inefficiency associated with free variables and with dense columns in the normal equations approach. Solving the indefinite systems does incur an extra overhead, whose median is about 40% in our tests; but the augmented system approach proves to be faster for a minority of cases in which the normal equations have relatively dense Cholesky factors. A detailed analysis shows that the augmented system factorization is reliable over a fairly large range of the parameter settings that control the tradeoff between sparsity and numerical stability.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 20
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 119-131 
    ISSN: 1436-4646
    Keywords: Linear programming ; interior point algorithm ; complexity ; potential function
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We propose a potential-reduction algorithm which always uses the primal—dual affine-scaling direction as a search direction. We choose a step size at each iteration of the algorithm such that the potential function does not increase, so that we can take a longer step size than the minimizing point of the potential function. We show that the algorithm is polynomial-time bounded. We also propose a low-complexity algorithm, in which the centering direction is used whenever an iterate is far from the path of centers.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 21
    Electronic Resource
    Electronic Resource
    Springer
    Mathematical programming 62 (1993), S. 497-515 
    ISSN: 1436-4646
    Keywords: Linear programming ; primal—dual methods ; optimal face ; strict complementarity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We study the problem of finding a point in the relative interior of the optimal face of a linear program. We prove that in the worst case such a point can be obtained in O(n 3 L) arithmetic operations. This complexity is the same as the complexity for solving a linear program. We also show how to find such a point in practice. We report and discuss computational results obtained for the linear programming problems in the NETLIB test set.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 22
    Electronic Resource
    Electronic Resource
    Springer
    Algorithmica 9 (1993), S. 64-83 
    ISSN: 1432-0541
    Keywords: Linear programming ; Interior-point methods ; Projective methods ; Combined phase 1-phase 2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We compare the projective methods for linear programming due to de Ghellinck and Vial, Anstreicher, Todd, and Fraley. These algorithms have the feature that they approach feasibility and optimality simultaneously, rather than requiring an initial feasible point. We compare the directions used in these methods and the lower-bound updates employed. In many cases the directions coincide and two of the lower-bound updates give the same result. It appears that Todd's direction and Fraley's lower-bound update have slight advantages, and this is borne out in limited computational testing.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 23
    ISSN: 1432-0541
    Keywords: Linear programming ; Karmarkar's algorithm ; Potential function ; Primal-dual, Modified method ; Rank-one updates
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We consider partial updating in Kojima, Mizuno, and Yoshise's primal-dual potential reduction algorithm for linear programming. We use a simple safeguard condition to control the number of updates incurred on combined primal-dual steps. Our analysis allows for unequal steplengths in the primal and dual variables, which appears to be a computationally significant factor for primal-dual methods. The safeguard we use is a primal-dual Goldstein-Armijo condition, modified to deal with the unequal primal and dual steplengths.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 24
    Electronic Resource
    Electronic Resource
    Springer
    Numerische Mathematik 65 (1993), S. 63-75 
    ISSN: 0945-3245
    Keywords: 41A15 ; 65DO5 ; 65D15
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary We give a complete characterization of the Hermite interpolation problem by periodic splines with Birkhoff knots. As a dual result we derive the characterization of the Birkhoff interpolation by periodic splines with multiple knots.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 25
    Electronic Resource
    Electronic Resource
    Springer
    Numerische Mathematik 66 (1993), S. 281-294 
    ISSN: 0945-3245
    Keywords: 41A15 ; 60F15
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary The purpose of this paper is to study the convergence of smoothingD m -splines relative to sets of data perturbed by a random noise. Conditions of almost sure convergence and error estimates are given.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 26
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 9 (1993), S. 123-166 
    ISSN: 1432-0940
    Keywords: Primary 41A63 ; 46C99 ; Secondary 41A30 ; 41A15 ; 42B99 ; 46E20 ; Wavelets ; Multiresolution ; Shift-invariant spaces ; Box splines
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract A new approach for the construction of wavelets and prewavelets onR d from multiresolution is presented. The method uses only properties of shift-invariant spaces and orthogonal projectors fromL 2(R d ) onto these spaces, and requires neither decay nor stability of the scaling function. Furthermore, this approach allows a simple derivation of previous, as well as new, constructions of wavelets, and leads to a complete resolution of questions concerning the nature of the intersection and the union of a scale of spaces to be used in a multiresolution.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 27
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 9 (1993), S. 191-208 
    ISSN: 1432-0940
    Keywords: Primary 28C20 ; 41A15 ; 46E30 ; 60J65 ; Secondary 60E15 ; 62J10 ; Wiener measure ; Brownian motion ; Spline approximation ; Orthonormal spline system ; Franklin system ; Orlicz spaces ; Hölder classes ; Covariance ; Correlation ; Gaussian vectors
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract There are three results proved in this paper. The first one characterizes the Hölder classes in Orlicz spaces by the coefficients of the orthogonal spline expansions of the Franklin type. The second one gives a sharp estimate for the correlation of two random variables obtained as a composition of two Borel functions with the components of a given two-dimensional Gaussian vector. The third one is obtained with the help of the first two and it states that the Wiener measure is concentrated on the Banach space of Hölder functions with exponent 1/2 but in the norm of the Orlicz spaceL M * withM(t)=expt(t 2)−1.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 28
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 9 (1993), S. 209-236 
    ISSN: 1432-0940
    Keywords: Primary 41A63 ; 46C99 ; Secondary 41A30 ; 41A15 ; 42B99 ; 46E20 ; Courant interpolating function ; Linear splines ; Hexagonal filter banks ; Biorthogonal wavelets ; multiresolution analysis
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We study a class of subband coding schemes allowing perfect reconstruction for a bidimensional signal sampled on the hexagonal grid. From these schemes we construct biorthogonal wavelet bases ofL 2(R 2) which are compactly supported and such that the sets of generating functionsψ 1,ψ 2,ψ 3 for the synthesis and $$\tilde \psi _1 , \tilde \psi _2 , \tilde \psi _3 ,$$ for the analysis, as well as the scaling functions φ and $$\tilde \varphi $$ , are globally invariant by a rotation of 2π/3. We focus on the particular case of linear splines and we discuss how to obtain a higher regularity. We finally present the possibilities of sharp angular frequency resolution provided by these new bases.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 29
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 9 (1993), S. 263-281 
    ISSN: 1432-0940
    Keywords: 15A23 ; 15A24 ; 39B42 ; 41A15 ; 42C15 ; 47A62 ; Splines ; Wavelets ; Matrix equations ; Hurwitz matrices ; Toeplitz matrices ; Two-slanted matrices ; Matrix factorization ; Total positivity
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Given two function spacesV 0,V 1 with compactly supported basis functionsC i, Fi, i∈Z, respectively, such thatC i can be written as a finite linear combination of theF i's, we study the problem of decomposingV 1 into a direct sum ofV 0 and some subspaceW ofV 1 in such a way thatW is spanned by compactly supported functions and that eachF i can be written as a finite linear combination of the basis functions inV 0 andW. The problem of finding such locally finite decompositions is shown to be equivalent to solving certain matrix equations involving two-slanted matrices. These relations may be reinterpreted in terms of banded matrices possessing banded inverses. Our approach to solving the matrix equations is based on factorization techniques which work under certain conditions on minors. In particular, we apply these results to univariate splines with arbitrary knot sequences.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 30
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 9 (1993), S. 373-389 
    ISSN: 1432-0940
    Keywords: 41A05 ; 41A15 ; 41A20 ; 65D05 ; 65D07 ; 65D17 ; 68U07 ; Geometric rational curve interpolation ; Shape preservation ; Convexity ; Parametric splines ; Conics ; Approximation order
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Five points in general position inR 2 always lie on a unique conic, and three points plus two tangents also have a unique interpolating conic, the type of which depends on the data. These well-known facts from projective geometry are generalized: an odd number 2n+1≥5 of points inR 2, if they can be interpolated at all by a smooth curve with nonvanishing curvature, will have a uniqueGC 2 interpolant consisting of pieces of conics of varying type. This interpolation process reproduces conics of arbitrary type and preserves strict convexity. Under weak additional assumptions its approximation order is ϑ(h 5), whereh is the maximal distance of adjacent data pointsf(t i ) sampled from a smooth and regular planar curvef with nonvanishing curvature. Two algorithms for the construction of the interpolant are suggested, and some examples are presented.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 31
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 9 (1993), S. 407-433 
    ISSN: 1432-0940
    Keywords: 41A15 ; 41A25 ; 41A30 ; Quasi-interpolation ; Thin-plate spline ; Radial basis functions ; Order of convergence
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Quasi-interpolation is one method of generating approximations from a space of translates of dilates of a single function ψ. This method has been applied widely to approximation by radial basis functions. However, such analysis has most often been performed in the setting of an infinite uniform grid of centers. In this paper we develop general error bounds for approximation by quasiinterpolation on ann-cube. The quasi-interpolant analyzed involves a finite number, growing ash −n , of translates of dilates of the function ψ, and a bounded number of edge functions. The centers of the translates of dilates of ψ form a uniformly spaced grid within the cube. These error bounds are then applied to approximation by thin-plate splines on a square. The result is an O(ω(f, [-1,1]2,h)) error bound for approximation by thin-plate splines supplemented with eight arctan functions.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 32
    Electronic Resource
    Electronic Resource
    Springer
    Numerical algorithms 5 (1993), S. 71-81 
    ISSN: 1572-9265
    Keywords: Approximation order ; multivariate splines ; polynomial splines ; 41A15 ; 65D07
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We give an algorithm which computes the approximation order of spaces of periodic piece-wise polynomial functions, given the degree, the smoothness and tesselation. The algorithm consists of two steps. The first gives an upper bound and the second a lower bound on the approximation order. In all known cases the two bounds coincide.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 33
    Electronic Resource
    Electronic Resource
    Springer
    Numerical algorithms 5 (1993), S. 591-601 
    ISSN: 1572-9265
    Keywords: Quadratic box splines in three variables ; isosurface sampling ; Boltzmann transport equation ; 41A15
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Numerical approximation has played a valuable supporting role in VLSI device simulation. Examples include (1) tensor product variation diminishing splines for models of transistor charges and currents and (2) continuation to find a safe operating region avoiding avalanche breakdown. More recently, quadratic box splines in three variables have been studied for use in Monte Carlo solution of the Boltzmann transport equation. The bivariate Zwart-Powell element does not directly generalize, but another particular box spline is constructed.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 34
    Electronic Resource
    Electronic Resource
    Springer
    Numerical algorithms 4 (1993), S. 323-337 
    ISSN: 1572-9265
    Keywords: Multivariate polynomials ; B-patch ; B-spline ; product ; tensor product ; conversion ; pyramidal algorithm ; de Casteljau algorithm ; blossom ; polar form ; 41A15 ; 65D07
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract Products and tensor products of multivariate polynomials in B-patch form are viewed as linear combinations of higher degree B-patches. Univariate B-spline segments and certain regions of simplex splines are examples of B-patches. A recursive scheme for transforming tensor product B-patch representations into B-patch representations of more variables is presented. The scheme can also be applied for transforming ann-fold product of B-patch expansions into a B-patch expansion of higher degree. Degree raising formulas are obtained as special cases. The scheme calculates the blossom of the (tensor) product surface and generalizes the pyramidal recursive scheme for B-patches.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 35
    Electronic Resource
    Electronic Resource
    Springer
    Numerical algorithms 5 (1993), S. 121-129 
    ISSN: 1572-9265
    Keywords: Surface splines ; scattered data interpolation ; incompressible fluid flow ; 41A05 ; 41A15 ; 41A29 ; 41A63 ; 65D05 ; 65D07 ; 65D25 ; 76B99 ; 76D99
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract We show how one may interpolate a vector-valued function in two or three dimensions, whose value is (wholly or partly) known at a sufficient (but not large) number of points disposed in almost any configuration, under the condition that the interpolating function has zero divergence. The technique is based on the theory of thin-plate splines. One may use a similar scheme in the case where the data consist of flux integrals (or other linear functionals) of the unknown function.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 36
    Electronic Resource
    Electronic Resource
    Springer
    Numerical algorithms 5 (1993), S. 229-245 
    ISSN: 1572-9265
    Keywords: Stable decompositions ; periodic multiresolution analysis ; pseudodifferential equations ; preconditioning ; decompositions of refinable spaces ; matrix equations ; 41A65 ; 41A15 ; 15A12 ; 15A24 ; 65N40 ; 47G05
    Source: Springer Online Journal Archives 1860-2000
    Topics: Computer Science , Mathematics
    Notes: Abstract This paper presents a brief survey of several recent applications of multilevel techniques, in particular, in connection with the solution of periodic pseudodifferential equations. It is pointed out that these applications naturally lead to certain decompositions of refinable spaces which are induced by a class of linear projectors. Then recent results on the construction of such nonorthogonal wavelets are reviewed and extended to the particular needs of the present context.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 37
    Electronic Resource
    Electronic Resource
    Springer
    Advances in computational mathematics 1 (1993), S. 109-126 
    ISSN: 1572-9044
    Keywords: Hilbert space ; commuting unitary operators ; Riesz basis ; wandering subspaces ; multiresolution approximation ; duality principle ; box splines ; 41A15 ; 42C15 ; 47B37
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Let (U=U 1, ...,U d ) be an orderedd-tuple of distinct, pairwise commuting, unitary operators on a complex Hilbert space ℋ, and letX:={x 1, ...,x r } ⊂ ℋ such that $$U^{\mathbb{Z}^d } X: = \{ U_1^{n_1 } \ldots U_d^{n_d } x_j :(n_1 , \ldots ,n_d ) \in \mathbb{Z}^d ,j = 1, \ldots ,r\} $$ is a Riesz basis of the closed linear spanV 0 of $$U^{\mathbb{Z}^d } X$$ . Suppose there is unitary operatorD on ℋ such thatV 0 ⊂D V 0 =:V 1 andU n D=DU An for alln ∈ ℤ d , whereA is ad ×d matrix with integer entries and Δ := det(A) ≠ 0. Then there is a subset Λ inV 1, withr(Δ − 1) vectors, such that $$U^{\mathbb{Z}^d } (\Gamma )$$ is a Riesz basis ofW 0, the orthogonal complement ofV 0 inV 1. The resulting multiscale and decomposition relations can be expressed in a Fourier representation by one single equation, in terms of which the duality principle follows easily. These results are a consequence of an extension, to a set of commuting unitary operators, of Robertson's Theorems on wandering subspace for a single unitary operator [24]. Conditions are given in order that $$U^{\mathbb{Z}^d } (\Gamma )$$ is a Riesz basis ofW 0. They are used in the construction of a class of linear spline wavelets on a four-direction mesh.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 38
    Electronic Resource
    Electronic Resource
    Springer
    Numerische Mathematik 47 (1985), S. 191-215 
    ISSN: 0945-3245
    Keywords: AMS(MOS): 30B70 ; 40A15 ; 41A15 ; CR: G1.2
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Summary For continued fractionsK(a n /1) the concept of limit region is discussed, and its use for obtaining modified truncation error estimates is illustrated on examples. A certain strategy for numerical computation of limit regions is presented and illustrated on examples.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 39
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 1 (1985), S. 137-154 
    ISSN: 1432-0940
    Keywords: 41A15 ; 41A5 ; 41A65 ; Perfect splines ; Monosplines ; Extended totally positive kernels ; Monotone norms ; Optimal quadrature formulas ; Optimal interpolation ; N-widths ; Optimal spaces
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Generalized monosplines of least norm are shown to exist and to determine optimal approximation processes such as numerical integration, interpolation and best approximating spaces. This extends various classical results related to monosplines and perfect splines, which are particular cases of generalized monosplines. The analysis here also provides for a unified treatment of the two classical classes of monosplines and perfect splines of least norm, and of their extremal properties.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 40
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 1 (1985), S. 305-322 
    ISSN: 1432-0940
    Keywords: 41A15 ; Box spline ; Convergence rate ; Subdivision algorithms ; Control net
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Dahmen and Micchelli [8] have shown that in general the coefficients of the refined control nets of a box spline surface converge to the surface at (at least) the rate of the refinement. The purpose of this article is to show that under mild additional assumptions the convergence rate is even quadratic. Although this rate is in general best possible, we point out under what circumstances even higher rates are obtained (locally).
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 41
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 1 (1985), S. 15-62 
    ISSN: 1432-0940
    Keywords: 41A46 ; 41A15 ; n-Widths ; Total positivity ; Eigenvalues ; Eigenfunctions ; Implicit function theorem
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract LetW p (r) ={f:f∈C r−1[0, 1],f (r−1) abs.cont., ∥f (r)∥ p 〈∞}, and setB p (r) ={f:f∈W p (r) ,∥f (r)∥ p ≤1}. We find the exact Kolmogorov, Gel'fand, linear, and Bernsteinn-widths ofB p (r) inL p for allp∈(1, ∞). For the Kolmogorovn-width we show that forn≥r there exists an optimal subspace of splines of degreer−1 withn−r fixed simple knots depending onp.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 42
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 1 (1985), S. 155-173 
    ISSN: 1432-0940
    Keywords: 41A15 ; 65D07 ; Chebyshevian B-splines ; generalized divided differences
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract The fundamental recurrence relation for polynomialB-splines is generalized to ChebyshevianB-splines.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 43
    Electronic Resource
    Electronic Resource
    Springer
    Constructive approximation 1 (1985), S. 183-193 
    ISSN: 1432-0940
    Keywords: 41A05 ; 41A15 ; 41A63 ; Bivariate ; Box-splines ; Interpolation ; Convergence ; Exponential type ; Whittaker operator
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract We give necessary and sufficient conditions for the convergence of cardinal interpolation with bivariate box splines as the degree tends to infinity.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
  • 44
    Electronic Resource
    Electronic Resource
    Springer
    Journal of optimization theory and applications 45 (1985), S. 33-39 
    ISSN: 1573-2878
    Keywords: Linear programming ; simplex method ; unrestricted variables ; simplex multipliers ; LU-factorization
    Source: Springer Online Journal Archives 1860-2000
    Topics: Mathematics
    Notes: Abstract Suppose that the simplex method is applied to a linear programming problem havingm equality constraints andr unrestricted variables. We give a method of performing the steps of the simplex method which reduces the arithmetic operation count byrm at each iteration. This savings in operations is achieved, since the method does not update the rows of the basis inverse associated with the unrestricted variables. Similar computational savings are achieved when the method is applied to the updating of anLU-factorization of the basis matrix.
    Type of Medium: Electronic Resource
    Location Call Number Expected Availability
    BibTip Others were also interested in ...
Close ⊗
This website uses cookies and the analysis tool Matomo. More information can be found here...