Infinitely constrained optimization problems

A generalized cutting-plane algorithm designed to solve problems of the form min{f(x) :x X andg(x,y) 0 for ally Y} is described. Convergence is established in the general case (f,g continuous,X andY compact). Constraint dropping is allowed in a special case [f,g(·,y) convex functions,X a convex set]. Applications are made to a variety of max-min problems. Computational considerations are discussed.Dr. Falk's research was supported by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under AFOSR Contract No. 73–2504.     

Addition of sequences in general fields

IfX, Y are two finite subsets of a fieldL and the characteristic ofL is either 0 or is sufficiently large compared to the cardinalities ofX andY then there exists az L uniquely representable asx+y,xX,yY.Dedicated to Prof. Dr. E. Hlawka on the occasion of his 60th birthday     

Laws of Iterated Logarithm and Related Asymptotics for Estimators of Conditional Density and Mode

Let (X _i , Y _i ) be a sequence of i.i.d. random vectors in R with an absolutely continuous distribution function H and let g _x (y), y R denote the conditional density of Y given X = x(F), the support of F, assuming that it exists. Also let M(x) be the (unique) conditional mode of Y given X = x defined by M(x) = arg max _y (y)). In this paper new classes of smoothed rank nearest neighbor (RNN) estimators of g _x (y), its derivatives and M(x) are proposed and the laws of iterated logarithm (pointwise), uniform a.s. convergence over – < y < and x a compact C(F) and the asymptotic normality for the proposed estimators are established. Our results and proofs also cover the Nadayara-Watson (NW) case. It is shown using the concept of the relative efficiency that the proposed RNN estimator is superior (asymtpotically) to the corresponding NW type estimator of M(x), considered earlier in literature.     

Über Distanzfunktionen mit Werten in angeordneten Halbgruppen

This paper presents a general investigation of the relations between structural properties of a totally ordered abelian semigroupS and the properties of various topological structures, such as topologies, bitopologies and (semi-)uniformities on a spaceX induced byS-valued distance functionsdX×XS satisfyingd(x,y)=0 iffx=y and the triangular inequalityd(x,z)d(x,y)+d(y,z), for allx,y,zX. Since a linearly ordered abelian semigroupS need not be a topological semigroup with respect to its order topology we have to consider two cases: the case where addition inS is continuous at 0S, and the case where it is not. For both cases, we state several metrization theorems, examples and applications. In this connection, we are also concerned with some special basis-properties of topological spaces. Closely connected is the program stated byAlexandroff-Bourbaki (amongst others) to investigate to what extent countability inherent in matrization theory can be replaced by order-theoretic properties.—Distinguishing between symmetric and not necessarily symmetric distancesd _S we obtain a theory containing the theory of _µ -metrics and _µ- quasimetrics.—As far as it concerns not necessarily symmetric distancesd onX, it seems adequate to study the bitopological structure ( _e , _r ) induced onX byd and the inverse distanced ^–1 respectively. This is done in § 4 where, in this respect, we also generalize a well-known theorem ofSion andZelmer.

---

---

Herrn Prof. Dr. E. Hlawka zum 60. Geburtstag gewidmet

---

Die ersten Anregungen zur grundsätzlichen Problemstellung erhielt der erste Autor in einem Seminar über Bewertungstheorie und Analysis in bewerteten Körpern, das unter der Leitung Herrn Prof. Dr.E. Hlawkas am Mathematischen Institut der Universität Wien abgehalten wurde.     

Outer approximation algorithm for nondifferentiable optimization problems

It is known that the problem of minimizing a convex functionf(x) over a compact subsetX of ⁿ can be expressed as minimizing max{g(x, y)|y X}, whereg is a support function forf[f(x) g(x, y), for ally X andf(x)=g(x, x)]. Standard outer-approximation theory can then be employed to obtain outer-approximation algorithms with procedures for dropping previous cuts. It is shown here how this methodology can be extended to nonconvex nondifferentiable functions.This research was supported by the Science and Engineering Research Council, UK, and by the National Science Foundation under Grant No. ECS-79-13148.     

A White Noise Approach to Stochastic Neumann Boundary-Value Problems

We illustrate the use of white noise analysis in the solution of stochastic partial differential equations by explicitly solving the stochastic Neumann boundary-value problem LU(x)–c(x)U(x)=0, xDR ^d ,(x)U(x)=–W(x), xD, where L is a uniformly elliptic linear partial differential operator and W(x), xR ^d , is d-parameter white noise.     

On the strong controllability of the diffusion equation

Let (x,t)y (x,t),x[0, 1],t[0,T], be the solution of the diffusion equation in one spatial variable corresponding to zero initial conditions and boundary controluL ₂(0,T). GivenfL ₂(0, 1), it is not possible, in general, to find a controlu such thaty(·,T)=f. We extend the space of controls in such a manner thatL ₂(0,T) can be considered to be a subset of a new spaceS of control elements; this space contains elements which do provide a solution to the problem of moments associated with the problem of makingy(·,T)=f inL ₂(0, 1). We show then that the action of the elements ofS can be approximated by that of control functions inL ₂(0,T) in a suitable manner.     

