Global optima results for the Kauffman NK model

The Kauffman NK model has been used in theoretical biology, physics and business organizations to model complex systems with interacting components. Recent NK model results have focused on local optima. This paper analyzes global optima of the NK model. The resulting global optimization problem is transformed into a stochastic network model that is closely related to two well-studied problems in operations research. This leads to applicable strategies for explicit computation of bounds on the global optima particularly with K either small or close to N. A general lower bound, which is sharp for K = 0, is obtained for the expected value of the global optimum of the NK model. A detailed analysis is provided for the expectation and variance of the global optimum when K = N−1. The lower and upper bounds on the expectation obtained for this case show that there is a wide gap between the values of the local and the global optima. They also indicate that the complexity catastrophe that occurs with the local optima does not arise for the global optima.     

Laplace approximations for sums of independent random vectors

Let X _i , i∈N, be i.i.d. B-valued random variables, where B is a real separable Banach space. Let Φ be a mapping B→R. Under a central limit theorem assumption, an asymptotic evaluation of Z _n = E (exp (n Φ (∑ _{i =1} ⁿ X _i /n))), up to a factor (1 + o(1)), has been gotten in Bolthausen [1]. In this paper, we show that the same asymptotic evaluation can be gotten without the central limit theorem assumption. Received: 19 September 1997 / Revised version:22 April 1999     

The relation of Banach-Alaoglu theorem and Banach-Bourbaki-Kakutani-Šmulian theorem in complete random normed modules to stratification structure

Let (Ω,A,μ) be a probability space, K the scalar field R of real numbers or C of complex numbers,and (S,X) a random normed space over K with base (ω,A,μ). Denote the support of (S,X) by E, namely E is the essential supremum of the set {A ∈ A: there exists an element p in S such that X _p (ω) > 0 for almost all ω in A}. In this paper, Banach-Alaoglu theorem in a random normed space is first established as follows: The random closed unit ball S ^*(1) = {f ∈ S ^*: X ^* _f ⩽ 1} of the random conjugate space (S ^*,X ^*) of (S,X) is compact under the random weak star topology on (S ^*,X ^*) iff E∩A=: {E∩A | A ∈ A} is essentially purely μ-atomic (namely, there exists a disjoint family {A _n : n ∈ N} of at most countably many μ-atoms from E ∩ A such that E = ∪ _n=1^∞ A _n and for each element F in E ∩ A, there is an H in the σ-algebra generated by {A _n : n ∈ N} satisfying μ(FΔH) = 0), whose proof forces us to provide a key topological skill, and thus is much more involved than the corresponding classical case. Further, Banach-Bourbaki-Kakutani-Šmulian (briefly, BBKS) theorem in a complete random normed module is established as follows: If (S,X) is a complete random normed module, then the random closed unit ball S(1) = {p ∈ S: X _p ⩽ 1} of (S,X) is compact under the random weak topology on (S,X) iff both (S,X) is random reflexive and E ∩ A is essentially purely μ-atomic. Our recent work shows that the famous classical James theorem still holds for an arbitrary complete random normed module, namely a complete random normed module is random reflexive iff the random norm of an arbitrary almost surely bounded random linear functional on it is attainable on its random closed unit ball, but this paper shows that the classical Banach-Alaoglu theorem and BBKS theorem do not hold universally for complete random normed modules unless they possess extremely simple stratification structure, namely their supports are essentially purely μ-atomic. Combining the James theorem and BBKS theorem in complete random normed modules leads directly to an interesting phenomenum: there exist many famous classical propositions that are mutually equivalent in the case of Banach spaces, some of which remain to be mutually equivalent in the context of arbitrary complete random normed modules, whereas the other of which are no longer equivalent to another in the context of arbitrary complete random normed modules unless the random normed modules in question possess extremely simple stratification structure. Such a phenomenum is, for the first time, discovered in the course of the development of random metric theory.     

A remark on the unconditional structure ofL (E,F)

We present a sequence of symmetric Banach spacesE _n ,n εN, withd (E _n , ),n ∈N, unbounded and ubc(L(E*_n,E _n )),n ∈N, uniformly bounded. During the preparation of this paper the author was supported by the Deutsche Forschungsgemeinschaft.     

Sudakov-type minoration for gaussian chaos processes

