An error analysis for absolute and relative approximation

We consider the vectorial algorithm for finding best polynomial approximationsp P _n to a given functionf C[a, b], with respect to the norm · _s , defined byp – f _s =w ₁ (p – f)+w ₂ (p – f) A bound for the modulus of continuity of the best vectorial approximation operator is given, and using the floating point calculus of J. H. Wilkinson, a bound for the rounding error in the algorithm is derived. For givenf, these estimates provide an indication of the conditioning of the problem, an estimate of the obtainable accuracy, and a practical method for terminating the iteration.This paper was supported in part by the Canadian NCR A-8108, FCAC 74-09 and G.E.T.M.A.Part of this research was done during the first-named author's visit to theB! Chair of Applied Mathematics, University of Athens, Spring term, 1975.     

Multi-stage stochastic optimization applied to energy planning

This paper presents a methodology for the solution of multistage stochastic optimization problems, based on the approximation of the expected-cost-to-go functions of stochastic dynamic programming by piecewise linear functions. No state discretization is necessary, and the combinatorial explosion with the number of states (the well known curse of dimensionality of dynamic programming) is avoided. The piecewise functions are obtained from the dual solutions of the optimization problem at each stage and correspond to Benders cuts in a stochastic, multistage decomposition framework. A case study of optimal stochastic scheduling for a 39-reservoir system is presented and discussed.     

A statistical generalized programming algorithm for stochastic optimization problems

In this paper, we are concerned with an algorithm which combines the generalized linear programming technique proposed by Dantzig and Wolfe with the stochastic quasigradient method in order to solve stochastic programs with recourse. In this way, we overcome the difficulties arising in finding the exact values of the objective function of recourse problems by replacing them with the statistical estimates of the function. We present the basic steps of the proposed algorithm focusing our attention on its implementation alternatives aimed at improving both the convergence and computational performances. The main application areas are mentioned and some computational experience in the validation of our approach is reported. Finally, we discuss the possibilities of parallelization of the proposed algorithmic schemes.This paper has been partially supported by the Italian MURST 40% project on Flexible Manufacturing Systems.     

Stochastic Lagrangian Relaxation Applied to Power Scheduling in a Hydro-Thermal System under Uncertainty

A dynamic (multi-stage) stochastic programming model for the weekly cost-optimal generation of electric power in a hydro-thermal generation system under uncertain demand (or load) is developed. The model involves a large number of mixed-integer (stochastic) decision variables and constraints linking time periods and operating power units. A stochastic Lagrangian relaxation scheme is designed by assigning (stochastic) multipliers to all constraints coupling power units. It is assumed that the stochastic load process is given (or approximated) by a finite number of realizations (scenarios) in scenario tree form. Solving the dual by a bundle subgradient method leads to a successive decomposition into stochastic single (thermal or hydro) unit subproblems. The stochastic thermal and hydro subproblems are solved by a stochastic dynamic programming technique and by a specific descent algorithm, respectively. A Lagrangian heuristics that provides approximate solutions for the first stage (primal) decisions starting from the optimal (stochastic) multipliers is developed. Numerical results are presented for realistic data from a German power utility and for numbers of scenarios ranging from 5 to 100 and a time horizon of 168 hours. The sizes of the corresponding optimization problems go up to 200000 binary and 350000 continuous variables, and more than 500000 constraints.     

On some global well-posedness and asymptotic results for quasilinear parabolic equations

We prove that the quasilinear parabolic initial-boundary value problem (1.1) below is globally well-posed in a class of high order Sobolev solutions, and that these solutions possess compact, regular attractors ast+.     

A Constant-Potential Infeasible-Start Interior-Point Algorithm with Computational Experiments and Applications

We present a constant-potential infeasible-start interior-point (INFCP) algorithm for linear programming (LP) problems with a worst-case iteration complexity analysis as well as some computational results.The performance of the INFCP algorithm is compared to those of practical interior-point algorithms. New features of the algorithm include a heuristic method for computing a good starting point and a procedure for solving the augmented system arising from stochastic programming with simple recourse. We also present an application to large scale planning problems under uncertainty.     

Chebyshev Solution of the Nearly-Singular One-Dimensional Helmholtz Equation and Related Singular Perturbation Equations: Multiple Scale Series and the Boundary Layer Rule-of-Thumb

