首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 62 毫秒
1.
We obtain an integral representation of even functions of two variables for which the kernel [k 1(x + y) + k 2(x − y)], x, yR 2, is positive definite.  相似文献   

2.
Viresh Patel 《Order》2008,25(2):131-152
Given a poset P = (X, ≺ ), a partition X 1, ..., X k of X is called an ordered partition of P if, whenever x ∈ X i and y ∈ X j with x ≺ y, then i ≤ j. In this paper, we show that for every poset P = (X, ≺ ) and every integer k ≥ 2, there exists an ordered partition of P into k parts such that the total number of comparable pairs within the parts is at most (m − 1)/k, where m ≥ 1 is the total number of edges in the comparability graph of P. We show that this bound is best possible for k = 2, but we give an improved bound, , for k ≥ 3, where c(k) is a constant depending only on k. We also show that, given a poset P = (X, ≺ ) and an integer 2 ≤ k ≤ |X|, we can find an ordered partition of P into k parts that minimises the total number of comparable pairs within parts in time polynomial in the size of P. We prove more general, weighted versions of these results. Supported by an EPSRC doctoral training grant.  相似文献   

3.
An accelerated hybrid conjugate gradient algorithm represents the subject of this paper. The parameter β k is computed as a convex combination of bkHS\beta_k^{HS} (Hestenes and Stiefel, J Res Nat Bur Stand 49:409–436, 1952) and bkDY\beta_k^{DY} (Dai and Yuan, SIAM J Optim 10:177–182, 1999), i.e. bkC = (1-qk)bkHS + qk bkDY\beta_k^C =\left({1-\theta_k}\right)\beta_k^{HS} + \theta_k \beta_k^{DY}. The parameter θ k in the convex combinaztion is computed in such a way the direction corresponding to the conjugate gradient algorithm is the best direction we know, i.e. the Newton direction, while the pair (s k , y k ) satisfies the modified secant condition given by Li et al. (J Comput Appl Math 202:523–539, 2007) B k + 1 s k  = z k , where zk = yk +(hk / || sk ||2 )skz_k =y_k +\left({{\eta_k} / {\left\| {s_k} \right\|^2}} \right)s_k, hk = 2( fk -fk+1 )+( gk +gk+1 )Tsk\eta_k =2\left( {f_k -f_{k+1}} \right)+\left( {g_k +g_{k+1}} \right)^Ts_k, s k  = x k + 1 − x k and y k  = g k + 1 − g k . It is shown that both for uniformly convex functions and for general nonlinear functions the algorithm with strong Wolfe line search is globally convergent. The algorithm uses an acceleration scheme modifying the steplength α k for improving the reduction of the function values along the iterations. Numerical comparisons with conjugate gradient algorithms show that this hybrid computational scheme outperforms a variant of the hybrid conjugate gradient algorithm given by Andrei (Numer Algorithms 47:143–156, 2008), in which the pair (s k , y k ) satisfies the classical secant condition B k + 1 s k  = y k , as well as some other conjugate gradient algorithms including Hestenes-Stiefel, Dai-Yuan, Polack-Ribière-Polyak, Liu-Storey, hybrid Dai-Yuan, Gilbert-Nocedal etc. A set of 75 unconstrained optimization problems with 10 different dimensions is being used (Andrei, Adv Model Optim 10:147–161, 2008).  相似文献   

4.
The linear discrepancy of a poset P is the least k such that there is a linear extension L of P such that if x and y are incomparable in P, then |h L (x) − h L (y)| ≤ k, where h L (x) is the height of x in L. Tannenbaum, Trenk, and Fishburn characterized the posets of linear discrepancy 1 as the semiorders of width 2 and posed the problem for characterizing the posets of linear discrepancy 2. Howard et al. (Order 24:139–153, 2007) showed that this problem is equivalent to finding all posets of linear discrepancy 3 such that the removal of any point reduces the linear discrepancy. In this paper we determine all of these minimal posets of linear discrepancy 3 that have width 2. We do so by showing that, when removing a specific maximal point in a minimal linear discrepancy 3 poset, there is a unique linear extension that witnesses linear discrepancy 2. The first author was supported during this research by National Science foundation VIGRE grant DMS-0135290.  相似文献   