Consider a setA of symmetricn×n matricesa=(a _i,j) _i,j≤n . Consider an independent sequence (g _i) _i≤n of standard normal random variables, and letM=Esup_a∈A|Σ_i,j⪯na_i,jg_ig_j|. Denote byN ₂(A, α) (resp.N _t(A, α)) the smallest number of balls of radiusα for thel ₂ norm ofR ^{n 2} (resp. the operator norm) needed to coverA. Then for a universal constantK we haveα(logN ₂(A, α))^1/4≤KM. This inequality is best possible. We also show that forδ≥0, there exists a constantK(δ) such thatα(logN _t≤K(δ)M. Work partially supported by an N.S.F. grant.     

Robust global optimization with polynomials

We consider the optimization problems max_z∈Ω min_x∈K p(z, x) and min_{x ∈ K} max_{z ∈ Ω} p(z, x) where the criterion p is a polynomial, linear in the variables z, the set Ω can be described by LMIs, and K is a basic closed semi-algebraic set. The first problem is a robust analogue of the generic SDP problem max_{z ∈ Ω} p(z), whereas the second problem is a robust analogue of the generic problem min_{x ∈ K} p(x) of minimizing a polynomial over a semi-algebraic set. We show that the optimal values of both robust optimization problems can be approximated as closely as desired, by solving a hierarchy of SDP relaxations. We also relate and compare the SDP relaxations associated with the max-min and the min-max robust optimization problems.     

Compactly Supported Distributional Solutions of Nonstationary Nonhomogeneous Refinement Equations

Let A be a matrix with the absolute values of all eigenvalues strictly larger than one, and let Z ₀ be a subset of Z such than n∈Z ₀ implies n + 1 ∈Z ₀. Denote the space of all compactly supported distributions by D′, and the usual convolution between two compactly supported distributions f and g by f*g. For any bounded sequence G _n and H _n , n∈Z ₀, in D′, define the corresponding nonstationary nonhomogeneous refinement equation Φ _n =H _n *Φ _n+1 (A·)+G _n for all n∈Z ₀ where Φ _n , n∈Z ₀, is in a bounded set of D′. The nonstationary nonhomogeneous refinement equation (*) arises in the construction of wavelets on bounded domain, multiwavelets, and of biorthogonal wavelets on nonuniform meshes. In this paper, we study the existence problem of compactly supported distributional solutions Φ _n , n∈Z ₀, of the equation (*). In fact, we reduce the existence problem to finding a bounded solution of the linear equations for all n∈Z ₀ where the matrices S _n and the vectors , n∈Z ₀, can be constructed explicitly from H _n and G _n respectively. The results above are still new even for stationary nonhomogeneous refinement equations. Received December 30, 1999, Accepted June 15, 2000     

Kernel regression estimation for continuous spatial processes

We investigate here a kernel estimate of the spatial regression function r(x) = E(Y _u | X _u = x), x ∈ ℝ^d, of a stationary multidimensional spatial process { Z _u = (X _u, Y _u), u ∈ ℝ ^N }. The weak and strong consistency of the estimate is shown under sufficient conditions on the mixing coefficients and the bandwidth, when the process is observed over a rectangular domain of ℝ^N. Special attention is paid to achieve optimal and suroptimal strong rates of convergence. It is also shown that this suroptimal rate is preserved by using a suitable spatial sampling scheme.      

The range of a projection of small norm inl 1 n

It is proved that there exists a positive function Φ(∈) defined for sufficiently small ∈ 〉 0 and satisfying lim_t→0 Φ(∈) =0 such that for any integersn 〉>0, ifQ is a projection ofl ₁ ⁿ onto ak-dimensional subspaceE with ‖|Q‖|≦1+∈ then there is an integerh〉=k(1−Φ(∈)) and anh-dimensional subspaceF ofE withd(F,l ₁ ^h ) 〈= 1+Φ (∈) whered(X, Y) denotes the Banach-Mazur distance between the Banach spacesX andY. Moreover, there is a projectionP ofl ₁ ⁿ ontoF with ‖|P‖| ≦1+Φ(∈). Author was partially supported by the N.S.F. Grant MCS 79-03042.     

Fixed point theorems for non-Lipschitzian mappings of asymptotically nonexpansive type

LetX be a Banach space,K a nonempty, bounded, closed and convex subset ofX, and supposeT:K→K satisfies: for eachx∈K, lim sup _i→∞{sup _y∈K ‖t ⁱx−Tⁱy∼−‖x−y‖}≦0. IfT ^N is continuous for some positive integerN, and if either (a)X is uniformly convex, or (b)K is compact, thenT has a fixed point inK. The former generalizes a theorem of Goebel and Kirk for asymptotically nonexpansive mappings. These are mappingsT:K→K satisfying, fori sufficiently large, ‖Tⁱx−Tⁱy‖≦k _i‖x−y∼,x,y∈K, wherek _i→1 asi→∞. The precise assumption in (a) is somewhat weaker than uniform convexity, requiring only that Goebel’s characteristic of convexity, ɛ₀ (X), be less than one. Research supported by National Science Foundation Grant GP 18045.     

On calculation of moments of ladder heights

Let X,X ₁,X ₂, … be independent identically distributed random variables, F(x) = P{X < x}, S ₀ = 0, and S _n =Σ _i=1 ⁿ X _i . We consider the random variables, ladder heights Z ₊ and Z ₋ that are respectively the first positive sum and the first negative sum in the random walk {S _n }, n = 0, 1, 2, …. We calculate the first three (four in the case EX = 0) moments of random variables Z ₊ and Z ₋ in the qualitatively different cases EX > 0, EX < 0, and EX = 0. __________ Translated from Lietuvos Matematikos Rinkinys, Vol. 46, No. 2, pp. 159–179, April–June, 2006.     

A Property About Minimum Edge- and Minimum Clique-Cover of a Graph

 Let G be a graph with n vertices, and denote as γ(G) (as θ(G)) the cardinality of a minimum edge cover (of a minimum clique cover) of G. Let E (let C) be the edge-vertex (the clique-vertex) incidence matrix of G; write then P(E)={x∈ℜ ⁿ :Ex≤1,x≥0}, P(C)={x∈ℜ ⁿ :Cx≤1,x≥0}, α _E (G)=max{1 ^T x subject to x∈P(E)}, and α _C (G)= max{1 ^T x subject to x∈P(C)}. In this paper we prove that if α _E (G)=α _C (G), then γ(G)=θ(G). Received: May 20, 1998?Final version received: April 12, 1999     

The maximal and minimal 2-correlation of a class of 1-dependent 0–1 valued processes

We compute the maximal and minimal value ofP[X _N =X _N+1=1] for fixedP[X _N =1], where (X _N ) _N∈Z is a 0–1 valued 1-dependent process obtained by a coding of an i.i.d.-sequence of uniformly [0,1] distributed random variables with a subset of the unit square. This research was supported by the Netherlands Foundation for Mathematics (S.M.C.) with financial aid from the Netherlands Organization for the Advancement of Pure Research (ZWO).     

Large deviation results for generalized compound negative binomial risk models

In this paper we extend and improve some results of the large deviation for random sums of random variables. Let {Xn;n 〉 1} be a sequence of non-negative, independent and identically distributed random variables with common heavy-tailed distribution function F and finite mean μ ∈R^＋, {N（n）; n ≥0} be a sequence of negative binomial distributed random variables with a parameter p C （0, 1）, n ≥ 0, let {M（n）; n ≥ 0} be a Poisson process with intensity λ 〉 0. Suppose {N（n）; n ≥ 0}, {Xn; n≥1} and {M（n）; n ≥ 0} are mutually independent. Write S（n） =N（n）∑i=1 Xi-cM（n）.Under the assumption F ∈ C, we prove some large deviation results. These results can be applied to certain problems in insurance and finance.     

Strong laws for exponential order statistics and spacings

We obtain upper and lower almost sure asymptotic bounds for spacings η _{K, N} − η _{K + 1, N} , where η _{1, N} > η _{2, N} > ⋯ > η _{N, N} are the order statistics of independent exponentially distributed random variables η ₁, η ₂, ..., η _N with mean 1; here N → ∞, and K = 1, 2, ... is fixed. Published in Lietuvos Matematikos Rinkinys, Vol. 46, No. 4, pp. 477–491, October–December, 2006.     

Sharp Estimates for the Global Attractor of Scalar Reaction–Diffusion Equations with a Wentzell Boundary Condition

In this paper, we derive optimal upper and lower bounds on the dimension of the attractor A_W\mathcal{A}_{\mathrm{W}} for scalar reaction–diffusion equations with a Wentzell (dynamic) boundary condition. We are also interested in obtaining explicit bounds on the constants involved in our asymptotic estimates, and to compare these bounds to previously known estimates for the dimension of the global attractor A_K\mathcal{A}_{K}, K∈{D,N,P}, of reaction–diffusion equations subject to Dirichlet, Neumann and periodic boundary conditions. The explicit estimates we obtain show that the dimension of the global attractor A_W\mathcal {A}_{\mathrm{W}} is of different order than the dimension of A_K\mathcal{A}_{K}, for each K∈{D,N,P}, in all space dimensions that are greater than or equal to three.     

Approximating common fixed points of asymptotically nonexpansive mappings by composite algorithm in Banach spaces

Let E be a uniformly convex Banach space and K a nonempty convex closed subset which is also a nonexpansive retract of E. Let T ₁, T ₂ and T ₃: K → E be asymptotically nonexpansive mappings with {k _n }, {l _n } and {j _n }. [1, ∞) such that Σ _n=1 ^∞ (k _n − 1) < ∞, Σ _n=1 ^∞ (l _n − 1) < ∞ and Σ _n=1 ^∞ (j _n − 1) < ∞, respectively and F nonempty, where F = {x ∈ K: T _1x = T _2x = T ₃ x} = x} denotes the common fixed points set of T ₁, _{T 2} and T ₃. Let {α _n }, {α′ _n } and {α″ _n } be real sequences in (0, 1) and ∈ ≤ {α _n }, {α′ _n }, {α″ _n } ≤ 1 − ∈ for all n ∈ N and some ∈ > 0. Starting from arbitrary x ₁ ∈ K define the sequence {x _n } by

The classification of injective Banach lattices

LetE be a 1-injective Banach lattice,X any Banach space andT: E ← X a norm bounded linear operator. Then eitherT is an isomorphism on some copy ofl _∞ inE or for all σ > 0 there is φ ∈E ₊ ^′ such that ‖Tu‖≦φ (|u|)+σ ‖u‖ for allu ∈E. We deduce the theorem that: A norm order continuous injective Banach lattice is order isomorphic to an (AL)-space.