不可分离凸背包问题的拉格朗日分解和区域分割方法

本文对线性约束不可分离凸背包问题给出了一种精确算法．该算法是拉格朗日分解和区域分割结合起来的一种分枝定界算法．利用拉格朗日分解方法可以得到每个子问题的一个可行解，一个不可行解，一个下界和一个上界．区域分割可以把一个整数箱子分割成几个互不相交的整数子箱子的并集，每个整数子箱子对应一个子问题．通过区域分割可以逐步减小对偶间隙并最终经过有限步迭代找到原问题的最优解．数值结果表明该算法对不可分离凸背包问题是有效的．     

A stabilized column generation scheme for the traveling salesman subtour problem

Given an undirected graph with edge costs and both revenues and weights on the vertices, the traveling salesman subtour problem is to find a subtour that includes a depot vertex, satisfies a knapsack constraint on the vertex weights, and that minimizes edge costs minus vertex revenues along the subtour.We propose a decomposition scheme for this problem. It is inspired by the classic side-constrained 1-tree formulation of the traveling salesman problem, and uses stabilized column generation for the solution of the linear programming relaxation. Further, this decomposition procedure is combined with the addition of variable upper bound (VUB) constraints, which improves the linear programming bound. Furthermore, we present a heuristic procedure for finding feasible subtours from solutions to the column generation problems. An extensive experimental analysis of the behavior of the computational scheme is presented.     

SU(1,1)对称量子系统时间最优控制

基于李群分解,讨论了控制不受限情况下SU(1,1)对称量子控制系统的时间最优控制问题.针对系统控制哈密顿项为椭圆型和抛物型这两种情形,分别给出了实现任意演化矩阵所需要的最短时间.针对系统控制哈密顿项为双曲型情形,给出了实现任意演化矩阵所需要最短时间的一个上界.     

无符号拉普拉斯谱半径的新上界

如果一个图存在定向满足其最大出度△~＋不超过最大度△的一半,则通过估计图的半边路径（semi-edge walk）的个数,得到了该图的无符号拉普拉斯谱半径的一个新上界.进而根据D.Goncalves对平面图边分解的结果,得到了平面图无符号拉普拉斯谱半径的一个新上界.     

A Characterization of Sparse Nonstationary Gabor Expansions

We investigate the problem of constructing sparse time–frequency representations with flexible frequency resolution, studying the theory of nonstationary Gabor frames (NSGFs) in the framework of decomposition spaces. Given a painless NSGF, we construct a compatible decomposition space and prove that the NSGF forms a Banach frame for the decomposition space. Furthermore, we show that the decomposition space norm can be completely characterized by a sparseness condition on the frame coefficients and we prove an upper bound on the approximation error occurring when thresholding the frame coefficients for signals belonging to the decomposition space.     

Bounds for visual cryptography schemes

In this paper, we investigate the best pixel expansion of various models of visual cryptography schemes. In this regard, we consider visual cryptography schemes introduced by Tzeng and Hu (2002) [13]. In such a model, only minimal qualified sets can recover the secret image and the recovered secret image can be darker or lighter than the background. Blundo et al. (2006) [4] introduced a lower bound for the best pixel expansion of this scheme in terms of minimal qualified sets. We present another lower bound for the best pixel expansion of the scheme. As a corollary, we introduce a lower bound, based on an induced matching of hypergraph of qualified sets, for the best pixel expansion of the aforementioned model and the traditional model of visual cryptography scheme realized by basis matrices. Finally, we study access structures based on graphs and we present an upper bound for the smallest pixel expansion in terms of strong chromatic index.     

Wavelet Expansions and Fractal Dimensions

The bounds of the upper and lower box dimensions of the graph of a function in terms of the coefficients in its wavelet decomposition are given. An example, that the formula for upper box dimension, given in [4], does not hold, is presented. March 10, 1997. Date revised: March 3, 1998. Date accepted: March 3, 1998.     

离散FitzHugh-Nagumo方程的整体吸引子和维数

该文对ＦｉｔｚＨｕｇｈ Ｎａｇｕｍｏ方程初边值问题用有限差分格式离散空间变量,证明了离散模型整体吸引子的存在性,并给出了与犿无关的Ｈａｕｓｄｏｒｆｆ维数和Ｆｒａｃｔａｌ维数上界估计。     

Upper bound on the slope of steady water waves with small adverse vorticity

We consider the angle of inclination (with respect to the horizontal) of the profile of a steady 2D inviscid symmetric periodic or solitary water wave subject to gravity. There is an upper bound of 31.15° in the irrotational case [1] and an upper bound of 45° in the case of favorable vorticity [13]. On the other hand, if the vorticity is adverse, the profile can become vertical. We prove here that if the adverse vorticity is sufficiently small, then the angle still has an upper bound which is slightly larger than 45°.     