5.
For a finite poset P = (V, ≤ ), let _s(P){\cal B}_s(P) consist of all triples (x,y,z) ∈ V 3 such that either x < y < z or z < y < x. Similarly, for every finite, simple, and undirected graph G = (V,E), let Bs(G){\cal B}_s(G) consist of all triples (x,y,z) ∈ V 3 such that y is an internal vertex on an induced path in G between x and z. The ternary relations Bs(P){\cal B}_s(P) and Bs(G){\cal B}_s(G) are well-known examples of so-called strict betweennesses. We characterize the pairs (P,G) of posets P and graphs G on the same ground set V which induce the same strict betweenness relation Bs(P)=Bs(G){\cal B}_s(P)={\cal B}_s(G).  相似文献   

6.
In this paper we propose a modification of the von Neumann method of alternating projection x k+1=P A P B x k where A,B are closed and convex subsets of a real Hilbert space ℋ. If Fix P A P B then any sequence generated by the classical method converges weakly to a fixed point of the operator T=P A P B . If the distance δ=inf  xA,yB xy is known then one can efficiently apply a modification of the von Neumann method, which has the form x k+1=P A (x k +λ k (P A P B x k x k )) for λ k >0 depending on x k (for details see: Cegielski and Suchocka, SIAM J. Optim. 19:1093–1106, 2008). Our paper contains a generalization of this modification, where we do not suppose that we know the value δ. Instead of δ we apply its approximation which is updated in each iteration.  相似文献   

7.
The real-valued Lambert W-functions considered here are w 0(y) and w  − 1(y), solutions of we w  = y, − 1/e < y < 0, with values respectively in ( − 1,0) and ( − ∞ , − 1). A study is made of the numerical evaluation to high precision of these functions and of the integrals ò1 [-w0(-xe-x)]a x-bx\int_1^\infty [-w_0(-xe^{-x})]^\alpha x^{-\beta}\d x, α > 0, β ∈ ℝ, and ò01 [-w-1(-x e-x)]a x-bx\int_0^1 [-w_{-1}(-x e^{-x})]^\alpha x^{-\beta}\d x, α > − 1, β < 1. For the latter we use known integral representations and their evaluation by nonstandard Gaussian quadrature, if α ≠ β, and explicit formulae involving the trigamma function, if α = β.  相似文献   

8.
Let {X n ,n ≥ 1} be a sequence of i.i.d. random variables. Let M n and m n denote the first and the second largest maxima. Assume that there are normalizing sequences a n  > 0, b n and a nondegenerate limit distribution G, such that . Assume also that {d k ,k ≥ 1} are positive weights obeying some mild conditions. Then for x > y we have
when G(y) > 0 (and to zero when G(y) = 0).   相似文献   

9.
For a natural number k, define an oriented site percolation on ℤ2 as follows. Let x i , y j be independent random variables with values uniformly distributed in {1, …, k}. Declare a site (i, j) ∈ℤ2 closed if x i = y j , and open otherwise. Peter Winkler conjectured some years ago that if k≥ 4 then with positive probability there is an infinite oriented path starting at the origin, all of whose sites are open. I.e., there is an infinite path P = (i 0, j 0)(i 1, j 1) · · · such that 0 = i 0i 1≤· · ·, 0 = j 0j 1≤· · ·, and each site (i n , j n ) is open. Rather surprisingly, this conjecture is still open: in fact, it is not known whether the conjecture holds for any value of k. In this note, we shall prove the weaker result that the corresponding assertion holds in the unoriented case: if k≤ 4 then the probability that there is an infinite path that starts at the origin and consists only of open sites is positive. Furthermore, we shall show that our method can be applied to a wide variety of distributions of (x i ) and (y j ). Independently, Peter Winkler [14] has recently proved a variety of similar assertions by different methods. Received: 4 March 1999 / Revised version: 27 September 1999 / Published online: 21 June 2000  相似文献   