The one-dimensional Helmholtz equation, ² u _xx –u=f(x), arises in many applications, often as a component of three-dimensional fluids codes. Unfortunately, it is difficult to solve for 1 because the homogeneous solutions are exp(±x/), which have boundary layers of thickness O(1/). By analyzing the asymptotic Chebyshev coefficients of exponentials, we rederive the Orszag–Israeli rule [16] that Chebyshev polynomials are needed to obtain an accuracy of 1% or better for the homogeneous solutions. (Interestingly, this is identical with the boundary layer rule-of-thumb in [5], which was derived for singular functions like tanh([x–1]/).) Two strategies for small are described. The first is the method of multiple scales, which is very general, and applies to variable coefficient differential equations, too. The second, when f(x) is a polynomial, is to compute an exact particular integral of the Helmholtz equation as a polynomial of the same degree in the form of a Chebyshev series by solving triangular pentadiagonal systems. This can be combined with the analytic homogeneous solutions to synthesize the general solution. However, the multiple scales method is more efficient than the Chebyshev algorithm when is very, very tiny.     

When Is a Subspace of B(H) Ideal?

Let be a real or complex Hilbert space and let () denote the algebra of all bounded linear operators on . We show that if N is a subspace of (H) and for positive operators P₁, P₂ and every A N, P₁P₂A^* + AP₁P₂ N then N is an ideal. Furthermore if is an infinite dimensional real space then N = (H).AMS Subject Classification (1991): Primary 47B47, 47D25     

Functional Approach of Large Deviations in General Spaces