Analytic Approximations for a Singularly Perturbed Convection—Diffusion Problem with Discontinuous Data in a Half-Infinite Strip

We consider a singularly perturbed convection—diffusion equation, –u+v u=0, defined on a half-infinite strip, (x,y)(0,)×(0,1) with a discontinuous Dirichlet boundary condition: u(x,0)=1, u(x,1)=u(0,y)=0. Asymptotic expansions of the solution are obtained from an integral representation in two limits: (a) as the singular parameter 0⁺ (with fixed distance r to the discontinuity point of the boundary condition) and (b) as that distance r0⁺ (with fixed ). It is shown that the first term of the expansion at =0 contains an error function or a combination of error functions. This term characterizes the effect of discontinuities on the -behavior of the solution and its derivatives in the boundary or internal layers. On the other hand, near the point of discontinuity of the boundary condition, the solution u(x,y) is approximated by a linear function of the polar angle at the point of discontinuity (0,0).     

Geometrical Characterization of Strict Suns in ℓ∞(n)

A subset M of a normed linear space X is called a strict sun if, for any x X\M, the set of its nearest points from M is nonempty and for any point y M which is nearest to x, the point y is a nearest point from M to any point of the ray {x + (1 - )y | > 0\}. We give an intrinsic geometrical characterization of strict suns in the space (n).     

Blocking of billiard orbits and security for polygons and flat surfaces

We introduce and study the notion of security for polygons and flat surfaces. Let P be one. For x, y P let G(x, y) be the set of geodesics connecting x and y. We say that P is secure if for any x, y P all geodesics in G(x, y) can be blocked by a finite set B P. We prove, in particular, that a lattice polygon is secure iff it is arithmetic.Received: September 2003 Revision: March 2004 Accepted: March 2004     

An iff fixed point criterion for continuous self-mappings on a complete metric space

Summary Letf be a self-map on a metric space (X, d). We give necessary and sufficient conditions for the sequences {f ⁿ x} (x X) to be equivalent Cauchy. As a typical application we get the following result. Letf be continuous and (X, d) be complete. If, for anyx, y X d(f ⁿ x, f ⁿ y) 0 and for somec > 0, this convergence is uniform for allx, y inX withd(x, y) c thenf has a unique fixed pointp, andf ⁿ x p, for eachx inX. This theorem includes among others results of Angelov, Browder, Edelstein, Hicks and Matkowski.     

Nonlinear Markov Operators,Discrete Heat Flow,and Harmonic Maps Between Singular Spaces

We develop a theory of harmonic maps f:MN between singular spaces M and N. The target will be a complete metric space (N,d) of nonpositive curvature in the sense of A. D. Alexandrov. The domain will be a measurable space (M,) with a given Markov kernel p(x,dy) on it. Given a measurable map f:MN, we define a new map Pf:MN in the following way: for each xM, the point Pf(x)N is the barycenter of the probability measure p(x,f ^–1(dy)) on N. The map f is called harmonic on DM if Pf=f on D. Our theory is a nonlinear generalization of the theory of Markov kernels and Markov chains on M. It allows to construct harmonic maps by an explicit nonlinear Markov chain algorithm (which under suitable conditions converges exponentially fast). Many smoothing and contraction properties of the linear Markov operator P _M,R carry over to the nonlinear Markov operator P=P _M,N . For instance, if the underlying Markov kernel has the strong Lipschitz Feller property then all harmonic maps will be Lipschitz continuous.     

Congruences and ideals in ternary rings

A ternary ring is an algebraic structure R=(R,t0.1) of type (3, 0, 0) satisfying the identities t(0, x, y) = y = t(x, 0, y) and t(1, x, 0) = x = (x, l, 0) where, moreover, for any a, b, c R there exists a unique d R with t(a, b, d) = c. A congruence on R is called normal if R with t is a ternary ring again. We describe basic properties of the lattice of all normal congruences on R and establish connections between ideals (introduced earlier by the third author) and congruence kernels.     

A Class of Iterative Algorithms and Solvability of Nonlinear Variational Inequalities Involving Multivalued Mappings

The solvability of the following class of nonlinear variational inequality (NVI) problems based on a class of iterative procedures, which possess an equivalence to a class of projection formulas, is presented.Determine an element x ^* K and u ^* T(x ^*) such that u ^*, x – x ^* 0 for all x K where T: K P(H) is a multivalued mapping from a real Hilbert space H into P(H), the power set of H, and K is a nonempty closed convex subset of H. The iterative procedure adopted here is represented by a nonlinear variational inequality: for arbitrarily chosen initial points x ⁰, y ⁰ K, u ⁰ T(y ⁰) and v ⁰ T(x ⁰), we have u ^k + x ^k+1 – y ^k , x – x ^k+1 0, x K, for u ^k T(y ^k ) and for k 0where v ^k + y ^k – x ^k , x – y ^k 0, x K and for v ^k T(x ^k ).     