10.
Summary The aim of this paper is to prove the following theorem about characterization of probability distributions in Hilbert spaces:Theorem. — Let x1, x2, …, xn be n (n≥3) independent random variables in the Hilbert spaceH, having their characteristic functionals fk(t) = E[ei(t,x k)], (k=1, 2, …, n): let y1=x1 + xn, y2=x2 + xn, …, yn−1=xn−1 + xn. If the characteristic functional f(t1, t2, …, tn−1) of the random variables (y1, y2, …, yn−1) does not vanish, then the joint distribution of (y1, y2, …, yn−1) determines all the distributions of x1, x2, …, xn up to change of location.  相似文献   

11.
We establish the existence of infinitely many polynomial progressions in the primes; more precisely, given any integer-valued polynomials P 1, …, P k  ∈ Z[m] in one unknown m with P 1(0) = … = P k (0) = 0, and given any ε > 0, we show that there are infinitely many integers x and m, with 1 \leqslant m \leqslant xe1 \leqslant m \leqslant x^\varepsilon, such that x + P 1(m), …, x + P k (m) are simultaneously prime. The arguments are based on those in [18], which treated the linear case P j  = (j − 1)m and ε = 1; the main new features are a localization of the shift parameters (and the attendant Gowers norm objects) to both coarse and fine scales, the use of PET induction to linearize the polynomial averaging, and some elementary estimates for the number of points over finite fields in certain algebraic varieties.  相似文献   

12.
Construction of multivariate compactly supported orthonormal wavelets   总被引:2,自引:0,他引:2  
We propose a constructive method to find compactly supported orthonormal wavelets for any given compactly supported scaling function φ in the multivariate setting. For simplicity, we start with a standard dilation matrix 2I2×2 in the bivariate setting and show how to construct compactly supported functions ψ1,. . .,ψn with n>3 such that {2kψj(2kx−ℓ,2kym), k,ℓ,mZ, j=1,. . .,n} is an orthonormal basis for L2(ℝ2). Here, n is dependent on the size of the support of φ. With parallel processes in modern computer, it is possible to use these orthonormal wavelets for applications. Furthermore, the constructive method can be extended to construct compactly supported multi-wavelets for any given compactly supported orthonormal multi-scaling vector. Finally, we mention that the constructions can be generalized to the multivariate setting. Dedicated to Professor Charles A. Micchelli on the occasion of his 60th birthday Mathematics subject classifications (2000) 42C15, 42C30.  相似文献   

13.
We determine the general solution of the functional equation f(x + ky) + f(x-ky) = g(x + y) + g(x-y) + h(x) + h(y) for fixed integers with k ≠ 0; ±1 without assuming any regularity conditions for the unknown functions f, g, h, and0020[(h)\tilde] \tilde{h} . The method used for solving these functional equations is elementary but it exploits an important result due to Hosszú. The solution of this functional equation can also be obtained in groups of certain type by using two important results due to Székelyhidi.  相似文献   

14.
We consider an Abel equation (*)y’=p(x)y 2 +q(x)y 3 withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty 0=y(0)≡y(1) for any solutiony(x) of (*). Folowing [7], we consider a parametric version of this condition: an equation (**)y’=p(x)y 2 +εq(x)y 3 p, q as above, ε ∈ ℂ, is said to have a parametric center, if for any ɛ and for any solutiony(ɛ,x) of (**)y(ɛ, 0)≡y(ɛ, 1).. We give another proof of the fact, shown in [6], that the parametric center condition implies vanishing of all the momentsm k (1), wherem k (x)=∫ 0 x pk (t)q(t)(dt),P(x)=∫ 0 x p(t)dt. We investigate the structure of zeroes ofm k (x) and generalize a “canonical representation” ofm k (x) given in [7]. On this base we prove in some additional cases a composition conjecture, stated in [6, 7] for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.  相似文献   

