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.     

Embeddings of Lorentz—Marcinkiewicz spaces with mixed norms

X(Y) f -:X(Y)={fM(×): f_{X(Y)=f(x,.)YX<} . =(0, ), M (×) — , ×, X, Y, Z— . X(Y) Z(×).     

Optimal trajectories associated with a solution of the contingent Hamilton-Jacobi equation

In this paper we study the existence of optimal trajectories associated with a generalized solution to the Hamilton-Jacobi-Bellman equation arising in optimal control. In general, we cannot expect such solutions to be differentiable. But, in a way analogous to the use of distributions in PDE, we replace the usual derivatives with contingent epiderivatives and the Hamilton-Jacobi equation by two contingent Hamilton-Jacobi inequalities. We show that the value function of an optimal control problem verifies these contingent inequalities.Our approach allows the following three results: (a) The upper semicontinuous solutions to contingent inequalities are monotone along the trajectories of the dynamical system. (b) With every continuous solutionV of the contingent inequalities, we can associate an optimal trajectory along whichV is constant. (c) For such solutions, we can construct optimal trajectories through the corresponding optimal feedback.They are also viscosity solutions of a Hamilton-Jacobi equation. Finally, we prove a relationship between superdifferentials of solutions introduced by Crandallet al. [10] and the Pontryagin principle and discuss the link of viscosity solutions with Clarke's approach to the Hamilton-Jacobi equation.     

On a class of orthogonal series

, [0, 1], (n+1) n-. . [2]. — (. 5.4 5.6). . 6.4 2 [5]. , [4]. , , [6] [7]. [1].     

The existence of probability measures with specified projections

Let X and Y be locally compact-compact topological spaces, F X×Y is closed, and P(F) is the set of all Borel probability measures on F. For us to find, for the pair of probability measures (_x, _y P (X)×P(Y), a probability measure P(F) such that _X = _X ^–1 , _Y = _Y ^–1 it is necessary and sufficient that, for any pair of Borel sets A X, B Y for which (A× B) F=Ø, the condition _XA+ _YB 1 holds.Translated from Matematicheskie Zametki, Vol. 14, No. 4, pp. 573–576, October, 1973.     

A Strong Maximum Principle for some quasilinear elliptic equations

In its simplest form the Strong Maximum Principle says that a nonnegative superharmonic continuous function in a domain ⁿ ,n 1, is in fact positive everywhere. Here we prove that the same conclusion is true for the weak solutions of – u + (u) = f with a nondecreasing function ,(0)=0, andf0 a.e. in if and only if the integral((s)s) ^–1/2 ds diverges ats=0+. We extend the result to more general equations, in particular to – _p u + (u) =f where _p (u) = div(|Du| ^p-2 Du), 1 <p < . Our main result characterizes the nonexistence of a dead core in some reaction-diffusion systems.This work was partly done while the author was visiting the University of Minnesota as a Fulbright Scholar.     

Circles and spheres in pseudo-Riemannian geometry

Summary A totally umbilical pseudo-Riemannian submanifold with the parallel mean curvature vector field is said to be an extrinsic sphere. A regular curve in a pseudo-Riemannian manifold is called a circle if it is an extrinsic sphere. LetM be ann-dimensional pseudo-Riemannian submanifold of index (0n) in a pseudo-Riemannian manifold with the metricg and the second fundamental formB. The following theorems are proved. For ₀ = +1 or –1, ₁ = +1, –1 or 0 (2–2 ₀+ ₁2n–2–2) and a positive constantk, every circlec inM withg(c, c) = ₀ andg( _c c, _c c) = ₁ k ² is a circle in iffM is an extrinsic sphere. For ₀ = +1 or –1 (–₀n–), every geodesicc inM withg(c, c) = ₀ is a circle in iffM is constant isotropic and B(x,x,x) = 0 for anyx T(M). In this theorem, assume, moreover, that 1n–1 and the first normal space is definite or zero at every point. Then we can prove thatM is an extrinsic sphere. When = 0 orn, this fact does not hold in general.     

A survey of pseudo (v,k, λ)-designs

This work is an attempt to give a complete survey of all known results about pseudo (v, k, )-designs. In doing this, the author hopes to bring more attention to his conjecture given in Section 6; an affirmative answer to this conjecture would settle completely the existence and construction problem for a pseudo (v, k, )-design in terms of the existence of an appropriate (v, k, )-design.     

On the two-gap elliptic potentials

The-parametrized family of two-gap elliptic potentials is constructed so that (i) 0<<1, (ii) for rational values of such potentials are elliptic (i.e., double-periodic), (iii) within the limit0 this family degenerates to the soliton potential, (iv) within the limit1 this family degenerates to the one-gap Lamé potential.Dedicated to the memory of J.-L. Verdier     

Riesz representation theorem and weak compactness

. , .     

Derivatives of the Spectral Function and Sobolev Norms of Eigenfunctions on a Closed Riemannian Manifold

Let e(x, y, ) be the spectral function and the unit spectral projection operator, with respect to the Laplace–Beltrami operator on a closed Riemannian manifold M. We generalize the one-term asymptotic expansion of e(x, x, ) by Hörmander (Acta Math. 88 (1968), 341–370) to that of _{x y} e(x,y,)| _x=y for any multiindices , in a sufficiently small geodesic normal coordinate chart of M. Moreover, we extend the sharp (L ²,L ^p) (2 p) estimates of by Sogge (J. Funct. Anal. 77 (1988), 123–134; London Math. Soc. Lecture Note Ser. 137, Cambridge University Press, Cambridge, 1989; Vol. 1, pp. 416–422) to the sharp (L ², Sobolev L ^p) estimates of .     

Solving systems of polynomial inequalities over a real closed field in subexponential time

Let _m= (₁,..., _m) denote an ordered field, where _i+1>0 is infinitesimal relative to the elements of _i, 0 < –i < m (by definition, ₀= ). Given a system of inequalities f₁ > 0, ..., f_s > 0, f_s+1 0, ..., f_k 0, where f_{j m} [X₁,..., X_n] are polynomials such that, and the absolute value of any integer occurring in the coefficients of the f_js is at most 2^M. An algorithm is constructed which tests the above system of inequalities for solvability over the real closure of _m in polynomial time with respect to M, ((d)ⁿd₀)^n+m. In the case _m=, the algorithm explicitly constructs a family of real solutions of the system (provided the latter is consistent). Previously known algorithms for this problem had complexity of the order ofM(d d ₀ ^{m 2U(n)} .Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Maternaticheskogo Instituta im. V. A. Steklova Akad. Nauk SSSR, Vol. 174, pp. 3–36, 1988.     

Convex Separable Minimization Subject to Bounded Variables

A minimization problem with convex and separable objective function subject to a separable convex inequality constraint and bounded variables is considered. A necessary and sufficient condition is proved for a feasible solution to be an optimal solution to this problem. Convex minimization problems subject to linear equality/linear inequality constraint, and bounds on the variables are also considered. A necessary and sufficient condition and a sufficient condition, respectively, are proved for a feasible solution to be an optimal solution to these two problems. Algorithms of polynomial complexity for solving the three problems are suggested and their convergence is proved. Some important forms of convex functions and computational results are given in the Appendix.     

Divisorial Linear Algebra of Normal Semigroup Rings

We investigate the minimal number of generators and the depth of divisorial ideals over normal semigroup rings. Such ideals are defined by the inhomogeneous systems of linear inequalities associated with the support hyperplanes of the semigroup. The main result is that for every bound C there exist, up to isomorphism, only finitely many divisorial ideals I such that (I)C. It follows that there exist only finitely many Cohen–Macaulay divisor classes. Moreover, we determine the minimal depth of all divisorial ideals and the behaviour of and depth in arithmetic progressions in the divisor class group.The results are generalized to more general systems of linear inequalities whose homogeneous versions define the semigroup in a not necessarily irredundant way. The ideals arising this way can also be considered as defined by the nonnegative solutions of an inhomogeneous system of linear diophantine equations.We also give a more ring-theoretic approach to the theorem on minimal number of generators of divisorial ideals: it turns out to be a special instance of a theorem on the growth of multigraded Hilbert functions.     

Some inequalities about the covering radius of Reed-Muller codes

Let R(r, m) be the rth order Reed-Muller code of length 2 ^m , and let (r, m) be its covering radius. We prove that if 2 k m - r - 1, then (r + k, m + k) (r, m + 2(k - 1). We also prove that if m - r 4, 2 k m - r - 1, and R(r, m) has a coset with minimal weight (r, m) which does not contain any vector of weight (r, m) + 2, then (r + k, m + k) (r, m) + 2k(. These inequalities improve repeated use of the known result (r + 1, m + 1) (r, m).This work was supported by a grant from the Research Council of Wright State University.     

On the construction and calculation of optimal nonlifting critical airfoils

Numerical calculations are carried out in the hodograph plane to construct optimal critical airfoil shapes and the flow about them. These optimal airfoil shapes give the highest free-stream Mach numberM for a given thickness ratio and tail angle _t (nonlifting) for which the flow is nowhere supersonic. A relationship betweenM and for various _t is given. Analytical and numerical solutions to the same problem are found on the basis of transonic small-disturbance theory. These results provide a limiting case asM 1, 0 and agree well with the calculations of the full problem. Using a numerical method to calculate the flow about general (subsonic) airfoils, a comparison is made between the critical free-stream Mach numbers for some standard airfoil shapes and the optimal free stream Mach number of the corresponding and _t . A significant increase in the critical free-stream Mach number is found for the optimal airfoils.     

An Inequality for Tail Probabilities of Martingales with Bounded Differences

Let M _n =X₁+...+X_n be a martingale with bounded differences X_m=M_m-M_m-1 such that {|X_m| _m}=1 with some nonnegative _m. Write ²= ₁ ² + ... + _n ² . We prove the inequalities {M _nx}c(1-(x/)), {M _n x} 1- c(1- (-x/)) with a constant . The result yields sharp inequalities in some models related to the measure concentration phenomena.     

Almost flat locally finite coverings of the sphere

For any subset A of the unit sphere of a Banach space X and for [0,2) the notion of -flatness is introduced as a measure of non-flatness of A. For any positive , construction of locally finite tilings of the unit sphere by -flat sets is carried out under suitable -renormings of X in a quite general context; moreover, a characterization of spaces having separable dual is provided in terms of the existence of such tilings. Finally, relationships between the possibility of getting such tilings of the unit sphere in the given norm and smoothness properties of the norm are discussed.     

Characterization,structure and analysis on abelian ℒ∞ groups

An abelian topological group is an group if and only if it is a locally -compactk-space and every compact subset in it is contained in a compactly generated locally compact subgroup. Every abelian groupG is topologically isomorphic to G ₀ where ₀ andG ₀ is an abelian group where every compact subset is contained in a compact subgroup. Intrinsic definitions of measures, convolution of measures, measure algebra,L ₁-algebra, Fourier transforms of abelian groups are given and their properties are studied.     

Asymptotic Density and the Asymptotics of Partition Functions

Let A be a set of positive integers with gcd (A) = 1, and let p _A (n) be the partition function of A. Let c ₀ = 2/3. If A has lower asymptotic density and upper asymptotic density , then lim inf log p _A (n)/c ₀ n and lim sup log p _A (n)/c ₀ n . In particular, if A has asymptotic density > 0, then log p _A (n) c₀n. Conversely, if > 0 and log p _A (n) c ₀ n, then the set A has asymptotic density .