Sharp Bounds for Vertical Decompositions of Linear Arrangements in Four Dimensions

We prove tight and near-tight combinatorial complexity bounds for vertical decompositions of arrangements of hyperplanes and 3-simplices in four dimensions. In particular, we prove a tight upper bound of (n⁴) for the vertical decomposition of an arrangement of n hyperplanes in four dimensions, improving the best previously known bound [8] by a logarithmic factor. We also show that the complexity of the vertical decomposition of an arrangement of n 3-simplices in four dimensions is O(n⁴ (n) log² n), where (n) is the inverse Ackermann function, improving the best previously known bound [2] by a near-linear factor.     

Biquadratic tensors,biquadratic decompositions,and norms of biquadratic tensors

Biquadratic tensors play a central role in many areas of science.Examples include elastic tensor and Eshelby tensor in solid mechanics,and Riemannian curvature tensor in relativity theory.The singular values and spectral norm of a general third order tensor are the square roots of the M-eigenvalues and spectral norm of a biquadratic tensor,respectively.The tensor product operation is closed for biquadratic tensors.All of these motivate us to study biquadratic tensors,biquadratic decomposition,and norms of biquadratic tensors.We show that the spectral norm and nuclear norm for a biquadratic tensor may be computed by using its biquadratic structure.Then,either the number of variables is reduced,or the feasible region can be reduced.We show constructively that for a biquadratic tensor,a biquadratic rank-one decomposition always exists,and show that the biquadratic rank of a biquadratic tensor is preserved under an independent biquadratic Tucker decomposition.We present a lower bound and an upper bound of the nuclear norm of a biquadratic tensor.Finally,we define invertible biquadratic tensors,and present a lower bound for the product of the nuclear norms of an invertible biquadratic tensor and its inverse,and a lower bound for the product of the nuclear norm of an invertible biquadratic tensor,and the spectral norm of its inverse.     

Nonconvex quadratically constrained quadratic programming: best D.C. decompositions and their SDP representations

We propose in this paper a general D.C. decomposition scheme for constructing SDP relaxation formulations for a class of nonconvex quadratic programs with a nonconvex quadratic objective function and convex quadratic constraints. More specifically, we use rank-one matrices and constraint matrices to decompose the indefinite quadratic objective into a D.C. form and underestimate the concave terms in the D.C. decomposition formulation in order to get a convex relaxation of the original problem. We show that the best D.C. decomposition can be identified by solving an SDP problem. By suitably choosing the rank-one matrices and the linear underestimation, we are able to construct convex relaxations that dominate Shor’s SDP relaxation and the strengthened SDP relaxation. We then propose an extension of the D.C. decomposition to generate an SDP bound that is tighter than the SDP+RLT bound when additional box constraints are present. We demonstrate via computational results that the optimal D.C. decomposition schemes can generate both tight SDP bounds and feasible solutions with good approximation ratio for nonconvex quadratically constrained quadratic problems.     

Limit analysis decomposition and finite element mixed method

This paper proposes an original decomposition approach to the upper bound method of limit analysis. It is based on a mixed finite element approach and on a convex interior point solver, using linear or quadratic discontinuous velocity fields. Presented in plane strain, this method appears to be rapidly convergent, as verified in the Tresca compressed bar problem in the linear velocity case. Then, using discontinuous quadratic velocity fields, the method is applied to the celebrated problem of the stability factor of a Tresca vertical slope: the upper bound is lowered to 3.7776-value to be compared to the best published lower bound 3.7752-by succeeding in solving a nonlinear optimization problem with millions of variables and constraints.     

基于D.C.分解的一类箱型约束的非凸二次规划的新型分支定界算法

提出了一类求解带有箱约束的非凸二次规划的新型分支定界算法.首先,把原问题目标函数进行D.C.分解(分解为两个凸函数之差),利用次梯度方法,求出其线性下界逼近函数的一个最优值,也即原问题的一个下界.然后,利用全局椭球算法获得原问题的一个上界,并根据分支定界方法把原问题的求解转化为一系列子问题的求解.最后,理论上证明了算法的收敛性,数值算例表明算法是有效可行的.     

Estimation of optimal backward perturbation bounds for the linear least squares problem

In this paper a method of estimating the optimal backward perturbation bound for the linear least squares problem is presented. In contrast with the optimal bound, which requires a singular value decomposition, this method is better suited for practical use on large problems since it requiresO(mn) operations. The method presented involves the computation of a strict lower bound for the spectral norm and a strict upper bound for the Frobenius norm which gives a gap in which the optimal bounds for the spectral and the Frobenius norm must be. Numerical tests are performed showing that this method produces an efficient estimate of the optimal backward perturbation bound.     