15.
The solvability of the equation n = x 2 + y 2 + 6pz 2 (p is a fixed large prime) is proved under some natural congruential conditions and the assumption nm 12 > p 21. As an implication, the solvability of the equation n = x 2 + y 2 + u 3 + v 3 + z 4 + w 16 + t 4k+1 for all sufficiently large n is established. Bibliography: 13 titles. Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 357, 2008, pp. 5–21.  相似文献   

16.
We establish necessary and sufficient conditions under which a sequence x 0 = y 0 , x n+1 = Ax n  + y n+1 , n ≥ 0, is bounded for each bounded sequence { yn :n \geqslant 0 } ì { x ? èn = 1 D( An ) |supn \geqslant 0 || An x || < ¥ }\left\{ {y_n :n \geqslant 0} \right\} \subset \left\{ {\left. {x \in \bigcup\nolimits_{n = 1}^\infty {D\left( {A^n } \right)} } \right|\sup _{n \geqslant 0} \left\| {A^n x} \right\| < \infty } \right\}, where A is a closed operator in a complex Banach space with domain of definition D(A) .  相似文献   

17.
Let X 1 , X 2 , . . . be a sequence of negatively dependent and identically distributed random variables, and let N be a counting random variable independent of X i ’s. In this paper, we study the asymptotics for the tail probability of the random sum SN = ?k = 1N Xk {S_N} = \sum\nolimits_{k = 1}^N {{X_k}} in the presence of heavy tails. We consider the following three cases: (i) P(N > x) = o(P(X 1> x)), and the distribution function (d.f.) of X 1 is dominatedly varying; (ii) P(X 1> x) = o(P(N > x)), and the d.f. of N is dominatedly varying; (iii) the tails of X 1 and N are asymptotically comparable and dominatedly varying.  相似文献   

18.
We consider an Abel equation (*)y’=p(x)y 2 +q(x)y 3 withp(x), q(x) polynomials inx. A center condition for (*) (closely related to the classical center condition for polynomial vector fields on the plane) is thaty 0=y(0)≡y(1) for any solutiony(x) of (*). We introduce a parametric version of this condition: an equation (**)y’=p(x)y 2 +εq(x)y 3 p, q as above, ℂ, is said to have a parametric center, if for any ε and for any solutiony(ε,x) of (**),y(ε,0)≡y(ε,1). We show that the parametric center condition implies vanishing of all the momentsm k (1), wherem k (x)=∫ 0 x pk (t)q(t)(dt),P(x)=∫ 0 x p(t)dt. We investigate the structure of zeroes ofm k (x) and on this base prove in some special cases a composition conjecture, stated in [10], for a parametric center problem. The research of the first and the third author was supported by the Israel Science Foundation, Grant No. 101/95-1 and by the Minerva Foundation.  相似文献   

19.
In this article, we provide a global search algorithm for maximizing a piecewise convex function F over a compact D. We propose to iteratively refine the function F at local solution y by a virtual cutting function p y (⋅) and to solve max {min {F(x)−F(y),p y (x)}∣xD} instead. We call this function either a patch, when it avoids returning back to the same local solutions, or a pseudo patch, when it possibly yields a better point. It is virtual in the sense that the role of cutting constraints is played by additional convex pieces in the objective function. We report some computational results, that represent an improvement on previous linearization based techniques.  相似文献   

20.
The article studies diagnostic tests for local k -fold coalescences of variables in Boolean functions f( [(x)\tilde]n )( 1 £ kn,  1 £ t £ 22k ) f\left( {{{\tilde{x}}^n}} \right)\left( {1 \leq k \leq n,\;1 \leq t \leq {2^{{2^k}}}} \right) . Upper and lower bounds are proved for the Shannon function of the length of the diagnostic test for local k -fold coalescences generated by the system of functions Ftk \Phi_t^k . The Shannon function of the length of a complete diagnostic test for local k -fold coalescences behaves asymptotically as 2 k (n − k + 1) for n → ∞, k → ∞.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号