Let X be a topological space, ( ) a net of Borel probability measures on X, and (t) a net in ]0,[ converging to 0. Let be a set of continuous functions such that for all x X that can be suitably distinguished by some continuous functions from any closed set not containing contains such a distinguishing function. Assuming that exists for all , we give a sufficient condition in order that ( ₎ satisfies a large deviation principle with powers (t₎ and not necessary tight rate function. When X is completely regular (not necessary Hausdorff), this condition is also necessary, and so strictly weaker than exponential tightness; this allows us to strengthen Brycs theorem in various ways. We give the general form of a rate function in terms of . A Prohorov-type theorem with a weaker notion than exponential tightness is obtained, which improves known results.     

Computation of efficient solutions of discretely distributed stochastic optimization problems

In engineering and economics often a certain vectorx of inputs or decisions must be chosen, subject to some constraints, such that the expected costs (or loss) arising from the deviation between the outputA() x of a stochastic linear systemxA()x and a desired stochastic target vectorb() are minimal. Hence, one has the following stochastic linear optimization problem minimizeF(x)=Eu(A()x b()) s.t.xD, (1) whereu is a convex loss function on ^m , (A(), b()) is a random (m,n + 1)-matrix, E denotes the expectation operator andD is a convex subset of ⁿ . Concrete problems of this type are e.g. stochastic linear programs with recourse, error minimization and optimal design problems, acid rain abatement methods, problems in scenario analysis and non-least square regression analysis.Solving (1), the loss functionu should be exactly known. However, in practice mostly there is some uncertainty in assigning appropriate penalty costs to the deviation between the outputA ()x and the targetb(). For finding in this situation solutions hedging against uncertainty a set of so-called efficient points of (1) is defined and a numerical procedure for determining these compromise solutions is derived. Several applications are discussed.     

Design of Stacked Self-Healing Rings Using a Genetic Algorithm

Ring structures in telecommunications are taking on increasing importance because of their self-healing properties. We consider a ring design problem in which several stacked self-healing rings (SHRs) follow the same route, and, thus, pass through the same set of nodes. Traffic can be exchanged among these stacked rings at a designated hub node. Each non-hub node may be connected to multiple rings. It is necessary to determine to which rings each node should be connected, and how traffic should be routed on the rings. The objective is to optimize the tradeoff between the costs for connecting nodes to rings and the costs for routing demand on multiple rings. We describe a genetic algorithm that finds heuristic solutions for this problem. The initial generation of solutions includes randomly-generated solutions, complemented by seed solutions obtained by applying a greedy randomized adaptive search procedure (GRASP) to two related problems. Subsequent generations are created by recombining pairs of parent solutions. Computational experiments compare the genetic algorithm with a commercial integer programming package.     

Statistical verification of optimality conditions for stochastic programs with recourse

Statistically motivated algorithms for the solution of stochastic programming problems typically suffer from their inability to recognize optimality of a given solution algorithmically. Thus, the quality of solutions provided by such methods is difficult to ascertain. In this paper, we develop methods for verification of optimality conditions within the framework of Stochastic Decomposition (SD) algorithms for two stage linear programs with recourse. Consistent with the stochastic nature of an SD algorithm, we provide termination criteria that are based on statistical verification of traditional (deterministic) optimality conditions. We propose the use of bootstrap methods to confirm the satisfaction of generalized Kuhn-Tucker conditions and conditions based on Lagrange duality. These methods are illustrated in the context of a power generation planning model, and the results are encouraging.This work was supported in part by Grant No. AFOSR-88-0076 from the Air Force Office of Scientific Research and Grant No. DDM-89-10046 from the National Science Foundation.     

Messung der Rotationsdiffusion von Molekülen in Flüssigkeiten mit gestörter γ-γ-Winkelkorrelation

Zusammenfassung An einem in Chloroform gelösten, sowohl fluoreszierenden wie auch radioaktiven¹⁸¹Hafnium-Metallchelatkomplex wurden bei verschiedenen Temperaturen die Rotationsdiffusionszeiten mit gestörter --Winkelkorrelation und mit Fluoreszenzdepolarisation gemessen.     

Partly convex programming and zermelo's navigation problems

Mathematical programs, that become convex programs after freezing some variables, are termed partly convex. For such programs we give saddle-point conditions that are both necessary and sufficient that a feasible point be globally optimal. The conditions require cooperation of the feasible point tested for optimality, an assumption implied by lower semicontinuity of the feasible set mapping. The characterizations are simplified if certain point-to-set mappings satisfy a sandwich condition.The tools of parametric optimization and basic point-to-set topology are used in formulating both optimality conditions and numerical methods. In particular, we solve a large class of Zermelo's navigation problems and establish global optimality of the numerical solutions.Research partly supported by NSERC of Canada.     

Arithmetics of binary quadratic forms,symmetry of their continued fractions and geometry of their de Sitter world

This article concerns the arithmetics of binary quadratic forms with integer coefficients, the De Sitters world and the continued fractions.Given a binary quadratic forms with integer coefficients, the set of values attaint at integer points is always a multiplicative tri-group. Sometimes it is a semigroup (in such case the form is said to be perfect). The diagonal forms are specially studied providing sufficient conditions for their perfectness. This led to consider hyperbolic reflection groups and to find that the continued fraction of the square root of a rational number is palindromic.The relation of these arithmetics with the geometry of the modular group action on the Lobachevski plane (for elliptic forms) and on the relativistic De Sitters world (for the hyperbolic forms) is discussed. Finally, several estimates of the growth rate of the number of equivalence classes versus the discriminant of the form are given.Partially supported by RFBR, grant 02-01-00655.     

Chapter 13 Satisficing DEA models under chance constraints

DEA (Data Envelopment Analysis) models and concepts are formulated here in terms of the P-Models of Chance Constrained Programming, which are then modified to contact the satisficing concepts of H.A. Simon. Satisficing is thereby added as a third category to the efficiency/inefficiency dichotomies that have heretofore prevailed in DEA. Formulations include cases in which inputs and outputs are stochastic, as well as cases in which only the outputs are stochastic. Attention is also devoted to situations in which variations in inputs and outputs are related through a common random variable. Extensions include new developments in goal programming with deterministic equivalents for the corresponding satisficing models under chance constraints.     

Congruences for Quadratic Units of Norm −1

Let D 1 (mod 4) be a positive integer. Let R be the ring {x + y(1 + )/2 : x, y }. Suppose that R contains a unit of norm –1 as well as an element of norm 2, and thus an element of norm –2. It is not hard to see that ±1(mod ²). In this paper we determine modulo ³ and modulo ³ using only elementary techniques. This determination extends a recent result of Mastropietro, which was proved using class field theory.     

Complete lattices of subgroups in compact groups

Summary LetG be a compact group and a sublattice of the lattice of all closed subgroups ofG. In Proposition 1 it is shown that is a complete lattice if it is a closed subset of the spaceG ^c of all closed non empty subsets ofG. In general the converse of this fact is not true (Example 3), but the following result can be obtained (Theorem 5): If is complete and if each element of is normalized by the connected component of the identity ofG, then is a closed, totally disconnected subset ofG ^c. We mention the following corollary: IfG is totally disconnected or abelian, then is complete if and only if it is a closed subset ofG ^c.While writing this paper the author was a fellow of the National Research Council (A 7171).     

On the Regularity of Stresses in the Closed Domain for the Linear Theory of Elasticity

The article deals with the estimates of the first derivatives of the solutions of the system L(u) u + ( + )(u) = –f(x). The solutions are fixed at the boundary u| = 0. The estimates are obtained in the whole closed domain in terms of the right-hand term f in a certain strong norm. If the norm of f in l ₂ is sufficiently small as compared to its strong norm, one can obtain estimates in an explicit form.