Implicitly defined optimization problems

This paper considers the solution of the problem: inff[y, x(y)] s.t.y [y, x(y)] E ^k , wherex(y) solves: minF(x, y) s.t.x R(x, y) E ⁿ . In order to obtain local solutions, a first-order algorithm, which uses {dx(y)/dy} for solving a special case of the implicitly definedy-problem, is given. The derivative is obtained from {dx(y, r)/dy}, wherer is a penalty function parameter and {x(y, r)} are approximations to the solution of thex-problem given by a sequential minimization algorithm. Conditions are stated under whichx(y, r) and {dx(y, r)/dy} exist. The computation of {dx(y, r)/dy} requires the availability of _y F(x, y) and the partial derivatives of the other functions defining the setR(x, y) with respect to the parametersy.Research sponsored by National Science Foundation Grant ECS-8709795 and Office of Naval Research Contract N00014-89-J-1537. We thank the referees for constructive comments on an earlier version of this paper.     

Recurrent random walks in nonnegative matrices II

Summary In this paper, we continue the study undertaken in our earlier paper [M1]. One of the main results here can be described as follows. LetX ₀,X ₁, ... be a sequence of iid random affine maps from (R ⁺) ^d into itself. Let us write:W _n X _n X _n –1...X ₀ andZ _n X ₀ X ₁...X _n , where composition of maps is the rule of multiplication. By the attractorA(u),u(R ⁺) ^d , we mean the setA u={y(R⁺)^d:P(W_n uN i.o.) > 0 for every openN containingy}. It is shown that the attractorA(u), under mild conditions, is the support of a stationary probability measure, when the random walk (Z _n ) has at least one recurrent state.     

Об отделимости множе ств гиперплоскостью вL p

LetA and be two arbitrary sets in the real spaceL _p, 1p<. Sufficient conditions are obtained for their strict separability by a hyperplane, in terms of the distance between the setsd(A,B) _p=inf{x-y_p,xA,yB} and their diametersd(A) _p, d(B)_p, whered(A) _p=sup{x-y_p; x,yA}. In particular, it is proved that if in an infinite-demensional spaceL _p we haved ^r(A,B)_p>2^–r+1(d^r(A)_p+d^r(B)_p), r=min{p, p(p–1)^–1}, then there is a hyperplane which separatesA andB. On the other hand, the conditiond ^r(A,B)_p=2^–r+1(d^r(A)_p+d^r(B)_p) does not guarantee strict separability. Earlier these results where obtained by V. L. Dol'nikov for the case of Euclidean spaces.     

Counting Split Semiorders

A poset P=(X,) is a split semiorder if a unit interval and a distinguished point in that interval can be assigned to each xX so that xy precisely when x's distinguished point precedes y's interval, and y's distinguished point follows x's interval. For each |X|10, we count the split semiorders and identify all posets that are minimal forbidden posets for split semiorders.     

On operators with the same local spectra

Let B(X) be the algebra of all bounded linear operators in a complex Banach space X. We consider operators T ₁, T ₂ B(X) satisfying the relation for any vector x X, where _T (x) denotes the local spectrum of T B(X) at the point x X. We say then that T ₁ and T ₂ have the same local spectra. We prove that then, under some conditions, T ₁ – T ₂ is a quasinilpotent operator, that is as n . Without these conditions, we describe the operators with the same local spectra only in some particular cases.     

On signpost systems and connected graphs

By a signpost system we mean an ordered pair (W, P), where W is a finite nonempty set, P W × W × W and the following statements hold: if (u, v, w) P, then (v, u, u) P and (v, u, w) P, for all u, v, w W; if u v; then there exists r W such that (u, r, v) P, for all u, v W. We say that a signpost system (W, P) is smooth if the folowing statement holds for all u, v, x, y, z W: if (u, v, x), (u, v, z), (x, y, z) P, then (u, v, y) P. We say thay a signpost system (W, P) is simple if the following statement holds for all u, v, x, y W: if (u, v, x), (x, y, v) P, then (u, v, y), (x, y, u) P.By the underlying graph of a signpost system (W, P) we mean the graph G with V(G) = W and such that the following statement holds for all distinct u, v W: u and v are adjacent in G if and only if (u, v, v) P. The main result of this paper is as follows: If G is a graph, then the following three statements are equivalent: G is connected; G is the underlying graph of a simple smooth signpost system; G is the underlying graph of a smooth signpost system.Research was supported by Grant Agency of the Czech Republic, grant No. 401/01/0218.