抛物型方程的一种高精度区域分解有限差分算法

1引言 近年来,区域分解算法以可以将大型问题分解为一系列小型问题以减少计算规模及算法可高度并行实现等特点受到了人们的广泛关注.前人也做了很多很好的工作:参考文献[1]中C.N.Dawson等人提出了显一隐格式的区域分解算法,在时间层不分层的内边界点采用大步长向前-中心差分显格式及在内点采用古典隐格式,取得的精度为O(△t+h2+H3).参考文献[2]中给出了[1]中区域分解算法对于内边界点为等距分布的多子区域时的新的误差估计,使含H3误差项的系数比[1]中缩小了一倍.还将采用大步长日的saul'yev的非对称差分格式应用于内边界点,并给出了两个子区域和多个子区域情形下差分解的先验误差估计.     

Upper Semicontinuity and Kolmogorov ε-Entropy of Global Attractor for κ-Dimensional Lattice Dynamical System Corresponding to Klein-Gordon-SchrSdinger Equation

In this paper, we establish the existence of a global attractor for a coupled κ-dimensional lattice dynamical system governed by a discrete version of the Klein-Gordon-SchrSdinger Equation. An estimate of the upper bound of the Kohnogorov ε-entropy of the global attractor is made by a method of element decomposition and the covering property of a polyhedron by balls of radii ε in a finite dimensional space. Finally, a scheme to approximate the global attractor by the global attractors of finite-dimensional ordinary differential systems is presented .     

On the Dealer's Randomness Required in Secret Sharing Schemes

In this paper we provide upper and lower bounds on the randomness required by the dealer to set up a secret sharing scheme for infinite classes of access structures. Lower bounds are obtained using entropy arguments. Upper bounds derive from a decomposition construction based on combinatorial designs (in particular, t-(v,k,) designs). We prove a general result on the randomness needed to construct a scheme for the cycle Cn; when n is odd our bound is tight. We study the access structures on at most four participants and the connected graphs on five vertices, obtaining exact values for the randomness for all them. Also, we analyze the number of random bits required to construct anonymous threshold schemes, giving upper bounds. (Informally, anonymous threshold schemes are schemes in which the secret can be reconstructed without knowledge of which participants hold which shares.)     

Some Condition-Number bounds for the Gaussian Elimination Process

It is well-known that Gaussian Elimination is equivalent toLU decomposition. This paper shows that if Gaussian Eliminationis applied to a well-conditioned matrix, and if an increasein element size is observed during the elimination process,then both the triangular factors will be badly conditioned.It is further shown that the effect of partial pivoting is toplace an upper bound upon the condition number of the lowertriangular factor.     

Multiplicative Lattice with Maximal Condition

This paper defines multiplicative lattice. The conception of multiplicative lattice is abstracted from several lattices, which may be composed of ideals of the associative ring, ideals of the non-associative ring, or ideals of the both non-assooiatiye and non-distributive ring and which may be composed of normal subgroups of the group as well. Definition 1. The multiplicative lattice L is a lattice with following conditions: 1. L is complemented and Dedekind's, the least upper bound of L equals 1 and the greatest lower bound of L equals 0. 2. The multiplication is closed and ab\leq a \cap b, where a\cap b denotes the greatest lower bound of a and b. 3.a(b+c)=ab+ac,(b+c)=ba+bc, where b+c denotes the least upper bound of b and c. Suppose L is multiplicative lattice with maximal condition, the following theorems are proved: Theorem 1. Every element a of L has normal (right) third decomposition, that means every element is the intersection of finite number of (right) third elements, whose (right) third roots are different from each other and if $a=T_1\cap \cdots \cap T_m=T_1'\cap \cdots\cap T_n'$ are two different normal (right) third decomposition of a, then m=n and their third roots are equal correspondingly by rearranging properly Theorem 2. If A is an element of L and has property that c^2\leq A \rightarrow c\leq A, then A is the intersection of finite number of prime elements. Theorem 3. Every element of L has primary decomposition if and only if L satisfies Artin-Rees condition. Definition 2. u is called a solvable radical of the multiplicative lattice with maximal condition if u is the least upper bound, of the subset of L whose every element a? satisfies that there exists a group of positive integers n_1,\cdots,n_r such that $X^n_1,\cdots,n_r=0$. Theorem 4. u is an intersection of finite number of prime elements. Theorem 5. If L is semi-simple, i. e. $O=u=\cap\limits_{i=1}^n P_i$, and if $P_i+P_j=1(i\ne j)$ and $1\cdot 1=1$ then 1 is the direct sum in R_1,\cdots,R_n, where $R_i=P_1\cap \cdots \cap P_i-1\cap P_i+1\cap \cdots \cap P_n$